树结构和递归 [英] Tree Structure and Recursion

问题描述

使用 PostgreSQL 8.4.14 数据库，我有一个表示树结构的表，如下例所示:

Using a PostgreSQL 8.4.14 database, I have a table representing a tree structure like the following example:

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

我想为这些单元创建一个访问控制列表，其中每个单元可能有自己的 ACL，或者从最近的祖先那里继承它并拥有自己的 ACL.

I want to create an Access Control List for those units, where each unit may have it's own ACL, or is inheriting it from the nearest ancestor with an own ACL.

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

我正在使用视图来确定一个单元是否从祖先那里继承了它的 ACL:

I'm using a view to determine if a unit is inheriting it's ACL from an ancestor:

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

我的问题是:我怎样才能获得不从祖先那里继承 ACL 的最近单元?我的预期结果应该类似于下表/视图:

My question is: how can I get the nearest unit which is NOT inheriting the ACL from an ancestor? My expected result should look similar to the following table/view:

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

推荐答案

使用 递归 CTE 可以完成这项工作.需要 PostgreSQL 8.4 或更高版本:

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

UNION 的第二个分支中的中断条件是 n.acl IS NULL.这样，一旦找到 acl，查询就会停止遍历树.
在最后的 SELECT 中，我们只返回找到 acl 的行.瞧.

The break condition in the second leg of the UNION is n.acl IS NULL. With that, the query stops traversing the the tree as soon as an acl is found.
In the final SELECT we only return the rows where an acl was found. Voilá.

顺便说一句:使用通用的、非描述性的 id 作为列名是一种反模式.可悲的是，一些 ORM 默认情况下会这样做.将其称为 unit_id，您就不必一直在查询中使用别名.

As an aside: It is an anti-pattern to use the generic, non-descriptive id as column name. Sadly, some ORMs do that by default. Call it unit_id and you don't have to use aliases in queries all the time.

这篇关于树结构和递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！