Правильная ссылка на эту страницу
http://az-design.ru/Support/DataBase/DBTree2/5000.shtml

Деревья как вложенные множества

Архангельский Андрей

Математик доказывает теорему. После того как почти вся доска была исписана формулами он заявляет:
— А здесь происходит чудо и переменная x становится равной y/2
Из зала раздается возглас:
— а можно с этого места поподробнее?

       Все что говорилось до сих пор относилось к деревьям построенных на модели смежных вершин. Однако, есть и другой способ построения деревьев. Джо Селко в своей книге "SQL для профессионалов" посвятил этой модели (гл.29) в два раза больше страниц, чем модели смежных вершин (гл.28). На многих сайтах и форумах, например sql.ru, есть множество аппологетов, которые считают, что модель вложенных множеств является единственной и лучшей моделью для построения деревьев.
       Попробуем разобраться, что хорошего в этой модели, и сравним ее с моделью смежных вершин. Цитаты из книги Джо Селко выделены курсивов.

Определение модели

       Вот как определяет эту модель Джо Селко:
       "Чтобы то же самое дерево представить в виде вложенных множеств, замените квадратики овалами, а подчиненные овалы вложите внутрь своих предков. Самый большой овал, содержащий все остальные узлы, будет корнем. Листовые узлы соответствуют самым маленьким внутренним овалам, не содержащим больше ничего, а вложение овалов друг в друга иллюстрирует иерархию связей. Такой метод является естественным при моделировании спецификации изделия, поскольку готовое изделие состоит из физически вложенных компонентов, собираемых из отдельных деталей. Дерево на рис. 29.2 преобразуется во вложение множеств, показанное на рис. 29.3.


Рис.4-1 Celko_29.3 Модель вложенных множеств

       Такой подход позволяет моделировать дерево из lft и rgt вложенных множеств с помощью пар чисел. Эти пары всегда содержат пары своих подчиненных, так что порожденный узел находится в границах своего родителя. На рис. 29.4 представлена версия вложенных множеств, преобразованная в схему.


Рис.4-2 Celko_29.4 Схема модели вложенных множеств

       Подобную модель можно визуализировать в виде маленького червя с нумерующей печатью. Этот червь ползет по дереву типа "квадратики и стрелки". Начинает свое движение он на вершине, в корне дерева, и затем полностью обходит его. Прибыв на узел, он ставит номер на его ячейке, после чего номер на его печати увеличивается. Каждый узел получает два номера, один на правой (rgt) стороне, а другой на левой (lft). Специалист легко узнает здесь модифицированный алгоритм обхода дерева в прямом порядке. Такая схема нумерации имеет предсказуемые результаты, которые можно использовать при построении запросов."
       Джо Селко начинает изложение с уже созданного дерева, избегая коварного вопроса — а как его сделать. Следуя порядку изложения мастера — поверим в чудо и будем считать, что дерево существует. Для анализа возьмем возьмем таблицы GoodsTreeTops и GoodsTreeSets:

Create table GoodsTreeTops
      (Parnt        AZInt32 default 0 not null references GoodsNew2 on update cascade,
       Child        AZInt32 default 0 not null references GoodsNew2 on update cascade,
       PCnt         AZInt32D0, -- Количество детей [Для смежных вершин]
       GdOrd        AZInt32D0, -- Порядок узлов    [Для смежных вершин]
       CLev         AZInt32D0, -- Уровень узла     [Для смежных вершин]
Primary key(Parnt,Child));
Commit;

       Так как Джо Селко позволяет себе добавить два столбца для нумерации узлов, то и в нашем примере есть два столбца для дополнительной информации об узле. Как описывалось ранее — это количество детей у узла и порядок узла в списке родителя. Столбец CLev в данном анализе не используется, но как было показано выше он может принести пользу.

Create table GoodsTreeSets
      (Parnt        AZInt32 default 0 not null references GoodsNew2 on update cascade,
       Child        AZInt32 default 0 not null references GoodsNew2 on update cascade,
       Lft          AZInt32D0, -- Левый номер      [Для вложенных множеств]
       Rgt          AZInt32D0, -- Правый номер     [Для вложенных множеств]
Primary key(Parnt,Child));
Commit;

       Для варианта Джо Селко добавляем левый номер узла — Lft и правый номер узла — Rgt.
       И в том и другом случае Parnt и Child указатели на реальные описания товаров в таблице GoodsNew2. В качестве заполнения возьмем часть структуры классификатора УДК — всего 1950 саписей. Примеры Джо Селко отредактируем соответственно нашим таблицам.
       И так, начнем!

