Работа с деревьями в Oracle

Источник: all-oracle

Рекомендовано для:

Oracle Database 8i
Oracle Database 9i R1
Oracle Database 9i R2
Oracle Database 10g R1
Oracle Database 10g R2
Oracle Database 11g R1

Эта статья посвящена работе с деревьями в Oracle. В большинстве современных СУБД нет встроенных средств для работы с иерархическими структурами, для построения дерева на основе таблицы приходится писать громоздкие процедуры, или разносить данные по нескольким таблицам.

Oracle предлагает достаточно средств, для удовлетворения практически любых желаний при работе с иерархиями. В это статье я попытаюсь на примерах показать, как это применять, и какие результаты достигаются.

Классическим примером дерева является иерархия сотрудников на предприятии. Для демонстрации работы с деревьями создадим таблицу и заполним ее данными:

CREATE TABLE EMPL (
       ID         INTEGER PRIMARY KEY,
       NAME    VARCHAR(50),
       PARENT_ID REFERENCES EMPL
);

Добавим данные в таблицу:

INSERT INTO EMPL VALUES (1, 'Директор', NULL);
INSERT INTO EMPL VALUES (2, 'Заместитель по экономике', 1);
INSERT INTO EMPL VALUES (3, 'Заместитель по ИТ', 1);
INSERT INTO EMPL VALUES (4, 'Программист', 3);
INSERT INTO EMPL VALUES (5, 'Программист-стажер', 4);
INSERT INTO EMPL VALUES (6, 'Главный бухгалтер', 1);
INSERT INTO EMPL VALUES (7, 'Бухгалтер 1', 6);
INSERT INTO EMPL VALUES (8, 'Бухгалтер 2', 6);

Проверяем:

SQL> SELECT * FROM EMPL;
        ID NAME                                                PARENT_ID
---------- -------------------------------------------------- ----------
         1 Директор
         2 Заместитель по экономике                                    1
         3 Заместитель по ИТ                                           1
         4 Программист                                                 3
         5 Программист-стажер                                          4
         6 Главный бухгалтер                                           1
         7 Бухгалтер 1                                                 6
         8 Бухгалтер 2                                                 6
8 rows selected.

Значения столбца PARENT_ID, реально указывают на другие строки в таблице EMPL. Для отображения получившийся иерархии имея в распоряжении стандартный SQL и любой язык программирования, такой как C++, Delphi или C# придется написать достаточно громоздкий код. Отобрать сначала узлы верхнего уровня, далее в зависимости от выбранного узла запрашивать подчиненные записи и т.д.

В распоряжение пользователя, Oracle предоставляет предложение языка PL/SQL - CONNECT BY. Оно позволяет строить иерархию одним запросом, просто и изящно:

SELECT NAME, ID, PARENT_ID
FROM EMPL
CONNECT BY PRIOR ID = PARENT_ID;
NAME                                                       ID  PARENT_ID
-------------------------------------------------- ---------- ----------
Заместитель по экономике                                    2          1
Заместитель по ИТ                                           3          1
Программист                                                 4          3
Программист-стажер                                          5          4
Главный бухгалтер                                           6          1
Бухгалтер 1                                                 7          6
Бухгалтер 2                                                 8          6
Программист                                                 4          3
Программист-стажер                                          5          4
Программист-стажер                                          5          4
Бухгалтер 1                                                 7          6
Бухгалтер 2                                                 8          6
Директор                                                    1
Заместитель по экономике                                    2          1
Заместитель по ИТ                                           3          1
Программист                                                 4          3
Программист-стажер                                          5          4
Главный бухгалтер                                           6          1
Бухгалтер 1                                                 7          6
Бухгалтер 2                                                 8          6
20 rows selected.

Полученный результат кажется не совсем понятным, но если внимательно посмотреть, то видно, что выстроены все возможные деревья и поддеревья. Теперь добавим в запрос конструкцию START WITH:

SELECT NAME, ID, PARENT_ID
FROM EMPL
CONNECT BY PRIOR ID = PARENT_ID
START WITH ID IN (SELECT ID 
                  FROM EMPL 
                  WHERE PARENT_ID IS NULL);
