用sql最小化图

kd3sttzy  于 2021-07-26  发布在  Java
关注(0)|答案(1)|浏览(353)

假设我们有一个有向图,定义如下:

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) 可以从第一个表中删除,因为可以访问节点 31 通过节点 2 outuput表应该如下所示:

node | neighbor
 -----------------
   1  | 2
   2  | 3
   3  | 4

如何编写执行此操作的sql查询?

kmynzznz

kmynzznz1#

这里有一种方法:

with recursive cte as (
    select node, neighbor, 1 is_initial from graph
    union all 
    select c.node, g.neighbor, 0
    from cte c
    inner join graph g on g.node = c.neighbor
)
select node, neighbor
from graph g
where not exists (
        select 1 
        from cte c
        where c.node = g.node and c.neighbor = g.neighbor and c.is_initial = 0
    )
order by node, neighbor

这只使用第一个表(我称之为 graph ). 我们首先用递归查询生成所有可能的路径。这与闭包表非常相似,但是有一个额外的列, is_initial ,指示路径是来自原始表,还是在进一步迭代过程中生成的。
然后,剩下要做的就是过滤图以删除匹配“非初始”路径的元组。
db小提琴演示:

node | neighbor
---: | -------:
   1 |        2
   2 |        3
   3 |        4

相关问题