Come attraversare una struttura gerarchica della struttura ad albero all'indietro usando le domande ricorsive

Question

Sto usando PostgreSQL 9.1 per interrogare i dati gerarchici strutturati ad albero, costituiti da spigoli (o elementi) con connessioni ai nodi. I dati sono in realtà per le reti di streaming, ma ho astratto il problema a tipi di dati semplici. Considera la tabella tree di esempio. Ogni spigolo ha attributi di lunghezza e area, che sono usati per determinare alcune metriche utili dalla rete.

CREATE TEMP TABLE tree (
    edge text PRIMARY KEY, 
    from_node integer UNIQUE NOT NULL, -- can also act as PK 
    to_node integer REFERENCES tree (from_node), 
    mode character varying(5), -- redundant, but illustrative 
    length numeric NOT NULL, 
    area numeric NOT NULL, 
    fwd_path text[], -- optional ordered sequence, useful for debugging 
    fwd_search_depth integer, 
    fwd_length numeric, 
    rev_path text[], -- optional unordered set, useful for debugging 
    rev_search_depth integer, 
    rev_length numeric, 
    rev_area numeric 
); 
CREATE INDEX ON tree (to_node); 
INSERT INTO tree(edge, from_node, to_node, mode, length, area) VALUES 
('A', 1, 4, 'start', 1.1, 0.9), 
('B', 2, 4, 'start', 1.2, 1.3), 
('C', 3, 5, 'start', 1.8, 2.4), 
('D', 4, 5, NULL, 1.2, 1.3), 
('E', 5, NULL, 'end', 1.1, 0.9); 

Che può essere illustrato di seguito, in cui i bordi rappresentati da A-E sono collegati con i nodi 1-5. Il NULL to_node (Ø) rappresenta il nodo finale. Il from_node è sempre univoco, quindi può fungere da PK. Se questa rete scorre come un drainage basin, sarebbe da cima a fondo, dove cominciando bordi tributari sono A, B, C e il bordo deflusso finale è E.

Il documentation for WITH fornire un bell'esempio di come utilizzare i grafici di ricerca nelle query ricorsive. Quindi, per ottenere le informazioni "in avanti", la query inizia alla fine, e funziona al contrario:

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 

È possibile che questo ha un senso, e scala bene per reti di grandi dimensioni. Ad esempio, posso vedere il bordo B a 3 spigoli dalla fine e il percorso in avanti è {B,D,E} con una lunghezza totale di 3,5 dalla punta alla fine.

Tuttavia, non riesco a trovare un buon modo per creare una query inversa. Cioè, da ciascun lato, quali sono i bordi, le lunghezze e le aree "a monte" accumulate. Utilizzando WITH RECURSIVE, il meglio che ho è:

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 

desidero costruire aggregati nel secondo termine della query ricorsiva, poiché ogni bordo a valle collega a 1 o più bordi a monte, ma aggregates are not allowed with recursive queries. Inoltre, sono a conoscenza del fatto che il join è sciatto, dal momento che il risultato with recursive ha più condizioni di join per edge.

Il risultato atteso per il retro/indietro interrogazione è:

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 

Come posso scrivere questa query di aggiornamento?

Nota che alla fine sono più preoccupato di accumulare valori precisi di lunghezza e area e che gli attributi del percorso sono per il debug. Nel mio caso del mondo reale, i percorsi in avanti ammontano a un paio di centinaia, e mi aspetto percorsi inversi a decine di migliaia per bacini di grandi dimensioni e complessi.

Answer 1

UPDATE 2: ho riscritto la query ricorsive originale in modo che tutto l'accumulo/aggregazione è fatto al di fuori della parte ricorsiva. Dovrebbe funzionare meglio della versione precedente di questa risposta. Questo è molto simile allo answer da @a_horse_with_no_name per una domanda simile.

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 
; 

I risultati sono come previsto:

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