sql - 使用递归公用表表达式检测 SQL 图中的循环
问题描述
给定具有循环的有向图,如何仅使用标准 SQL 检测和列出循环?输入 = 图边和一个根节点,我们从中计算传递闭包。输出 = 循环中的节点列表。
解决方案
CREATE TABLE #myEdge (
ID INT IDENTITY(1,1) PRIMARY KEY,
NodeIDFrom INT,
NodeIDTo INT
)
INSERT INTO #myEdge(NodeIDFrom, NodeIDTo) VALUES (4, 5),(5, 6),(6, 4);
DECLARE @rootNode AS integer = 4;
--compute the transitive closure from this root. column Niveau holds the recursion nesting level.
WITH cte_transitive_closure(rootNode, NodeFrom, NodeTo, Niveau)
AS (
SELECT @rootNode, NULL, @rootNode, 0
UNION ALL
SELECT rootNode, e.NodeIDFrom, e.NodeIDTo, Niveau+1
FROM cte_transitive_closure AS cte
JOIN #myEdge AS e ON cte.NodeTo=e.NodeIdFrom
WHERE Niveau < 99
)
SELECT *
INTO #transitive_closure
FROM cte_transitive_closure;
SELECT * FROM #transitive_closure;
--starting from root as a reached target, move back in the trace until the root is hit again.
WITH cte_cycle(NodeFrom, NodeTo, Cycle)
AS (
SELECT @rootNode,NULL,0
UNION ALL
SELECT t.NodeFrom, t.NodeTo, 0
FROM cte_cycle AS cte
JOIN #transitive_closure AS t ON cte.NodeFrom = t.NodeTo
WHERE t.NodeFrom != @rootNode AND Cycle=0
UNION ALL
SELECT t.NodeFrom, t.NodeTo, 1
FROM cte_cycle AS cte
JOIN #transitive_closure AS t ON cte.NodeFrom = t.NodeTo
WHERE t.NodeFrom = @rootNode AND Cycle=0
)
SELECT DISTINCT * FROM cte_cycle;
result set:
NodeFrom -> NodeTo (Cycle)
4 -> NULL (0)
4 -> 5 (1)
5 -> 6 (0)
6 -> 4 (0)
推荐阅读
- reactjs - 在 Reducer 操作中对数据进行排序
- python - 使用循环堆叠从循环生成的数据帧
- python - 如何将整数列表列表转换为字节列表而不会在python3中耗尽内存?
- python - “cudaGetDevice() 失败”尽管遵循了说明
- c# - 将自定义按钮背景/边框绑定到自定义属性
- angular - Angular 9.0.4,子模块中找不到异步管道(git repo)
- c# - AutoMapper:多对多关系映射
- spring-boot - Spring Boot How to run multiple method with @Scheduled
- python - ValueError:检查输入时出错:预期 simple_rnn_1_input 具有 3 个维度,但得到的数组具有形状 (32、813、701、3)
- mysql - INNER JOIN 创建重复的主键错误,但它不应该