Деревья Nested sets

Работа VB и СУБД (Access, MSSQL, MySQL, Oracle и пр.)
Правила форума
При создании новой темы не забывайте указывать используемую СУБД.
Antonariy
Повелитель Internet Explorer
Повелитель Internet Explorer
Аватара пользователя
 
Сообщения: 4824
Зарегистрирован: 28.04.2005 (Чт) 14:33
Откуда: Мимо проходил

Деревья Nested sets

Сообщение Antonariy » 16.06.2008 (Пн) 16:04

Делал сабж на sql2005 по этой статье. Все работает кроме перемещения ветки (без изменения порядка). Через несколько произвольных перемещений уровни расползаются на недопустимые значения, начинают дублироваться ключи.

Таблица:
NormCatalogID pk
Name varchar
RefID - ссылка на NormCatalogID parent'а
Lk - левый ключ
Rk - правый ключ
Lev - уровень
Код: Выделить всё
ALTER proc [dbo].[procMoveNormCtlg]
@NormCatalogID int,
@ParentID int
as
begin tran
declare @Lev int, @Lk int, @Rk int
declare @LevNew int, @right_key_near int, @PrevID int
declare @skew_level int, @skew_tree int, @skew_edit int

SELECT   @Lev = Lev, @Lk = Lk, @Rk = Rk FROM tblNormCatalog WHERE NormCatalogID = @NormCatalogID
select   @LevNew = Lev, @right_key_near=Rk-1 FROM tblNormCatalog WHERE NormCatalogID = @ParentID

set @skew_level = @LevNew - @Lev + 1
set @skew_tree = @Rk - @Lk + 1
set @skew_edit = @right_key_near - @Lk + 1

print @right_key_near
print @Rk

if @right_key_near>@rk
   UPDATE   tblNormCatalog
   SET      Lk =  case when Rk <= @Rk then Lk +  @skew_edit  else case when Lk > @Rk then Lk - @skew_tree else Lk end end,
         Lev = case when Rk <= @Rk then Lev + @skew_level else Lev end,
         Rk =  case when Rk <= @Rk then Rk +  @skew_edit  else case when Rk <= @right_key_near then Rk - @skew_tree else Rk end end
   WHERE   Rk > @Lk AND
         Lk <= @right_key_near
else
   UPDATE   tblNormCatalog
   SET      Rk =  case when Lk >= @Lk then Rk + @skew_edit else case when Rk < @Lk then Rk + @skew_tree else Rk end end,
         Lev = case when Lk >= @Lk then Lev + @skew_level else Lev end,
         Lk =  case when Lk >= @Lk then Lk + @skew_edit else case when Lk > @right_key_near then Lk + @skew_tree else Lk end end
   WHERE Rk > @right_key_near AND Lk < @Rk

update   tblNormCatalog Set RefID = @ParentID where NormCatalogID = @NormCatalogID

if @@error<>0
   rollback tran
else
   commit tran
Где я накосячил?
Лучший способ понять что-то самому — объяснить это другому.

HandKot
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 283
Зарегистрирован: 28.06.2006 (Ср) 13:34
Откуда: Sergiev Posad

Сообщение HandKot » 17.06.2008 (Вт) 7:21

а можно поподробнее
если на примере картинки из статья, то какой узел и куда перетаскивается (что должно получиться в итоге)
I Have Nine Lives You Have One Only
THINK!

Antonariy
Повелитель Internet Explorer
Повелитель Internet Explorer
Аватара пользователя
 
Сообщения: 4824
Зарегистрирован: 28.04.2005 (Чт) 14:33
Откуда: Мимо проходил

Сообщение Antonariy » 17.06.2008 (Вт) 11:05

Пример в аттаче.
У вас нет доступа для просмотра вложений в этом сообщении.
Лучший способ понять что-то самому — объяснить это другому.

HandKot
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 283
Зарегистрирован: 28.06.2006 (Ср) 13:34
Откуда: Sergiev Posad

Сообщение HandKot » 17.06.2008 (Вт) 13:36

не проверял, но есть подозрение что Вы упустили следующую фразу
Определяем смещение ключей редактируемого узла $right_key_near - $left_key + 1 = $skew_edit;
...
Определяем смещение ключей редактируемого узла $right_key_near - $left_key + 1 - $skew_tree = $skew_edit.