Поиск корневых и листовых узлов

       Celko_29.1:
       "В столбце lft корневого узла всегда содержится число 1, а в столбце rgt — удвоенное количество узлов. Это легко понять: червь должен посетить каждый узел дважды, один раз со стороны lft, а другой раз со стороны rgt, поэтому окончательное число в два раза превосходит количество узлов всего дерева. Корень дерева можно найти запросом:

SELECT *
  FROM GoodsTreeSets
 WHERE lft = 1;

       Этот запрос будет работать быстрее, если проиндексировать столбец lft."
       Прекрасно!
       А в модели смежных вершин это делается также просто:

SELECT *
  FROM GoodsTreeTops
 WHERE Parnt = 0;

       Так как корневой узел не содержит родителей, то в качестве родителя у него будет значение 0. Запрос работает быстро, потому что внешний ключ автоматический создает индекс.
       Разница этих двух вариантов только в одном — в модели смежных вершин допускается несколько корневых узлов, а в модели вложенных множеств — только один.
       Пойдем дальше:
       "Листовой узел не содержит потомков. В модели матрицы смежности листовые узлы найти не слишком просто, так как необходимо использовать коррелированный подзапрос:

SELECT *

FROM GoodsTreeTops AS G1 WHERE NOT EXISTS (SELECT * FROM GoodsTreeTops AS P2 WHERE G1.Child = G2.Parnt);"

       Здесь Джо Селко несколько лукавит. Он же прямо сказал, что "листовой узел не содержит потомков" значит правильный запрос выглядит так:

SELECT *
  FROM GoodsTreeTops
 WHERE PCnt = 0;

       Для модели вложенных множеств Селко предлагает следующий вариант:
       "В модели вложенных таблиц разница между значениями lft и rgt листового узла всегда равна 1. Это понятно, ведь червь как бы огибает угол на таких узлах. Следовательно, листовые узлы можно получить простым предикатом:

SELECT *
  FROM GoodsTreeSets 
 WHERE (rgt - lft) = 1;"

       Дальше Селко объясняет как ускорить выполнение этого запроса, так как выражение в левой части не позволяет использовать индекс.
       Как видно из запросов, в модели смежных вершин запрос ВСЕГДА выполняется быстрее, просто потому, что не нужно выполнять вычисления.

Поиск ветвей

       Самая важная операция с деревьями — поиск ветвей. Именно иерархический поиск позволяет просматривать значительно меньше информации постепенно уточняя критерий поиска. Что по этому поводу говорит Селко:
       "Еще одним полезным свойством является то, что любой узел дерева представляет собой корень ветви (листовые узлы считаются вырожденным случаем). Чтобы в таблице вложенных множеств найти всех потомков узла, достаточно определить узлы, значения rgt и lft которых располагаются между значениями lft и rgt родительского узла. Например, всех подчиненных каждого начальника в компании можно найти так:

SELECT Managers.Child, ' is a boss of ', Workers.Child
  FROM GoodsTreeSets AS Managers, GoodsTreeSets AS Workers 
 WHERE Workers.lft BETWEEN Managers.lft AND Managers.rgt 
   AND Workers.rgt BETWEEN Managers.lft AND Managers.rgt;"

       Это конечно здорово, но! Представим себе начальника большого отдела, который захотел провести совещание — в кабинет входят тысяча человек, вместо пяти начальников подразделений. Да есть случаи, когда необходимо найти всё содержимое ветви, но это очень редко. Просто потому, что иерархия нужна именно в тех случаях, когда нужно уменьшить объем информации. И в этом случае требуется поиск не всех детей узла, а только непосредственно подчиненных. Но как раз с этим в модели вложенных множеств есть проблемы.
       А поиск непосредственных детей узла выполняется одинаково как в одной, так и в другой модели:

SELECT *
  FROM GoodsTree
 WHERE Parnt=:Child;

