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

Леонов Ю.А.

(Москва, Московский Энергетический Институт (ТУ), Россия)

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

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

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

Для представления дерева в базе данных необходимо, очевидно, хранить информацию обо всех вершинах графа, а также матрицу смежности, содержащей информацию о связях между вершинами. Однако постольку, поскольку для каждого узла, кроме корневого узла, существует один и только один непосредственный предок, вся информация о дереве может храниться в одной таблице (рис. 1). В таблице GoodsGroup хранится информация о группах товаров (в данном примере у группы представлен только один атрибут – название, обычно число полей у таких таблиц гораздо больше). Первичный ключ таблицы – поле id, столбец parent содержит id группы-предка для каждой записи таблицы.

Как показывает практика, наиболее часто, при работе с такого рода данными, возникают задачи – «выбрать всех потомков какого-либо узла» и «выбрать всех предков какого-либо узла». Нетрудно написать рекурсивную хранимую процедуру, которая выдаст искомое множество данных. Проблема в том, что данные, полученные таким образом, не являются конечным результатом, их надо использовать для объединения с другими таблицами, в более сложных запросах. Таким образом, более точно выделить и сформулировать одну из наиболее важных проблем, которая стоит перед разработчиками при работе с деревьями, можно так: необходимо сформировать множество всех предков или потомков какого-либо узла в дереве с помощью одного SQL-запроса.

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

Суть первого варианта заключается в следующем: в таблице c деревом заводится дополнительное поле, содержащее информацию, как о самом узле, так и обо всех его предках. Введем в таблицу GoodsGroup строковое поле Ord, которое для каждого элемента дерева будет заполнено следующим образом – оно складывается из значения этого поля у родительского элемента, преобразованного в строку поля id самого элемента и какого-либо символа-разделителя, например « , ». Поддерживать данные в таком поле удобнее всего при помощи триггеров на таблицу GoodsGroup. SQL-запросы, необходимые для этого, оставим вне рамок доклада, отметив только, что они достаточно просты.

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

SELECT GG2.* FROM GoodsGroups GG1, GoodsGroups GG2

WHERE GG1.id = :id AND GG2.ord LIKE GG1.ord + ‘%’

Несмотря на свою простоту, этот запрос имеет важный недостаток, связанный с особенностями оптимизации планов выполнения запросов на конкретных СУБД – при его выполнении не будет использоваться индекс по полю ord, что приведет к увеличению времени выполнения и нагрузки на сервер (это справедливо для SQL-серверов Microsoft и Sybase).

Авторство второго метода хранения – модели вложенных множеств –принадлежит Joe Celko; приведем ниже его краткое описании. Обойдем узлы дерева в порядке, указанном на рис. 3., начиная с корня графа. Таким образом, каждый узел получит два номера – один для правой и один для левой стороны. Схема, необходимая для хранения такой структуры данных, приобретает вид, показанный на рис. 4.

Корень дерева всегда имеет значение 1 в левом столбце и удвоенное число узлов (2*n) в правом столбце. Вот как в этом случае будет выглядеть запрос, выдающий всех потомков узла:

SELECT GG2.* FROM GoodsGroup GG1, GoodsGroup GG2 WHERE GG1.id=:id AND GG2.left between GG1.leftAND GG1.right;

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

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

В этой таблице для каждого элемента дерева хранятся записи обо всех его потомках, но в отличие от матрицы смежности, не только непосредственных, но абсолютно всех. Таким образом, если для любых двух элементов дерева существует отношение Предок-Потомок, то в таблице GoodsGroupTree для этой связи будет запись, где в поле parent содержится идентификатор предка, а в поле id – идентификатор потомка. Вот как в этом случае будет выглядеть запрос, выдающий всех потомков какого-либо узла:

SELECT GoodsGroup.* FROM GoodsGroup, GoodsGroupTree

WHERE GoodsGroupTree.parent=:id AND GoodsGroup.id=Goods GroupTree.id

Запрос будут выполняться с эффективным использованием индексов на обе таблицы. Данные в таблице GoodsGroupTree удобнее всего модифицировать при помощи относительно несложных конструкций в триггерах на таблицу GoodsGroup.

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

                                Сравнение методов хранения иерархий                    Таблица 1

Характеристика	Модель вложенных множеств		Хранение полного набора
	Метод строки	Метод Celko
Простота реализации	+	-	+
Простота модификации данных	+	-	+
Эффективность запросов	+/-	+/-	+
Небольшой объем данных	-	+	-
Возможность множеств. наследия	-	-	+

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

Литература

1.     Дейт К. Руководство по реляционной СУБД DB2. - М.: Финансы и статистика, 1988. - 320 с.

2.     Мейер М. Теория реляционных баз данных. -М.: Мир, 1987. - 608 с.