и тогда должно получиться что-то следующее
Код: Выделить всё
IF @right_key_near>@rk
BEGIN
        SET @skew_edit = @right_key_near - @Lk + 1 - @skew_tree
        UPDATE  tblNormCatalog
        SET             Lk =  case when Rk <= @Rk then Lk +  @skew_edit  else case when Lk > @Rk then Lk - @skew_tree else Lk end end,
                        Lev = case when Rk <= @Rk then Lev + @skew_level else Lev end,
                        Rk =  case when Rk <= @Rk then Rk +  @skew_edit  else case when Rk <= @right_key_near then Rk - @skew_tree else Rk end end
        WHERE   Rk > @Lk AND
                        Lk <= @right_key_near
END
else
BEGIN
        SET @skew_edit = @right_key_near - @Lk + 1
        UPDATE  tblNormCatalog
        SET             Rk =  case when Lk >= @Lk then Rk + @skew_edit else case when Rk < @Lk then Rk + @skew_tree else Rk end end,
                        Lev = case when Lk >= @Lk then Lev + @skew_level else Lev end,
                        Lk =  case when Lk >= @Lk then Lk + @skew_edit else case when Lk > @right_key_near then Lk + @skew_tree else Lk end end
        WHERE Rk > @right_key_near AND Lk < @Rk
END
I Have Nine Lives You Have One Only
THINK!

Antonariy
Повелитель Internet Explorer
Повелитель Internet Explorer
Аватара пользователя
 
Сообщения: 4824
Зарегистрирован: 28.04.2005 (Чт) 14:33
Откуда: Мимо проходил

Сообщение Antonariy » 17.06.2008 (Вт) 13:45

В яблочко! :D Спасибо.
Лучший способ понять что-то самому — объяснить это другому.

Antonariy
Повелитель Internet Explorer
Повелитель Internet Explorer
Аватара пользователя
 
Сообщения: 4824
Зарегистрирован: 28.04.2005 (Чт) 14:33
Откуда: Мимо проходил

Сообщение Antonariy » 11.07.2008 (Пт) 12:03

Понадобилось таки добавить изменение порядка веток. Для этого нужен @left_key_near:
Код: Выделить всё
SELECT  @LevNew = Lev, @right_key_near=Rk-1, @left_key_near = Lk FROM tblNormCatalog WHERE NormCatalogID = @ParentID
А что с ним делать дальше — не понятно. В статье он больше не упоминается.
Лучший способ понять что-то самому — объяснить это другому.

HandKot
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 283
Зарегистрирован: 28.06.2006 (Ср) 13:34
Откуда: Sergiev Posad

Сообщение HandKot » 15.07.2008 (Вт) 6:56

не совсем понятен вопрос.
по возможности, пропишите в виде
вид дерева "до"

2А 2Б 2В
3А 3Б 3В 3Г 3Д 3Е

нужно перенсти ветку 2А в ветку ..., чтобы ...
I Have Nine Lives You Have One Only
THINK!

Antonariy
Повелитель Internet Explorer
Повелитель Internet Explorer
Аватара пользователя
 
Сообщения: 4824
Зарегистрирован: 28.04.2005 (Чт) 14:33
Откуда: Мимо проходил

Сообщение Antonariy » 17.07.2008 (Чт) 16:15

Не совсем понятен хекс :)
Дерево до:
Код: Выделить всё
Корень
    Ветвь 1
    Ветвь 2
    Ветвь 3

Дерево после:
Код: Выделить всё
Корень
    Ветвь 3
    Ветвь 1
    Ветвь 2
Лучший способ понять что-то самому — объяснить это другому.

HandKot
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 283
Зарегистрирован: 28.06.2006 (Ср) 13:34
Откуда: Sergiev Posad

Сообщение HandKot » 28.07.2008 (Пн) 14:36

наконец-то добрался
вот решение, но нужно проверить на реальных данных

@id - что перемещаем
@new_parent_id - родитель (может быть null, когда перемещаем в корень)
@id_befor - узел, что остается слева (если null, то будет первым в род.узле)

