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