Trova padre in modo ricorsivo utilizzando la query

Question

Sto usando postgresql. Ho il tavolo come sotto

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

Voglio scrivere una query sql che darà il genitore finale di input.

cioè immagino io passo 106 come input quindi, la sua uscita sarà 103.

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

Answer 1

Ecco un esempio completo. In primo luogo i 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 

... e alcuni dati ...

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) 

Questo esegue una query ricorsiva su ogni id nel nodo:

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) 

Questo ottiene tutti i discendenti DOVE 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) 

Di seguito vi ottenere il percorso del nodo con 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) 

E supponiamo che si desidera limitare la ricerca ai discendenti con un depth inferiore a tre (si noti che depth non è stato ancora incrementato):

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) 

mi consiglia di utilizzare un tipo di dati ARRAY invece di una stringa per dimostrare il "percorso", ma la freccia è più illustrativo del genitore < => relazione figlio.

Answer 2

Utilizzare WITH RECURSIVE per creare un'espressione di tabella comune (CTE). Per il termine non ricorsiva, ottenere le righe in cui il bambino si trova subito sotto il genitore:

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 

Per il termine ricorsivo, si desidera che i figli di questi bambini.

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 

È possibile filtrare i bambini quando l'interrogazione del CTE:

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

root 
------ 
    103