Данные, организованные иерархически, - дерево или деревья - чаще всего представлены в реляционной БД как список узлов, где дочерний узел ссылается на родительский.
Создадим и заполним таблицу locations, иллюстрирующую именно этот подход:
create table locations (
id number primary key,
parent number references locations (id) on delete cascade,
name varchar2(50) not null
);
insert into locations values (1, null, 'Земля');
insert into locations values (2, 1, 'Азия');
insert into locations values (3, 2, 'Владивосток');
insert into locations values (4, 2, 'Саппоро');
insert into locations values (5, 2, 'Стамбул');
insert into locations values (6, 1, 'Европа');
insert into locations values (7, 6, 'Реймс');
insert into locations values (8, 6, 'Санкт-Петербург');
Здесь узел 'Земля' есть корень дерева, на него ссылаются узлы 'Азия' и 'Европа', на них ссылаются остальные узлы - листья. Здесь каждый узел
- принадлежит одному дереву, поскольку дочерний узел ссылается только на одного родителя (родительский и дочерний узлы находятся в отношении один-ко-многим);
- идентифицирует поддерево, корнем которого является;
- лежит на пути, соединяющем корень дерева и один из его листьев.
Какими средствами языка SQL можно извлечь все узлы некоторого поддерева? А все узлы, лежащие на пути от данного узла до корня дерева?
Традиционно в СУБД Oracle это делается с помощью иерархического запроса. В таком запросе используется предложение connect by для описания связей между родительскими и дочерними узлами, и предложение start with - для задания узла (узлов), с которого нужно начать построение иерархии. Псевдостолбец level и функции sys_connect_by_path и connect_by_root позволяют получить для узла иерархии его уровень, путь к нему от корня и корень построенной иерархии, соответственно.
Вот иерархический запрос, возвращающий все узлы дерева, начиная с корня - узла 'Земля'. Значение level используется, чтобы сдвинуть название узла вправо на (level-1)*2 пробелов и наглядно представить уровни дерева:
-- от корня к листьям, или получить все узлы-потомки
select id, parent, rpad(' ', (level-1)*2) || name, level, sys_connect_by_path(id, '/') path, connect_by_root(id) root
from locations
connect by prior id = parent
start with parent is null
;
ID PARENT RPAD('',(LEVEL-1)*2)||NAME LEVEL PATH ROOT
------ ------ ---------------------------- ------ -------------------- ------
1 Земля 1 /1 1
2 1 Азия 2 /1/2 1
3 2 Владивосток 3 /1/2/3 1
4 2 Саппоро 3 /1/2/4 1
5 2 Стамбул 3 /1/2/5 1
6 1 Европа 2 /1/6 1
7 6 Реймс 3 /1/6/7 1
8 6 Санкт-Петербург 3 /1/6/8 1
8 rows selected
Следующий запрос выполняет обратный проход от узлов-городов, заданных в предложении start with, к узлу 'Земля' - терминальному для построенных иерархий:
-- от листьев к корню, или получить все узлы-предки
select id, parent, rpad(' ', (level-1)*2) || name, level, sys_connect_by_path(id, '/') path, connect_by_root(id) root
from locations
connect by prior parent = id
start with id not in (select nvl(parent,-1) from locations)
;
ID PARENT RPAD('',(LEVEL-1)*2)||NAME LEVEL PATH ROOT
------ ------ ---------------------------- ------ -------------------- ------
3 2 Владивосток 1 /3 3
2 1 Азия 2 /3/2 3
1 Земля 3 /3/2/1 3
4 2 Саппоро 1 /4 4
2 1 Азия 2 /4/2 4
1 Земля 3 /4/2/1 4
5 2 Стамбул 1 /5 5
2 1 Азия 2 /5/2 5
1 Земля 3 /5/2/1 5
7 6 Реймс 1 /7 7
6 1 Европа 2 /7/6 7
1 Земля 3 /7/6/1 7
8 6 Санкт-Петербург 1 /8 8
6 1 Европа 2 /8/6 8
1 Земля 3 /8/6/1 8
15 rows selected
Начиная с версии Oracle 11gR2 для работы с иерархически организованными данными поддерживаются так называемые recursive common table expressions (CTEs), описанные в стандарте SQL-99. Обратите внимание, как (очевидным образом) строятся значения столбцов lvl (уровень), path и root при использовании CTEs в следующих запросах.
-- от корня к листьям, или получить все узлы-потомки
with tree (id, parent, name, lvl, path, root) as (
select id, parent, name, 1, '/'||id, id
from locations
where parent is null
union all
select l.id, l.parent, l.name, t.lvl+1, t.path||'/'||l.id, t.root
from locations l join tree t on l.parent = t.id
)
select id, parent, rpad(' ', (lvl-1)*2) || name, lvl, path, root from tree
order by path
;
ID PARENT RPAD('',(LEVEL-1)*2)||NAME LEVEL PATH ROOT
------ ------ ---------------------------- ------ -------------------- ------
1 Земля 1 /1 1
2 1 Азия 2 /1/2 1
3 2 Владивосток 3 /1/2/3 1
4 2 Саппоро 3 /1/2/4 1
5 2 Стамбул 3 /1/2/5 1
6 1 Европа 2 /1/6 1
7 6 Реймс 3 /1/6/7 1
8 6 Санкт-Петербург 3 /1/6/8 1
8 rows selected
-- от листьев к корню, или получить все узлы-предки
with tree (id, parent, name, lvl, path, root) as (
select id, parent, name, 1, '/'||id, id
from locations
where id not in (select nvl(parent, -1) from locations)
union all
select l.id, l.parent, l.name, t.lvl+1, t.path||'/'||l.id, t.root
from locations l join tree t on l.id = t.parent
)
select id, parent, rpad(' ', (lvl-1)*2) || name, lvl, path, root from tree
order by path
;
ID PARENT RPAD('',(LEVEL-1)*2)||NAME LEVEL PATH ROOT
------ ------ ---------------------------- ------ -------------------- ------
3 2 Владивосток 1 /3 3
2 1 Азия 2 /3/2 3
1 Земля 3 /3/2/1 3
4 2 Саппоро 1 /4 4
2 1 Азия 2 /4/2 4
1 Земля 3 /4/2/1 4
5 2 Стамбул 1 /5 5
2 1 Азия 2 /5/2 5
1 Земля 3 /5/2/1 5
7 6 Реймс 1 /7 7
6 1 Европа 2 /7/6 7
1 Земля 3 /7/6/1 7
8 6 Санкт-Петербург 1 /8 8
6 1 Европа 2 /8/6 8
1 Земля 3 /8/6/1 8
15 rows selected
Результаты упорядочены по столбцу path, чтобы выглядеть так же, как результаты традиционных connect by-запросов, приведенных выше.
Теперь, на примере иерархии locations рассмотрим основные операции на дереве:
- добавить узел,
- переместить узел,
- удалить узел.
Добавляется всегда терминальный узел (лист дерева). С помощью этой операции выше была заполнена таблица locations.
Переместить можно произвольный узел, и, если этот узел не терминальный, то перемещается поддерево, корнем которого он является. Технически ничто не мешает переместить узел с уровня на уровень; то есть, узел в дереве можно переместить горизонтально, вертикально, или по диагонали.
SQL> -- перенос Стамбула в Европу
SQL> update locations set parent = 6 where name = 'Стамбул';
1 row updated
SQL> -- перенос Азии в Европу
SQL> update locations set parent = (select id from locations where name = 'Европа')
2 where name = 'Азия';
1 row updated
SQL> with tree (id, parent, name, lvl, path, root) as (
2 select id, parent, name, 1, '/'||id, id
3 from locations
4 where parent is null
5 union all
6 select l.id, l.parent, l.name, t.lvl+1, t.path||'/'||l.id, t.root
7 from locations l join tree t on l.parent = t.id
8 )
9 select id, parent, rpad(' ', (lvl-1)*2) || name, lvl, path, root from tree
10 order by path
11 ;
ID PARENT RPAD('',(LEVEL-1)*2)||NAME LEVEL PATH ROOT
------ ------ ---------------------------- ------ -------------------- ------
1 Земля 1 /1 1
6 1 Европа 2 /1/6 1
2 6 Азия 3 /1/6/2 1
3 2 Владивосток 4 /1/6/2/3 1
4 2 Саппоро 4 /1/6/2/4 1
5 6 Стамбул 3 /1/6/5 1
7 6 Реймс 3 /1/6/7 1
8 6 Санкт-Петербург 3 /1/6/8 1
8 rows selected
Перемещение или добавление узла может привести к появлению цикла - и разрушению дерева:
SQL> update locations set parent = (select id from locations where name = 'Азия') where name = 'Европа';
1 row updated
SQL> with tree (id, parent, name, lvl, path, root) as (
2 select id, parent, name, 1, '/'||id, id
3 from locations
4 where id = 6
5 union all
6 select l.id, l.parent, l.name, t.lvl+1, t.path||'/'||l.id, t.root
7 from locations l join tree t on l.parent = t.id
8 )
9 select id, parent, rpad(' ', (lvl-1)*2) || name, lvl, path, root from tree
10 order by path
11 ;
ORA-32044: cycle detected while executing recursive WITH query
SQL> rollback;
Rollback complete
Удалить можно произвольный узел. Если удаляется нетерминальный узел, то удаляется поддерево, корнем которого он является:
SQL> delete from locations where name = 'Азия';
1 row deleted
SQL> with tree (id, parent, name, lvl, path, root) as (
2 select id, parent, name, 1, '/'||id, id
3 from locations
4 where parent is null
5 union all
6 select l.id, l.parent, l.name, t.lvl+1, t.path||'/'||l.id, t.root
7 from locations l join tree t on l.parent = t.id
8 )
9 select id, parent, rpad(' ', (lvl-1)*2) || name, lvl, path, root from tree
10 order by path
11 ;
ID PARENT RPAD('',(LEVEL-1)*2)||NAME LEVEL PATH ROOT
------ ------ ---------------------------- ------ -------------------- ------
1 Земля 1 /1 1
6 1 Европа 2 /1/6 1
7 6 Реймс 3 /1/6/7 1
8 6 Санкт-Петербург 3 /1/6/8 1
Удаление поддерева возможно потому, что ссылочное ограничение целостности на таблице locations определено с опцией on delete cascade. Если бы не это, удаление нетерминальных узлов было бы невозможно.
Представление иерархически организованных данных, проиллюстрированное с помощью таблицы locations, - когда строка таблицы представляет узел, ссылающийся на родительский - не единственно возможное. Поскольку каждый узел дерева имеет уникальный путь, веудущий к нему от корня через промежуточные узлы, то дерево можно представить как список таких путей. Или как список путей от корня к листьям. Выбор того или иного представления зависит от решаемой задачи. Несколько способов хранения деревьев в реляционной БД, их преимущества и недостатки описаны, например, в книге SQL Antipatterns: Avoiding the Pitfalls of Database Programming by Bill Karwin.
В заключение, удаляю таблицу, которая больше не нужна:
SQL> drop table locations;
Table dropped
Комментариев нет:
Отправить комментарий