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

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

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

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

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

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

Существует 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. Достоинства и недочеты подхода родитель-потомок

Черта Модель перечня смежных вершин
Простота структуры (количество таблиц/ссылок/ малое количество полей) 1/1/3
Ровная подборка малышей узла Да
Ровная подборка поддерева (всех потомков узла) Нет, рекурсия
Ровная подборка пути от узла до корня (всех протцов узла) Нет, рекурсия
Порядок следования узлов при Модель вложенных множеств сортировке Нет
Стремительная вставка новых узлов Да
Резвое перемещение поддерева Да
Резвое удаление поддерева Да, рекурсия
Избыточность хранения Нет
Количество уровней дерева Не ограничено
Дополнительная поддержка целостности (не считая ссылочной) Не нужна

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

Модель вложенных множеств либо множественная модель дерева (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. Если для текущей верхушки не существует ни 1-го прямого потомка либо посреди потомков нет таких, для которых значение не присвоено, то значение этой Модель вложенных множеств верхушки равно . . Переход на 5.

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

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

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

Достоинства и недочеты множественной модели Модель вложенных множеств дерева приведены в таблице 2.

Таблица 2. Достоинства и недочеты множественной модели дерева

Черта Модель перечня смежных вершин
Простота структуры (количество таблиц/ссылок/ малое количество полей) 1/0/4
Ровная подборка деток узла Да
Ровная подборка поддерева (всех потомков узла) Да
Ровная подборка пути от узла до корня (всех протцов узла) Да
Порядок следования узлов Модель вложенных множеств при сортировке Да
Стремительная вставка новых узлов Нет
Резвое перемещение поддерева Нет
Резвое удаление поддерева Да
Избыточность хранения Нет
Количество уровней дерева Не ограничено
Дополнительная поддержка целостности (не считая ссылочной) Нужна, непростая


model-vospitatelnoj-deyatelnosti-razvitie-fizicheskoj-kulturi-i-sporta-v-sovremennih-usloviyah-materiali-mezhregionalnoj.html
model-vselennoj-stranica-17.html
model-vselennoj.html