Обеспечение уникальности в рекурсивном запросе

Question

У меня есть очень простая иерархия parent-child/tree и рекурсивный запрос, который также добавляет depth и загружает все идеально ... почти. Когда я пытаюсь загрузить несколько узлов, где один из них является дочерним по отношению к другому, я получаю повторяющиеся строки (потому что depth получает обновление, а строки больше не идентичны).

Я прочитал documentation, я не использую UNION ALL, я сделал попробовать NOT cycle трюк из документации, я знаю о типе ltree данных, но я не могу его использовать. Это что-то другое, рассмотрим следующее дерево:

5 
├─9 
│ └─15 
├─10 
│ └─16 
└─11 
    └─17 

И запрос:

WITH RECURSIVE "CTE" AS 
(
    SELECT "id", 0 AS "depth" 
    FROM "Node" WHERE "id" IN (5, 9, 15) 
    UNION 
    SELECT "Node"."id", "CTE"."depth" + 1 
    FROM "CTE" JOIN "Node" ON "Node"."parentId" = "CTE"."id" 
) 
SELECT * 
FROM "CTE" 
ORDER BY "id"; 

что приводит:

id depth 
5 0 
9 0 
9 1 
10 1 
11 1 
15 0 
15 1 
15 2 
16 2 
17 2 

Вместо желаемого результата:

id depth 
5 0 
9 0 
10 1 
11 1 
15 0 
16 2 
17 2 

Выполнение того же qu чень с WHERE "id" = 5 производит (обратите внимание, как глубина отличается, потому что выбор сделан прямо от корня):

id depth 
5 0 
9 1 
10 1 
11 1 
15 2 
16 2 
17 2 

Решение это было бы изменить присоединиться стать:

FROM "CTE" JOIN "Node" ON 
    "Node"."parentId" = "CTE"."id" AND 
    "Node"."id" NOT IN (SELECT "id" FROM "CTE") 

Но Postgres не позволяет ссылаться на «CTE» из подзапроса. Я хочу знать, есть ли подходящий подход к этой проблеме?

Кстати,, я придумал решение, которое работает, я попробовал его в нескольких разных сценариях, но я не уверен на 100%, что он будет работать во всех случаях. Он в основном устраняет первоначально выбранные значения, гарантируя, что итерация не будет «вводить» их. Я на правой ноге с ним/есть ли какие-то подводные камни с этим подходом?

WITH RECURSIVE "CTE" AS 
(
    SELECT "id", 0 AS "depth" 
    FROM "Node" WHERE "id" IN (5, 9, 15) 
    UNION 
    SELECT "Node"."id", "CTE"."depth" + 1 
    FROM "CTE" JOIN "Node" ON 
     "Node"."parentId" = "CTE"."id" 
     AND NOT IN (5, 9, 15) 
) 
SELECT * 
FROM "CTE" 
ORDER BY "id"; 

Answer 1

-- Data 
CREATE TABLE node 
     (id integer NOT NULL PRIMARY KEY 
     , parentid integer REFERENCES node(id) 
     ); 

INSERT INTO node(id,parentid) VALUES 
(5, NULL) 
, (9,5), (10,5), (11,5) 
, (15,9), (16,10), (17,11) 
     ; 

-- query 
WITH RECURSIVE tree AS (
    SELECT id, 0 AS depth 
    FROM node WHERE id IN (5, 9, 15) 
    UNION 
    SELECT node.id, tree.depth + 1 
    FROM tree JOIN node ON node.parentid = tree.id 
    ) 
SELECT * 
FROM tree tr 
WHERE NOT EXISTS (-- trivial way to suppress duplicates with longer path 
     SELECT * 
     FROM tree nx 
     WHERE nx.id = tr.id 
     AND nx.depth < tr.depth 
     ) 
ORDER BY id 
     ; 

---

UPDATE: Это выглядит менее дорогостоящим. Это верно для данных (но не в общем случае IIUC):

WITH RECURSIVE tree AS (
    SELECT id, 0 AS depth 
    FROM node WHERE id IN (5, 9, 15) 
    UNION 
    SELECT node.id, tree.depth + 1 
    FROM tree JOIN node ON node.parentid = tree.id 
    WHERE node.id NOT IN (5, 9, 15) 
    ) 
SELECT * 
FROM tree tr 
ORDER BY id 
     ;