Поиск уровней и путей в дереве

       Уровень узла дерева соответствует числу ребер между узлом и корнем, при этом чем больше номер глубины, тем дальше узел от корня. Путь — это множество ребер, непосредственно соединяющих два узла.
       Celko_29.3:
       "Модель вложенных множеств использует тот факт, что каждое содержащее множество шире (ширина равна (rgt - lft)) тех множеств, которые оно содержит. Очевидно, корень всегда является самой широкой строкой таблицы. Функция уровня соответствует числу ребер между двумя данными узлами, вычислить ее сравнительно просто. Например, уровень каждого исполнителя можно определить так:

SELECT P2.emp, (COUNT(P1.emp) - 1) AS level
  FROM Personnel AS P1, Personnel AS P2
 WHERE P2.lft BETWEEN P1.lft AND P1.rgt;

       Выражение (COUNT( *) - 1) применяется с целью удаления повторяющегося номера для самого узла (дерево начинается с уровня 0). Чтобы начинать с 1, уберите из запроса лишние выражения."
       Попытка выполнить этот запрос сразу окончилась крахом — level — зарезервированное слово. А count() без group by или других агрегатных функций дает следующее сообщение об ошибке:

Invalid expression in the select list (not contained in either an aggregate function or the GROUP BY clause).

       Итак, исправленный вопрос будет выглядеть следующим образом:

SELECT G2.Child, (COUNT(G1.Child) - 1) AS GdsLevel
  FROM GoodsTreeSets AS G1, GoodsTreeSets AS G2
 WHERE G2.lft BETWEEN G1.lft AND G1.rgt
 group by G2.Child;

       Запрос действительно выдает список узлов и их уровней и выполняется 3.297 сек.
       Для модели смежных вершин такой запрос написать действительно нельзя, но можно написать хранимую процедуру, которая сделает тоже самое:

Create procedure GoodsTreeTopsLevel (GdsPrnt Integer, ItLev SmallInt)
       returns (GdsChld Integer, GdsLev SmallInt) as
begin
   for select Child from GoodsTreeTops where Parnt=:GdsPrnt into :GdsChld
       do begin
          GdsLev = ItLev + 1;
          suspend;
          for select GdsChld,GdsLev from GoodsTreeTopsLevel(:GdsChld,:GdsLev)
                     into :GdsChld,:GdsLev
            do begin 
               suspend;
               end
          end
end !!

       Процедура просто обходит все ветви дерева и выполняется за 0.047 сек.
       Почему так быстро? Все очень просто:
       — запрос на вложенных множествах выполняет 3902600 неиндексированных чтений. Сложность запроса таким образом составляет n*n записей.
       — процедура, несмотря на то, что выполняет много запросов, а) делает только 1975 индексированных чтений, б) каждый запрос получает только малую часть всех записей. Сложность запроса пропорциональна n.
       В модели вложенных множеств полученный результат представляет собой хорошо перемешанный набор данных. В модели смежных вершин результат отсортирован в порядке обхода узлов, что само по себе уже может использоваться в реальных задачах. В любой случае для получения высоты дерева необходимо использовать функцию MAX().

Поиск непосредственных подчиненных

       Джо Селко признает, что в модели смежных вершин поиск непосредственных подчиненных осуществляется очень легко.
       "В модели вложенных множеств задача усложняется. Вам придется отсечь ветвь с корнем на узле начальника глубиной в один уровень. Чтобы найти всех его непосредственных подчиненных, можно определить их как людей, между которыми и их начальником нет больше никаких сотрудников.

