Wie durchläuft man eine hierarchische Baumstrukturstruktur mit rekursiven Abfragen?

Question

Ich benutze PostgreSQL 9.1, um hierarchische baumstrukturierte Daten abzufragen, die aus Kanten (oder Elementen) mit Verbindungen zu Knoten bestehen. Die Daten sind eigentlich für Stream-Netzwerke, aber ich habe das Problem auf einfache Datentypen abstrahiert. Betrachten Sie das Beispiel tree Tabelle. Jede Kante verfügt über Längen- und Bereichsattribute, die zum Ermitteln einiger nützlicher Metriken aus dem Netzwerk verwendet werden.

Welche können unten dargestellt werden, wo die Kanten von A-E mit den Knoten 1-5 verbunden sind. Der NULL to_node (Ø) repräsentiert den Endknoten. Die from_node ist immer eindeutig, sodass sie als PK fungieren kann. Wenn dieses Netzwerk wie ein drainage basin fließt, wäre es von oben nach unten, wo die Ausgangs Tributary Kanten A, B, C und der Abströmkante endet E. ist

Die documentation for WITH ein schönes Beispiel liefern wie Suchgraphen in rekursiven Abfragen verwendet werden. Also, die „vorwärts“ Informationen zu erhalten, beginnt die Abfrage am Ende, und arbeitet nach hinten:

WITH RECURSIVE search_graph AS (
    -- Begin at ending nodes 
    SELECT E.from_node, 1 AS search_depth, E.length 
    , ARRAY[E.edge] AS path -- optional 
    FROM tree E WHERE E.to_node IS NULL 

    UNION ALL 
    -- Accumulate each edge, working backwards (upstream) 
    SELECT o.from_node, sg.search_depth + 1, sg.length + o.length 
    , o.edge|| sg.path -- optional 
    FROM tree o, search_graph sg 
    WHERE o.to_node = sg.from_node 
) 
UPDATE tree SET 
    fwd_path = sg.path, 
    fwd_search_depth = sg.search_depth, 
    fwd_length = sg.length 
FROM search_graph AS sg WHERE sg.from_node = tree.from_node; 

SELECT edge, from_node, to_node, fwd_path, fwd_search_depth, fwd_length 
FROM tree ORDER BY edge; 

edge | from_node | to_node | fwd_path | fwd_search_depth | fwd_length 
------+-----------+---------+----------+------------------+------------ 
A |   1 |  4 | {A,D,E} |    3 |  3.4 
B |   2 |  4 | {B,D,E} |    3 |  3.5 
C |   3 |  5 | {C,E} |    2 |  2.9 
D |   4 |  5 | {D,E} |    2 |  2.3 
E |   5 |   | {E}  |    1 |  1.1 

Die oben macht Sinn, und skaliert gut für große Netzwerke. Zum Beispiel kann ich sehen, Kante B ist 3 Kanten vom Ende, und der Vorwärtsweg ist {B,D,E} mit einer Gesamtlänge von 3,5 von der Spitze bis zum Ende.

Allerdings kann ich nicht eine gute Möglichkeit, eine umgekehrte Abfrage zu erstellen. Das heißt, von jeder Kante, was sind die angesammelten "Upstream" -Kanten, Längen und Flächen. Verwendung WITH RECURSIVE, die best ich habe, ist:

WITH RECURSIVE search_graph AS (
    -- Begin at starting nodes 
    SELECT S.from_node, S.to_node, 1 AS search_depth, S.length, S.area 
    , ARRAY[S.edge] AS path -- optional 
    FROM tree S WHERE from_node IN (
    -- Starting nodes have a from_node without any to_node 
    SELECT from_node FROM tree EXCEPT SELECT to_node FROM tree) 

    UNION ALL 
    -- Accumulate edges, working forwards 
    SELECT c.from_node, c.to_node, sg.search_depth + 1, sg.length + c.length, sg.area + c.area 
     , c.edge || sg.path -- optional 
    FROM tree c, search_graph sg 
    WHERE c.from_node = sg.to_node 
) 
UPDATE tree SET 
    rev_path = sg.path, 
    rev_search_depth = sg.search_depth, 
    rev_length = sg.length, 
    rev_area = sg.area 
