假设我们有一个有向图,定义如下:
node | neighbor
-----------------
1 | 2
1 | 3
2 | 4
2 | 3
3 | 4
上表只定义了两个节点之间的边,一对 (1,2)
例如,表示该节点 1
以及 2
由一条边连接,这是一张图。
我还有一个图的传递闭包表,这个表包含了图的所有可能路径(例如: (1,3)
存在两次,因为它可以直接或通过路径到达 1=>2=>3
),表格如下:
node | neighbor
-----------------
1 | 2
1 | 3
2 | 4
2 | 3
3 | 4
1 | 3
1 | 4
1 | 4
2 | 4
从这两个表中,我想返回一个最小化的图而不丢失任何可达性,一个想法是只返回不依赖于这两个表的边,下面是一个示例: (1,2)
在第一张table上 (2,3)
是在第二个,因此 (1,3)
可以从第一个表中删除,因为可以访问节点 3
从 1
通过节点 2
outuput表应该如下所示:
node | neighbor
-----------------
1 | 2
2 | 3
3 | 4
如何编写执行此操作的sql查询?
1条答案
按热度按时间kmynzznz1#
这里有一种方法:
这只使用第一个表(我称之为
graph
). 我们首先用递归查询生成所有可能的路径。这与闭包表非常相似,但是有一个额外的列,is_initial
,指示路径是来自原始表,还是在进一步迭代过程中生成的。然后,剩下要做的就是过滤图以删除匹配“非初始”路径的元组。
db小提琴演示: