PostgreSQL: рекурсивный обход дерева вверх в PostgreSQL

Question

есть таблица вида

[id] [name] [parent]

В поле parent указывается name родителя. Если у записи нет родителя, то parent = name.

Необходимо зная id записи найти всех его детей, а также предков и "племянников", т.е. полностью обойти дерево в обе стороны.

Вот таким запросом:

WITH RECURSIVE tmp_t AS (
    -- стартовая часть рекурсии 
    SELECT id, name, parent
    FROM tree_t
    WHERE id = <id записи>

    UNION ALL

    -- рекурсивная часть
    SELECT t.id, t.name, t.parent 
    FROM tree_t AS t
    JOIN tmp_t ON t.parent = tmp_t.name AND t.parent <> t.name
)
SELECT tmp_t.id
FROM tmp_t;

я могу найти только все дочерние элементы.

А как найти все элементы от которых можно добраться до указанного id?

P.S.

И второй вопрос - а как подняться вверх и найти корень дерева? Т.е. sql запрос должен выдать id самого старшего родителя.

Answer 1

Возникла проблема дубликатов. Подскажите в чем может быть дело?

создал такую таблицу

id, name, parent
1,A,A
2,AB,A
3,AA,A
4,AAA,AA
5,AAB,AA
6,ABB,AB
7,ABC,AB
8,ABA,AB
9,AAABA,AAB
10,AAABB,AAB
11,ABBA,ABB
12,ABCA,ABC
13,ABCB,ABC
14,ABBAA,ABBA
15,ABBAB,ABBA
16,B,B
17,BA,B
18,BB,B
19,BBA,BB
20,BBB,BB
21,C,C

И соответственно код для обхода дерева:

CREATE OR REPLACE FUNCTION public.dbg_get_tree_full(
    node_id bigint)
    RETURNS TABLE(id bigint, parent_id text) 
    LANGUAGE 'sql'
    COST 100
    VOLATILE PARALLEL UNSAFE
    ROWS 1000

AS $BODY$
    WITH RECURSIVE tmp_t AS (
        SELECT t1.name, t1.parent, t1.id, 1 as level, '/1/' as path
        FROM dbg_tree t1
        WHERE t1.id = node_id

        UNION

        SELECT t2.name, t2.parent, t2.id, level+1 as level, tmp_t.path||t2.name||'/' path
        FROM dbg_tree t2
        INNER JOIN tmp_t
        ON (
            (
                t2.parent = tmp_t.name AND t2.parent <> t2.name OR 
                tmp_t.parent = t2.name AND tmp_t.parent <> tmp_t.name
            )
            AND tmp_t.path NOT LIKE '%/'||t2.name||'/%') 
    )
    SELECT id, parent
    FROM tmp_t
$BODY$;

В результате запроса:

select * from dbg_get_tree_full(2)

получается 61 запись!!! (Хотя в базе их 21, причем лишь часть образуют дерево)

Если же посмотреть кол-во записей

select *
from (
select id, parent_id, COUNT(*) as c
from dbg_get_tree_full(2)
group by id, parent_id) as t
where t.c > 1

то можно увидеть многократное дублирование

id  parent_id  count
6   "AB"    3
12  "ABC"   3
2   "A" 3
15  "ABBA"  3
13  "ABC"   3
1   "A" 3
8   "AB"    3
4   "AA"    3
11  "ABB"   3
14  "ABBA"  3
9   "AAB"   3
5   "AA"    3
7   "AB"    4
3   "A" 3
10  "AAB"   3

подскажите как это исправить можно и в чем дело - почему такое вообще возникло!

Answer 2

Думаю, Вы многократно обходите дерево, составляя список всех возможных путей из данного узла. Посмотрите пример. Здесь делается различие в движении к родителю (вверх) и потомкам(вниз). От родителей вниз - по "чужим" ветвям - не ходим.

CREATE OR REPLACE FUNCTION public.dbg_get_tree_full(
    node_id bigint)
    RETURNS TABLE(id bigint, name text,parent_id text,lvl int,path text,updown int) 
    LANGUAGE 'sql'
    COST 100
    VOLATILE PARALLEL UNSAFE
    ROWS 1000

AS $BODY$
    WITH RECURSIVE tmp_t AS (
        SELECT 1 lvl,t1.name, t1.parent, t1.id, 1 as level
              , '/'||cast(t1.id as varchar)||'/' as path
              ,0 updown
        FROM dbg_tree t1
        WHERE t1.id = node_id

        UNION

        SELECT tmp_t.lvl+1,t2.name, t2.parent, t2.id, level+1 as level
            , tmp_t.path||t2.name||'/' path
            ,case when t2.parent = tmp_t.name AND t2.parent <> t2.name then 1 
                when tmp_t.parent = t2.name AND tmp_t.parent <> tmp_t.name then -1
             end
        FROM dbg_tree t2
        INNER JOIN tmp_t
        ON (
            (
                (t2.parent = tmp_t.name AND t2.parent <> t2.name 
                  and (updown=0 or updown=1)
                 )
             OR 
                (tmp_t.parent = t2.name AND tmp_t.parent <> tmp_t.name
                  and (updown=0 or updown=-1)
                )
            )
            AND tmp_t.path NOT LIKE '%/'||t2.name||'/%') 
    )
    SELECT id, name,parent,lvl,path,updown
    FROM tmp_t
$BODY$;
select * from public.dbg_get_tree_full(2)
order by id

Результат запроса

id	name	parent_id	lvl	path	updown
1	A	A	2	/2/A/	-1
2	AB	A	1	/2/	0
6	ABB	AB	2	/2/ABB/	1
7	ABC	AB	2	/2/ABC/	1
8	ABA	AB	2	/2/ABA/	1
11	ABBA	ABB	3	/2/ABB/ABBA/	1
12	ABCA	ABC	3	/2/ABC/ABCA/	1
13	ABCB	ABC	3	/2/ABC/ABCB/	1
14	ABBAA	ABBA	4	/2/ABB/ABBA/ABBAA/	1
15	ABBAB	ABBA	4	/2/ABB/ABBA/ABBAB/	1

Для узла 11 результат будет такой

id	name	parent_id	lvl	path	updown
1	A	A	4	/11/ABB/AB/A/	-1
2	AB	A	3	/11/ABB/AB/	-1
6	ABB	AB	2	/11/ABB/	-1
11	ABBA	ABB	1	/11/	0
14	ABBAA	ABBA	2	/11/ABBAA/	1
15	ABBAB	ABBA	2	/11/ABBAB/	1

БЛОГ НА HUSL

PostgreSQL: рекурсивный обход дерева вверх в PostgreSQL

Ответы (2 шт):