Иерархические структуры данных в реляционных БД
Часто уровень вложенности элемента иерархии привязан к какому-либо классификационному признаку предметной области. Отсюда возникает задача определения уровня вложенности произвольного элемента.
структура со ссылкой на предка, структура с хранением границ ветви
Построение полного пути к корню дерева и определение числа предков. Довольно неудобно, но другого способа нет.
структура со ссылкой на предка и хранением уровня вложенности
Недаром мы ввели поле для хранения уровня вложенности. Оно-то и содержит нужную нам информацию.
структура с потабличным хранением уровней
Уровень вложенности определяется таблицей, в которой хранится запись об элементе.
структура с поразрядным ключом
Уровень вложенности определяется положением последнего ненулевого разряда в ключе.
Получения полного пути от элемента до корня иерархии
структура со ссылкой на предка и ее модификация с поддержкой информации об уровне элемента, структура с хранением границ ветви
Опять же, для вычисления полного пути нужно получать предков с помощью последовательных запросов. Одним простым запросом здесь не обойтись. Ниже приведен текст хранимой процедуры получения полного пути от произвольного элемента:
|
CREATE PROCEDURE GET_PARENTS (ID INTEGER) RETURNS (E_ID INTEGER, NAME CHAR(200)) AS declare 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; END END ^ |
структура с потабличным хранением уровней, структура с поразрядным ключом
Полный путь содержится в первичном ключе элемента.
Операции вставки, удаления, перемещения элемента и его потомков
структура со ссылкой на предка
Добавление нового элемента:
| insert into “CATALOG”(“name”,”parent_id”) values( _win1251 ‘Новый элемент’, <значение первичного ключа предка>); |
Удаление элемента: Кроме непосредственно самого элемента необходимо удалить и его потомков. Проблема решается введением триггера:
|
CREATE TRIGGER "CATALOG_AFTER_DEL" FOR "CATALOG" ACTIVE AFTER DELETE POSITION 0 AS BEGIN 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 0 AS 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)) then exception 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; end END ^ /* Триггер перед обновлением - контролирует правильность поля Level */ CREATE TRIGGER "CATALOG_BEFORE_UPD" FOR "CATALOG" ACTIVE BEFORE UPDATE POSITION 0 AS 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) then exception WRONG_LEVEL;
END ^ /* Триггер после обновления - контролирует правильность поля Level */ CREATE TRIGGER "CATALOG_AFTER_UPD" FOR "CATALOG" ACTIVE AFTER UPDATE POSITION 0 AS BEGIN update "CATALOG" set "LEVEL" = NEW."LEVEL"+1 where "PARENT_ID" = NEW."ID"; END ^ |
структура с потабличным хранением уровней
Запросы на вставку и перемещения тривиальны, и потому не приводятся. При удалении элемента можно ввести дополнительный триггер для удаления потомков, аналогично триггеру для структуры со ссылкой на предка.
структура с хранением границ ветви
Вставка и удаление аналогичны случаю структуры со ссылкой на предка. Перемещение элемента в общем случае невозможно без перегенерации первичных ключей элементов, поэтому применяется редко.
Заключение
Ну вот, пожалуй, и все. Надеюсь, что данная статья будет вам полезна. Если у вас появились замечания, предложения или Вы обнаружили какие-либо ошибки, пишите мне mgoblin@mail