Эта статья о практическом применении деревьев в ваших проектах. На примерах постараюсь показать решения основных задач, с которыми вы, возможно, столкнетесь при проектировании или разработке вашего проекта. В SQL-стандарте для рекурсивных запросов используется CTE. Примеры с CTE будут показаны для  СУБД Firebird. Параллельно будут показаны примеры для Oracle, так как в нем синтаксис рекурсивных запросов будет отличаться.

Для наших примеров необходимо создать полигон:

  1. Основную таблицу, в которой будет храниться наше дерево.
  2. Соответствующие индексы и ключи
firebird
create table test_tree
(
id integer not null,
parent_id integer,
name varchar(240),
val number(18,4)
);

alter table test_tree
add constraint
pk_test_tree primary key (id);

alter table test_tree
add constraint
fk_test_tree_parent foreign key (parent_id)
references
test_tree (id);
oracle
create table test_tree
(
id integer not null,
parent_id integer,
name varchar2(240),
val number(18,4)
);

alter table test_tree
add constraint pk_test_tree primary key (id);

alter table test_tree
add constraint
fk_test_tree_parent foreign key (parent_id)
references
test_tree (id);

Простой пример обхода дерева начиная с заданного узла

firebird
with recursive tree
as (select t.id, t.parent_id, t.name, t.val, 1 lvl, '/' || name path
from test_tree t
where parent_id = 0
union all select t.id, t.parent_id, t.name, t.val, prior.lvl + 1 lvl, prior.path || '/' || t.name
from test_tree t
inner join tree prior on prior.id = t.parent_id)
select * from tree
oracle
select id, parent_id, name, val, level lvl, sys_connect_by_path(name, '/') path
from test_tree
start with parent_id = 0
connect by prior id = parent_id

В результате обхода дерева мы получили для каждого узла
LVL = значение уровня: 1 для начального узла, 2 для дочерних узлов начального, и так далее…
PATH = полный путь имен через разделитель, начиная от начального узла

Как видим в примере для Oracle для получения значения уровня узла используется псевдо колонка LEVEL, а для получения пути имен (все имена предков через разделитель) используем функцию SYS_CONNECT_BY_PATH(). В Firebird-варианте мы рассчитываем данные значения на каждом шаге.

Вычисление значений для каждого узла с учетом всех его дочерних узлов

В нашем примере мы для каждого узла рассчитаем сумму, максимальное значение и кол-во подузлов.

firebird
with recursive tree
as (select t.id parent_id, t.name, t.id, t.val
from test_tree t
union all select prior.parent_id, prior.name, t.id, t.val
from test_tree t
inner join tree prior on prior.id = t.parent_id)
select parent_id, name, count(1) cnt, sum(val) sum_val, max(val) max_val
from tree
group by parent_id, name
oracle
select parent_id, name, count(1) cnt, sum(val) sum_val, max(val) max_val
from (select connect_by_root id parent_id,
connect_by_root name name,
id,
val
from test_tree
connect by prior id = parent_id)
group by parent_id, name

Разворачивание CSV-строки в таблицу

firebird
execute block (
lst varchar(1024) = :lst,
delimiter char = :delimiter)
returns (
val varchar(1024))
as
begin
for
with recursive params
as (select substring(:lst from 1 for coalesce(nullif(position(:delimiter, :lst), 0), char_length(:lst) + 1) - 1) val,
substring(:lst from coalesce(nullif(position(:delimiter, :lst), 0), char_length(:lst) + 1) + 1) lst
from rdb$database
union all select substring(lst from 1 for coalesce(nullif(position(:delimiter, lst), 0), char_length(lst) + 1) - 1) val,
substring(lst from coalesce(nullif(position(:delimiter, lst), 0), char_length(lst) + 1) + 1) lst
from params
where lst != '')
select val
from params
into :val
do
suspend
;
end
Comments