检索层次结构组...具有无限递归

Question

我有一个这样的表,其中包含链接:

key_a    key_b
--------------
a        b        
b        c
g        h     
a        g       
c        a
f        g

不是很整洁和无限递归......

key_a = parent key_b = child

需要一个查询,它将重新组合并为每个层次组(父级+直接子级+间接子级)赋予一个数字:

key_a    key_b    nb_group
--------------------------
a        b        1
a        g        1
b        c        1
**c        a**        1
f        g        2
g        h        2

**link responsible of infinite loop**

因为我们有

ABCA

- >只想显示如图所示的链接.

任何的想法 ？

提前致谢

Answer 1

问题是你并没有真正处理严格的层次结构; 你正在处理有向图,其中一些图有循环.请注意,您的nbgroup#1没有任何规范的根 - 由于来自ca的循环引用,它可能是a,b或c.

处理这个问题的基本方法是根据图形技术进行思考,而不是递归.实际上,迭代方法(不使用CTE)是我在SQL中可以想到的唯一解决方案.这里解释了基本方法.

这是一个SQL Fiddle,它提供了一个解决周期和共享叶案例的解决方案.注意它使用迭代(具有故障保护以防止失控进程)和表变量来操作; 我认为没有任何解决方法.还要注意更改的样本数据(ag更改为ah;下面说明).

如果你深入研究SQL,你会注意到我从链接中给出的解决方案中改变了一些关键的东西.该解决方案处理的是无向边缘,而边缘是有向的(如果使用了无向边缘,则由于ag连接,整个样本集是单个组件).

这就是我在样本数据中将ag更改为ah的原因.如果只共享叶节点,那么您对问题的说明很简单; 这是我编码的规范.在这种情况下,啊和gh都可以捆绑到它们的正确组件而没有问题,因为我们担心来自父节点的可达性(即使给定周期).

但是,当您共享分支时,您不清楚要显示的内容.考虑ag链接:鉴于此,gh可以存在于任一组件(agh或fgh)中.你把它放在第二个,但它可能在第一个,而不是？这种模糊性是为什么我没有尝试在这个解决方案中解决它.

编辑:要清楚,在上面的解决方案中,如果遇到共享分支,它会将整个集合视为单个组件.不是你上面描述的,但在问题澄清后必须改变.希望这能让你接近.