45807 (Иерархические структуры данных в реляционных БД)
Описание файла
Документ из архива "Иерархические структуры данных в реляционных БД", который расположен в категории "". Всё это находится в предмете "информатика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "45807"
Текст из документа "45807"
Иерархические структуры данных в реляционных БД
Михаил Голованов
Введение
Архитектура реляционных баз данных ориентирована на хранение внутри таблиц БД информации о сущностях информационной системы и связях между ними. Каждая из записей таблицы содержит информацию об одном экземпляре. Организация хранения информации о независимых друг от друга экземплярах сущностей (т.е. так называемых «плоских» данных) не вызывает никаких затруднений. Однако, наряду с «плоскими» данными, при построении даже простых информационных систем, приходится хранить в БД и информацию о «вложенных» друг в друга сущностях, т.е иерархические данные. Организация хранения такой информации в реляционных БД проста, но не всегда очевидна для тех, кто впервые сталкивается с подобной задачей. В данной статье я попытаюсь поделиться накопленным опытом.
Примеры, приводимые далее, были созданы и протестированы с помощью Interbase 6.
Иерархии данных
Чтобы обсудить проблему хранения иерархии в реляционной БД, мы вначале рассмотрим вопрос о том, какие же иерархии данных могут встретиться на практике. В реальной жизни иерархии имеют, как правило, некоторые ограничения. Учитывая эти ограничения, можно построить более эффективные процедуры обработки иерархических данных.
Так, в общем случае, дерево может иметь любое количество уровней иерархии. Но в частных случаях число уровней может, и часто оказывается, конечным. Может быть ограничено количество непосредственных потомков одного элемента иерархии.
Рассмотрим некоторые варианты представления иерархических структур в реляционных БД.
Возможные варианты структур БД для хранения иерархий
Наиболее общим случаем является дерево с неограниченным уровнем вложенности и неограниченным количеством потомков. Для хранения такого рода иерархии необходимо добавить в описание сущности дополнительное поле – ссылку на первичный ключ предка. Такой способ организации иерархии является самым распространенным и универсальным. Однако ему присущи следующие недостатки:
Необходимость рекурсивных запросов для получения полного пути от произвольного элемента до корня дерева.
Сложность вычисления уровня вложенности произвольного элемента.
Сложность получения всех (в том числе и не прямых) потомков данного узла.
Дальнейшее рассмотрение мы будем вести на примере построения иерархической структуры – тематического каталога библиотеки. Данный каталог применяется для классификации, сортировки и поиска книг по их содержанию. Будем считать, что каждый элемент каталога описывается собственным неуникальным символьным именем. Для обеспечения уникальности записей для каждого элемента каталога необходимо ввести первичный ключ. Для поддержки иерархичности данных введем дополнительное поле-ссылку на предка данного элемента иерархии. Ниже приведено описание полученной структуры на языке SQL:
| CREATE TABLE "CATALOG" ( "ID" INTEGER NOT NULL PRIMARY KEY, "NAME" VARCHAR(200) CHARACTER SET WIN1251 NOT NULL, "PARENT_ID" INTEGER ); |
Данная структура является минимально необходимой и достаточной для организации и хранения иерархии. Назовем ее структурой со ссылкой на предка. В данной структуре присутствует как минимум один недостаток – отсутствие контроля правильности ссылки на родителя. Какие же значения поля PARENT_ID являются правильными? Ответ очевиден – весь диапазон значений первичного ключа (поля ID) + одно значение, используемое для обозначения отсутствия родительского элемента. Данное значение необходимо для ввода и хранения корневых элементов иерархии. Чаще всего в качестве значения, обозначающего отсутствие родителя, используется NULL, хотя нет никаких физических ограничений для использования других значений. Так, например, если вы уверены, что значения первичного ключа будут больше 0, в качестве признака корневого элемента можно использовать значение (–1) или другие отрицательные значения в поле PARENT_ID. Я не буду оригинален и в качестве значения PARENT_ID для корневых элементов использую NULL. Тогда для контроля правильности PARENT_ID можно использовать следующее ограничение:
| "PARENT_ID" INTEGER CHECK( ("PARENT_ID" IS NULL) OR ( "PARENT_ID" = ANY(SELECT "ID" FROM "CATALOG") ) ) (в принципе, такие ограничения намного проще и эффективнее описывать как внешние ключи. Единственной проблемой при этом является вставка корневой записи, т.к. родительской записи для нее не существует. Обойти такое ограничение можно, добавляя внешний ключ после вставки корневой записи. – прим.ред.) |
Вернемся к отмеченным выше недостаткам данной структуры (сложность формирования полного пути и вычисления уровня элемента). Эти недостатки вытекают из того простого факта, что в данной структуре информация о полном пути и уровне нигде не хранится. Решить проблему быстрого получения уровня вложенности можно введением в структуру таблицы дополнительного поля Level. Описание таблицы тогда будет выглядеть так:
| CREATE TABLE "CATALOG" ( "ID" INTEGER NOT NULL PRIMARY KEY, "NAME" VARCHAR(200) CHARACTER SET WIN1251 NOT NULL, "PARENT_ID" INTEGER CHECK( "PARENT_ID" = ANY(SELECT "ID" FROM "CATALOG") or "PARENT_ID" is NULL ), "LEVEL" INTEGER DEFAULT 1 NOT NULL ); |
Структура для хранения иерархии с неограниченным числом уровней вложенности и потомков готова.
Следующей по степени универсальности является иерархия с неограниченным числом уровней вложенности и конечным числом потомков элемента иерархии. Ограничение количества потомков позволяет хранить данные в следующем виде.
Ссылка на предка
Информация о первом элементе уровня иерархии
Информация о втором элементе уровня иерархии
…
Информация о n-ном элементе уровня иерархии, где n – количество максимальное количество потомков
Ссылка на предка содержит в себе ссылку на запись, хранящую информацию о предыдущем уровне иерархии и смещение (номер столбца) с описанием родителя.
В нашем примере мы ограничим количество предков числом 5, тогда SQL-описание таблицы будет выглядеть следующим образом:
| CREATE TABLE "CATALOG2" ( "LEVEL" INTEGER NOT NULL, "OFFSET" SMALLINT NOT NULL CHECK("OFFSET" > 0 and "OFFSET" < 6), "NAME_1" VARCHAR(200) CHARACTER SET WIN1251, "NAME_2" VARCHAR(200) CHARACTER SET WIN1251, "NAME_3" VARCHAR(200) CHARACTER SET WIN1251, "NAME_4" VARCHAR(200) CHARACTER SET WIN1251, "NAME_5" VARCHAR(200) CHARACTER SET WIN1251, "PARENT_LEVEL" INTEGER, "PARENT_OFFSET" SMALLINT CHECK(("PARENT_OFFSET" > 0 and "PARENT_OFFSET" < 6) or ("PARENT_OFFSET" is NULL)), CONSTRAINT "PK_CATALOG2" PRIMARY KEY("LEVEL","OFFSET") ); |
Больших преимуществ использования такой структуры я не вижу, недостаток же налицо – при изменении максимального количества потомков одного узла придется добавлять еще один столбец таблицы, что крайне неудобно. По этой причине подробно рассматривать эту структуру мы не станем, а перейдем к следующему случаю – иерархии с конечным числом уровней вложенности и бесконечным числом потомков узла.
Одним из вариантов хранения таких иерархий является поуровневое хранение в различных таблицах. Например, таблица CATALOG_LEVEL_1 хранит все элементы первого уровня вложенности, таблица CATALOG_LEVEL_2 – второго, и т.д. Ниже приведено описание такой структуры для случая трехуровневой иерархии.
| CREATE TABLE "CATALOG3_LEVEL1" ( "ID" INTEGER NOT NULL PRIMARY KEY, "NAME" VARCHAR(200) CHARACTER SET WIN1251 NOT NULL ); CREATE TABLE "CATALOG3_LEVEL2" ( "ID" INTEGER NOT NULL UNIQUE, "NAME" VARCHAR(200) CHARACTER SET WIN1251 NOT NULL, "PARENT_ID" INTEGER NOT NULL REFERENCES "CATALOG3_LEVEL1"("ID"), PRIMARY KEY("ID","PARENT_ID") ); CREATE TABLE "CATALOG3_LEVEL3" ( "ID" INTEGER NOT NULL UNIQUE, "NAME" VARCHAR(200) CHARACTER SET WIN1251 NOT NULL, "PARENT_ID" INTEGER NOT NULL REFERENCES "CATALOG3_LEVEL1"("ID"), "PARENT_ID2" INTEGER NOT NULL REFERENCES "CATALOG3_LEVEL2"("ID"), PRIMARY KEY ("ID", "PARENT_ID", "PARENT_ID2") ); |
При большем количестве уровней необходимо определить дополнительные таблицы для каждого уровня, по структуре аналогичные таблице CATALOG3_LEVEL2. В данной структуре получение уровня элемента не представляет никакой сложности, т.к однозначно определяется таблицей, в которой он хранится. Полный путь от любого элемента до корня также определяется составным первичным ключом таблицы. Этот вид структуры назовем структурой с потабличным хранением уровней
Последний из видов иерархии – иерархия с ограниченной вложенностью и ограниченным числом потомков. Многие из реальных задач, встречавшихся мне, в той или иной степени можно было свести к этому виду иерархии. Так, например, наша задача с каталогом библиотеки, хотя в строгом виде и является иерархией с неограниченным числом потомков узла и вложенностью, может быть сведена к рассматриваемому типу иерархии. Вполне можно ограничить количество элементов на одном уровне значением 9 (или другим достаточно большим числом) и 5 уровнями вложенности. Зачем? Затем, что в данном типе иерархии при определенной организации первичного ключа можно существенно упростить работу с иерархией. Для хранения данного вида иерархии можно использовать ранее описанные структуры иерархий с неограниченной вложенностью и количеством потомков и иерархий с ограниченным количеством уровней и неограниченным числом потомков. Однако есть две модификации структур специфичных для данного типа иерархии.
Первый тип приведен ниже:
| CREATE TABLE "CATALOG4" ( "ID" DECIMAL(5) NOT NULL PRIMARY KEY, "NAME" VARCHAR(200) CHARACTER SET WIN1251 NOT NULL ); |
Весь фокус в принципе формирования первичного ключа ID. Позиция последнего ненулевого десятичного разряда ключа – это уровень элемента, а цифра в этой позиции – номер элемента на данном уровне. Например, первый элемент первого уровня будет иметь ID = 00001, второй – 00002. На втором уровне третий элемент, имеющий предком первый элемент первого уровня, будет иметь ID = 00031, и т.д. Данная структура хороша при равномерном распределении элементов по уровням. Ее мы назовем структурой с поразрядным ключом. В зависимости от того, справа или слева находится разряд, кодирующий первый уровень, можно выделить структуру с поразрядным правым ключом и структуру с поразрядным левым ключом. В нашем случае я описал правый ключ. Если же максимальное число элементов конечно, но различно для различных ветвей дерева, и хотя бы приблизительно может быть оценено для каждой ветви, можно воспользоваться следующей структурой:
| CREATE TABLE "CATALOG5" ( "ID" INTEGER NOT NULL PRIMARY KEY, "NAME" VARCHAR(200) CHARACTER SET WIN1251 NOT NULL, "PARENT_ID" INTEGER CHECK( "PARENT_ID" = ANY(SELECT "ID" FROM "CATALOG") or "PARENT_ID" is NULL ), "LOW" INTEGER NOT NULL, "HIGH" INTEGER NOT NULL ); |
Данная структура является модификацией структуры для хранения иерархии с неограниченным уровнем вложенности и количеством потомков. В структуру добавлены поля LOW и HIGH для хранения начала и конца диапазона первичных ключей всех потомков данного элемента. Такая иерархия может быть представлена набором отрезков (см. рисунок). Это позволяет быстро и легко выбрать всех потомков данного элемента. Данную структуру назовем структурой с хранением границ ветви.
Итак, мы рассмотрели несколько различных типов структур для хранения иерархий. Далее мы рассмотрим решение задач, связанных с использованием этих структур:
получения потомков элемента;
получения уровня вложенности элемента;
