Given a table Edge(Source, Sink) representing a directed graph, the transitive closure TC(Source, Sink) is the set of all paths in the graph. Relational algebra (on which SQL is based) can’t express it. However, you can express it using first-order logic rules:
TC(X,Y) :- Edge(X,Y)
TC(X,Y) :- Edge(X,Z), TC(Z,Y)
or
“there is a path from X to Y if there is an edge from X to Y, or an edge from X to some Z such that there is a path from Z to Y”.
SQLServer 2005 now offers you a way to do this using recursive tables:
with TC(Source,Sink,Depth) as
(
select Source, Sink, 0 as Depth
from Edge
union all
select e.Source, t.Sink , t.Depth+1 as Depth
from Edge e, TC t
where e.Sink = t.Source
and t.Depth < 10
)
select …
Note that we have limited the recursion depth to 10 to force termination. This has been sufficient for a recent project. The default recursion depth in SqlServer2005 is 100, but you can set it to be higher (up to 32767). So if your graph has paths with lengths over 32767, you won’t get a complete result. However, this seems to work in practice.
