Иерархические структуры данных в реляционных БД

Михаил Голованов

Введение

Архитектура реляционных баз данных ориентирована на хранение внутри таблиц БД информации о сущностях информационной системы и связях между ними. Каждая из записей таблицы содержит информацию об одном экземпляре. Организация хранения информации о независимых друг от друга экземплярах сущностей (т.е. так называемых «плоских» данных) не вызывает никаких затруднений. Однако, наряду с «плоскими» данными, при построении даже простых информационных систем, приходится хранить в БД и информацию о «вложенных» друг в друга сущностях, т.е иерархические данные. Организация хранения такой информации в реляционных БД проста, но не всегда очевидна для тех, кто впервые сталкивается с подобной задачей. В данной статье я попытаюсь поделиться накопленным опытом.

Примеры, приводимые далее, были созданы и протестированы с помощью Interbase 6.

Иерархии данных

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

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

Рассмотрим некоторые варианты представления иерархических структур в реляционных БД.

Возможные варианты структур БД для хранения иерархий

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

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

Сложность вычисления уровня вложенности произвольного элемента.

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

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

Данная структура является минимально необходимой и достаточной для организации и хранения иерархии. Назовем ее структурой со ссылкой на предка. В данной структуре присутствует как минимум один недостаток – отсутствие контроля правильности ссылки на родителя. Какие же значения поля PARENT_ID являются правильными? Ответ очевиден – весь диапазон значений первичного ключа (поля ID) + одно значение, используемое для обозначения отсутствия родительского элемента. Данное значение необходимо для ввода и хранения корневых элементов иерархии. Чаще всего в качестве значения, обозначающего отсутствие родителя, используется NULL, хотя нет никаких физических ограничений для использования других значений. Так, например, если вы уверены, что значения первичного ключа будут больше 0, в качестве признака корневого элемента можно использовать значение (–1) или другие отрицательные значения в поле PARENT_ID. Я не буду оригинален и в качестве значения PARENT_ID для корневых элементов использую NULL. Тогда для контроля правильности PARENT_ID можно использовать следующее ограничение: