Câu hỏi Cấu trúc cây và đệ quy


Sử dụng cơ sở dữ liệu PostgreSQL 8.4.14, tôi có một bảng biểu diễn 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 Danh sách điều khiển truy cập cho các đơ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 chế độ xem để xác định xem đơn vị có kế thừa ACL từ tổ tiên hay không:

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ể có được đơn vị gần nhất KHÔNG PHẢI kế thừa ACL từ tổ tiên? Kết quả mong đợi của tôi sẽ trông giống như bảng / chế độ xem sau:

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

13
2017-11-01 19:42


gốc


1 câu hỏi rất hay. Như luôn luôn, nên đưa phiên bản PostgreSQL của bạn vào. - Erwin Brandstetter


Các câu trả lời:


Truy vấn với một CTE đệ quy có thể làm công việc. Yêu cầu PostgreSQL 8,4 hoặc sau đó:

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 phá vỡ ở chân thứ hai của UNION Là n.acl IS NULL. Cùng với đó, truy vấn sẽ dừng ngang qua cây ngay khi acl được tìm thấy.
Trong trận chung kết SELECT chúng tôi chỉ trả lại các hàng ở nơi acl được tìm thấy. Voilá.

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


13
2017-11-01 21:02



Hoàn hảo, cảm ơn! - jabu.10245