Древовидные структуры данных. Рекурсивные запросы

Достаточно часто приходится иметь дело с древовидными структурами данных. Классическим примером является структура подразделений организации, где один отдел является частью другого, и при этом также состоит из нескольких подразделений. Также можно в виде дерева описать отношения между сотрудниками - кто кому приходится начальником; некий список документов, где один документ появляется на основании другого, а тот в свою очередь был создан на основании третьего, и т.п.

Реализация древовидных структур в РСУБД

Для того, чтобы можно было листья дерева собрать воедино, нужно знать, как они соотносятся друг с другом. Как правило, все данные, которые нужно хранить в виде дерева, хранятся в одной таблице. Для того, чтобы по определенной строке определить ее родителя, в таблицу добавляется колонка, которая ссылается на родителя в этой же таблице. У корневого узла в дереве колонка с 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 = 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. Но мы знаем, что у корневых узлов нет родителей, что и указали в конструкции 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

Здесь используется функция 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

Сортировка в рекурсивных запросах

В запросах с использованием 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

Как видно, корневой узел теперь шестой в выборке, а на первом месте подразделение, которое находится на втором уровне вложенности в дереве.

Для того, чтобы отсортировать данные, не нарушая их древовидной структуры, используется конструкция ORDER SIBLINGS BY. В этом случае сортировка будет применяться отдельно для каждой группы потомков в дереве:

Теперь узлы, находящиеся на одном уровне, сортируются в алфавитном порядке, при этом структура дерева не нарушена.

Нарушение древовидной структуры при выборке

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

select *
from departments
start with upper(dept_name) like upper('%Отдел%')
connect by prior id = parent_id

Некоторые строки дублируются, хотя в таблице имена подразделений не повторяются.

Теперь выполним тот же запрос, только добавим к списку колонок псевдостолбец level:

select id, dept_name, parent_id, level
from departments
start with upper(dept_name) like upper('%Отдел%')
connect by prior id = parent_id

Теперь понятно, что строки дублируются из-за того, что они находятся на разных уровнях в дереве.

Разберем, почету так происходит, пройдя путь построения дерева:

  1. В качестве корней дерева добавляются узлы, которые удовлетворяют условию, находящемуся в START WITH. Это "Отдел продаж", "IT-отдел", "Отдел QA" и "Отдел разработки". Все они находятся на первом уровне вложенности в дереве.
  2. Рекурсивно ищем потомков для всех выбранных на первом шаге узлов. Из всех них вложенность есть только у отдела IT - и внутри него как раз находятся "Отдел QA" и "Отдел разработки", поэтому они добавляются со вторым уровнем вложенности.

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