Using a CTE to traverse a graph containing cycles

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2005 Forums

Transact-SQL (2005)

Using a CTE to traverse a graph containing cycles

Author

Topic

jthg
Starting Member

5 Posts

Posted - 2009-01-21 : 13:42:39

This is sort of a fundamental question about using CTEs. If I have a table with the following schema and data:

Nodes
----------
id | name
1  | node1
2  | node2
3  | node3
4  | node4

Paths (these are unidirectional)
---------
from | to
1    | 2
2    | 3
1    | 4
3    | 1

How can I write a query which figures out all nodes reachable from node2?

If I do the following:

with Route as (
  select 2 as id
 union all
  select p.to as id
  from Route r, Paths p
  where r.id = p.from
)
select * from Route

I'll get infinite recursion.

If I add one more WHERE clause and do

with Route as (
  select 2 as id
 union all
  select p.to as id
  from Route r, Paths p
  where r.id = p.from
   and not exists (select count(*) from Route r2 where r2.id = p.to)
)
select * from Route

I'll get the error "Recursive member of a common table expression 'Route' has multiple recursive references."

Is there any way to write a CTE for this scenerio?

Skorch
Constraint Violating Yak Guru

300 Posts

Posted - 2009-01-21 : 13:56:33

What are your expected results here?

TG
Master Smack Fu Yak Hacker

6065 Posts

Posted - 2009-01-21 : 14:03:54

Since your data contains a circular reference I think your options are to use option(maxrecursion n) or to do it the 2000 way - using your own while loop.

Be One with the Optimizer
TG

jthg
Starting Member

5 Posts

Posted - 2009-01-21 : 16:23:48

quote:
Originally posted by Skorch

What are your expected results here?

My desired result is:

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2009-01-21 : 16:34:15

See http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=115290

E 12°55'05.63"
N 56°04'39.26"

Skorch
Constraint Violating Yak Guru

300 Posts

Posted - 2009-01-21 : 16:39:59

I guess I'm confused. You originally asked for a query that would list all of the nodes reachable from node2. Shouldn't that just be 3 since in the Paths table node2 [from] corresponds to [to] 3?

If so, this should give you the correct result:

create table #nodes (id int, name varchar(20))
insert into #nodes (id, name) values (1, 'node1')
insert into #nodes (id, name) values (2, 'node2')
insert into #nodes (id, name) values (3, 'node3')
insert into #nodes (id, name) values (4, 'node4')

create table #paths ([from] int, [to] int)
insert into #paths ([from], [to]) values (1,2)
insert into #paths ([from], [to]) values (2,3)
insert into #paths ([from], [to]) values (1,4)
insert into #paths ([from], [to]) values (3,1)

with cte as
(
select p.[to] as id
from #nodes n
inner join #paths p on n.id = p.[from]
where n.id = 2
)
select * from cte

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2009-01-21 : 16:44:54

Unidirectional paths too...
And what about hops? 2 -> 3 -> 1 ?

E 12°55'05.63"
N 56°04'39.26"

jthg
Starting Member

5 Posts

Posted - 2009-01-23 : 10:02:39