CREATE VIEW Immediate_Subordinates (boss, worker, lft, rgt)
  AS SELECT Managers.emp, Workers.emp, Workers.lft, Workers.rgt
       FROM Personnel AS Managers, Personnel AS Workers
      WHERE Workers.lft BETWEEN Managers.lft AND Managers.rgt
        AND NOT EXISTS -- между начальником и нами нет промежуточных менеджеров!
           (SELECT *
              FROM Personnel AS MidMgr 
             WHERE MidMgr.lft BETWEEN Managers.lft AND Managers.rgt
               AND Workers.lft BETWEEN MidMgr.lft AND MidMgr.rgt 
               AND MidMgr.emp NOT IN (Workers.emp, Managers.emp));"

       Для выполнения этого запроса в наших условиях его необходимо немного модифицировать — заменить имя таблицы и столбцов. В результате получилось следующее:

  SELECT Managers.Child, Workers.Child, Workers.lft, Workers.rgt
       FROM GoodsTreeSets AS Managers, GoodsTreeSets AS Workers
      WHERE Workers.lft BETWEEN Managers.lft AND Managers.rgt
        AND NOT EXISTS -- между начальником и нами нет промежуточных менеджеров!
           (SELECT *
              FROM GoodsTreeSets AS MidMgr
             WHERE MidMgr.lft BETWEEN Managers.lft AND Managers.rgt
               AND Workers.lft BETWEEN MidMgr.lft AND MidMgr.rgt
               AND MidMgr.Child NOT IN (Workers.Child, Managers.Child));

       И, несмотря на то, что время выполнения этого запроса сравнительно невелико (0.6 сек) использовать его на практике не представляется возможным. Количество неиндексированных чтений для нашего конкретного случая составляет 14456349!!!!
       Поиск непосредственных подчиненных самая популярная операция, потому что используется в в интерактивных приложениях и визуализации дерева. И чем больше дерево, тем важнее быстродойствие этой операции. Для модели вложенных множеств быстродействие будет уменьшаться с ростом дерева независимо от его структуры и количества уровней. Для модели смежных вершин эта операция выполняется практически мгновенно и не зависит от размера дерева.

Поиск самого старшего и самого младшего подчиненного

       Celko_29.3.3.:
       "Модель вложенных множеств обычно предполагает, что непосредственные подчиненные узла ранжированы слева направо по возрасту, старшинству или какому-либо другому признаку. В модели смежных вершин такой концепции нет, поэтому приводимые далее запросы в ней невозможны без добавления к таблице еще одного столбца для ранга.
       Этот запрос позволяет найти самого старшего подчиненного:

SELECT Workers.emp, ' is the oldest child of ', :myemployee
  FROM Personnel AS Managers, Personnel AS Workers
 WHERE Managers.emp = :myemployee
   AND Workers.lft - 1 = Managers.lft; -- самый левый потомок"

       На самом деле Селко и здесь лукавит. Сортировка листьев внутри ветви не является функцией дерева. Это функция запроса, который выдает листья в том или ином порядке. Для модели вложенных множеств непосредственные подчиненные узла ранжированы слева направо по порядку поступления, а не "по возрасту, старшинству или какому-либо другому признаку". Для того, чтобы ранжировать по какому-либо признаку, необходим этот признак и механизм изменения порядка по этому признаку. Но модель не преполагает и не позволяет иметь множество признаков для ранжирования.
       Что же касается механизма изменения порядка, то следует отметить, что сначала нужно получить список непосредственных подчиненных (см. предыдущий раздел) — что само по себе связано с большими трудностями — и для уже для этого списка изменить значения lft и rgt.
       На самом деле этот пример еще раз показывает ограниченность модели вложенных множеств — если используется порядок листьев, то это только один порядок. В модели смежных вершин если и задействуется какой-то порядок листьев, то можно использовать несколько столбцов GdOrd, и тогда можно сортировать по значению любого из них. Кроме того, сортировку можно задавать как прямую, так и обратную.
       Таким образом, при равных условиях работа с упорядоченными листьями в модели смежных вершин много проще, чем в модели вложенных множеств.

Поиск пути

       Celko_29.3.4:
       "Чтобы найти любое число узлов на пути от :start_node до : finish_node, можно дважды повторить конструкцию вложенного множества с предикатом BETWEEN. Таким способом вы сформируете верхнюю и нижнюю границу множества.

SELECT T2.node,
       (SELECT COUNT(*)
          FROM Tree AS T4 
         WHERE T4.lft BETWEEN T1.lft AND T1.rgt
           AND T2.lft BETWEEN T4.lft AND T4.rgt) AS path_nbr
  FROM Tree AS T1, Tree AS T2, Tree AS T3 
 WHERE T1.node = :start_node 
   AND T3.node = :fimsh_node 
   AND T2.lft BETWEEN T1.lft AND T1.rgt
   AND T3.lft BETWEEN T2.lft AND T2.rgt;"

       Для использования в нашем случае запрос нужно несколько модифицировать.

