用sql计算完全图的边的算法

lf5gs5x2  于 2021-06-26  发布在  Impala
关注(0)|答案(0)|浏览(290)

假设我们有一个表t,它表示(无向)图的边。有两列x和y,其中x列中的条目是起始节点,y列中的条目是结束节点。
例如,下图:

可以用下表表示:

|-----|----|
|  X  |  Y |
|-----|----|
|  a  |  e |
|  b  |  c |
|  d  |  c |
|-----|----|

一个sql查询可以用来生成一个表,其中包含t所暗示的所有不相交完整图的所有边吗?也就是说,如果存在某条路径(任意长度),则通过将任意两个节点与边连接而从t生成的图在他们之间。
对于上面的示例,完成的图形如下所示:

table可以是:

|-----|----|
|  X  |  Y |
|-----|----|
|  a  |  e |
|  b  |  c |
|  d  |  c |
|  b  |  d |
|-----|----|

一般来说,我的印象是,如果不使用某种递归公共表表达式,就不能用sql查询来完成这项工作。通过使用循环,可以通过将t连接到自身来生成由长度为2的路径连接的节点列表,然后再次连接长度为3的路径等,在n步之后停止,其中n是节点数。
但是,我认为在“标准”sql中不可能有这样的循环。有没有一种惯用的sql方法来实现这一点?

暂无答案!

目前还没有任何答案,快来回答吧!

相关问题