Rekursive Abfrage-Challenge - einfaches Eltern/Kind-Beispiel

Question

Hinweis: Mit Hilfe von RhodiumToad auf #postgresql bin ich zu einer Lösung gekommen, die ich als Antwort gepostet habe. Wenn irgendjemand das verbessern kann, bitte läuten!

Ich war nicht in der Lage, eine previous recursive query solution auf die folgenden gerichteten azyklischen Graphen anzupassen, die mehrere "root" (Vorfahren) Knoten enthält. Ich versuche, eine Abfrage, deren Ausgang zu schreiben, was man gemeinhin als Verschlusstabelle bekannt ist: eine many-to-many-Tabelle, die jeden Weg von jedem Knoten zu jedem seiner Nachkommen und selbst speichert:

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); 

Es war schwierig, das Problem (die Probleme) genau zu bestimmen - fehlen mir node_relation Zeilen? Ist die Abfrage falsch?

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; 

Erwartete Ausgabe:

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

Mit Hilfe von RhodiumToad auf #postgresql, ich an dieser Lösung angekommen sind:

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); 

Das Ergebnis ist genau wie erwartet.

Answer 2

Ich sehe zwei Probleme mit der Abfrage:

1. das nicht-rekursive Teil spezifiziert nicht den Root-Knoten. Sie müssen entweder explizit auswählen, dass WHERE descendant_node_id = 14 oder „dynamisch“ mit einem:

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

2. mit dem richtigen Ausgangspunkt, der Pfad nicht abgeschlossen ist, da sie die Endknoten während der Aggregation im rekursiven Teil vermissen. In der äußeren Abfrage müssen Sie daher ancestor_node_id an den generierten Pfad anhängen.

Also die Abfrage würde wie folgt aussehen:

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 

Hier ist die SQLFiddle: http://sqlfiddle.com/#!15/e646b/3

Answer 3

Ein alternativer Ansatz wäre die Grafik in umgekehrter Reihenfolge zu durchlaufen:

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; 

Dies erzeugt eine Teilmenge mit jedem Pfad von jedem Wurzelknoten zu seinem letzten Abkömmling. Bei tiefen Bäumen, die sich ebenfalls weit ausbreiten, würde dies viel weniger Join-Operationen erfordern. Um zusätzlich jeden Teilpfad hinzufügen, können Sie fügen Sie ein LATERAL an den äußeren Verknüpfung 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;

ich einen schnellen Test lief, aber es hat nicht schneller laufen als RhodiumToad Lösung. Bei großen oder großen Tischen kann es immer noch schneller sein. Versuchen Sie es mit Ihren Daten.