FROM search_graph AS sg WHERE sg.from_node = tree.from_node; 

SELECT edge, from_node, to_node, rev_path, rev_search_depth, rev_length, rev_area 
FROM tree ORDER BY edge; 

edge | from_node | to_node | rev_path | rev_search_depth | rev_length | rev_area 
------+-----------+---------+----------+------------------+------------+---------- 
A |   1 |  4 | {A}  |    1 |  1.1 |  0.9 
B |   2 |  4 | {B}  |    1 |  1.2 |  1.3 
C |   3 |  5 | {C}  |    1 |  1.8 |  2.4 
D |   4 |  5 | {D,A} |    2 |  2.3 |  2.2 
E |   5 |   | {E,C} |    2 |  2.9 |  3.3 

Ich mag würde Aggregate in den zweiten Term der rekursive Abfrage bauen, da jede stromabwärtige Kante auf 1 oder vielen stromaufwärtigen Kanten verbindet, aber aggregates are not allowed with recursive queries. Außerdem bin ich mir bewusst, dass der Join schlampig ist, da das Ergebnis with recursive mehrere Join-Bedingungen für edge hat.

Das erwartete Ergebnis für die Rückwärts/rückwärts Abfrage ist:

edge | from_node | to_node | rev_path | rev_search_depth | rev_length | rev_area 
------+-----------+---------+-------------+------------------+------------+---------- 
A |   1 |  4 | {A}   |    1 |  1.1 |  0.9 
B |   2 |  4 | {B}   |    1 |  1.2 |  1.3 
C |   3 |  5 | {C}   |    1 |  1.8 |  2.4 
D |   4 |  5 | {A,B,D}  |    3 |  3.5 |  3.5 
E |   5 |   | {A,B,C,D,E} |    5 |  6.4 |  6.8 

Wie kann ich diese Update-Abfrage schreiben?

Beachten Sie, dass ich letztlich mehr darauf bedacht bin, genaue Längen- und Bereichsgesamtwerte zu akkumulieren, und dass die Pfadattribute zum Debuggen sind. In meinem realen Fall sind Vorwärtswege bis zu ein paar hundert und ich erwarte umgekehrte Pfade in Zehntausenden für große und komplexe Einzugsgebiete.

Answer 1

UPDATE 2: Ich schrieb die ursprüngliche rekursive Abfrage neu, so dass die gesamte Akkumulation/Aggregation außerhalb des rekursiven Teils erfolgt. Es sollte besser als die vorherige Version dieser Antwort sein. Dies ist sehr ähnlich der answer von @a_horse_with_no_name für eine ähnliche Frage.

WITH 
    RECURSIVE search_graph(edge, from_node, to_node, length, area, start_node) AS 
    (
     SELECT edge, from_node, to_node, length, area, from_node AS "start_node" 
     FROM tree 
     UNION ALL 
     SELECT o.edge, o.from_node, o.to_node, o.length, o.area, p.start_node 
     FROM tree o 
    JOIN search_graph p ON p.from_node = o.to_node 
    ) 
    SELECT array_agg(edge) AS "edges" 
     -- ,array_agg(from_node) AS "nodes" 
      ,count(edge) AS "edge_count" 
      ,sum(length) AS "length_sum" 
      ,sum(area) AS "area_sum" 
    FROM search_graph 
    GROUP BY start_node 
    ORDER BY start_node 
; 

Ergebnisse sind wie erwartet:

start_node | edges  | edge_count | length_sum | area_sum 
------------+-------------+------------+------------+------------ 
    1   | {A}   |   1 |  1.1 |  0.9 
    2   | {B}   |   1 |  1.2 |  1.3 
    3   | {C}   |   1 |  1.8 |  2.4 
    4   | {D,B,A}  |   3 |  3.5 |  3.5 
    5   | {E,D,C,B,A} |   5 |  6.4 |  6.8