Модель вложенных множеств

Теоретический материал

Подходы к организации иерархических структур

Любая достаточно сложная естественная или искусственная система характеризуется иерархической структурой – многоуровневой формой организации объектов с соответствием объектов нижнего уровня одному или нескольким объектам верхнего уровня. Примеры таких структур могут быть найдены в совершенно разных предметных областях: классификация товаров, контрагентов, комплектация изделия, иерархия должностей, административно-территориальное деление, генеалогическое древо, наконец, просто дерево перебора вариантов или дерево классов.

В связи с этим разработчикам программных продуктов все чаще приходится работать с иерархически организованными данными. В общем случае все сводится к моделированию многоуровневой связи «главный-подчиненный», «предок-потомок», «общий-конкретный», т.е. моделируется граф без циклов.

Существует 3 основных подхода к организации иерархических данных:

· родитель-потомок;

· метод вложенных множеств;

· модель материализованного пути.

Родитель-потомок

Метод родитель-потомок или модель списка смежных вершин (adjacency list model) – является одним из первых методов, разработанных для хранения иерархий в реляционных БД.

Это интуитивно понятный способ организации иерархической структуры, который представляет собой рефлексивную связь – замыкание связи таблицы БД на саму себя (Рисунок 1).

Рисунок 1. Пример рефлексивной связи

Как известно из теории, граф можно представить в виде матрицы, где на пересечении i-й строки и j-го столбца стоит 1, если между узлами (вершинами) графа с номерами i и j есть связь (ребро, дуга), или 0 в противном случае. Такая абстракция называется матрицей смежности.

Матрица смежности может быть также представлена в виде списка (множества) пар с номерами (идентификаторами, кодами) вершин по принципу: есть пара – есть связь, нет пары – нет связи.

Корневые вершины отличаются от других пар пустой (NULL) ссылкой на предка, в приведенном примере это поле «BuyerIDParent».

Выборка непосредственных родителей или потомков при такой организации иерархических данных представляет собой простой SQL-запрос, в то время как для выборки поддерева по заданному узлу потребуется рекурсивный запрос

--Выборка непосредственных потомков некоторого узла

SELECT * FROM dbo.Buyer where BuyerIDParent=1

--Выборка всех потомков некоторого узла

WITH BuyerChild(BuyerID, BuyerIDParent, [Name], [Level]) AS

(

SELECT BuyerID, BuyerIDParent, [Name], 1

FROM dbo.Buyer

WHERE BuyerID=1

UNION ALL

SELECT dbo.Buyer.BuyerID, dbo.Buyer.BuyerIDParent, dbo.Buyer.[Name], [Level]+1

FROM dbo.Buyer INNER JOIN BuyerChild ON BuyerChild.BuyerID=dbo.Buyer.BuyerIDParent

)

SELECT * FROM BuyerChild ORDER BY [Level], BuyerIDParent

Преимущества и недостатки модели списка смежных вершин приведены в таблице1.

Таблица 1. Преимущества и недостатки подхода родитель-потомок

Модель вложенных множеств

Модель вложенных множеств или множественная модель дерева (nested-set model of trees) была предложена Джо Селко и представляет собой хранение маршрута обхода графа в префиксном порядке (Рисунок 2).

Квадратик на рисунке обозначает узел, цифра в левом его углу является порядковым номером этапа маршрута при входе в узел, а цифра справа — при выходе. При префиксном порядке обхода сначала посещается корень графа, вершина «Федоров Егор Иванович», а затем выполнятся префиксный обход поддеревьев с корнями «Кравцов Евгений Николаевич», …, «Петько Татьяна Филиповна» в указанной последовательности.

Рисунок 2. Пример префиксного маршрута обхода

Как нетрудно заметить, номера потомков всегда располагаются в интервале между соответствующими номерами предка, сколь угодно дальнего. Храня такой порядок обхода дерева в БД (Рисунок 3), при выборке потомков/предков некоторого узла можно избежать рекурсии

Рисунок 3. Пример таблицы с полями для хранения префиксного порядка обхода

--Выборка всех потомков некоторого узла

SELECT b2.* FROM dbo.Buyer b1 INNER JOIN dbo.Buyer b2 ON b2.[left] BETWEEN b1.[left] AND b1.[right]

WHERE b1.BuyerID=1

Очевидная сложность модели вложенных множеств – это пересчет порядка обхода при добавлении новых или перемещении имеющихся узлов.

Для вычисления значений и right вершин используется следующий алгоритм:

1. Обход начинается с корневой вершины. Значению корня присваивается 1. Счетчику присваивается 2.

2. Если для текущей вершины не существует ни одного прямого потомка или среди потомков нет таких, для которых значение не присвоено, то значение этой вершины равно . . Переход на 5.

3. Прямому потомку текущей вершины, для которого значение еще не было присвоено, назначается . .

4. Текущей вершиной становится прямой потомок, которому было присвоено значение . Переход на 2.

5. Если для текущей вершины существует родитель, то текущей вершиной становится этот родитель. Переход на 2. Иначе конец алгоритма.

Преимущества и недостатки множественной модели дерева приведены в таблице 2.

Таблица 2. Преимущества и недостатки множественной модели дерева