3.2. Случай ограниченного числа потомков

В случае, когда каждый узел может иметь только ограниченное число потомков, а дерево может иметь произвольное количество уровней, можно воспользоваться следующей структурой (табл. 15 – 16):

Таблица 15

Модель с полным перечислением потомков

Идентификатор узла	Потомок 1	…	Потомок K	Содержательная часть

Для нашего примера абстрактной иерархии приведённой на рис. 1, положим, что узлы не могут иметь более трёх потомков. Тогда таблица, описывающая иерархию, будет выглядеть следующим образом:

Таблица 16

Пример заполненной таблицы

Уникальный идентификатор узла	Потомки			Содержательная часть
	1	2	3
A	B	C	NULL	A
B	D	E	NULL	B
C	F	G	H	C
D	I	NULL	NULL	D
E	J	K	L	E
F	O	NULL	NULL	F
G	M	N	NULL	G
H	P	NULL	NULL	H
I	NULL	NULL	NULL	I
J	NULL	NULL	NULL	J
K	NULL	NULL	NULL	K
L	NULL	NULL	NULL	L
O	NULL	NULL	NULL	O
M	NULL	NULL	NULL	M
N	NULL	NULL	NULL	N
P	NULL	NULL	NULL	P

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

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

Заключение

Моделирование деревьев средствами реляционных СУБД всегда представляет собой нетривиальную задачу.

Вернёмся к определению иерархии или дерева. Дерево определяется как структура, состоящая из корневого узла, который может быть связан с другими узлами - «потомками» или «дочерними узлами». Каждый узел - «потомок» может быть связан со своими узлами - «потомками», причём с любым узлом - «потомком» должен быть связан ровно один узел - "предок". Таким образом, узлы в дереве упорядочены.

Обратите внимание, что в определении отсутствует понятие «уровень» или «номер уровня».

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

Упорядоченный (линейный) список можно рассматривать как дерево с единственной ветвью. Иерархию можно представить как набор таких линейных списков. Сетевая структура или структура типа произвольного графа может быть представлена как набор деревьев и, следовательно, как набор списков, где каждый список содержит в себе путь от одного «крайнего» узла до другого. Таким образом, во всех этих структурах может быть выделено общее свойство – та или иная упорядоченность элементов.

Реляционная модель не поддерживает рекурсии или итерации. Отношения в этой модели определяются как неупорядоченные множества кортежей атомарных элементов. СУБД не поддерживает упорядоченность как для строк, так и для столбцов в таблицах. Упорядоченность ограничивается возможностями оператора SELECT. Индексы также не могут быть использованы для поддержки структур данных с упорядочением. Отсюда моделирование любых структур данных, имеющих упорядочение, возможно только при использовании внешнего по отношению к SQL объемлющего языка, например языка СУБД для написания встроенных процедур и триггеров или внешнего языка, на котором пишется приложение.

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

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

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

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

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

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

Ожидать в будущем введения каких-то расширений в стандарт SQL, позволяющих «просто» решить данную задачу, видимо, не стоит – несоответствие теории даром не проходит, хотя разработчики СУБД и предлагают свои «фирменные» средства, уменьшающие трудности манипулирования иерархическими данными.

Приведём пример работы с иерархическими данными средствами СУБД ORACLE из следующей публикации: Кайт Т. О наиболее предпочтительных особенностях и предложении CONNECT BY (On Favorites and CONNECT BY, by Tom Kyte) // Oracle Magazine, 2005., May-June.

http://www.oracle.com/technology/oramag/oracle/05-may/o35asktom.html.

Развертывание иерархии

Вопрос. У меня есть таблица, содержащая простую иерархию:

SQL> DESC test_table;

Name Null? Type

------ ------ --------------

A NUMBER(38)

B NUMBER(38)

Со следующими данными:

SQL> SELECT * FROM test_table;

A B

----------- ----------

1 -1

2 1

3 1

4 2

5 2

6 4

7 4

8 5

9 5

10 3

11 3

11 rows selected.

