Реферат: Иерархические структуры данных в реляционных БД
"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) запросов.
|
К-во Просмотров: 216
Бесплатно скачать Реферат: Иерархические структуры данных в реляционных БД
|