Деревоподібні структури в SQL, Мова запитів SQL, Бази даних, статті

sql.ru

За матеріалами статті Joe Celko на intelligententerprise.com ”
Trees in SQL"

Огляд деяких загальних питань, що стосуються деревовидних структур та ієрархії в SQL

Ця тема вже розглядалася мною раніше, але вона заслуговує повторення. У спеціалізованих конференціях я зустрічав дуже багато питань про деревовидних структурах та ієрархії в SQL. В літературі по SQL наводиться стандартна модель деревоподібної структури, яка називається список суміжних вершин графа і виглядає наступним чином:


CREATE TABLE Personnel
(emp CHAR(10) NOT NULL PRIMARY KEY,
boss CHAR(10) DEFAULT NULL REFERENCES Personnel(emp),
salary DECIMAL(6,2) NOT NULL DEFAULT 100.00);

Personnel
emp
boss salary
'Albert' 'NULL' 1,000.00
'Bert' 'Albert' 900.00
'Chuck' 'Albert' 900.00
'Donna' 'Chuck' 800.00
'Eddie' 'Chuck' 700.00
'Fred' 'Chuck' 600.00

Таблиця 1. Список суміжних вершин графа

Іншим способом представлення деревовидної структури є вкладені множини. Оскільки SQL є мовою, призначеним для роботи з множинами, то ця модель є більш кращою, ніж стандартний приклад списку суміжних вершин графа, який більш часто зустрічається в літературі. Давайте створимо тестову таблицю Personnel, не звертаючи поки уваги на поля lft і rgt:


CREATE TABLE Personnel
(emp CHAR(10) NOT NULL PRIMARY KEY,
lft INTEGER NOT NULL UNIQUE CHECK (lft > 0),
rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1),
CONSTRAINT order_okay CHECK (lft < rgt) );

Ця проблема часто описується в підручниках з допомогою поля для Співробітника (Personnel emp) і одного з його Начальників (Boss). Наступна таблиця (Таблиця 2) - за винятком полів lft і rgt - в теорії графів називається список суміжних вершин графа або пари вершин графа, суміжні один одному.

Personnel
emp
ift rgt
'Albert' 1 12
'Bert' 2 3
'Chuck' 4 11
'Donna' 5 6
'Eddie' 7 8
'Fred' 9 10

Таблиця 2. Вкладені безлічі

Структура організації може бути представлена ​​у вигляді спрямованого графа, як показано на рис.1


           Albert (1, 12)
                ¦
   -------------+---------------
   ¦                           ¦ 
   ¦                           ¦ 
Bert (2, 3)                Chuck (4, 11)
                               ¦ 
   ---------------------------------------------------------
   ¦                           ¦                           ¦ 
   ¦                           ¦                           ¦ 
Donna (5, 6)               Eddie (7, 8)                 Fred (9, 10)

Таблиця 1 є денормалізованной за кількома напрямками. Ми моделюємо структуру персоналу та організації в одній таблиці. Заради економії дискового простору уявімо собі, що ім'я співробітника є також назвою його посади і що ми маємо ще одну таблицю, яка містить інформацію про співробітників і займаних ними посадах.

Ще однією проблемою, пов'язаною з моделлю "Список суміжних вершин графа" є те, що поля Начальник (Boss) і Співробітник (Personnel emp) містять дані однакового виду (ім'я співробітника) і тому ці дані повинні розташовуватися в одному і тому ж полі нормалізованої таблиці. Для підтвердження того, що ці дані не нормалізовані, припустимо, що "Chuck" змінив своє ім'я на "Charles"; ви повинні змінити його ім'я в обох полях і в декількох місцях. За визначенням, в нормалізованої таблиці одна сутність повинна зустрічатися лише один раз і тільки в одному місці.

Останньою проблемою є те, що "Список суміжних вершин графа" не є підлеглою (Субординаційної) моделлю. Повноваження передаються зверху вниз в ієрархічному порядку, але якщо я приберу співробітника на ім'я "Chuck", я розірву всю його підпорядкованість від співробітника по імені "Albert". В деяких випадках (наприклад, для трубопроводів) це справедливо, але в нашому випадку ми не припускаємо такій ситуації.

Щоб зобразити деревоподібну структуру у вигляді вкладених множин, замінимо вершини графа овалами, де підлеглі овали вкладені один в іншій. Підстава дерева буде представлено самим великим овалом, який містить всі інші овали. Кінцеві вершини будуть представлені самими внутрішніми овалами, не містять всередині ніяких інших овалів, а вкладеність буде показана ієрархічними відносинами. Поля rgt і lft (я не використовую зарезервовані слова RIGHT і LEFT) - це саме те, що показує вкладеність.

Якщо ця образна модель не працює, то уявіть собі маленького хробака, що повзе вздовж дерева проти годинникової стрілки. Кожен раз, коли він досягає праву або ліву сторону вершини, він нумерує її. Черв'як зупиняється після того, коли він обійде навколо всього дерева і повернеться назад до основи.

Ця модель натуральним чином показує як збільшується кількість частин, тому що остання збірка складається з вкладених збірок, які, в кінцевому підсумку, складаються з окремих частин.

Тепер ми бачимо, що поле Начальник (Boss) є надлишковим і денормалізованним, отже воно може бути видалено. Зверніть також увагу на те, що деревоподібна структура може бути розміщена в одній таблиці, а вся інформація про вершини графа може бути поміщена в іншу таблицю. Ви можете пов'язати обидві таблиці між собою за номером співробітника.

