Древовидные (иерархические) структуры данных в реляционных базах данных

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

Предположим что мы действительно хотим создать таблицу "Люди", в которой нужно отслеживать родственные связи типа родитель-потомок. Для простоты представим себе, что у потомков родитель может быть только один (например, "Родитель"):

Для того, чтобы хранить информацию о родителе экземпляра объекта, любой объект в таблице должен помимо идентификатора иметь атрибут "родитель". На рисунке видно, что все "Потомки" имеют родителя, кроме самого "Родитель1". Экземпляр "Родитель1" может в принципе вообще отсутствовать – можно принять что у потомков первого уровня всегда один и тот же родитель, поэтому хранить информацию о нем необязательно (в каких случаях это необходимо, мы рассмотрим дальше).

Читатель может заметить – а как же множественное наследование? А никак. В природе такового не существует – все объекты реального мира являются или цельными, или составными. Множественное наследование было создано только как методика проектирования классов, когда разработчик не обладает полной информацией о самих классах. Автор статьи считает, что множественное наследование только запутывает реализацию прикладной области. Например, в ряде книг приводится случай, когда объект "тесто" получается множественным наследованием объектов "вода" и "мука". На самом деле это не так – даже при диффузии отдельные материалы все равно остаются сами собой, т. е. в данном случае мы имеем совершенно новый объект "тесто", который имеет среди атрибутов указатели на два класса – "тесто" и "вода" (или список составляющих "тесто" классов, как угодно). Характеристики "теста" при этом зависят не только от состава "воды" и "муки", но и от их процентного соотношения. То же самое относится и к биологическому "рождению" – ребенок наследует свойства родителей, т. е. их наборы хромосом, и представляет собой типичный составной объект при отсутствии какого бы то ни было множественного наследования. Конечно, множественное наследование в редких случаях облегчает программирование, однако это не значит, что оно отражает суть реальных вещей, которые можно описать в программе.

Итак, структура нашей "родовитой" таблицы будет выглядеть следующим образом:

Поле "Родитель" всегда ссылается на значение поля "Идентификатор". Здесь нас поджидает подводный камень – если бы мы решили, что "…ссылается на существующее значение поля…", и в соответствии с реляционными правилами объявили-бы связь конструкцией SQL "alter table … add constraint … foreign key", то попали-бы в замкнутый круг "курица и яйцо". Как создать экземпляр объекта если родителя нет? Действительно, может-ли существовать экземпляр объекта без указания родителя? Чтобы избавиться на начальном этапе хотя-бы от первого вопроса, нужно отказаться от декларации связи Родитель->Идентификатор на уровне сервера. Это снизит защищенность данных, но избавит нас от долгих раздумий в самом начале пути. На второй вопрос (может-ли существовать экземпляр без родителя) можно безболезненно ответить "нет", установив ограничение целостности для поля "Родитель" как "значение обязательно" (NOT NULL).

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

Давайте теперь посмотрим, как будет выглядеть таблица, заполненная экземплярами объектов с рисунка 2: Идентификатор Родитель Остальные атрибуты … Родитель1 . Потомок1 Родитель1 Потомок2 Родитель1 Потомок3 Потомок1 Из таблицы видно, что Потомок1 одновременно является и потомком элемента "Родитель1", и родителем элемента "Потомок3".

Такую таблицу можно создать конструкцией SQL:

Представить такую информацию можно в виде "каталогов" и "файлов", например, как в Windows Explorer. Щелчок мыши по каталогу приводит к "проваливанию" на более глубокий уровень, и т. д.

Конечно, для того чтобы иметь возможность вернуться назад по дереву нужно в приложении хранить "список возврата", т. е. список элементов, по которым мы углубились внутрь, с идентификаторами их владельцев (своеобразный "стек"). С другой стороны, нужно иметь возможность выбрать весь путь вплоть до корня начиная с произвольного элемента. Это можно сделать написав хранимую процедуру (если ваш SQL-сервер поддерживает стандарт ANSI SQL 3 в части хранимых процедур (PSM) и позволяет из хранимых процедур возвращать наборы записей). Вот как выглядит такая процедура для InterBase:

В процедуру передается идентификатор, с которого нужно подниматься “вверх” по дереву. В цикле, пока идентификатор не стал равным 0 (не поднялись выше корневого элемента) происходит выборка записи с указанным идентификатором, затем идентификатор меняется на идентификатор родителя.

Выполнение этой процедуры для наших данных привело бы к следующему результату (запрос SELECT * FROM GETPARENTS 4):

Для визуализации подобной структуры можно воспользоваться компонентом TTreeView, поставляемым в Delphi 2.0 и 3.0. Этот компонент формирует представление типа "outline" при помощи объектов TTreeNode. К сожалению, с этим типом объекта работать не очень удобно, поскольку он произведен от стандартного элемента GUI и при разработке нельзя использовать наследование. Для хранения дополнительных данных узла дерева приходится использовать поле TTreeNode.Data, представляющее собой указатель на произвольный объект или структуру данных.

При отображении небольшого количества записей (до 1000) можно считывать в память всю таблицу и формировать TTreeView в памяти, не обращаясь затем к базе данных. Однако если нужно периодически перечитывать "дерево", то такой подход будет слишком медленным. Оптимальным было бы перечитывание только раскрываемой ветви дерева. При этом перечитывание будет происходить максимально быстро, т. к. даже самая сложная древовидная структура содержит максимум 200-500 элементов в одной ветви.

Для реализации перечитывания записей по "распахиванию" ветви дерева можно использовать приведенный выше запрос с выборкой элементов одной ветви.

После выполнения этой функции создаются элементы, дочерние для указанного Node, или корневые элементы, если Node=nil.

Однако в этом случае структура данных таблицы OBJECTS не дает нам возможности узнать (без дополнительного запроса) есть ли у элемента его "подэлементы". И TreeView для всех элементов не будет показывать признак “раскрываемости” или значок “+”.

Для этих целей без расширения нашей структуры данных не обойтись. Очевидно необходимо добавить в таблицу OBJECTS поле, которое будет содержать количество дочерних элементов (0 или больше). Такое поле можно добавить

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

Триггер по вставке записи должен увеличить количество "детей" у своего родителя:

(Обратите внимание, что во всех триггерах при обращении к таблице используетс псевдоним O, а для полей в триггере используется уточнитель new. или old. Это сделано для того, чтобы SQL-сервер не перепутал изменяемые поля в UPDATE и поля таблицы в контексте триггера).

Теперь таблица OBJECTS полностью автоматически отслеживает количество "детей" у каждого элемента.

(Для того чтобы правильно освобождать память, занимаемую операцией New(R), необходимо в методе TTreeView.OnDeletion написать одну строку – Dispose(PItemRec(Node.Data); Это освободит занятую память при удалении любого элемента TTreeNode или группы элементов).

Свойство HasChildren приведет к автоматической прорисовке значка "+" в TreeView у элемента, который имеет дочерние элементы. Таким образом мы получаем представление дерева без необходимости считывать все его элементы сразу.