Oracle дерево connect by

Hierarchical Queries in Oracle

This articles gives an overview of how to query hierarchical data in Oracle databases using SQL.

Setup

The following table contains hierarchical data.

DROP TABLE tab1 PURGE; CREATE TABLE tab1 ( id NUMBER, parent_id NUMBER, CONSTRAINT tab1_pk PRIMARY KEY (id), CONSTRAINT tab1_tab1_fk FOREIGN KEY (parent_id) REFERENCES tab1(id) ); CREATE INDEX tab1_parent_id_idx ON tab1(parent_id); INSERT INTO tab1 VALUES (1, NULL); INSERT INTO tab1 VALUES (2, 1); INSERT INTO tab1 VALUES (3, 2); INSERT INTO tab1 VALUES (4, 2); INSERT INTO tab1 VALUES (5, 4); INSERT INTO tab1 VALUES (6, 4); INSERT INTO tab1 VALUES (7, 1); INSERT INTO tab1 VALUES (8, 7); INSERT INTO tab1 VALUES (9, 1); INSERT INTO tab1 VALUES (10, 9); INSERT INTO tab1 VALUES (11, 10); INSERT INTO tab1 VALUES (12, 9); COMMIT;

Basic Hierarchical Query

In its simplest form a hierarchical query needs a definition of how each child relates to its parent. This is defined using the CONNECT BY .. PRIOR clause, which defines how the current row (child) relates to a prior row (parent). In addition, the START WITH clause can be used to define the root node(s) of the hierarchy. Hierarchical queries come with operators, pseudocolumns and functions to help make sense of the hierarchy.

• LEVEL : The position in the hierarchy of the current row in relation to the root node.
• CONNECT_BY_ROOT : Returns the root node(s) associated with the current row.
• SYS_CONNECT_BY_PATH : Returns a delimited breadcrumb from root to the current row.
• CONNECT_BY_ISLEAF : Indicates if the current row is a leaf node.
• ORDER SIBLINGS BY : Applies an order to siblings, without altering the basic hierarchical structure of the data returned by the query.

The following query gives an example of these items based on the previously defined test table.

SET PAGESIZE 20 LINESIZE 110 COLUMN tree FORMAT A20 COLUMN path FORMAT A20 SELECT id, parent_id, RPAD('.', (level-1)*2, '.') || id AS tree, level, CONNECT_BY_ROOT id AS root_id, LTRIM(SYS_CONNECT_BY_PATH(id, '-'), '-') AS path, CONNECT_BY_ISLEAF AS leaf FROM tab1 START WITH parent_id IS NULL CONNECT BY parent_id = PRIOR id ORDER SIBLINGS BY id; ID PARENT_ID TREE LEVEL ROOT_ID PATH LEAF ---------- ---------- -------------------- ---------- ---------- -------------------- ---------- 1 1 1 1 1 0 2 1 ..2 2 1 1-2 0 3 2 . 3 3 1 1-2-3 1 4 2 . 4 3 1 1-2-4 0 5 4 . 5 4 1 1-2-4-5 1 6 4 . 6 4 1 1-2-4-6 1 7 1 ..7 2 1 1-7 0 8 7 . 8 3 1 1-7-8 1 9 1 ..9 2 1 1-9 0 10 9 . 10 3 1 1-9-10 0 11 10 . 11 4 1 1-9-10-11 1 12 9 . 12 3 1 1-9-12 1

Cyclic Hierarchical Query

It is possible for a hierarchy to be cyclical, which can represent a problem when querying the data.

-- Create a cyclic reference UPDATE tab1 SET parent_id = 9 WHERE id, parent_id, RPAD('.', (level-1)*2, '.') || id AS tree, level, CONNECT_BY_ROOT id AS root_id, LTRIM(SYS_CONNECT_BY_PATH(id, '-'), '-') AS path, CONNECT_BY_ISLEAF AS leaf FROM tab1 START WITH parent_id IS NULL CONNECT BY parent_id = PRIOR id ORDER SIBLINGS BY id; ERROR: ORA-01436: CONNECT BY loop in user data

To simplify matters, the CONNECT BY NOCYCLE clause tells the database not to traverse cyclical hierarchies. In this case the CONNECT_BY_ISCYCLE function indicates which record is responsible for the cycle.

We can now use the NOCYCLE option and check the results of the CONNECT_BY_ISCYCLE function.

SELECT id, parent_id, RPAD('.', (level-1)*2, '.') || id AS tree, level, CONNECT_BY_ROOT id AS root_id, LTRIM(SYS_CONNECT_BY_PATH(id, '-'), '-') AS path, CONNECT_BY_ISLEAF AS leaf, CONNECT_BY_ISCYCLE AS cycle FROM tab1 START WITH BY NOCYCLE parent_id = PRIOR id ORDER SIBLINGS BY id; ID PARENT_ID TREE LEVEL ROOT_ID PATH LEAF CYCLE ---------- ---------- -------------------- ---------- ---------- -------------------- ---------- ---------- 1 9 1 1 1 1 0 0 2 1 ..2 2 1 1-2 0 0 3 2 . 3 3 1 1-2-3 1 0 4 2 . 4 3 1 1-2-4 0 0 5 4 . 5 4 1 1-2-4-5 1 0 6 4 . 6 4 1 1-2-4-6 1 0 7 1 ..7 2 1 1-7 0 0 8 7 . 8 3 1 1-7-8 1 0 9 1 ..9 2 1 1-9 0 1 10 9 . 10 3 1 1-9-10 0 0 11 10 . 11 4 1 1-9-10-11 1 0 12 9 . 12 3 1 1-9-12 1 0

Hope this helps. Regards Tim.

Created: 2015-03-09 Updated: 2019-03-23

Источник

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

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

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

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

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

Источник