Эта статья о практическом применении деревьев в ваших проектах. На примерах постараюсь показать решения основных задач, с которыми вы, возможно, столкнетесь при проектировании или разработке вашего проекта. В 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