NAME                                                       ID  PARENT_ID
-------------------------------------------------- ---------- ----------
Директор                                                    1
Заместитель по экономике                                    2          1
Заместитель по ИТ                                           3          1
Программист                                                 4          3
Программист-стажер                                          5          4
Главный бухгалтер                                           6          1
Бухгалтер 1                                                 7          6
Бухгалтер 2                                                 8          6
8 rows selected.

Обратите внимание, что в предложении START WITH использован вложенный запрос для определения кто стоит на самом верху. Обычно, в поле PARENT_ID для узлов, используют NULL или -1. Естественно, что их может быть один и более. Сама конструкция START WIDTH указывает, откуда начинать строить дерево.

Теперь, наведем немного порядок, упорядочим записи, и покажем кто находится на каком уровне иерархии. Для этого, Oracle предоставляет псевдоколонку LEVEL. Она может быть использована только в том случае, если в запросе присутствует CONNECT BY. Для упрощения укажем ID =1:

SELECT NAME, ID, PARENT_ID, LEVEL
FROM EMPL
CONNECT BY PRIOR ID = PARENT_ID
START WITH ID = 1;
NAME                                             ID  PARENT_ID      LEVEL
---------------------------------------- ---------- ---------- ----------
Директор                                          1                     1
Заместитель по экономике                          2          1          2
Заместитель по ИТ                                 3          1          2
Программист                                       4          3          3
Программист-стажер                                5          4          4
Главный бухгалтер                                 6          1          2
Бухгалтер 1                                       7          6          3
Бухгалтер 2                                       8          6          3
8 rows selected.

