Tree Cấu trúc và Đệ quy

Question

Sử dụng một cơ sở dữ liệu PostgreSQL 8.4.14, tôi có một bảng đại diện cho một cấu trúc cây như ví dụ sau:

CREATE TABLE unit (
    id bigint NOT NULL PRIMARY KEY, 
    name varchar(64) NOT NULL, 
    parent_id bigint, 
    FOREIGN KEY (parent_id) REFERENCES unit (id) 
); 
INSERT INTO unit VALUES (1, 'parent', NULL), (2, 'child', 1) 
         , (3, 'grandchild A', 2), (4, 'grandchild B', 2); 

id | name  | parent_id 
----+--------------+----------- 
    1 | parent  |   
    2 | child  |   1 
    3 | grandchild A |   2 
    4 | grandchild B |   2 

Tôi muốn tạo một Access Control List cho những đơn vị, trong đó mỗi đơn vị có thể có ACL riêng của nó, hoặc kế thừa nó từ tổ tiên gần nhất với một ACL riêng.

CREATE TABLE acl (
    unit_id bigint NOT NULL PRIMARY KEY, 
    FOREIGN KEY (unit_id) REFERENCES unit (id) 
); 
INSERT INTO acl VALUES (1), (4); 

unit_id 
--------- 
     1 
     4 

Tôi đang sử dụng một cái nhìn để xác định xem một đơn vị được kế thừa đó là ACL từ một tổ tiên:

CREATE VIEW inheriting_acl AS 
    SELECT u.id AS unit_id, COUNT(a.*) = 0 AS inheriting 
    FROM unit AS u 
    LEFT JOIN acl AS a ON a.unit_id = u.id 
    GROUP BY u.id; 

unit_id | inheriting 
---------+------------ 
     1 | f 
     2 | t 
     3 | t 
     4 | f 

Câu hỏi của tôi là: làm thế nào tôi có thể nhận được đơn vị khu vực gần đó là KHÔNG kế thừa ACL từ một tổ tiên? Kết quả mong đợi của tôi trông giống như bảng/chế độ xem sau:

unit_id | acl 
---------+------------ 
     1 | 1 
     2 | 1 
     3 | 1 
     4 | 4 

Answer 1

Truy vấn có số recursive CTE có thể thực hiện công việc. Yêu cầu PostgreSQL 8.4 hay muộn:

WITH RECURSIVE next_in_line AS (
    SELECT u.id AS unit_id, u.parent_id, a.unit_id AS acl 
    FROM unit u 
    LEFT JOIN acl a ON a.unit_id = u.id 

    UNION ALL 
    SELECT n.unit_id, u.parent_id, a.unit_id 
    FROM next_in_line n 
    JOIN unit u ON u.id = n.parent_id AND n.acl IS NULL 
    LEFT JOIN acl a ON a.unit_id = u.id 
    ) 
SELECT unit_id, acl 
FROM next_in_line 
WHERE acl IS NOT NULL 
ORDER BY unit_id 

Điều kiện nghỉ ngơi trong trận lượt đi thứ hai của UNION là n.acl IS NULL. Cùng với đó, các truy vấn dừng lại đi qua các cây càng sớm càng một acl được tìm thấy.
Trong số SELECT cuối cùng, chúng tôi chỉ trả lại các hàng có một số acl được tìm thấy. Voilá.

Ngoài ra: Đây là mô hình chống sử dụng tên chung chung, không mô tả id làm tên cột. Đáng buồn thay, một số ORM làm điều đó theo mặc định. Gọi nó là unit_id và bạn không phải sử dụng bí danh trong truy vấn mọi lúc.