transitive closure of a graph

with TransClosedEdges (tail, head) as
( select tail, head from Edges
  union all
  select e.tail, ee.head from Edges e, TransClosedEdges ee   where e.head = ee.tail
)
select distinct * from TransClosedEdges

except that this query might never terminate. I was surprised to learn from Graeme Birchall's DB2 cookbook that there is no really satisfactory solution to this problem. Graeme suggests building a path and searching for repeated node entry in the path. Is there a more satisfactory approach that doesn't require string parsing? I understand that the problem of finding loops is undecideable in general case, but, cmon, we are taking about very narrowly scoped transitive closure problem here.

BTW, TC with goofy oracle syntax is just 3 lines

select connect_by_root(tail), tail
from Edges
connect by nocycle prior head = tail

with cycles being automatically taken care of. Received on Wed Oct 12 2005 - 04:01:58 CEST