SELECT T2.Child,
       (SELECT COUNT(*)
          FROM GoodsTreeSets AS T4 
         WHERE T4.lft BETWEEN T1.lft AND T1.rgt
           AND T2.lft BETWEEN T4.lft AND T4.rgt) AS path_nbr 
  FROM GoodsTreeSets AS T1, GoodsTreeSets AS T2, GoodsTreeSets AS T3 
 WHERE T1.Child = 972    -- :start_node
   AND T3.Child = 3426   -- :fimsh_node
   AND T2.lft BETWEEN T1.lft AND T1.rgt
   AND T3.lft BETWEEN T2.lft AND T2.rgt;"

       Результат, правда, несколько отличается, от того что приводит Селко у себя в книге, но походит на правду. При этом время выполнения запроса составляет 63 ms и требует 31600 неиндексированных + 7900 индексированных чтений.
       Что касается модели смежных вершин, что здесь стоит вспомнить, что рассматриваются "чистые деревья" (это вытекает из ограничений модели вложенных множеств), а значит поиск пути можно произвести в обратном порядке — найти всех родителей от текущего узла до самой верхней вершины (в данном случае). Это можно сделать с помощью простой рекурсивной процедуры:

create procedure GoodsTreeTopsGetParent(GdsChld Integer, ItLev SmallInt)
       returns (GdsPrnt Integer, GdsLev SmallInt) as
begin
   for select Parnt from GoodsTreeTops where Child=:GdsChld into :GdsPrnt
     do begin
        If (GdsPrnt<>0) then begin
           GdsLev = ItLev - 1;
           suspend;
           for select GdsPrnt,GdsLev from GoodsTreeTopsGetParent(:GdsPrnt,:GdsLev)
                      into :GdsPrnt,:GdsLev
             do begin 
                suspend;
                end
           end
        end
end;

       Если вызвать эту процедуру следующим образом:

Select * from GoodsTreeTopsGetParent(3426, 0);

       То получим следующий результат:

GDSPRNT GDSLEV
2070 -1
2437 -2
856 -3
1581 -4
1590 -5
972 -6
22 -1
9 -2
8 -3
2927 -4
2259 -5
2064 -6
972 -7

       Это говорит только о том, что узел, до которого определялся путь, существует в дереве 2 раза.
       При это затраты времени просто смешные — 0 ms и 15 индексированных чтений.
       Если отсортировать результаты и свести их в одну таблицу, то результат будет похожий:

CHILD PATH_NBR   GDSPRNT GDSLEV
972 1   972 -7
972 1   972 -6
1590 2   2064 -6
2064 2   1590 -5
1581 3   2259 -5
2259 3   1581 -4
856 4   2927 -4
2927 4   8 -3
8 5   856 -3
2437 5   9 -2
9 6   2437 -2
2070 6   22 -1
22 7   2070 -1

       Из этого можно сделать простой вывод. В модели вложенных множеств требуется накладывать ограничение "unique Child", чтобы не допустить появления дублирующих узлов. В противном случае результаты запроса становяться неопределенными.
       В модели смежных вершин дублирующие узлы допустимы и они просто создают несколько правильно упорядоченных списков.
       После наложения ограничений результат обоих запросов становится одинаковым:

CHILD PATH_NBR   GDSPRNT GDSLEV
972 1   972 -6
1590 2   1590 -5
1581 3   1581 -4
856 4   856 -3
2437 5   2437 -2
2070 6   2070 -1
3426 7      

       Затраты времени в обоих случаях при этом уменьшаются в 2 раза.

Функции в модели вложенных множеств

       Celko_29.4:
       "Функция LEVEL для узла данного сотрудника просто подсчитывает, сколько групп lft - rgt находится внутри узла данного сотрудника. Эту информацию можно получить, модифицировав контекст предиката BETWEEN в запросе для ветвей:

SELECT COUNT(Managers.emp) AS level
  FROM Personnel AS Managers, Personnel AS Workers 
 WHERE Workers.lft BETWEEN Managers.lft AND Managers.rgt
   AND Workers.emp = :myemployee;"

       Опять правим запрос применительно к нашей ситуации:

