Làm thế nào để đi qua cấu trúc cây cấu trúc phân cấp ngược bằng truy vấn đệ quy

Question

Tôi đang sử dụng PostgreSQL 9.1 để truy vấn dữ liệu có cấu trúc cây phân cấp, bao gồm các cạnh (hoặc các phần tử) với các kết nối tới các nút. Dữ liệu thực sự dành cho các mạng luồng, nhưng tôi đã trừu tượng hóa vấn đề với các kiểu dữ liệu đơn giản. Xem xét ví dụ tree bảng. Mỗi cạnh có các thuộc tính độ dài và diện tích, được sử dụng để xác định một số chỉ số hữu ích từ mạng.

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

Có thể minh họa dưới đây, trong đó các cạnh được biểu diễn bằng A-E được kết nối với các nút 1-5. NULL to_node (Ø) đại diện cho nút kết thúc. from_node luôn là duy nhất, do đó, nó có thể hoạt động như PK. Nếu mạng này chảy giống như một drainage basin, nó sẽ là từ trên xuống dưới, nơi mà các cạnh nhánh bắt đầu là A, B, C và các dòng chảy kết thúc cạnh là E.

Các documentation for WITH cung cấp một ví dụ tốt đẹp về cách sử dụng biểu đồ tìm kiếm trong truy vấn đệ quy. Vì vậy, để có được thông tin "chuyển tiếp", truy vấn bắt đầu ở cuối và hoạt động ngược lại:

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 

Điều trên có ý nghĩa và cân tốt cho các mạng lớn. Ví dụ, tôi có thể thấy cạnh B là 3 cạnh từ cuối và đường dẫn tiến là {B,D,E} với tổng chiều dài 3,5 từ đầu đến cuối.

Tuy nhiên, tôi không thể tìm ra cách tốt để tạo truy vấn ngược lại. Tức là, từ mỗi cạnh, các cạnh tích lũy, độ dài và khu vực tích lũy là gì. Sử dụng WITH RECURSIVE, là tốt nhất tôi có là:

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 

Tôi muốn xây dựng uẩn vào nhiệm kỳ thứ hai của truy vấn đệ quy, vì mỗi cạnh hạ lưu kết nối với 1 hoặc nhiều cạnh thượng nguồn, nhưng aggregates are not allowed with recursive queries. Ngoài ra, tôi biết rằng kết nối là cẩu thả, vì kết quả with recursive có nhiều điều kiện tham gia cho edge.

Kết quả dự kiến ​​cho điều ngược lại/về phía sau truy vấn là:

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 

Làm thế nào tôi có thể viết truy vấn cập nhật này?

Lưu ý rằng cuối cùng tôi quan tâm hơn đến việc tích lũy độ dài chính xác và tổng số vùng và các thuộc tính của đường dẫn là để gỡ lỗi. Trong trường hợp thế giới thực của tôi, các con đường chuyển tiếp lên đến vài trăm, và tôi mong đợi các đường dẫn ngược lại trong hàng chục nghìn cho các lưu vực lớn và phức tạp.

Answer 1

CẬP NHẬT 2: Tôi viết lại truy vấn đệ quy ban đầu để tất cả tích lũy/tập hợp được thực hiện bên ngoài phần đệ quy. Nó sẽ hoạt động tốt hơn so với phiên bản trước của câu trả lời này. Điều này rất giống với số answer từ @a_horse_with_no_name cho một câu hỏi tương tự.

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 
; 

Kết quả như mong đợi:

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