Моделирование иерархических объектов

Виноградов С. А.
04.06.2001 г.

Введение

Многим структурам и объектам свойственна иерархичность. За примерами далеко ходить не надо. Почти все объекты состоят из частей, которые, в свою очередь, могут состоять из более мелких деталей. Общественные структуры, как правило, отражают жесткую иерархическую модель подчинения, сходящуюся к одному подразделению или человеку.

Из-за внешнего сходства, иерархические модели часто называют деревьями, вершину иерархии - корнем дерева, самые низшие ответвления - листьями.

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

Иерархические структуры довольно часто приходиться моделировать в базах данных, при этом возникают некоторые, характерные только для иерархии, вопросы. Например, как узнать количество всех потомков у данного элемента, или, на каком уровне он находится, или, допустим, требуется получить список всех потомков заданного элемента, у которых нет детей. Попробуем получить ответы на эти и другие вопросы.

Простейшая иерархия

В качестве примера, возьмем часть схемы подразделений на предприятии:

A1
B1	B2
C1	C2	C3

где А1 - подразделение верхнего уровня (возможно, не единственное на этом уровне),
В1 и В2 - входят в А1,
С1 - входит в В1, С2 и С3 - входят в В2.

Можно легко создать таблицу, которая содержит информацию об этих подразделениях (здесь идалее - синтаксис MS SQL):

create table Departments
(
Id int not null identity primary key,
Parent int not null references Departments(Id),
Name varchar(32) not null
)

Поле Parent является ссылкой на Id (первичный ключ) вышестоящего уровня в иерархии. В данном случае оно указывает, в какое подразделение входит каждый отдел.

Departments
Id	Parent	Name
1	0	A1
2	1	B1
3	1	B2
4	2	C1
5	3	C2
6	3	C3

Характерные вопросы

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

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

Также может потребоваться узнать, на каком уровне иерархии находится заданный элемент.

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

Часто бывает нужно получить всех потомков какого-нибудь элемента, при этом с разными условиями: например, только терминальных, или, находящихся только на определенном уровне и т. д.

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

Обход дерева

Одно из решений было предложено Joe Celko (см. [1]). Он рекомендовал добавить в таблицу два дополнительных целочисленных поля: Left и Right, в которые заносятся результаты обхода дерева, начиная с корня. Обход организуется следующим образом: каждый раз, при прохождении какого-нибудь элемента указателем, счетчик увеличивается на единицу; при попадании в терминальный элемент, указатель возвращается в родителя и ищет следующего ребенка. В поле Left записывается значение счетчика при первом прохождении элемента, а в поле Right - при последнем. При таком варианте, наша таблица подразделений выглядела бы следующим образом:

create table Departments
(
Id int not null identity primary key,
Parent int not null references Departments(Id),
Name varchar(32) not null,
Left int not null,
Right int not null
)

Departments
Id	Parent	Name	Left	Right
1	0	A1	1	11
2	1	B1	2	4
3	1	B2	6	10
4	2	C1	3	3
5	3	C2	7	7
6	3	C3	9	9

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

Терминальные элементы заметно сразу - у них Left = Right.

Отношения предок - потомок вычисляются тоже легко: Left потомка всегда больше чем у предка, а Right - меньше.

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

Количество потомков = (Right - Left) / 2.

Главный недостаток этого решения в том, что при изменении в структуре дерева, приходится заново пересчитывать значения полей Left и Right во всей таблице. То есть, такой способ годится только для небольших, редко изменяемых таблиц.

Вспомогательная таблица

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

create table DepartmentsAncestors
(
Department int not null references Departments(Id),
Ancestor int not null references Departments(Id)
constraint DepartmentAncestor primary key (Department, Ancestor)
)

Поле Ancestor ссылается на Id предка каждого элемента. В данном случае оно позволяет узнать все подразделения, в которые входит данный отдел.

DepartmentsAncestors
Department	Ancestor
2	1
3	1
4	2
4	1
5	3
5	1
6	3
6	1

Подобная схема легко позволяет получить любую информацию об иерархических элементах одним запросом.

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

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

Терминальность элемента можно узнать, пользуясь только основной таблицей - достаточно проверить, есть ли элементы, Parent которых равен Id текущего.

Модификация вспомогательной таблицы, при изменении основной, производится довольно просто. Заботу о ней можно предоставить либо триггерам, либо приложению.

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

create table Departments
(
Id int not null identity primary key,
Parent int not null references Departments(Id),
Name varchar(32) not null,
Level int not null,
Terminal bit not null defaul(1)
)

Departments
Id	Parent	Name	Level	Terminal
1	0	A1	1	0
2	1	B1	2	0
3	1	B2	2	0
4	2	C1	3	1
5	3	C2	3	1
6	3	C3	3	1

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

---

Используемые источники

[1] Joe Celko "A Look at SQL Trees",
http://ib.demo.ru/DevInfo/DBMSTrees/9603d06.html
http://ib.demo.ru/DevInfo/DBMSTrees/9604d06.html
http://ib.demo.ru/DevInfo/DBMSTrees/9605d06.html