SELECT COUNT(Managers.Child) AS mLev
  FROM GoodsTreeSets AS Managers, GoodsTreeSets AS Workers
 WHERE Workers.lft BETWEEN Managers.lft AND Managers.rgt
   AND Workers.Child = 3426; -- :myemployee;

       Для модели смежных вершин все то же самое выполняется с помощью процедуры:

Create procedure GoodsTreeTopsLevel (GdsPrnt Integer, ItLev SmallInt)
       returns (GdsChld Integer, GdsLev SmallInt) as
begin
   for select Child from GoodsTreeTops where Parnt=:GdsPrnt into :GdsChld
       do begin
          GdsLev = ItLev + 1;
          suspend;
          for select GdsChld,GdsLev from GoodsTreeTopsLevel(:GdsChld,:GdsLev)
                     into :GdsChld,:GdsLev
            do begin 
               suspend;
               end
          end
end;

       Затраты времени и количество чтений для обоих запросов одинаковы. Но в процедуре легко получается разность уровней, потому что уровень считается от одного (родительского) узла до другого (дочернего) узла.

       Celko:
       "Простую суммарную заработную плату подчиненных данного руководителя можно получить приблизительно так же. Обратите внимание, что в эту сумму входит и зарплата самого начальника.

SELECT SUM(Workers.salary) AS payroll
  FROM Personnel AS Managers, Personnel AS Workers
 WHERE Workers.lft BETWEEN Managers.lft AND Managers.rgt
   AND Managers.emp = :myemployee;"

       Это действительно просто. Но и в модели смежных вершин это решалось не сложнее. Для этого достаточно вспомнить раздел "Подсчет суммарной зарплаты".

       Celko:
       "Несколько сложнее подсчитать накопленную сумму с использованием столбцов количества для узлов. Это, например, может потребоваться в спецификации изделия, когда одна сборочная единица содержит несколько экземпляров другой сборочной единицы.

SELECT SUM (Subassem.qty * Subassem.price) AS totalcost
  FROM Blueprint AS Assembly, Blueprint AS Subassem 
 WHERE Subassem.lft BETWEEN Assembly.lft AND Assembly.rgt
   AND Assembly.partno = :thispart;

       В разделе 29.7 это описано несколько подробнее."
       Конечно слова "несколько сложнее" написаны позабывчивости. Дело в том, что как было показано выше модель вложенных множеств не позволяет использовать "несколько экземпляров другой сборочной единицы", так как другие функции дают неопределенные результаты. Следовательно и комментировать здесь нечего.

Удаление узлов и ветвей

       В данном разделе (29.5) Селко опять пытается доказать, что в модели вложенных множеств "порядку следования потомков придается некоторое значение". Что есть узлы "первые среди равных", несмотря на то, что обсуждается лишь удаление ветвей и узлов.
       На самом деле вопрос несколько сложней. Селко считает, что можно и нужно удалять целиком ветвь так как это показано в разделе 29.5.1 и даже приводит сложнейшую процедуру, которая это делает. Но на практике при ошибке пользователя это может привести к краху системы. Например, бухгалтерскую систему фирмы "Фрегат" именно таким образом удалось сломать за 5 минут. Поэтому, с целью обеспечения защиты от ошибок пользователя удаление ветви вместе с узлами необходимо запретить.

       Celko_29.5.2:
       Удалить один узел из середины дерева труднее, чем целую ветвь. При удалении узла вам обязательно надо решить, что делать с образовавшимся пробелом в последовательности (как заполнить узел). Есть два способа. Во-первых, можно переместить одного из потомков на место удаленного узла: после смерти отца старший сын наследует его дело, как показано на рис. 29.5. Старший сын всегда является самым левым потомком узла-родителя.
       Однако при выполнении операции возникают некоторые трудности. Если у старшего сына есть свои дети, вам надо решить, как поступить с ними, и повторять это, спускаясь вниз по дереву, пока не окажетесь на листовом узле.
       Второй метод предполагает подключение детей к родителю удаленного узла: после смерти мамы детей усыновляет бабушка, как показано на рис.29.6.
       В модели вложенных множеств это происходит автоматически: вы просто удаляете узел, и его потомки автоматически входят в непосредственное подчинение узла-предка. Будьте внимательны, закрывая оставшийся после удаления пробел. Вам придется изменить нумерацию не только потомков удаленного узла, но и всех узлов справа. Код соответствующей процедуры:

