代码之家 › 专栏 › 技术社区 › Dante

遍历闭包表

postgresql sql

Dante · 技术社区 · 3 年前

看看这个闭包表:

祖宗	后代	路径长度
1.	1.	0
2.	2.	0
3.	3.	0
4.	4.	0
2.	4.	1.
5.	5.	0
2.	5.	1.
6.	6.	0
4.	6.	1.
2.	6.	2.
7.	7.	0
4.	7.	1.
2.	7.	2.
8.	8.	0
6.	8.	1.
4.	8.	2.
2.	8.	3.

现在我要按顺序排列:

请注意,节点的所有祖先可能都没有更低的节点编号。是否可以使用SQL查询?

我的尝试: 使用 PostgreSQL documentation section 7.8.2.1. Search Order ,我找到了以下解决方案:

WITH RECURSIVE search_tree(descendant, path) AS (
SELECT descendant, ARRAY[ROW(ct.ancestor, ct.descendant)]
FROM closure_table ct WHERE descendant = 2
UNION ALL
SELECT
ct.descendant, path || ROW(ct.ancestor, ct.descendant)
FROM closure_table ct, search_tree st
WHERE ct.ancestor = st.descendant AND ct.path_length = 1
)
SELECT * FROM search_tree ORDER BY path;

你可以看到 here 。但是我不知道它的效率有多高。

0 回复 | 直到 3 年前

lemon 3 年前

步骤1 :找到你的树根

给定您的输入表,您可以通过选择

所有祖先 路径长度=0 “(只选择一次)
在具有“ 路径长度>0 “(那些至少从级别=1开始找到的节点)。

SELECT ancestor AS root FROM tab WHERE path_length = 0
EXCEPT
SELECT descendant FROM tab WHERE path_length > 0

根
1.
2.
3.

步骤2 :为您实现深度优先搜索二叉树。

这可以通过

扫描“ 祖宗 “值只属于根表(以避免重复)” 后代 “值)
应用深度优先排序。

深度优先订购将基于:

祖先优先
以递归(深度优先)方式,使用 ROW_NUMBER 窗口功能,
pathlength当它向叶子深入时上升,当它向根向上时相同的pathlength下降,使用 CASE 构造来处理这两种情况。

WITH roots AS (
    SELECT ancestor AS root FROM tab WHERE path_length = 0
    EXCEPT
    SELECT descendant FROM tab WHERE path_length > 0
), ranked_nodes AS (
    SELECT *, ROW_NUMBER() OVER(PARTITION BY ancestor, path_length
                                ORDER     BY descendant           ) AS rn
    FROM tab
    INNER JOIN roots
            ON tab.ancestor = roots.root
)
SELECT descendant
FROM ranked_nodes
ORDER BY ancestor, 
         rn, 
         CASE WHEN rn = 1 THEN path_length ELSE -path_length END

查看演示 here 。

上面的一个是广义解决方案,但如果您假设预先知道根(1、2和3)的值,则可以简化查询,如下所示:

WITH ranked_nodes AS (
    SELECT *, ROW_NUMBER() OVER(PARTITION BY ancestor, path_length
                                ORDER     BY descendant           ) AS rn
    FROM tab
    WHERE ancestor <= 3
)
SELECT descendant
FROM ranked_nodes
ORDER BY ancestor, 
         rn, 
         CASE WHEN rn = 1 THEN path_length ELSE -path_length END

祖宗	后代	路径长度
1.	1.	0
2.	2.	0
3.	3.	0
4.	4.	0
2.	4.	1.
5.	5.	0
2.	5.	1.
6.	6.	0
4.	6.	1.
2.	6.	2.
7.	7.	0
4.	7.	1.
2.	7.	2.
8.	8.	0
6.	8.	1.
4.	8.	2.
2.	8.	3.

祖宗	后代	路径长度
1.	1.	0
2.	2.	0
3.	3.	0
4.	4.	0
2.	4.	1.
5.	5.	0
2.	5.	1.
6.	6.	0
4.	6.	1.
2.	6.	2.
7.	7.	0
4.	7.	1.
2.	7.	2.
8.	8.	0
6.	8.	1.
4.	8.	2.
2.	8.	3.

祖宗	后代	路径长度
1.	1.	0
2.	2.	0
3.	3.	0
4.	4.	0
2.	4.	1.
5.	5.	0
2.	5.	1.
6.	6.	0
4.	6.	1.
2.	6.	2.
7.	7.	0
4.	7.	1.
2.	7.	2.
8.	8.	0
6.	8.	1.
4.	8.	2.
2.	8.	3.