Рефераты | Рефераты по информатике, программированию | Иерархические структуры данных в реляционных БД
Иерархические структуры данных в реляционных БДКатегория реферата: Рефераты по информатике, программированию Теги реферата: реферат трудовой, древния греция реферат Добавил(а) на сайт: Кудяев. Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 | Следующая страница реферата 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 для хранения начала и конца диапазона первичных ключей всех потомков данного элемента. Такая иерархия может быть представлена набором отрезков (см. рисунок). Это позволяет быстро и легко выбрать всех потомков данного элемента. Данную структуру назовем структурой с хранением границ ветви.
Итак, мы рассмотрели несколько различных типов структур для хранения иерархий. Далее мы рассмотрим решение задач, связанных с использованием этих структур:
получения потомков элемента;
получения уровня вложенности элемента;