CREATE PROCEDURE DropNode (downsized IN CHAR(10))
BEGIN ATOMIC
DECLARE dropemp CHAR(10), droplft INTEGER, droprgt INTEGER;
-- сохраняем удаленный узел с помощью единичного оператора SELECT 
SELECT emp, lft, rgt 
  INTO dropemp, droplft, droprgt
  FROM Personnel 
 WHERE emp = downsized,
-- удаление происходит легко 
DELETE FROM Personnel WHERE emp = downsized,
-- закрываем пробел 
UPDATE Personnel 
   SET lft = CASE
             WHEN lft BETWEEN droplft AND droprgt THEN lft - 1 
             WHEN lft > droprgt THEN lft - 2 
             ELSE lft END
       rgt = CASE
             WHEN rgt BETWEEN droplft AND droprgt THEN rgt - 1
             WHEN rgt > droprgt THEN rgt - 2 
             ELSE rgt END; 
 WHERE lft > droplft; 
END PROCEDURE;"

       Да, конечно, можно в приложение вставить обе варианта удаления узлов и, как это обычно происходит, забыть в документации указать на подводные камни обоих способов. При этом необходимо помнить о том, сколько конечных пользователей читает документацию.
       Первый способ, упомянутый Селко прямо указывает — пользователь должен решить, что делать с дочерними узлами того узла, который должен стать родительским вместо удаленного. Значит такой способ недопустим.
       Второй способ, очень просто выполняется в модели вложенных множеств. Но если поведение дочерних узлов отличается от этого способа, то пользователь опять вручную должен изменить их положение. В модели смежных вершин простое удаление узла делает недоступным вложенную в него ветвь. Вспомните, файловую систему FAT в MS-DOS (Win-95,98) — при порче одного сектора можно было потерять половину диска. Хотя весьма простое решение позволяет реализовать второй способ и в модели смежных вершин:

Select Parnt from GoodsTreeTops
 where Child=:Node into :Prnt;
Update GoodsTreeTops set Parnt=:Prnt
 where Parnt=:Node;
Delete from GoodsTreeTops 
 where Child=:Node;

       Универсальное решение в данном случае заключается в том, чтобы запретить удаление узла, в случае наличия у него дочерних узлов. Как распорядится дочерними узлами пусть явно решит конечный пользователь.
       Для Селко же данный раздел нужен был только для показа как закрывать образовавшйся пробел при удалении узла. Подробностям этого и посвящен следующий раздел 29.6.

Применение функций суммирования к деревьям

       Этот раздел (29.7) в изложении Селко опирается на "БД со спецификацией изделия, но на этот раз в представлении вложенного множества". Можно было бы конечно проанализировать всю эквилибристику с запросами, если бы не одно НО! Спецификация изделия в подавляющем большинстве случаев содержит повторяющиеся детали в различных узлах. А модель вложенных множеств не позволяет использовать повторяющиеся детали, так как другие функции дают неопределенные результаты в таких случаях.
       С другой стороны, суммирование в модели смежных вершин не представляет проблемы.

Вставка и обновление деревьев

       Celko_29.8:
       Ввод ветви или нового узла предполагает поиск места в дереве для новых узлов, отдаление от корня других узлов путем увеличения номеров их вложенности, а затем изменение нумерации ветви, как требуется. В принципе, это можно назвать процедурой удаления узла наоборот. Сначала найдите родителя узла, а затем отодвиньте номера вложенности на две позиции (для номера rgt). Вставим, например, новый узел G1 под узлом G. Это можно сделать так:

BEGIN
INSERT INTO Frammis (part, qty, wgt, lft, rgt)
VALUES ('G1', 3, 4, 0, 0);
UPDATE Frammis
   SET lft = CASE WHEN lft >  (SELECT F1.lft
                                 FROM Frammis AS F1 
                                WHERE F1.part = 'G')
                  THEN lft + 2
                  WHEN lft = 0
                  THEN (SELECT F1.lft + 1
                          FROM Frammis AS F1
                         WHERE F1.part = 'G1')
                  ELSE lft END,
       rgt = CASE WHEN lft > (SELECT F1.lft
                                FROM Frammis AS F1
                               WHERE F1.part = 'G')
                  THEN rgt + 2
                  WHEN lft = 0
                  THEN (SELECT F2.lft + 2
                          FROM Frammis AS F2
                         WHERE F2.part = 'G')
                  ELSE rgt END;
