MyTetra Share
Делитесь знаниями!
Работа с деревьями
Время создания: 08.09.2017 17:34
Раздел: PL/SQL - Patterns - Деревья
Запись: xintrea/mytetra_db_mcold/master/base/1504881250qjm3b9fcnt/text.html на raw.githubusercontent.com

Работа с деревьями в 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);

 
MyTetra Share v.0.59
Яндекс индекс цитирования