Re: transitive closure of a graph
From: Serge Rielau <srielau_at_ca.ibm.com>
Date: Wed, 12 Oct 2005 14:55:19 -0400
Message-ID: <3r54gtFh58caU1_at_individual.net>
>
>
> 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 Unless I missed something it's a complete and generic mapping up to Oracle 10gR2.
Date: Wed, 12 Oct 2005 14:55:19 -0400
Message-ID: <3r54gtFh58caU1_at_individual.net>
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 Unless I missed something it's a complete and generic mapping up to Oracle 10gR2.
Cheers
Serge
-- Serge Rielau DB2 SQL Compiler Development IBM Toronto LabReceived on Wed Oct 12 2005 - 20:55:19 CEST