Для перетворення графа в модель вкладених множин згадайте про маленького черв'ячка, повзе вздовж дерева. Черв'як починає рухатися зверху - від основи - і обползает навколо всього дерева. Коли він приходить до вершини, він привласнює значення стороні, яку він відвідує і збільшує значення лічильника на одиницю. Кожна вершина отримує два значення - одне для правого боку і одне для лівої. (Фахівці називають це модифікованим алгоритмом обходу вершин графа в прямому порядку.) І на закінчення, видалимо за непотрібністю поле "Personnel.Boss", яке представляло ребро графа.

Це дає нам деякі передбачувані результати, які ми можемо використовувати при побудові запитів. Підстава завжди можна представити у вигляді:
(left = 1, right = 2 * (SELECT COUNT(*) FROM TreeTable));
для вершин завжди справедливо (left + 1 = right); умова BETWEEN визначає піддерево і т.д. Нижче представлені деякі базові запити, які можуть бути вам корисні:

1. Знайти співробітника і всіх його начальників, незалежно від глибини вкладення.


 SELECT P2.*
   FROM Personnel AS P1, Personnel AS P2
  WHERE P1.lft BETWEEN P2.lft AND P2.rgt
    AND P1.emp = :myemployee;

2. Знайти співробітника і всіх його підлеглих. (Цей запит симетричний першому.)

 SELECT P1. * - (В оригіналі помилка: SELECT P2. *)
   FROM Personnel AS P1, Personnel AS P2
  WHERE P1.lft BETWEEN P2.lft AND P2.rgt
    AND P2.emp = :myemployee;
 

3. Додайте GROUP BY і узагальнені функції до цих базових запитам і ви отримаєте ієрархічні звіти. Наприклад, сумарний ліміт заробітної плати, якою розпоряджається кожен співробітник:


SELECT P2.emp, SUM(S1.salary)
   FROM Personnel AS P1, Personnel AS P2,
        Salaries AS S1
  WHERE P1.lft BETWEEN P2.lft AND P2.rgt
    AND P1.emp = S1.emp
  GROUP BY P2.emp;
 

4. Знайти рівень (глибину вкладення) кожної вершини, що дає можливість роздрукувати деревоподібну структуру як лістинг з відступами.


SELECT COUNT(P2.emp) AS indentation, P1.emp
   FROM Personnel AS P1, Personnel AS P2
  WHERE P1.lft BETWEEN P2.lft AND P2.rgt
  GROUP BY P1.emp ORDER BY P1.emp; - (В оригіналі помилка: ORDER BY P1.lft)
 

5. Модель вкладених множин містить неявний порядок суміжних вершин, якого немає в моделі "Список суміжних вершин графа". Додавання нової вершини як суміжної крайній правій:


BEGIN
DECLARE right_most_sibling INTEGER;
SET right_most_sibling
    = (SELECT rgt
         FROM Personnel
        WHERE emp = :your_boss);
UPDATE Personnel
   SET lft = CASE WHEN lft > right_most_sibling
                  THEN lft + 2
                  ELSE lft END,
       rgt = CASE WHEN rgt >= right_most_sibling
                  THEN rgt + 2
                  ELSE rgt END
 WHERE rgt >= right_most_sibling;
INSERT INTO Personnel (emp, lft, rgt)
VALUES ('New Guy', right_most_sibling,
                  (right_most_sibling + 1))
END;
 

6. Для перетворення моделі "Список суміжних вершин графа" в модель вкладених множин можна використовувати a push down stack алгоритм. Припустимо, що ми маємо наступну таблицю:

 - Деревовидна структура містить модель "Список суміжних вершин графа"
CREATE TABLE Tree
(emp CHAR(10) NOT NULL,
 boss CHAR(10));
INSERT INTO Tree
SELECT emp, boss FROM Personnel;
-- Stack starts empty, will holds the nested set model - Спочатку стек порожній, він буде містити модель вкладених множин
CREATE TABLE Stack
(stack_top INTEGER NOT NULL,
 emp CHAR(10) NOT NULL,
 lft INTEGER,
 rgt INTEGER);
BEGIN ATOMIC
DECLARE counter INTEGER;
DECLARE max_counter INTEGER;
DECLARE current_top INTEGER;
SET counter = 2;
SET max_counter = 2 * (SELECT COUNT(*) FROM Tree);
SET current_top = 1;
INSERT INTO Stack
SELECT 1, emp, 1, NULL
  FROM Tree
 WHERE boss IS NULL;
DELETE FROM Tree
 WHERE boss IS NULL;
WHILE counter <= (max_counter - 2)
LOOP IF EXISTS (SELECT *
                   FROM Stack AS S1, Tree AS T1
                  WHERE S1.emp = T1.boss
                    AND S1.stack_top = current_top)
     THEN
     BEGIN -- push when top has subordinates, set lft value - Вершина має підлеглі вершини,  заносимо нове значення lft в стек
       INSERT INTO Stack
       SELECT (current_top + 1), MIN(T1.emp), counter, NULL
         FROM Stack AS S1, Tree AS T1
        WHERE S1.emp = T1.boss
          AND S1.stack_top = current_top;
        DELETE FROM Tree
         WHERE emp = (SELECT emp
                        FROM Stack
                       WHERE stack_top = current_top + 1);
        SET counter = counter + 1;
        SET current_top = current_top + 1;
     END
     ELSE
     BEGIN  -- pop the stack and set rgt value - Виштовхуємо значення з стека і визначаємо значення rgt
       UPDATE Stack
          SET rgt = counter,
              stack_top = -stack_top -- pops the stack
        WHERE stack_top = current_top
       SET counter = counter + 1;
       SET current_top = current_top - 1;
     END IF;
 END LOOP;
END;
 

Незважаючи на те, що ця процедура працює, ви можете переписати її на мові, що дозволяє працювати з масивами, замість того, щоб дотримуватися чистого SQL.

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*