Колонка LEVEL может быть использована для отметки записи. Используем оператор конкатенации (//)для добавления пробелов в начале каждой строки:

SELECT 
  LPAD(' ', (LEVEL - 1) * 2) // NAME AS H_NAME, 
  ID, 
  PARENT_ID, 
  LEVEL
FROM EMPL
CONNECT BY PRIOR ID = PARENT_ID
START WITH ID = 1;
H_NAME                                      ID  PARENT_ID      LEVEL
----------------------------------- ---------- ---------- ----------
Директор                                     1                     1
  Заместитель по экономике                   2          1          2
  Заместитель по ИТ                          3          1          2
    Программист                              4          3          3
      Программист-стажер                     5          4          4
  Главный бухгалтер                          6          1          2
    Бухгалтер 1                              7          6          3
    Бухгалтер 2                              8          6          3
8 rows selected.

Для ограничения вывода можно использовать стандартное условие WHERE. Уберем из вывода сотрудников, у которых уровень меньше, либо равен 3:

SELECT 
  LPAD(' ', (LEVEL - 1) * 2) // NAME AS H_NAME, 
  ID, 
  PARENT_ID, 
  LEVEL
FROM EMPL
WHERE LEVEL <=3
CONNECT BY PRIOR ID = PARENT_ID
START WITH ID = 1;
H_NAME                                      ID  PARENT_ID      LEVEL
----------------------------------- ---------- ---------- ----------
Директор                                     1                     1
  Заместитель по экономике                   2          1          2
  Заместитель по ИТ                          3          1          2
    Программист                              4          3          3
  Главный бухгалтер                          6          1          2
    Бухгалтер 1                              7          6          3
    Бухгалтер 2                              8          6          3
7 rows selected.

Если вы хотите произвести сортировку, то стоит учитывать, ORDER BY работает не совсем так, как в случае с простыми данными, без иерархии. Продемонстрируем это:

SELECT 
  LPAD(' ', (LEVEL - 1) * 2) // NAME AS H_NAME, 
  ID, 
  PARENT_ID, 
  LEVEL
FROM EMPL
CONNECT BY PRIOR ID = PARENT_ID
START WITH ID = 1
ORDER BY LEVEL, NAME;
H_NAME                                      ID  PARENT_ID      LEVEL
----------------------------------- ---------- ---------- ----------
Директор                                     1                     1
  Главный бухгалтер                          6          1          2
  Заместитель по ИТ                          3          1          2
  Заместитель по экономике                   2          1          2
    Бухгалтер 1                              7          6          3
    Бухгалтер 2                              8          6          3
    Программист                              4          3          3
      Программист-стажер                     5          4          4
8 rows selected.

Как видно, сортировка прошла по колонке LEVEL, и затем уже по имени, но замете, что самое важное, иерархия сохранена, и внутри каждого уровня иерархии уже идет сортировка по имени. А что же будет, если из условия сортировки убрать поле LEVEL?

SELECT 
  LPAD(' ', (LEVEL - 1) * 2) // NAME AS H_NAME, 
  ID, 
  PARENT_ID, 
  LEVEL
FROM EMPL
CONNECT BY PRIOR ID = PARENT_ID
START WITH ID = 1
ORDER BY NAME;
H_NAME                                      ID  PARENT_ID      LEVEL
----------------------------------- ---------- ---------- ----------
    Бухгалтер 1                              7          6          3
    Бухгалтер 2                              8          6          3
  Главный бухгалтер                          6          1          2
Директор                                     1                     1
  Заместитель по ИТ                          3          1          2
  Заместитель по экономике                   2          1          2
    Программист                              4          3          3
      Программист-стажер                     5          4          4
8 rows selected.

Как видно вся иерархия поломалась. Чтобы указать Oracle, что сортировать надо только в пределах одного уровня иерархии, поможет маленькая добавка в виде оператора SIBLINGS. Достаточно изменить условие сортировки на ORDER SIBLINGS BY <поле> - и все встанет на свои места.

SELECT 
  LPAD(' ', (LEVEL - 1) * 2) // NAME AS H_NAME, 
  ID, 
  PARENT_ID, 
  LEVEL
FROM EMPL
CONNECT BY PRIOR ID = PARENT_ID
START WITH ID = 1
ORDER SIBLINGS BY NAME;
H_NAME                                      ID  PARENT_ID      LEVEL
----------------------------------- ---------- ---------- ----------
Директор                                     1                     1
  Главный бухгалтер                          6          1          2
    Бухгалтер 1                              7          6          3
    Бухгалтер 2                              8          6          3
  Заместитель по ИТ                          3          1          2
    Программист                              4          3          3
      Программист-стажер                     5          4          4
  Заместитель по экономике                   2          1          2
8 rows selected.

Еще одна очень полезная функция - SYS_CONNECT_BY_PATH().Она принимает два параметра через запятую: название колонки и строку с символом-разделителем. Для иллюстрации ее работы выполним такой запрос:

SELECT SYS_CONNECT_BY_PATH(NAME, '/') AS PATH
FROM EMPL
WHERE ID=5
START WITH PARENT_ID IS NULL
CONNECT BY PRIOR ID = PARENT_ID;
PATH
-------------------------------------------------
/Директор/Заместитель по ИТ/Программист/Программист-стажер

В результате получаем путь от большого босса до стажера. Сейчас это выглядит как путь в файловом менеджере, но эта функция может быть вам очень полезна, к тому же разделитель можно сменить.

Топаем дальше. Псевдоколонка CONNECT_BY_ISLEAF. Ее можно использовать так же, как LEVEL. В этой колонке напротив каждой строки проставляется 0 или 1. Если есть потомки - то 0. Если потомков нет, такой узел в дереве называется "листом", тогда и значение в поле CONNECT_BY_ISLEAF будет равно 1.

Помните такую конструкцию PRIOR, которая позволяла ссылаться на родительскую запись? Так вот, есть такой оператор, CONNECT_BY_ROOT, который ссылается на корень дерева. Для демонстрации работы выполним:

SELECT ID, NAME, PARENT_ID, LEVEL, 
    CONNECT_BY_ISLEAF AS ISLEAF, 
    PRIOR NAME AS PARENT, 
    CONNECT_BY_ROOT NAME AS ROOT
FROM EMPL
START WITH PARENT_ID IS NULL
CONNECT BY PRIOR ID = PARENT_ID
ORDER SIBLINGS BY NAME;

Если при построении дерева вы получаете ошибку, о том, что найдена петля (цикл), то это означает - дерево неверно спроектировано. На такой случай, есть NOCYCLE. Это позволит вам избежать бесконечных циклов. Для иллюстрации работы, выполним:

UPDATE EMPL SET PARENT_ID=5 WHERE ID=5;
COMMIT;

Теперь, программист-стажер подчиняется сам себе. Выполняем:

SELECT 
  LPAD(' ', (LEVEL - 1) * 2) // NAME AS H_NAME, 
  ID, 
  PARENT_ID, 
  LEVEL
FROM EMPL
CONNECT BY PRIOR ID = PARENT_ID
START WITH ID = 1
ORDER BY LEVEL, NAME;

H_NAME                                 ID  PARENT_ID      LEVEL
------------------------------ ---------- ---------- ----------
Директор                                1                     1
  Главный бухгалтер                     6          1          2
  Заместитель по ИТ                     3          1          2
  Заместитель по экономике              2          1          2
    Бухгалтер 1                         7          6          3
    Бухгалтер 2                         8          6          3
    Программист                         4          3          3
7 rows selected.

И видим, что стажера нет, он выпал из дерева. Oracle не видит пути, и не включает элемент в иерархию. Попробуем заставить его начать со стажера. Для этого немного поменяем условия запроса:

SELECT 
  LPAD(' ', (LEVEL - 1) * 2) // NAME AS H_NAME, 
  ID, 
  PARENT_ID, 
  LEVEL
FROM EMPL
CONNECT BY PRIOR ID = PARENT_ID
START WITH ID = 5
ORDER BY LEVEL, NAME;
FROM EMPL
     *
error at line 6:
ORA-01436: CONNECT BY loop in user data

Что бы избежать таких неприятных ситуаций, изменим запрос, что бы он выглядел так:

SELECT 
  LPAD(' ', (LEVEL - 1) * 2) // NAME AS H_NAME, 
  ID, 
  PARENT_ID, 
  LEVEL
FROM EMPL
CONNECT BY NOCYCLE PRIOR ID = PARENT_ID
START WITH ID = 5
ORDER BY LEVEL, NAME;

H_NAME                                 ID  PARENT_ID      LEVEL
------------------------------ ---------- ---------- ----------
Программист-стажер

JOIN не работает с CONNECT BY

Например, построим отчет в котором укажем сотрудника и его непосредственного начальника:

SELECT 
  LPAD(' ', (LEVEL - 1) * 2) // A.NAME AS Н_NAME, 
  B.NAME AS BOSS_NAME 
FROM EMPL A, EMPL B
WHERE A.PARENT_ID = B.ID(+)
CONNECT BY PRIOR A.ID = A.PARENT_ID
START WITH A.ID = 1;

На старых версиях Oracle, можно получить сообщение об ошибке:

ERROR at line 4:
ORA-01437: cannot have join with CONNECT BY

Обойти эту проблему можно создав представление:

CREATE OR REPLACE VIEW V_EMPL 
AS
SELECT 
  LPAD(' ', (LEVEL - 1) * 2) // NAME AS H_NAME, 
  ID, 
  PARENT_ID, 
  LEVEL AS THE_LEVEL
FROM EMPL
CONNECT BY PRIOR ID = PARENT_ID
START WITH ID = 1;

Колонку LEVEL переименовали, чтобы представление не заканчивалось на зарезервированное слово.

SQL> SELECT * FROM V_EMPL;

Сейчас можно выполнить JOIN

SELECT 
   A.H_NAME,
   B.NAME AS BOSS_NAME
FROM V_EMPL A, EMPL B
WHERE A.PARENT_ID = A.ID(+);

Если обратите внимание, то увидите что выполнено OUTER JOIN, потому что в списке нет большого босса.

Подзапросы, списки и CONNECT BY

Вместо VIEW и JOIN можно использовать вложенные запросы в списке выборки:

SELECT 
  LPAD(' ', (LEVEL - 1) * 2) // NAME AS H_NAME, 
  (SELECT NAME 
   FROM EMPL B
   WHERE B. ID = A.PARENT_ID) AS BOSS_NAME
FROM EMPL A
CONNECT BY PRIOR ID = PARENT_ID
START WITH ID = 1;
H_NAME                              BOSS_NAME
----------------------------------- -----------------------------------
Директор
  Заместитель по экономике          Директор
  Заместитель по ИТ                 Директор
    Программист                     Заместитель по ИТ
      Программист-стажер            Программист
  Главный бухгалтер                 Директор
    Бухгалтер 1                     Главный бухгалтер
    Бухгалтер 2                     Главный бухгалтер
8 rows selected.

Производительность

Для увеличения производительности, вам потребуется создать индексы на таблицу, которые позволят Oracle быстрее получать ответ на вопрос, "кто является детьми некого родителя Х?":

CREATE INDEX EMPL_IDX1 ON EMPL (ID, PARENT_ID);
CREATE INDEX EMPL_IDX2 ON EMPL (PARENT_ID, ID);