Код: Выделить всё
alter procedure move_node(@id int, @new_parent_id int, @id_befor int)
as
begin
SET NOCOUNT ON

  --Ключи и уровень перемещаемого узла
  declare @level int, @leftkey int, @rightkey int
  select @level = level, @leftkey = leftkey, @rightkey = rightkey from nested_sets where id = @id

  --Ключи и уровень нового родительского узла
  declare @level_up int, @parent_leftkey int, @parent_rightkey int, @rightkey_near int
  if @new_parent_id is not null
    select @level_up = level from nested_sets where id = @new_parent_id
  else
    select @level_up = 0
  if @id_befor is null
    select @rightkey_near = leftkey + 1 from nested_sets where id = @new_parent_id
  else
    select @rightkey_near = rightkey from nested_sets where id = @id_befor
  --делаем по необходимости корректировку
  if @rightkey_near is null
    select @rightkey_near = 0

  --Определяем хар-ки перемещения
  declare @skew_level int, @skew_tree int
  set @skew_level = @level_up - @level + 1
  set @skew_tree = @rightkey - @leftkey + 1

  --Перемещаем
  declare @skew_edit int
  if (@rightkey < @rightkey_near)
  begin
    set @skew_edit = @rightkey_near - @leftkey + 1 - @skew_tree
    update nested_sets
      set leftkey = case
                      when rightkey <= @rightkey then leftkey +  @skew_edit 
                      else
                        case
                          when leftkey > @rightkey then leftkey - @skew_tree
                          else leftkey
                        end
                    end,
     [level] = case when rightkey <= @rightkey then [level] + @skew_level else [level] end,
     rightkey = case
                  when rightkey <= @rightkey then rightkey +  @skew_edit 
                  else
                    case
                      when rightkey <= @rightkey_near then rightkey - @skew_tree
                      else rightkey
                    end
               end
    where   
      rightkey > @leftkey and
      leftkey <= @rightkey_near

  end
  else
  begin
    set @skew_edit = @rightkey_near - @leftkey + 1
    update nested_sets
      set rightkey = case
                       when leftkey >= @leftkey then rightkey + @skew_edit
                       else
                         case
                           when rightkey < @leftkey then rightkey + @skew_tree
                           else rightkey
                         end
                     end,
      [level] = case when leftkey >= @leftkey then [level] + @skew_level else [level] end,
      leftkey = case 
                  when leftkey >= @leftkey then leftkey + @skew_edit
                  else
                    case
                      when leftkey > @rightkey_near then leftkey + @skew_tree
                      else leftkey
                    end
                end
    where
      rightkey > @rightkey_near and
      leftkey < @rightkey
  end
end


ЗЫЖ будут нарекания, то представьте данные таблицы и что и куда перемещаем
I Have Nine Lives You Have One Only
THINK!

Antonariy
Повелитель Internet Explorer
Повелитель Internet Explorer
Аватара пользователя
 
Сообщения: 4824
Зарегистрирован: 28.04.2005 (Чт) 14:33
Откуда: Мимо проходил

Сообщение Antonariy » 01.08.2008 (Пт) 10:35

Все отлично, за исключением одной неточности — не работало перемещение ветки в начало уровня*. И почему-то неправильно считался rightkey_near при переносе в другую ветку**. Код ниже рабочий.
Код: Выделить всё
if @id_befor is null and @new_parent_id is null
    *
    select @rightkey_near = leftkey from nested_sets where id = (select ParentID from nested_sets where id= @id)
else if @id_befor is null
    **
    select @rightkey_near = rightkey - 1 from nested_sets where id = @new_parent_id
else
    select @rightkey_near = rightkey from nested_sets where id = @id_befor
Лучший способ понять что-то самому — объяснить это другому.

HandKot
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 283
Зарегистрирован: 28.06.2006 (Ср) 13:34
Откуда: Sergiev Posad

Сообщение HandKot » 04.08.2008 (Пн) 7:04

главное что у Вас все получилось :)
I Have Nine Lives You Have One Only
THINK!


Вернуться в Базы данных

Кто сейчас на конференции

Сейчас этот форум просматривают: Google-бот, Yandex-бот и гости: 5

    TopList