Re: transitive closure of a graph

Serge Rielau wrote:
> Mikito Harakiri wrote:
> > Mikito Harakiri wrote:
> >
> >>Transitive closure (TC) of a graph is
> >>
> >>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.
> >
> >
> > Oops, it's actually quite obvious
> >
> > with TransClosedEdges (tail, head) as
> > ( select tail, head from Edges
> > where tail <> head --*******
> > union all
> > select e.tail, ee.head from Edges e, TransClosedEdges ee
> > where e.head = ee.tail
> > and e.tail <> ee.head --*******
> > )
> > select distinct * from TransClosedEdges
> >
> > Graeme handles more general case, hence the complication.
> >
> There will be a new developerWorks article on mapping CONnECT BY to DB2
> tomorrow (if all goes well).

There is July 2003 article by Torsten Steinbach. I guess your article would address 10g features, cycle handling first of all. Looking forward to read it.

Interestingly, that recursive "with" was brought up in past flame wars "A" vs. "B". (As if technical excellence really matters:-). It's amaising what difference a tiny standard uncomplience makes -- I mean "union all" instead of "union". Suddenly, transitive closure for graph with cycles is not expressible anymore. Received on Wed Oct 12 2005 - 12:27:53 CDT