Thử thách truy vấn đệ quy - ví dụ đơn giản về cha/con

Question

Lưu ý: với sự trợ giúp từ RhodiumToad trên #postgresql, tôi đã đến một giải pháp mà tôi đã đăng là câu trả lời. Nếu bất cứ ai có thể cải thiện về điều này, xin vui lòng kêu vang!

Tôi chưa thể điều chỉnh previous recursive query solution thành biểu đồ tuần hoàn theo hướng sau bao gồm nhiều nút "gốc" (tổ tiên-ít). Tôi đang cố gắng để viết một truy vấn mà đầu ra là những gì thường được gọi là một bảng đóng cửa: một bảng nhiều-nhiều mà các cửa hàng mỗi đường đi từ mỗi nút cho mỗi hậu duệ của nó và với bản thân:

1 2 11 8 4 5 7 
\/ | | \ |/
    3 | \ 6 
    \ | \/
    9 |  10 
    \/ /
    12 13 
     \/
     14 

CREATE TABLE node (
    id  SERIAL PRIMARY KEY, 
    node_name VARCHAR(50) NOT NULL 
); 

CREATE TABLE node_relations (
    id     SERIAL PRIMARY KEY, 
    ancestor_node_id INT REFERENCES node(id), 
    descendant_node_id INT REFERENCES node(id) 
); 

INSERT into node (node_name) 
SELECT 'node ' || g FROM generate_series(1,14) g; 

INSERT INTO node_relations(ancestor_node_id, descendant_node_id) VALUES 
(1,3),(2,3),(4,6),(5,6),(7,6),(3,9),(6,10),(8,10),(9,12),(11,12),(10,13),(12,14),(13,14); 

Thật khó để xác định (các) vấn đề - tôi có thiếu số node_relation hàng không? Truy vấn có sai không?

WITH RECURSIVE node_graph AS (
    SELECT ancestor_node_id, ARRAY[descendant_node_id] AS path, 0 AS level 
    FROM node_relations 

    UNION ALL 
    SELECT nr.ancestor_node_id, ng.path || nr.descendant_node_id,ng.level + 1 AS level 
    FROM node_graph ng 
    JOIN node_relations nr ON nr.descendant_node_id = ng.ancestor_node_id 
) 
SELECT path[array_upper(path,1)] AS ancestor, 
     path[1] AS descendant, 
     path, 
     level as depth 
FROM node_graph 
ORDER BY level, ancestor; 

Output dự kiến:

ancestor | descendant | path 
---------+------------+------------------ 
1  | 3   | "{1,3}" 
1  | 9   | "{1,3,9}" 
1  | 12   | "{1,3,9,12}" 
1  | 14   | "{1,3,9,12,14}" 
2  | 3   | "{2,3}" 
2  | 9   | "{2,3,9}" 
2  | 12   | "{2,3,9,12}" 
2  | 14   | "{2,3,9,12,14}" 
3  | 9   | "{3,9}" 
3  | 12   | "{3,9,12}" 
3  | 14   | "{3,9,12,14}" 
4  | 6   | "{4,6}" 
4  | 10   | "{4,6,10}" 
4  | 13   | "{4,6,10,13}" 
4  | 14   | "{4,6,10,13,14}" 
5  | 6   | "{5,6}" 
5  | 10   | "{5,6,10}" 
5  | 13   | "{5,6,10,13}" 
5  | 14   | "{5,6,10,13,14}" 
6  | 10   | "{6,10}" 
6  | 13   | "{6,10,13}" 
6  | 14   | "{6,10,13,14}" 
7  | 6   | "{7,6}" 
7  | 10   | "{7,6,10}" 
7  | 13   | "{7,6,10,13}" 
7  | 14   | "{7,6,10,13,14}" 
8  | 10   | "{8,10}" 
8  | 13   | "{8,10,13}" 
8  | 14   | "{8,10,13,14}" 
9  | 12   | "{9,12}" 
9  | 14   | "{9,12,14}" 
10  | 13   | "{10,13}" 
10  | 14   | "{10,13,14}" 
11  | 12   | "{11,12}" 
11  | 14   | "{11,12,14}" 
12  | 14   | "{12,14}" 
13  | 14   | "{13,14}" 

Answer 1

Với sự giúp đỡ từ RhodiumToad trên #postgresql, tôi đã đến giải pháp này:

