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

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 для хранения начала и конца диапазона первичных ключей всех потомков данного элемента. Такая иерархия может быть представлена набором отрезков (см. рисунок). Это позволяет быстро и легко выбрать всех потомков данного элемента. Данную структуру назовем структурой с хранением границ ветви.

Итак, мы рассмотрели несколько различных типов структур для хранения иерархий. Далее мы рассмотрим решение задач, связанных с использованием этих структур:

получения потомков элемента;

получения уровня вложенности элемента;

получения полного пути от элемента до корня иерархии;

операции вставки, удаления, перемещения элемента и его потомков для вышеперечисленных структур.

Получение непосредственных потомков

Получение потомков элемента является основной задачей при построении и отображении дерева. Далее мы рассмотрим получение потомков для:

структур со ссылкой на предка

К этому виду структур относится и модификация с поддержкой информации об уровне элемента, а также структура с хранением границ ветви. Очевидно, что в такой структуре потомками элемента будут все элементы, ссылающиеся на данный (PARENT_ID потомков равен ID родителя). Запрос на выборку потомков (имена таблицы и полей взяты из приведенных выше описаний) выглядит так:

SELECT “ID” FROM CATALOG WHERE “PARENT_ID” = <значение id родителя>

структур с потабличным хранением уровней

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

SELECT “ID” FROM <имя таблицы с потомками> where <сложная ссылка на предка> = <сложный первичный ключ предка>

Например, для определения потомков узла второго уровня с ID = 10 и PARENT_ID = 5 запрос будет:

SELECT “ID” FROM CATALOG3_LEVEL3 WHERE “PARENT_ID”=5 AND “PARENT_ID2” = 10

структур с поразрядным ключом

При структуре с поразрядным правым ключом непосредственные потомки имеют первичные ключи c ненулевым следующим разрядом и таким же, как первичный ключ предка числом в младших разрядах. В ранее рассмотренном нами случае потомки первого корневого элемента (ID = 1) будут иметь ID 11,21,31,41, …91. Запроснавыборку:

SELECT “ID” FROM “CATALOG4” WHERE “ID” IN (11,21,31,41,51,61,71,81,91)

Структура с левым ключом для первого корневого элемента (ID = 10000) потомки 11000, 12000,13000…19000.

Получение всех потомков

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

структура со ссылкой на предка и ее модификация с поддержкой информации об уровне элемента

Простого способа, к сожалению, нет. Приходится организовывать рекурсию запросов.

структура с потабличным хранением уровней

Потомки данного элемента содержатся в “нижележащих” таблицах и имеют как часть составной ссылки на предка в одном из полей значение ID предка. Общий список потомков можно получить объединением (UNION) запросов.

select "ID",'1' as "LEVEL" from CATALOG3_LEVEL2 where PARENT_ID = 1unionselect "ID",'2' as "LEVEL" from CATALOG3_LEVEL3 where PARENT_ID = 1

Ввод дополнительного поля LEVEL в запрос обусловлен тем, что потомки элемента в разных таблицах могут иметь одинаковые ID и при объединении запросов вместо нескольких строк в результате будет получена одна. Еще одна проблема, приводящая к необходимости ввода дополнительного поля в запрос, т.к. надо знать, из какой таблицы выбран данный ID.

структура с поразрядным ключом

В данной структуре содержится информация о полном пути к элементу. Это облегчает выборку всех потомков.

Левый ключ

Для первого корневого элемента диапазон ID потомков будет 10001… 19999, для второго 20001…29999 и т.д.

Правый ключ

Ну, здесь тоже все просто. Первый элемент иерархии ID = 1, на втором уровне его первый предок 11 и т.д. Таким образом, потомки будут иметь в конце ID цифры, совпадающие с ID предка.

структура с хранением границ ветви

Элементы структуры LOW и HIGH хранят границы диапазона первичных ключей всех потомков.

Получения уровня вложенности элемента

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

структура со ссылкой на предка, структура с хранением границ ветви

Построение полного пути к корню дерева и определение числа предков. Довольно неудобно, но другого способа нет.

структура со ссылкой на предка и хранением уровня вложенности

Недаром мы ввели поле для хранения уровня вложенности. Оно-то и содержит нужную нам информацию.

структура с потабличным хранением уровней

Уровень вложенности определяется таблицей, в которой хранится запись об элементе.

структура с поразрядным ключом

