Is there a way to detect a cycle in Hierarchical Queries in SQL Server?

Question

In Oracle, we can use the function CONNECT_BY_ISCYCLE to detect a cycle in Hierarchical Queries. I try to do the same in SQL Server. Is there a way to do this?

Thanks a lot!

Answer 1

Concatenate the records IDs / build a bitmap based on ROW_NUMBERs of the records and verify each new record against the list/bitmap

create table t (id int,pid int)
insert into t values (1,3),(2,1),(3,2)

---

List

Identify Cycles

with cte (id,pid,list,is_cycle) 
as
(
    select      id,pid,',' + cast (id as varchar(max))  + ',',0
    from        t
    where       id = 1

    union all

    select      t.id,t.pid,cte.list + cast (t.id as varchar(10)) +  ',' ,case when cte.list like '%,' + cast (t.id as varchar(10)) + ',%' then 1 else 0 end
    from        cte join t on t.pid = cte.id
    where       cte.is_cycle = 0
)
select      *
from        cte
where       is_cycle = 1

---

id  pid list        is_cycle
--  --- ----        --------
1   3   ,1,2,3,1,   1

---

Traverse Thorough Graph with Cycles

with cte (id,pid,list) 
as
(
    select      id,pid,',' + cast (id as varchar(max))  + ','
    from        t
    where       id = 1

    union all

    select      t.id,t.pid,cte.list + cast (t.id as varchar(10)) +  ',' 
    from        cte join t on t.pid = cte.id
    where       cte.list not like '%,' + cast (t.id as varchar(10)) + ',%'
)
select      *
from        cte

---

id  pid list
1   3   ,1,
2   1   ,1,2,
3   2   ,1,2,3,

Bitmap

ID should be a sequence of numbers starting with 1.
If necessary generate it using ROW_NUMBER.

Identify Cycles

with cte (id,pid,bitmap,is_cycle) 
as
(
    select      id,pid,cast (power(2,id-1) as varbinary(max)) ,0
    from        t
    where       id = 1

    union all

    select      t.id,t.pid,cast (cte.bitmap|power(2,t.id-1) as varbinary(max)),case when cte.bitmap & power(2,t.id-1) > 0 then 1 else 0 end
    from        cte join t on t.pid = cte.id
    where       cte.is_cycle = 0
)
select      *
from        cte
where       is_cycle = 1

---

id  pid bitmap      is_cycle
1   3   0x00000007  1

Traverse Thorough Graph with Cycles

with cte (id,pid,bitmap) 
as
(
    select      id,pid,cast (power(2,id-1) as varbinary(max))
    from        t
    where       id = 1

    union all

    select      t.id,t.pid,cast (cte.bitmap|power(2,t.id-1) as varbinary(max))
    from        cte join t on t.pid = cte.id
    where       cte.bitmap & power(2,t.id-1) = 0
)
select      *
from        cte

---

id  pid bitmap
1   3   0x00000001
2   1   0x00000003
3   2   0x00000007

Answer 2

If you look at a specific path across a hierarchy, you can say that it is a singled/doubled linked list (normally singled).

One easy way of making sure that you don't have a close loop, it to traverse the chain through two paths, each with its own index, one that advances by one position while the other by two.

If there is no closed loop, one of the indices will fall at some point (e.g. will reach the root node of the hierarchy which does not have any parent). If there is a loop, you will reach a point where the two indices point to the same node within the chain.

This is a rather old method but works beautifully.