END;

       Рассмотрим этот фрагмент подробнее. Первое предложение WHEN в операции обновления номеров lft и rgt увеличивает пространство на два номера, если узел находится справа от точки вставки. Второе предложение WHEN обновляет целый узел под его родителем. Предложение ELSE оставляет узлы слева от данного в неизменном виде."
       Вот и подобрались к "чуду".
       Так как же вставляются узлы. Как собрать новое дерево из ничего. Если следовать логике Селко, то для вставки новой записи необходимо указывать 2 вспомогательных параметра — узел и направление "Слева" или "Справа". При заполнение из скрипта большой таблицы для этого нужно проявить чудеса эквилибристики. Если же использовать метод, который применяется в модели смежных вершин, то требуется указывать только родительский узел, а порядок дочерних узлов определяется порядком вставки.
       Триггер, который выполняет обновления номеров lft и rgt показан ниже:

CREATE TRIGGER GOODSTreeSets_Insert FOR GOODSTreeSets
ACTIVE BEFORE INSERT POSITION 0 
AS
DECLARE VARIABLE Tmp Integer;
DECLARE VARIABLE Nbr Integer;
BEGIN
   Tmp = GEN_ID(gGoodsTreeSets,1); -- для измерений
-- [Для вложенных множеств] самый левый узел
    If (new.Parnt=0) then
      Begin
        new.Lft = 1;
        new.Rgt = 2;
     End
    Else
      Begin
        SELECT Lft FROM GoodsTreeSets WHERE Child = new.Parnt into :Nbr;
        UPDATE GoodsTreeSets
           SET lft = CASE WHEN lft > :Nbr THEN lft + 2 
                          ELSE lft END,
               rgt = CASE WHEN Rgt > :Nbr THEN rgt + 2
                          ELSE rgt END;
        new.Lft = :Nbr + 1;
        new.Rgt = :Nbr + 2;
     End
END;

       Использование генератора в данном триггере не относится в заполнению данных, а служит только как счетчик вставленых строк.
       Итак, каково время заполнения таблицы:

Таблица Кол.строк время, сек
GoodsTreeTops 1975 1.109
GoodsTreeSets 1975 23.688

       т.е. модель вложенных множеств проигрывает более чем в 20 раз. И это на очень маленькой таблице. Почему?
       Да, все очень просто! При вставке записи в модели смежных вершин Update делается ТОЛЬКО для одной строки. При вставке записи в модели вложенных множеств Update делается для ВСЕХ записей, которые правее вставляемой. И чем больше таблица, тем больше записей необходимо обновить. И так как верхняя граница сложности алгоритма для модели вложенных множеств равна N*(N-1)/2, то при больших таблицах вставка записей будет занимать недопустимо большое время.

Резюме

       Модель вложенных множеств может быть интересна как абстрактная математическая модель. Некоторые, не самые популярные функции в ней могут выполняться несколько быстрее. Другие, более популярные функции, как, например, вставка записей, будут выполняться много дольше. При больших таблицах время выполнения некоторых функций становится недопустимо большим. Кроме того, полный набор функций приводит к значительным ограничениям в структуре записей, таким как например, невозможность использовать повторное вхождения узла, как это требуется при описании сборочных узлов, например, автомобилей или других механизмов.
       При описании модели вложенных множеств Джо Селко несколько лукавит, ограничивая модель смежных вешин столько родительскими связями, а в модели вложенных множеств добавляя столбцы по своему усмотрению. При равных условиях, с добавлением соответствующих столбцов в модель смежных вершин, модель вложенных множеств проигрывает практически по всем параметрам в десятки, а то и в тысячи раз.

© 01.08.2009, Архангельский А.Г.

<<Пред. Оглавление
Начало раздела
След.>>




Дата последнего изменения:
Thursday, 21-Aug-2014 09:10:44 MSK


Постоянный адрес статьи:
http://az-design.ru/Support/DataBase/DBTree2/5000.shtml