Мне нужен запрос, который выдаст мне каждый узел и всех его предков (родителей). То есть, то, что я должен получить, выглядит так:

A B

----------- ----------

...

9 9

9 5

9 2

9 1

...

Мне нужно именно это, потому что 9 связана с 9, 9 связана с 5 (в исходной таблице), 9 косвенно связана с 2 (через 5), и т.д. Как я могу добиться этого в запросе?

Ответ. На первый взгляд это действительно кажется тяжело, но сделать это довольно легко в сервере Oracle9i Database, а еще легче в сервере Oracle Database 10g. Мы легко можем получить всю иерархию:

SQL> SELECT a

2 FROM test_table

3 CONNECT BY PRIOR b=a

4 /

Это действительно позволяет получить ваш столбец B в желательном результате запроса. Теперь мы должны получить корневой узел каждой из строк в этой иерархии. Используя довольно новую функцию SYS_CONNECT_BY_PATH (сервер Oracle9i Database и более поздние версии), мы можем получить каждый корневой узел. Используя следующий запрос, мы можем увидеть то, что функция SYS_CONNECT_BY_PATH (SCBP) возвращает:

SQL> SELECT a,

2 SYS_CONNECT_BY_PATH (a,'.') scbp

3 FROM test_table

4 CONNECT BY PRIOR b=a

5 ORDER BY 2

6 /

A SCBP

---------- ---------

...

9 .9

5 .9.5

2 .9.5.2

1 .9.5.2.1

...

Как видите, мы начинаем получать то, что хотим: передняя часть каждого значения SCBP – корень иерархии, а остаток – столбец A. Теперь мы воспользуемся небольшим "волшебством" получения подстрок (функция SUBSTR):

SQL> SELECT a,

2 TO_NUMBER(

3 SUBSTR(scbp,1,

4 INSTR(scbp,'.')-1)

5 ) b

6 FROM (

7 SELECT a,

8 LTRIM(

9 SYS_CONNECT_BY_PATH(a,'.'),

10 '.') ||'.' scbp

11 FROM test_table

12 CONNECT BY PRIOR b=a

13 )

14 ORDER BY 2

15 /

A B

----------- ----------

...

9 9

9 5

9 2

9 1

...

И мы получили то, что нужно. Вы будете рады узнать, что в сервере Oracle Database 10g это сделать еще легче. Для запросов с предложением CONNECT BY появилась целая группа новых функций, таких, как:

• CONNECT_BY_ROOT – возвращает корень иерархии текущей строки CONNECT BY, эта функция значительно упрощает наш запрос. (Пример см. ниже.);

• CONNECT_BY_ISLEAF – признак, указывающий, что текущая строка имеет дочерние строки;

• CONNECT_BY_ISCYCLE – признак, указывающий, что в вашей иерархии текущая строка является началом бесконечного цикла. Например, если A – родитель B, B – родитель C, а C – родитель A, то у вас будет бесконечный цикл. Вы можете использовать этот признак для определения, какая строка или строки ваших данных являются началом бесконечного цикла;

• NOCYCLE – позволяет в запросе с предложением CONNECT BY распознать, что встретился бесконечный цикл и прекратить выполнение запроса без выдачи ошибки (вместо возврата ошибки зацикливания при выполнении предложения CONNECT BY).

Для нашего вопроса важна первая новая функция, CONNECT_BY_ROOT. Следующий запрос работает на нас в сервере Oracle Database 10g:

SQL> SELECT CONNECT_BY_ROOT a cbr,

2 a b

3 FROM test_table

4 CONNECT BY PRIOR b=a

5 ORDER BY 1

6 /

CBR B

----------- ----------

...

9 9

9 5

9 2

9 1

...

Можно ли применить приведённый в статье код с другими СУБД, например с MS SQL Server или IBM DB2?

Если проблема моделирования упорядоченных множеств оказывается весьма острой, следует обратиться к СУБД, поддерживающим соответствующие структуры данных, например, к СУБД ADABAS или средствам на основе XML.