Özyinelemeli sorgular kullanılarak bir hiyerarşik ağaç yapısı yapısını geriye doğru nasıl geçilir?

Question

PostgreSQL 9.1'i, düğümlere bağlantılar içeren kenarlardan (veya öğelerden) oluşan hiyerarşik ağaç yapılandırılmış verileri sorgulamak için kullanıyorum. Veriler aslında akış ağları içindir, ancak sorunu basit veri türleri için soyutladım. Örnek tree tablosunu düşünün. Her kenar, ağdaki bazı yararlı metrikleri belirlemek için kullanılan uzunluk ve alan özelliklerine sahiptir.

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

Aşağıda, A-E tarafından temsil edilen kenarların 1-5 no'lu düğümlerle bağlandığı gösterilebilir. NULL to_node (Ø), son düğümü temsil eder. from_node her zaman benzersizdir, bu yüzden PK olarak davranabilir. Bu ağ bir drainage basin gibi akar, bu üstten başlayarak kolu kenarları, A, B, C ve sona eren çıkış kenarı E

documentation for WITH güzel bir örnek sağlamaktır olan alt olacaktır özyinelemeli sorgularda arama grafiklerini kullanma. Yani, "ileri" bilgi almak için, sorgu sonunda başlar ve geriye doğru çalışır:

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 

yukarıdaki mantıklı ve büyük ağlar için iyi ölçekler. Örneğin, kenardan B kenarının 3 kenarı olduğunu ve ön yolun uçtan uca 3.5 toplam uzunluğu olan {B,D,E} olduğunu görebiliyorum. Ancak, bir ters sorgu oluşturmak için iyi bir yol bulamıyorum. Yani, her kenardan, birikmiş "yukarı yönlü" kenarlar, uzunluklar ve alanlar. WITH RECURSIVE kullanarak, en iyisi bu: Her alt kenar, 1 veya daha çok üst kenarları, ancak aggregates are not allowed with recursive queries bağlandığı için, yinelemeli terimi ikinci terime agrega inşa etmek isteyen

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 

. Ayrıca, with recursive sonucu edge için çoklu birleştirme koşullarına sahip olduğundan, katılımın özensiz olduğunu biliyorum.

ters için beklenen sonuç/geri sorgusu:

Nasıl bu güncelleştirme sorgusu yazabilir

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 

?

Nihayetinde, doğru uzunluk ve alan toplamları biriktirme konusunda daha fazla endişe duyduğumu ve yol özniteliklerinin hata ayıklama için olduğunu unutmayın. Gerçek dünyadaki durumumda, ileriye giden yollar birkaç yüz kadardır ve büyük ve karmaşık havzalar için on binlerce insanda ters yollar bekliyorum.

Answer 1

GÜNCELLEME 2: tüm birikim/toplama özyinelemeli parçası dışında yapılır, böylece Ben orijinal özyinelemeli sorgu yeniden yazdım. Bu cevabın önceki versiyonundan daha iyi performans göstermelidir. Bu, benzer bir soru için @a_horse_with_no_name öğesinden answer'a benzer.

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 
; 

Sonuçlar beklendiği gibidir:

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