WITH RECURSIVE node_graph AS (
    SELECT ancestor_node_id as path_start, descendant_node_id as path_end, 
      array[ancestor_node_id, descendant_node_id] as path 
    FROM node_relations 

    UNION ALL 

    SELECT ng.path_start, nr.descendant_node_id as path_end, 
      ng.path || nr.descendant_node_id as path 
    FROM node_graph ng 
    JOIN node_relations nr ON ng.path_end = nr.ancestor_node_id 
) 
SELECT * from node_graph order by path_start, array_length(path,1); 

Kết quả chính xác như mong đợi.

Answer 2

tôi thấy hai vấn đề với truy vấn:

1. phần không đệ quy không xác định các nút gốc. Bạn cần phải hoặc explicitely chọn rằng việc sử dụng WHERE descendant_node_id = 14 hay "động" sử dụng:

   SELECT .. 
   FROM node_relations nr1 
   WHERE NOT EXISTS (SELECT 1 
           FROM node_relations nr2 
           WHERE nr2.ancestor_node_id = nr1.descendant_node_id) 
   

2. với điểm xuất phát đúng, con đường là chưa hoàn chỉnh vì nó sẽ bỏ lỡ điểm nút cuối cùng trong tập hợp ở phần đệ quy. Vì vậy, trong truy vấn bên ngoài, bạn cần phải thêm ancestor_node_id vào đường dẫn được tạo.

Vì vậy, các truy vấn sẽ trông như thế này:

WITH RECURSIVE node_graph AS (
    SELECT nr1.id, nr1.ancestor_node_id, nr1.descendant_node_id, ARRAY[nr1.descendant_node_id] AS path, 0 as level 
    FROM node_relations nr1 
    WHERE NOT EXISTS (SELECT 1 
         FROM node_relations nr2 
         WHERE nr2.ancestor_node_id = nr1.descendant_node_id) 

    UNION ALL 

    SELECT nr.id, nr.ancestor_node_id, nr.descendant_node_id, nr.descendant_node_id || ng.path, ng.level + 1 as level 
    FROM node_relations nr 
    JOIN node_graph ng ON ng.ancestor_node_id = nr.descendant_node_id 

) 
SELECT ancestor_node_id||path as path, -- add the last element of the sub-tree to the path 
     level as depth 
FROM node_graph 
ORDER BY level 

Đây là SQLFiddle: http://sqlfiddle.com/#!15/e646b/3

Answer 3

Một cách tiếp cận thay thế sẽ được đi qua đồ thị theo thứ tự đảo ngược:

WITH RECURSIVE cte AS (
    SELECT array[r.ancestor_node_id, r.descendant_node_id] AS path 
    FROM node_relations r 
    LEFT JOIN node_relations r0 ON r0.ancestor_node_id = r.descendant_node_id 
    WHERE r0.ancestor_node_id IS NULL -- start at the end 

    UNION ALL 
    SELECT r.ancestor_node_id || c.path 
    FROM cte c 
    JOIN node_relations r ON r.descendant_node_id = c.path[1] 
    ) 
SELECT path 
FROM cte 
ORDER BY path; 

này tạo ra một tập hợp con với mỗi đường đi từ mỗi nút gốc để hậu duệ cuối cùng của nó. Đối với những cây sâu cũng trải ra rất nhiều điều này sẽ đòi hỏi ít hoạt động tham gia hơn. Để bổ sung thêm mỗi tiểu đường, bạn có thể nối thêm một LATERAL tham gia với bên ngoài SELECT:

WITH RECURSIVE cte AS (
    SELECT array[r.ancestor_node_id, r.descendant_node_id] AS path 
    FROM node_relations r 
    LEFT JOIN node_relations r0 ON r0.ancestor_node_id = r.descendant_node_id 
    WHERE r0.ancestor_node_id IS NULL -- start at the end 

    UNION ALL 
    SELECT r.ancestor_node_id || c.path 
    FROM cte c 
    JOIN node_relations r ON r.descendant_node_id = c.path[1] 
    ) 
SELECT l.path FROM cte, LATERAL ( SELECT path[1:g] AS path FROM generate_series(2, array_length(path,1)) g ) l ORDER BY l.path;

Tôi chạy một thử nghiệm nhanh, nhưng nó không chạy nhanh hơn so với giải pháp RhodiumToad của. Nó vẫn có thể nhanh hơn cho các bảng lớn hoặc rộng. Hãy thử với dữ liệu của bạn.