Ієрархічні структури даних у реляційних БД
Михайло Голованов
Вступ
Архітектура реляційних баз даних орієнтована на
зберігання всередині таблиць БД інформації про сутності інформаційної системи і
зв'язках між ними. Кожна із записів таблиці містить інформацію про один
екземплярі. Організація зберігання інформації про незалежні один від одного
примірниках сутностей (тобто так званих «плоских» даних) не викликає
жодних труднощів. Однак, поряд з «плоскими» даними, при побудові навіть
простих інформаційних систем, доводиться зберігати в БД та інформацію про
«Вкладених» одна в одну сутності, тобто ієрархічні дані. Організація
зберігання такої інформації у реляційних БД проста, але не завжди очевидна для
тих, хто вперше стикається з подібним завданням. У даній статті я спробую
поділитися накопиченим досвідом.
Приклади, що наводяться далі, були створені та
протестовані за допомогою Interbase 6.
Ієрархії даних
Щоб обговорити проблему збереження ієрархії в
реляційної БД, ми спочатку розглянемо питання про те, які ж ієрархії даних
можуть зустрітися на практиці. У реальному житті ієрархії мають, як правило,
деякі обмеження. З огляду на ці обмеження, можна побудувати більш ефективні
процедури обробки ієрархічних даних.
Так, у загальному випадку, дерево може мати будь-яке
кількість рівнів ієрархії. Але в окремих випадках число рівнів може, і часто
виявляється, кінцевим. Може бути обмежена кількість безпосередніх
нащадків одного елемента ієрархії.
Розглянемо деякі варіанти представлення
ієрархічних структур в реляційних БД.
Можливі варіанти структур БД для зберігання ієрархій
Найбільш загальним випадком є дерево з
необмеженим рівнем вкладеності і необмеженою кількістю нащадків. Для
зберігання такого роду ієрархії необхідно додати опис суті
додаткове поле - посилання на первинний ключ предка. Такий спосіб організації
ієрархії є найпоширенішим і універсальним. Проте йому властиві
наступні недоліки:
Необхідність рекурсивних запитів для отримання
повного шляху від довільного елемента до кореня дерева.
Складність обчислення рівня вкладеності довільного
елементу.
Складність отримання всіх (у тому числі і не прямих)
нащадків даного сайту.
Подальший розгляд ми будемо вести на прикладі
побудови ієрархічної структури - тематичного каталогу бібліотеки. Даний
каталог застосовується для класифікації, сортування і пошуку книг з їх
змістом. Будемо вважати, що кожен елемент каталозі описується власним
неунікальним символьним ім'ям. Для забезпечення унікальності записів для
кожного елемента каталогу потрібно ввести первинний ключ. Для підтримки
ієрархічності даних введемо додаткове поле-посилання на предка цього елемента
ієрархії. Нижче наведено опис отриманої структури на мові SQL:
CREATE TABLE "CATALOG" (
"ID" INTEGER NOT NULL
PRIMARY KEY,
"NAME" VARCHAR (200)
CHARACTER SET WIN1251 NOT NULL,
"PARENT_ID" INTEGER
);
Дана структура є мінімально необхідною і
достатньою для організації та зберігання ієрархії. Назвемо її структурою з
посиланням на предка. У даній структурі присутній як мінімум один недолік
- Відсутність контролю правильності посилання на батька. Які ж значення поля
PARENT_ID є правильними? Відповідь очевидна - весь діапазон значень
первинного ключа (поля ID) + одне значення, яке використовується для позначення
відсутність батьківського елементу. Це значення необхідно для введення та
зберігання кореневих елементів ієрархії. Найчастіше в якості значення,
позначає відсутність батька, використовується NULL, хоча немає ніяких
фізичних обмежень для використання інших значень. Так, наприклад, якщо
ви впевнені, що значення первинного ключа будуть більше 0, як ознака
кореневого елемента можна використовувати значення (-1) або інші негативні
значення в полі PARENT_ID. Я не буду оригінальний і як значення PARENT_ID
для кореневих елементів використовую NULL. Тоді для контролю правильності
PARENT_ID можна використовувати наступне обмеження:
"PARENT_ID" INTEGER
CHECK (
( "PARENT_ID" IS
NULL)
OR
( "PARENT_ID" =
ANY (SELECT "ID" FROM "CATALOG"))
)
(в принципі, такі
обмеження набагато простіше й ефективніше
описувати як зовнішні
ключі. Єдиною проблемою при цьому
є вставка кореневої
запису, тому що батьківського запису
для неї не існує.
Обійти таке обмеження можна, додаючи
зовнішній ключ після вставки
кореневої запису. - Прим.ред.)
Повернемося до зазначених вище недоліків даної
структури (складність формування повного шляху і обчислення рівня елементу).
Ці недоліки випливають з того простого факту, що в даній структурі
інформація про повне шляхи та рівні ніде не зберігається. Вирішити проблему швидкого
отримання рівня вкладеності можна введенням в структуру таблиці
додаткового поля Level. Опис таблиці тоді буде виглядати так:
CREATE TABLE "CATALOG" (
"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
),
"LEVEL" INTEGER
DEFAULT 1 NOT NULL
);
Структура для зберігання ієрархії з необмеженим
кількістю рівнів вкладеності і нащадків готова.
Наступною за ступенем універсальності є ієрархія
з необмеженою кількістю рівнів вкладеності і кінцевим числом нащадків елемента
ієрархії. Обмеження кількості нащадків дозволяє зберігати дані в наступному
вигляді.
Посилання на предка
Інформація про перший елемент рівня ієрархії
Інформація про другому елементі рівня ієрархії
...
Інформація про n-ному елементі рівня ієрархії, де n --
кількість максимальну кількість нащадків
Посилання на предка містить в собі посилання на запис,
зберігає інформацію про попередньому рівні ієрархії і зсув (номер стовпчика) з
описом батька.
У нашому прикладі ми обмежимо кількість предків числом
5, тоді SQL-опис таблиці буде виглядати наступним чином:
CREATE TABLE "CATALOG2" (
"LEVEL" INTEGER NOT
NULL,
"OFFSET" SMALLINT NOT
NULL CHECK ( "OFFSET"> 0 and "OFFSET" <6),
"NAME_1" VARCHAR (200)
CHARACTER SET WIN1251,
"NAME_2" VARCHAR (200)
CHARACTER SET WIN1251,
"NAME_3" VARCHAR (200)
CHARACTER SET WIN1251,
"NAME_4" VARCHAR (200)
CHARACTER SET WIN1251,
"NAME_5" VARCHAR (200)
CHARACTER SET WIN1251,
"PARENT_LEVEL"
INTEGER,
"PARENT_OFFSET"
SMALLINT CHECK (( "PARENT_OFFSET"> 0 and
"PARENT_OFFSET" <6) or ( "PARENT_OFFSET" is NULL )),
CONSTRAINT
"PK_CATALOG2" PRIMARY KEY ( "LEVEL", "OFFSET")
);
Великих переваг використання такої структури я не
бачу, недолік ж у наявності - при зміні максимальної кількості нащадків
одного вузла доведеться додавати ще один стовпчик таблиці, що вкрай незручно.
З цієї причини детально розглядати цю структуру ми не будемо, а перейдемо до
наступного випадку - ієрархії з кінцевим числом рівнів вкладеності і
нескінченним числом нащадків вузла.
Одним з варіантів зберігання таких ієрархій є
поуровневое зберігання в різних таблицях. Наприклад, таблиця CATALOG_LEVEL_1
зберігає всі елементи першого рівня вкладеності, таблиця CATALOG_LEVEL_2 --
другий, і т.д. Нижче наведено опис такої структури для випадку
трирівневої ієрархії.
CREATE TABLE "CATALOG3_LEVEL1" (
"ID" INTEGER NOT NULL
PRIMARY KEY,
"NAME" VARCHAR (200)
CHARACTER SET WIN1251 NOT NULL
);
CREATE TABLE "CATALOG3_LEVEL2" (
"ID" INTEGER NOT NULL
UNIQUE,
"NAME" VARCHAR (200)
CHARACTER SET WIN1251 NOT NULL,
"PARENT_ID" INTEGER
NOT NULL REFERENCES "CATALOG3_LEVEL1" ( "ID "),
PRIMARY
KEY ( "ID", "PARENT_ID")
);
CREATE TABLE "CATALOG3_LEVEL3" (
"ID" INTEGER NOT NULL
UNIQUE,
"NAME" VARCHAR (200)
CHARACTER SET WIN1251 NOT NULL,
"PARENT_ID" INTEGER
NOT NULL REFERENCES "CATALOG3_LEVEL1" ( "ID "),
"PARENT_ID2" INTEGER
NOT NULL REFERENCES "CATALOG3_LEVEL2" ( "ID "),
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 для зберігання початку і кінця діапазону
первинних ключів всіх нащадків цього елемента. Така ієрархія може бути
представлена набором відрізків (див. малюнок). Це дозволяє швидко і легко
вибрати всіх нащадків цього елемента. Дану структуру назвемо структурою з
зберіганням кордонів гілки.
Отже, ми розглянули кілька різних типів
структур для зберігання ієрархій. Далі ми розглянемо вирішення завдань, пов'язаних з
використанням цих структур:
отримання нащадків елемента;
отримання рівня вкладеності елемента;
отримання повного шляху від елемента до кореня ієрархії;
операції вставки, видалення, переміщення елемента і його
нащадків для перелічених вище структур.
Отримання безпосередніх нащадків
Отримання нащадків елемента є основним завданням
при побудові та відображенні дерева. Далі ми розглянемо отримання нащадків
для:
структур з посиланням на предка
До цього виду структур відноситься і модифікація з
підтримкою інформації про рівень елементу, а також структура зі зберіганням кордонів
гілки. Очевидно, що в такій структурі нащадками елемента будуть всі елементи,
що посилаються на даний (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 ^
структура з потаблічним зберіганням рівнів
Запити на вставку і переміщення тривіальні, і тому
не наводяться. Під час видалення елемента можна ввести додатковий тригер для
видалення нащадків, аналогічно тригери для структури з посиланням на предка.
структура з зберіганням кордонів гілки
Вставка та видалення аналогічні нагоди структури з
посиланням на предка. Переміщення елемента в загальному випадку неможливо без
перегенерації первинних ключів елементів, тому застосовується рідко.
Висновок
Ну ось, мабуть, і все. Сподіваюся, що ця стаття
буде вам корисна. Якщо у вас з'явилися зауваження, пропозиції або Ви
виявили будь-які помилки, пишіть мені [email protected]
Список літератури
Для підготовки даної роботи були використані
матеріали з сайту http://www.rsdn.ru/
