Как получить полный путь к узлу дерева в обратном порядке в PostgreSQL? - PullRequest
Новая
       18

Как получить полный путь к узлу дерева в обратном порядке в PostgreSQL?

1 голос
/ 18 апреля 2020

У меня есть следующая таблица 

CREATE TABLE descriptor_value (
    id bigint NOT NULL,
    value varchar(250),
    parent_id bigint
) ;

id столбец является первичным ключом.

И у меня есть три строки 

id | value | parent_id
----------------------
1  | foo   | null
2  | bar   | 1
3  | baz   | 2

И мне нужно создайте представление, которое покажет полный путь узла every в обратном порядке. Например, если мы рассмотрим только baz, должен быть следующий вывод: 

child_id | parent_id | level
----------------------------
 3       | 3         | 1
 3       | 2         | 2    
 3       | 1         | 3

Кто-нибудь может сказать, как это сделать в Pg SQL 12?

Ответы [ 2 ]

1 голос
/ 18 апреля 2020

Я думаю, что вы хотите пройтись по дереву от листьев к узлам. Это будет: 

with recursive cte as (
    select id child_id, id parent_id, 1 lvl, parent_id real_parent_id
    from descriptor_value dv
    where not exists (select 1 from descriptor_value dv1 where dv1.parent_id = dv.id)
    union all
    select c.child_id, dv.id parent_id, lvl + 1, dv.parent_id
    from cte c
    inner join descriptor_value dv on dv.id = c.real_parent_id
)
select child_id, parent_id, lvl from cte order by lvl

Якорь рекурсивного запроса начинается со строк, которые не являются родительскими для любого другого узла. Затем мы поднимаемся вверх по дереву, увеличивая lvl на каждом шаге, пока не достигнем root.

Демонстрация по DB Fiddle : 

child_id | parent_id | lvl
-------: | --------: | --:
       3 |         3 |   1
       3 |         2 |   2
       3 |         1 |   3

Если вы хотите начать с любого узла, то это еще проще: нам просто нужно изменить определение якоря: 

with recursive cte as (
    select id child_id, id parent_id, 1 lvl, parent_id real_parent_id
    from descriptor_value dv
    union all
    select c.child_id, dv.id parent_id, lvl + 1, dv.parent_id
    from cte c
    inner join descriptor_value dv on dv.id = c.real_parent_id
)
select child_id, parent_id, lvl from cte order by child_id, lvl

Доходность : 

child_id | parent_id | lvl
-------: | --------: | --:
       1 |         1 |   1
       2 |         2 |   1
       2 |         1 |   2
       3 |         3 |   1
       3 |         2 |   2
       3 |         1 |   3
0 голосов
/ 18 апреля 2020

Использовать рекурсивный CTE: 

with recursive cte as (
      select dv.id, dv.value, dv.parent_id, dv.parent_id as root, 1 as lev,
             dv.id::text as path
      from descriptor_value dv
      where dv.parent_id is null
      union all
      select dv.id, dv.value, dv.parent_id, cte.root, lev + 1,
             cte.path || '-->' || (dv.id::text)
      from cte join
           descriptor_value dv
           on dv.parent_id = cte.id
    )
select cte.id, cte.value, cte.parent_id, cte.root, lev,
       max(lev) over (partition by cte.root) - lev + 1 as level
from cte
order by root, lev;

Здесь - это дБ <> скрипка.

...