Znajdź nadrzędny rekurencyjnie używając zapytania

Question

Używam postgresql. Mam tabelę jak poniżej:

parent_id child_id 
---------------------- 
101  102 
103  104 
104  105 
105  106 

Chcę napisać kwerendę sql, która da ostateczny nadrzędny dane wejściowe.

tj przypuszczać mijam 106 jako dane wejściowe, a następnie jej wyjście będzie 103.

(106 --> 105 --> 104 --> 103) 

Answer 1

Oto pełna przykładów. Najpierw DDL:

test=> CREATE TABLE node (
test(> id SERIAL, 
test(> label TEXT NOT NULL, -- name of the node 
test(> parent_id INT, 
test(> PRIMARY KEY(id) 
test(>); 
NOTICE: CREATE TABLE will create implicit sequence "node_id_seq" for serial column "node.id" 
NOTICE: CREATE TABLE/PRIMARY KEY will create implicit index "node_pkey" for table "node" 
CREATE TABLE 

... a niektóre dane ...

test=> INSERT INTO node (label, parent_id) VALUES ('n1',NULL),('n2',1),('n3',2),('n4',3); 
INSERT 0 4 
test=> INSERT INTO node (label) VALUES ('garbage1'),('garbage2'), ('garbage3'); 
INSERT 0 3 
test=> INSERT INTO node (label,parent_id) VALUES ('garbage4',6); 
INSERT 0 1 
test=> SELECT * FROM node; 
id | label | parent_id 
----+----------+----------- 
1 | n1  |   
2 | n2  |   1 
3 | n3  |   2 
4 | n4  |   3 
5 | garbage1 |   
6 | garbage2 |   
7 | garbage3 |   
8 | garbage4 |   6 
(8 rows) 

ten wykonuje kwerendę rekurencyjną na każdy identyfikator węzła:

test=> WITH RECURSIVE nodes_cte(id, label, parent_id, depth, path) AS (
SELECT tn.id, tn.label, tn.parent_id, 1::INT AS depth, tn.id::TEXT AS path 
FROM node AS tn 
WHERE tn.parent_id IS NULL 
UNION ALL 
SELECT c.id, c.label, c.parent_id, p.depth + 1 AS depth, 
     (p.path || '->' || c.id::TEXT) 
FROM nodes_cte AS p, node AS c 
WHERE c.parent_id = p.id 
) 
SELECT * FROM nodes_cte AS n ORDER BY n.id ASC; 
id | label | parent_id | depth | path  
----+----------+-----------+-------+------------ 
1 | n1  |   |  1 | 1 
2 | n2  |   1 |  2 | 1->2 
3 | n3  |   2 |  3 | 1->2->3 
4 | n4  |   3 |  4 | 1->2->3->4 
5 | garbage1 |   |  1 | 5 
6 | garbage2 |   |  1 | 6 
7 | garbage3 |   |  1 | 7 
8 | garbage4 |   6 |  2 | 6->8 
(8 rows) 

to pobiera wszystkie z potomkowie WHERE node.id = 1:

test=> WITH RECURSIVE nodes_cte(id, label, parent_id, depth, path) AS (
SELECT tn.id, tn.label, tn.parent_id, 1::INT AS depth, tn.id::TEXT AS path FROM node AS tn WHERE tn.id = 1 
UNION ALL     
SELECT c.id, c.label, c.parent_id, p.depth + 1 AS depth, (p.path || '->' || c.id::TEXT) FROM nodes_cte AS p, node AS c WHERE c.parent_id = p.id 
)                 
SELECT * FROM nodes_cte AS n; 
id | label | parent_id | depth | path  
----+-------+-----------+-------+------------ 
1 | n1 |   |  1 | 1 
2 | n2 |   1 |  2 | 1->2 
3 | n3 |   2 |  3 | 1->2->3 
4 | n4 |   3 |  4 | 1->2->3->4 
(4 rows) 

Poniższa dostanie ścieżkę do węzła o id 4:

test=> WITH RECURSIVE nodes_cte(id, label, parent_id, depth, path) AS (
SELECT tn.id, tn.label, tn.parent_id, 1::INT AS depth, tn.id::TEXT AS path 
FROM node AS tn 
WHERE tn.parent_id IS NULL 
UNION ALL 
SELECT c.id, c.label, c.parent_id, p.depth + 1 AS depth, 
     (p.path || '->' || c.id::TEXT) 
FROM nodes_cte AS p, node AS c 
WHERE c.parent_id = p.id 
) 
SELECT * FROM nodes_cte AS n WHERE n.id = 4; 
id | label | parent_id | depth | path  
----+-------+-----------+-------+------------ 
4 | n4 |   3 |  4 | 1->2->3->4 
(1 row) 

I załóżmy, chcesz ograniczyć wyszukiwanie do potomków z depth mniej niż trzy (zauważ, że depth nie został jeszcze zwiększany):

test=> WITH RECURSIVE nodes_cte(id, label, parent_id, depth, path) AS (
    SELECT tn.id, tn.label, tn.parent_id, 1::INT AS depth, tn.id::TEXT AS path 
    FROM node AS tn WHERE tn.id = 1 
UNION ALL 
    SELECT c.id, c.label, c.parent_id, p.depth + 1 AS depth, 
     (p.path || '->' || c.id::TEXT) 
    FROM nodes_cte AS p, node AS c 
    WHERE c.parent_id = p.id AND p.depth < 2 
) 
SELECT * FROM nodes_cte AS n; 
id | label | parent_id | depth | path 
----+-------+-----------+-------+------ 
    1 | n1 |   |  1 | 1 
    2 | n2 |   1 |  2 | 1->2 
(2 rows) 

polecam przy użyciu typu ARRAY danych zamiast sznurka do wykazania „ścieżka”, ale strzałka jest bardziej obrazowe rodzica < => relacjami dziecko.

Answer 2

Użyj WITH RECURSIVE, aby utworzyć wspólne wyrażenie tabelowe (CTE). Dla non-rekurencyjne perspektywie uzyskać wierszy w którym dziecko bezpośrednio poniżej dominującej:

SELECT 
    c.child_id, 
    c.parent_id 
FROM 
    mytable c 
LEFT JOIN 
    mytable p ON c.parent_id = p.child_id 
WHERE 
    p.child_id IS NULL 

child_id | parent_id 
----------+----------- 
     102 |  101 
     104 |  103 

dla rekurencyjnego wyrażenia, chcesz dzieci tych dzieci.

WITH RECURSIVE tree(child, root) AS (
    SELECT 
     c.child_id, 
     c.parent_id 
    FROM 
     mytable c 
    LEFT JOIN 
     mytable p ON c.parent_id = p.child_id 
    WHERE 
     p.child_id IS NULL 
    UNION 
    SELECT 
     child_id, 
     root 
    FROM 
     tree 
    INNER JOIN 
     mytable on tree.child = mytable.parent_id 
) 
SELECT * FROM tree; 

child | root 
-------+------ 
    102 | 101 
    104 | 103 
    105 | 103 
    106 | 103 

można filtrować dzieci podczas odpytywanie CTE:

WITH RECURSIVE tree(child, root) AS (...) SELECT root FROM tree WHERE child = 106; 

root 
------ 
    103