45807 (Иерархические структуры данных в реляционных БД), страница 2
Описание файла
Документ из архива "Иерархические структуры данных в реляционных БД", который расположен в категории "". Всё это находится в предмете "информатика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "45807"
Текст 2 страницы из документа "45807"
получения полного пути от элемента до корня иерархии;
операции вставки, удаления, перемещения элемента и его потомков для вышеперечисленных структур.
Получение непосредственных потомков
Получение потомков элемента является основной задачей при построении и отображении дерева. Далее мы рассмотрим получение потомков для:
структур со ссылкой на предка
К этому виду структур относится и модификация с поддержкой информации об уровне элемента, а также структура с хранением границ ветви. Очевидно, что в такой структуре потомками элемента будут все элементы, ссылающиеся на данный (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 = 1 union select "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)) 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.ru
Список литературы
Для подготовки данной работы были использованы материалы с сайта http://www.rsdn.ru/
