Re: transitive closure of a graph

Serge Rielau wrote:
> Mikito Harakiri wrote:
> > 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.
> >
> Didn't know about this article :-(. Here is my TOC:
> LEVEL pseudo column
> The CONNECT_BY_ROOT expression
> The SYS_CONNECT_BY_PATH() procedure
> ORDER SIBLINGS BY expression
> The NOCYCLE keyword
> CONNECT_BY_ISCYCLE
> CONNECT_BY_ISLEAF

>

How do you implement depth first traversal without a UDF ?

> Cheers
> Serge
> --
> Serge Rielau
> DB2 SQL Compiler Development
> IBM Toronto Lab
Received on Wed Oct 12 2005 - 23:50:04 CEST