我有一个有向无环图:
DROP TABLE IF EXISTS #Edges
CREATE TABLE #Edges(from_node int, to_node int);
INSERT INTO #Edges VALUES (1,2),(1,3),(1,4),(5,1);
我希望列出所有节点,始终将目标节点列在其来源节点之前。例如:二,三,四,一,五。
它也被称为拓扑排序,如何在SQL中实现呢?
我有一个有向无环图:
DROP TABLE IF EXISTS #Edges
CREATE TABLE #Edges(from_node int, to_node int);
INSERT INTO #Edges VALUES (1,2),(1,3),(1,4),(5,1);
我希望列出所有节点,始终将目标节点列在其来源节点之前。例如:二,三,四,一,五。
它也被称为拓扑排序,如何在SQL中实现呢?
4条答案
按热度按时间ykejflvf1#
您可以使用递归CTE来计算深度。然后按深度排序:
编辑:
我注意到你的边列表中没有“1”。要处理这个问题:
Here是db〈〉小提琴。
mspsb9vt2#
节点可能会列出多次。我们只希望保留第一次出现的节点:
e1xvtsh33#
我发现这个问题遇到了类似的问题。由于@Ludovic和@Gordon的回答都没有完全回答我的所有问题,而且评论的空间也不够,我决定总结一下我自己的答案。
递归查询解决方案很好
基本上,@Gordon的答案是基于图中所有路径的遍历,
cte.lev
列实际上表示从某个起始节点到cte.to_node
的路径长度。循环怎么样?
不清楚的是,当可能有多条路径进入特定节点时(即,如果DAG的无向版本有循环),返回什么。
节点
1
可以从距离为1的初始节点3
直接到达,并且可以通过距离为2的节点2
到达,因此节点1
以不同的路径长度值被扩展了两次。令 v 为两者中的最大值。v 通常可定义为 * 从起始节点到给定节点的最长路径的长度 *。此值对应于拓扑排序。它本质上将节点分割成块,使得对于分别具有值 v1、v2 的任何两个节点 n1、n2,当 *v1当 v1=v2 时,n2 是任意的。(我没有确切的证据,但通过反证,如果这种排序不成立,那么在块中必须有反向边或边,这样值 v 就不成立。)t是最长路径的长度。)
因此,SQL为(original example fiddle,my looped example fiddle)
(这与@Ludovic的答案接近,但Ludovic依赖于按id排序,IMHO无法保证在一般情况下正确排序。
优化
递归CTE现在生成具有
to_node
和路径长度的行。如果某个节点由多个相同长度的路径到达,则每个路径都将扩展到另一递归级别的新行,这将生成重复行,并且对于某些图形,这可能导致组合爆炸。例如,在以下图形中(假设边从左向右)从X1 M8 N1 X经由两条路径到达X1 M7 N1 X节点,但是算法没有将其考虑在内,因此X1 M9 N1 X具有两条路径,X1 M10 N1 X、X1 M11 N1 X甚至具有四条路径。
对于理想环境中基于SQL的解决方案,添加
distinct
就足够了,这将消除D-E
和D-F
边缘的重复扩展:不幸的是,由于SQLServer中的
DISTINCT operator is not allowed in the recursive part of a recursive common table expression 'cte'.
错误,这不起作用。(我实际上使用Oracle,结果类似于ORA-32486 unsupported operation in recursive branch of recursive WITH clause
。)同样,group by
和一些查询嵌套技巧都不能使用。在这一点上,我放弃了SQLServer,但对于Oracle,还有一个基于窗口函数的解决方案。在查询的递归部分,可以将一堆重复行定义为分区,对该分区中的行进行编号,并从潜在的许多重复行中只选择一个。
缺点是当前递归级别的
row_number
不能在where
条件下过滤。因此我们必须忍受重复行通过并扩展到下一个递归级别,在那里它们最终被修剪。然而,这种启发式方法仍然有用-我正在查询Oracledba_dependencies
表,查询没有它根本没有终止。我没有找到在SQLServer中使用这个小技巧的方法,因为SQLServer在递归查询中处理窗口函数的方式不同。抱歉把问题和Oracle的问题混为一谈,但我认为这个主题对任何发现这个问题的人来说都很有趣。
nwlls2ji4#
我需要一个SQLite应用程序的拓扑排序,下面的代码适用于SQLite 3.37.0,使用@Tomáš的代码和数据。在SQLite中,DISTINCT在一个递归CTE中工作。我在节点'C'和'F'之间添加了一个额外的依赖关系,使事情变得更有趣,但没有这个边,它的工作原理是一样的。
我需要确定依赖关系管理系统中处理实体的顺序,类似于@Ludovic的需要,因此我将排序顺序更改为DESC,以便返回的第一个项是要处理的第一个项。
结果: