Jak przejść hierarchiczną strukturę struktury drzewa wstecz za pomocą kwerend rekursywnych

Question

Używam PostgreSQL 9.1 do kwerendy hierarchiczne drzewa struktury danych, składający się z krawędzi (lub elementów) z połączeniami do węzłów. Dane są w rzeczywistości dla sieci strumieniowych, ale wyodrębniłem problem do prostych typów danych. Rozważmy przykład tabeli tree. Każda krawędź ma atrybuty długości i obszaru, które służą do określania niektórych przydatnych danych z sieci.

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

Które można zilustrować poniżej, gdzie krawędzie reprezentowane przez A-E są połączone z węzłami 1-5. NULL to_node (Ø) reprezentuje węzeł końcowy. from_node jest zawsze unikalny, więc może działać jako PK. Jeśli sieć ta płynie jak drainage basin, to jest z góry na dół, w którym wyjściowe Dopływu krawędziami A, B, C i zakończenie krawędzi odpływowej jest E.

documentation for WITH ładnego przykład sposobu korzystania z wykresów wyszukiwania w zapytaniach rekurencyjnych. Tak więc, aby uzyskać „do przodu” informacji, zapytanie zaczyna się na końcu, a działa wstecz:

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 

Powyższy sens, i dobrze skaluje do dużych sieci. Na przykład, widzę krawędź B ma 3 krawędzie od końca, a ścieżka przednia to {B,D,E} o całkowitej długości 3,5 od końca do końca.

Jednak nie mogę znaleźć dobrego sposobu na zbudowanie zapytania odwrotnego. To znaczy, z każdej krawędzi, jakie są nagromadzone krawędzie, długości i obszary "w górę". Korzystanie WITH RECURSIVE najlepsza mam to:

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 

Chciałbym zbudować agregaty do drugiego terminu zapytania rekurencyjne, ponieważ każda krawędź dalszy łączy się 1 lub wielu upstream krawędzi, ale aggregates are not allowed with recursive queries. Ponadto zdaję sobie sprawę, że sprzężenie jest niechlujne, ponieważ wynik with recursive ma wiele warunków łączenia dla edge.

Oczekiwany wynik na odwrocie/tył zapytania to:

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 

Jak mogę napisać tej kwerendy aktualizacji?

Zauważ, że ostatecznie jestem bardziej zaniepokojony gromadzeniem dokładnych sum długości i powierzchni oraz że atrybuty ścieżki służą do debugowania. W moim prawdziwym świecie ścieżki do przodu sięgają nawet kilkuset, a dla dużych i złożonych zlewni oczekuję odwrotnych dróg w dziesiątkach tysięcy.

Answer 1

UPDATE 2: przepisałem oryginalnego zapytania rekurencyjne tak że wszystko akumulacja/agregacja odbywa się poza rekurencyjnego części. Powinien działać lepiej niż poprzednia wersja tej odpowiedzi. To jest bardzo podobne do answer z @a_horse_with_no_name dla podobnego pytania.

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 
; 

Wyniki są zgodnie z oczekiwaniami:

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