树的结构和递归 [英] 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

I' m使用视图来确定某个单元是否正在继承祖先的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是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屋！