Уровень вложенности определяется положением последнего ненулевого разряда в ключе.

Получения полного пути от элемента до корня иерархии

структура со ссылкой на предка и ее модификация с поддержкой информации об уровне элемента, структура с хранением границ ветви

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

CREATE PROCEDURE GET_PARENTS (ID INTEGER)RETURNS (E_ID INTEGER, NAME CHAR(200))ASdeclare variable P_ID integer;BEGIN select PARENT_ID from CATALOG where ID = :ID into :ID; WHILE (ID > 0) DO BEGIN SELECT C.ID, C.PARENT_ID, C.NAME FROM CATALOG C WHERE ID = :ID INTO :E_ID, :P_ID,:NAME; ID=P_ID; SUSPEND; ENDEND ^

структура с потабличным хранением уровней, структура с поразрядным ключом

Полный путь содержится в первичном ключе элемента.

Операции вставки, удаления, перемещения элемента и его потомков

структура со ссылкой на предка

Добавление нового элемента:

insert into “CATALOG”(“name”,”parent_id”) values( _win1251 ‘Новый элемент’, <значение первичного ключа предка>);

Удаление элемента: Кроме непосредственно самого элемента необходимо удалить и его потомков. Проблема решается введением триггера:

CREATE TRIGGER "CATALOG_AFTER_DEL" FOR "CATALOG"ACTIVE AFTER DELETE POSITION 0ASBEGIN delete from "CATALOG" where "PARENT_ID" = OLD."ID";END ^

Перемещение элемента: надо просто поменять ссылку на родителя.

UPDATE “CATALOG” SET “PARENT_ID” = <Значение первичного ключа нового родителя> WHERE “ID” = <Значение первичного ключа элемента>

структура со ссылкой на предка и поддержкой уровней

Можно использовать запросы, аналогичные случаю с базовой структурой. Для проверки корректности поля Level можно ввести дополнительные триггеры:

CREATE EXCEPTION "WRONG_LEVEL" 'Неверный уровень вложенности элемента';/* Триггер перед вставкой записи в таблицу - проверяет корректность поля Level и формиррует ID записи*/CREATE TRIGGER "CATALOG_BEFORE_INS" FOR "CATALOG"ACTIVE BEFORE INSERT POSITION 0AS declare variable parent_level integer;BEGIN if (NEW."ID" is null) then NEW."ID" =GEN_ID(CATALOG_GEN,1); /*Корневыеэлементыимеютуровень 1*/ if ((NEW."PARENT_ID" is NULL) and (NEW."LEVEL" <> 1)) thenexception WRONG_LEVEL; /*Значение поля Level для некорневых элементов должно быть на 1 больше, чем у их родителя*/if (NEW."PARENT_ID" is NOT NULL) THEN begin select "LEVEL" from "CATALOG" WHERE "ID" = NEW."PARENT_ID" into :parent_level; if (NEW."LEVEL" <> :parent_level+1) then exception WRONG_LEVEL; endEND ^/* Триггер перед обновлением - контролирует правильность поля Level*/CREATE TRIGGER "CATALOG_BEFORE_UPD" FOR "CATALOG"ACTIVE BEFORE UPDATE POSITION 0AS declare variable parent_level integer; declare variable child_id integer;BEGIN if ((NEW."PARENT_ID" is NULL) and (NEW."LEVEL" <> 1)) then exception WRONG_LEVEL; select "LEVEL" from "CATALOG" WHERE "ID" = NEW."PARENT_ID" into :parent_level; if (NEW."LEVEL" <> :parent_level+1) thenexception WRONG_LEVEL;END ^/* Триггер после обновления - контролирует правильность поля Level*/CREATE TRIGGER "CATALOG_AFTER_UPD" FOR "CATALOG"ACTIVE AFTER UPDATE POSITION 0ASBEGIN update "CATALOG" set "LEVEL" = NEW."LEVEL"+1 where "PARENT_ID" = NEW."ID";END ^

структура с потабличным хранением уровней

Запросы на вставку и перемещения тривиальны, и потому не приводятся. При удалении элемента можно ввести дополнительный триггер для удаления потомков, аналогично триггеру для структуры со ссылкой на предка.

структура с хранением границ ветви

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

Заключение

Ну вот, пожалуй, и все. Надеюсь, что данная статья будет вам полезна. Если у вас появились замечания, предложения или Вы обнаружили какие-либо ошибки, пишите мне mgoblin@mail.ru