Моделирование иерархических объектов средствами реляционных СУБД (стр. 7 )

Таблица четвёртого уровня

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

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

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

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. /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.

Библиографический список

1.  Celko, J. Деревья в SQL / J. Celko // DBMS Online. 1996. March. http://www. /9603d06.html

2.  Celko, J Trees in SQL / J. Celko // Intelligent Enterprise. 2000. № 10.

3.  Celko, J. A Look at SQL Trees / J. Celko // http://ib. *****/DevInfo/DBMSTrees/9603d06.html http://ib. *****/DevInfo/DBMSTrees/9604d06.html http://ib. *****/DevInfo/DBMSTrees/9605d06.html

4.  Kimball, R. Help for Hierarchies / R. Kimball // DBMS. 1998. September.

5.  Виноградов иерархических объектов / // http://www. *****/database/articles/tree. shtml

6.  Стулов, А. Особенности построения информационных хранилищ / А. Стулов // Открытые системы. 2003. №04. http://www. *****/database/articles//

7.  Голованов, М. Иерархические структуры данных в реляционных БД / М. Голованов // RSDN Magazine. 2005. № 0. http://*****/article/db/Hierarchy. xml

8.  Мухачев, Е. Еще раз об иерархии / Е. Мухачев // http://www. isp. /development/interbase/devinfo/treeadd. htm

9.  Христофоров, Ю. Построение дерева иерархии с помощью PHP / MySQL / Ю. Христофоров // 2004. http://www. . ru/docs/tree. shtml

10.  Кузьменко, Д. Древовидные (иерархические) структуры данных в реляционных базах данных. Часть 1. / Д. Кузьменко // Epsylon Technologies. http://www. *****/devinfo/treedb. htm

11.  Кузьменко, Д. Древовидные (иерархические) структуры данных в реляционных базах данных. Часть 2. / Д. Кузьменко // Epsylon Technologies. http://www. *****/devinfo/treedb2.htm

12.  Ицик, Бен-Ган. Иерархические структуры, не требующие сопровождения / Бен-Ган Ицик // SQL Magazine OnLine. 2001. № 5. http://*****:8083/win2000/sql/2001/05/967.htm

13.  О наиболее предпочтительных особенностях и предложении CONNECT BY (On Favorites and CONNECT BY, by Tom Kyte) / Т. Кайт // Oracle Magazine, 2005., May-June. http://www. /technology/oramag/oracle/05-may/o35asktom. html

Учебное издание

МОДЕЛИРОВАНИЕ ИЕРАРХИЧЕСКИХ ОБЪЕКТОВ
СРЕДСТВАМИ РЕЛЯЦИОННЫХ СУБД

Редактор

Компьютерная верстка

ИД № 000 от 01.01.2001 г.

Подписано в печать		Формат 60х80 1/16
Бумага типографская	Плоская печать	Усл. печ. л.
Уч.-изд. л. 5,0	Тираж 50	Заказ

Редакционно-издательский отдел УГТУ-УПИ

Екатеринбург, ул. Мира, 19

*****@

Название и адрес типографии

[1] Этот метод также называют списком смежности или матрицей смежности

 [Ш1]Добавить каскадное удаление!!!

CREATE mytable

(id INT, ...

CONSTRAINT pk_mytable PRIMARY KEY (id),

CONSTRAINT fk_mytable FOREIGHN KEY (id)

REFERENCES object ON DELETE CASCADE,...)

И дальше во всех примерах, где это нужно!!!

 [Ш2]Добавить про каскадное удаление!!!