Sfida query ricorsiva - semplice esempio genitore/figlio

Question

Nota: con l'aiuto di RhodiumToad su #postgresql, sono arrivato a una soluzione, che ho inviato come risposta. Se qualcuno può migliorare su questo, per favore carillon!

Non sono stato in grado di adattare uno previous recursive query solution al seguente grafico aciclico diretto che include più nodi "root" (senza antenato). Sto cercando di scrivere una query cui uscita è ciò che è comunemente noto come una tabella di chiusura: una tabella molti-a-molti che memorizza ogni cammino da ogni nodo a ciascuno dei suoi discendenti e per sé:

1 2 11 8 4 5 7 
\/ | | \ |/
    3 | \ 6 
    \ | \/
    9 |  10 
    \/ /
    12 13 
     \/
     14 

CREATE TABLE node (
    id  SERIAL PRIMARY KEY, 
    node_name VARCHAR(50) NOT NULL 
); 

CREATE TABLE node_relations (
    id     SERIAL PRIMARY KEY, 
    ancestor_node_id INT REFERENCES node(id), 
    descendant_node_id INT REFERENCES node(id) 
); 

INSERT into node (node_name) 
SELECT 'node ' || g FROM generate_series(1,14) g; 

INSERT INTO node_relations(ancestor_node_id, descendant_node_id) VALUES 
(1,3),(2,3),(4,6),(5,6),(7,6),(3,9),(6,10),(8,10),(9,12),(11,12),(10,13),(12,14),(13,14); 

È stato difficile individuare i problemi: mi mancano le righe node_relation? La query è sbagliata?

WITH RECURSIVE node_graph AS (
    SELECT ancestor_node_id, ARRAY[descendant_node_id] AS path, 0 AS level 
    FROM node_relations 

    UNION ALL 
    SELECT nr.ancestor_node_id, ng.path || nr.descendant_node_id,ng.level + 1 AS level 
    FROM node_graph ng 
    JOIN node_relations nr ON nr.descendant_node_id = ng.ancestor_node_id 
) 
SELECT path[array_upper(path,1)] AS ancestor, 
     path[1] AS descendant, 
     path, 
     level as depth 
FROM node_graph 
ORDER BY level, ancestor; 

Output previsto:

ancestor | descendant | path 
---------+------------+------------------ 
1  | 3   | "{1,3}" 
1  | 9   | "{1,3,9}" 
1  | 12   | "{1,3,9,12}" 
1  | 14   | "{1,3,9,12,14}" 
2  | 3   | "{2,3}" 
2  | 9   | "{2,3,9}" 
2  | 12   | "{2,3,9,12}" 
2  | 14   | "{2,3,9,12,14}" 
3  | 9   | "{3,9}" 
3  | 12   | "{3,9,12}" 
3  | 14   | "{3,9,12,14}" 
4  | 6   | "{4,6}" 
4  | 10   | "{4,6,10}" 
4  | 13   | "{4,6,10,13}" 
4  | 14   | "{4,6,10,13,14}" 
5  | 6   | "{5,6}" 
5  | 10   | "{5,6,10}" 
5  | 13   | "{5,6,10,13}" 
5  | 14   | "{5,6,10,13,14}" 
6  | 10   | "{6,10}" 
6  | 13   | "{6,10,13}" 
6  | 14   | "{6,10,13,14}" 
7  | 6   | "{7,6}" 
7  | 10   | "{7,6,10}" 
7  | 13   | "{7,6,10,13}" 
7  | 14   | "{7,6,10,13,14}" 
8  | 10   | "{8,10}" 
8  | 13   | "{8,10,13}" 
8  | 14   | "{8,10,13,14}" 
9  | 12   | "{9,12}" 
9  | 14   | "{9,12,14}" 
10  | 13   | "{10,13}" 
10  | 14   | "{10,13,14}" 
11  | 12   | "{11,12}" 
11  | 14   | "{11,12,14}" 
12  | 14   | "{12,14}" 
13  | 14   | "{13,14}" 

Answer 1

Con l'aiuto di RhodiumToad su #postgresql, sono arrivato a questa soluzione:

WITH RECURSIVE node_graph AS (
    SELECT ancestor_node_id as path_start, descendant_node_id as path_end, 
      array[ancestor_node_id, descendant_node_id] as path 
    FROM node_relations 

    UNION ALL 

    SELECT ng.path_start, nr.descendant_node_id as path_end, 
      ng.path || nr.descendant_node_id as path 
    FROM node_graph ng 
    JOIN node_relations nr ON ng.path_end = nr.ancestor_node_id 
) 
SELECT * from node_graph order by path_start, array_length(path,1); 

Il risultato è esattamente come previsto.

Answer 2

vedo due problemi con la query:

1. parte non ricorsiva non specifica il nodo principale. È necessario sia esplicitamente selezionare che l'uso di WHERE descendant_node_id = 14 o "dinamico" utilizzando:

   SELECT .. 
   FROM node_relations nr1 
   WHERE NOT EXISTS (SELECT 1 
           FROM node_relations nr2 
           WHERE nr2.ancestor_node_id = nr1.descendant_node_id) 
   

2. con il punto di partenza corretto, il percorso non è completa in quanto mancherà il nodo finale durante l'aggregazione nella parte ricorsiva. Quindi nella query esterna è necessario aggiungere ancestor_node_id al percorso generato.

Quindi la query sarà simile a questa:

WITH RECURSIVE node_graph AS (
    SELECT nr1.id, nr1.ancestor_node_id, nr1.descendant_node_id, ARRAY[nr1.descendant_node_id] AS path, 0 as level 
    FROM node_relations nr1 
    WHERE NOT EXISTS (SELECT 1 
         FROM node_relations nr2 
         WHERE nr2.ancestor_node_id = nr1.descendant_node_id) 

    UNION ALL 

    SELECT nr.id, nr.ancestor_node_id, nr.descendant_node_id, nr.descendant_node_id || ng.path, ng.level + 1 as level 
    FROM node_relations nr 
    JOIN node_graph ng ON ng.ancestor_node_id = nr.descendant_node_id 

) 
SELECT ancestor_node_id||path as path, -- add the last element of the sub-tree to the path 
     level as depth 
FROM node_graph 
ORDER BY level 

Ecco la SQLFiddle: http://sqlfiddle.com/#!15/e646b/3

Answer 3

Un approccio alternativo sarebbe quello di attraversare il grafico in ordine inverso:

WITH RECURSIVE cte AS (
    SELECT array[r.ancestor_node_id, r.descendant_node_id] AS path 
    FROM node_relations r 
    LEFT JOIN node_relations r0 ON r0.ancestor_node_id = r.descendant_node_id 
    WHERE r0.ancestor_node_id IS NULL -- start at the end 

    UNION ALL 
    SELECT r.ancestor_node_id || c.path 
    FROM cte c 
    JOIN node_relations r ON r.descendant_node_id = c.path[1] 
    ) 
SELECT path 
FROM cte 
ORDER BY path; 

Questo produce un sottoinsieme di ogni percorso da ciascun nodo radice al suo discendente finale. Per gli alberi profondi che si estendono anche molto, ciò comporterebbe molte meno operazioni di unione. Per aggiungere inoltre ogni sotto-percorso, si potrebbe aggiungere un LATERAL unirsi alla esterno SELECT:

WITH RECURSIVE cte AS (
    SELECT array[r.ancestor_node_id, r.descendant_node_id] AS path 
    FROM node_relations r 
    LEFT JOIN node_relations r0 ON r0.ancestor_node_id = r.descendant_node_id 
    WHERE r0.ancestor_node_id IS NULL -- start at the end 

    UNION ALL 
    SELECT r.ancestor_node_id || c.path 
    FROM cte c 
    JOIN node_relations r ON r.descendant_node_id = c.path[1] 
    ) 
SELECT l.path FROM cte, LATERAL ( SELECT path[1:g] AS path FROM generate_series(2, array_length(path,1)) g ) l ORDER BY l.path;

ho fatto un test rapido, ma non ha funzionato più velocemente di quanto la soluzione di RhodiumToad. Potrebbe essere ancora più veloce per tavoli grandi o larghi. Prova con i tuoi dati.