Древовидные структуры данных. Рекурсивные запросы
Достаточно часто приходится иметь дело с древовидными структурами данных. Классическим примером является структура подразделений организации, где один отдел является частью другого, и при этом также состоит из нескольких подразделений. Также можно в виде дерева описать отношения между сотрудниками - кто кому приходится начальником; некий список документов, где один документ появляется на основании другого, а тот в свою очередь был создан на основании третьего, и т.п.
Реализация древовидных структур в РСУБД
Для того, чтобы можно было листья дерева собрать воедино, нужно знать, как они соотносятся друг с другом. Как правило, все данные, которые нужно хранить в виде дерева, хранятся в одной таблице. Для того, чтобы по определенной строке определить ее родителя, в таблицу добавляется колонка, которая ссылается на родителя в этой же таблице. У корневого узла в дереве колонка с id родительского узла остается пустой:
Для разбора создадим таблицу, которая будет содержать список подразделений.
create table departments(
id number primary key,
dept_name varchar2(100),
parent_id number,
constraint departments_parent_id_fk foreign key(parent_id)
references departments(id));
comment on table departments is 'Подразделения';
comment on column departments.parent_id is
'Ссылка на родительский узел';
insert into departments values(1, 'ЗАО ИнвестКорп', null);
insert into departments values(2, 'Бухгалтерия', 1);
insert into departments values(3, 'Отдел продаж', 1);
insert into departments values(4, 'IT-отдел', 1);
insert into departments values(5, 'Дирекция', 1);
insert into departments values(6, 'Бухгалтерия по участку 1', 2);
insert into departments values(7, 'Бухгалтерия по участку 2', 2);
insert into departments values(8, 'Отдел QA', 4);
insert into departments values(9, 'Отдел разработки', 4);Connect by
Oracle имеет свой собственный синтаксис для написания рекурсивных запросов. Сначала пример:
select d.*
from departments d
start with d.id = 1
connect by prior id = d.parent_id| ID | DEPT_NAME | PARENT_ID |
|---|---|---|
| 1 | ЗАО ИнвестКорп | - |
| 2 | Бухгалтерия | 1 |
| 6 | Бухгалтерия по участку 1 | 2 |
| 7 | Бухгалтерия по участку 2 | 2 |
| 3 | Отдел продаж | 1 |
| 4 | IT-отдел | 1 |
| 8 | Отдел QA | 4 |
| 9 | Отдел разработки | 4 |
| 5 | Дирекция | 1 |
Данный запрос проходит по дереву вниз начиная с узла, имеющего id = 1.
connect by задает правило, по которому дерево будет обходиться. В данном примере мы указываем, что у строк, которые должны будут выбираться на следующем шаге, значение столбца parent_id должно быть таким же, как значение столбца id на текущем.
В конструкции start with не обязательно указывать некие значения для id строк. Там можно указывать любое выражение. Те строки, для которых оно будет истинным, и будут являть собой стартовые узлы в выборке.
Псевдостолбец level
При использовании рекурсивных запросов, написанных с использованием connect by, становится доступен такой псевдостолбец, как level. Этот псевдостолбец возвращает 1 для корневых узлов в дереве, 2 для их дочерних узлов и т.д.
select dp.*, level
from departments dp
start with dp.parent_id is null
connect by prior id = dp.parent_id| ID | DEPT_NAME | PARENT_ID | LEVEL |
|---|---|---|---|
| 1 | ЗАО ИнвестКорп | - | 1 |
| 2 | Бухгалтерия | 1 | 2 |
| 6 | Бухгалтерия по участку 1 | 2 | 3 |
| 7 | Бухгалтерия по участку 2 | 2 | 3 |
| 3 | Отдел продаж | 1 | 2 |
| 4 | IT-отдел | 1 | 2 |
| 8 | Отдел QA | 4 | 3 |
| 9 | Отдел разработки | 4 | 3 |
| 5 | Дирекция | 1 | 2 |
В приведенном выше примере мы начинаем строить наше дерево с корневых узлов, не зная их конкретных id. Но мы знаем, что у корневых узлов нет родителей, что и указали в конструкции start with - parent_id is null. В этом случае корневые узлы дерева, которое вернет запрос, будут совпадать с корневыми узлами дерева, которое хранится в БД.
Можно, например, используя level, вывести дерево в более красивом виде:
select lpad(dp.dept_name, length(dp.dept_name) + (level * 4) - 4, ' ') dept_name, level
from departments dp
start with dp.parent_id is null
connect by prior id = dp.parent_id| DEPT_NAME | LEVEL |
|---|---|
| ЗАО ИнвестКорп | 1 |
| Бухгалтерия | 2 |
| Бухгалтерия по участку 1 | 3 |
| Бухгалтерия по участку 2 | 3 |
| Отдел продаж | 2 |
| IT-отдел | 2 |
| Отдел QA | 3 |
| Отдел разработки | 3 |
| Дирекция | 2 |
Здесь используется функция lpad, которая дополняет передаваемую строку(наименование подразделения) до определенной длины(длина наименования + уровень вложенности * 4) пробелами слева. Кстати, функция rpad работает так же, только дополняет символы справа.
Псевдостолбец CONNECT_BY_ISLEAF
Данный псевдостолбец вернет 1 в том случае, когда у узла в дереве больше нет потомков, и 0 в противном случае.
select dp.dept_name, CONNECT_BY_ISLEAF
from departments dp
start with dp.parent_id is null
connect by prior id = dp.parent_id| DEPT_NAME | CONNECT_BY_ISLEAF |
|---|---|
| ЗАО ИнвестКорп | 0 |
| Бухгалтерия | 0 |
| Бухгалтерия по участку 1 | 1 |
| Бухгалтерия по участку 2 | 1 |
| Отдел продаж | 1 |
| IT-отдел | 0 |
| Отдел QA | 1 |
| Отдел разработки | 1 |
| Дирекция | 1 |
Сортировка в рекурсивных запросах
В запросах с использованием CONNECT BY нельзя использовать ORDER BY и GROUP BY, т.к. они нарушат древовидную структуру.
Это можно увидеть на примере:
select dp.dept_name, level
from departments dp
start with dp.parent_id is null
connect by prior id = dp.parent_id
order by dp.dept_name asc| DEPT_NAME | LEVEL |
|---|---|
| IT-отдел | 0 |
| Бухгалтерия | 2 |
| Бухгалтерия по участку 1 | 3 |
| Бухгалтерия по участку 2 | 3 |
| Дирекция | 2 |
| ЗАО ИнвестКорп | 1 |
| Отдел QA | 3 |
| Отдел продаж | 2 |
| Отдел разработки | 3 |
Как видно, корневой узел теперь шестой в выборке, а на первом месте подразделение, которое находится на втором уровне вложенности в дереве.
Для того, чтобы отсортировать данные, не нарушая их древовидной структуры, используется конструкция ORDER SIBLINGS BY. В этом случае сортировка будет применяться отдельно для каждой группы потомков в дереве:
| DEPT_NAME | LEVEL |
|---|---|
| ЗАО ИнвестКорп | 1 |
| IT-отдел | 2 |
| Отдел QA | 3 |
| Отдел разработки | 3 |
| Бухгалтерия | 2 |
| Бухгалтерия по участку 1 | 3 |
| Бухгалтерия по участку 2 | 3 |
| Дирекция | 2 |
| Отдел продаж | 2 |
Теперь узлы, находящиеся на одном уровне, сортируются в алфавитном порядке, при этом структура дерева не нарушена.
Нарушение древовидной структуры при выборке
Предположим, что мы хотим получить структуру подразделений начиная с тех, чьи названия содержат в себе слово "отдел":
select *
from departments
start with upper(dept_name) like upper('%Отдел%')
connect by prior id = parent_id| ID | DEPT_NAME | PARENT_ID |
|---|---|---|
| 3 | Отдел продаж | 1 |
| 4 | IT-отдел | 1 |
| 8 | Отдел QA | 4 |
| 9 | Отдел разработки | 4 |
| 8 | Отдел QA | 4 |
| 9 | Отдел разработки | 4 |
Некоторые строки дублируются, хотя в таблице имена подразделений не повторяются.
Теперь выполним тот же запрос, только добавим к списку колонок псевдостолбец level:
select id, dept_name, parent_id, level
from departments
start with upper(dept_name) like upper('%Отдел%')
connect by prior id = parent_id| ID | DEPT_NAME | PARENT_ID | LEVEL |
|---|---|---|---|
| 3 | Отдел продаж | 1 | 1 |
| 4 | IT-отдел | 1 | 1 |
| 8 | Отдел QA | 4 | 2 |
| 9 | Отдел разработки | 4 | 2 |
| 8 | Отдел QA | 4 | 1 |
| 9 | Отдел разработки | 4 | 1 |
Теперь понятно, что строки дублируются из-за того, что они находятся на разных уровнях в дереве.
Разберем, почему так происходит, пройдя путь построения дерева:
- В качестве корней дерева добавляются узлы, которые удовлетворяют условию, находящемуся в
START WITH. Это "Отдел продаж", "IT-отдел", "Отдел QA" и "Отдел разработки". Все они находятся на первом уровне вложенности в дереве. - Рекурсивно ищем потомков для всех выбранных на первом шаге узлов. Из всех них вложенность есть только у отдела IT - и внутри него как раз находятся "Отдел QA" и "Отдел разработки", поэтому они добавляются со вторым уровнем вложенности.
WARNING
Следует различать фактическое дерево, которое хранится в таблице, и то, которое получается при выборке, так как они могут не совпадать.
На практике такая необходимость почти не встречается, и если при выборке данные не отражают той структуры, которая хранится в БД, то скорее всего запрос написан с ошибкой.