Re: transitive closure of a graph
From: Serge Rielau <srielau_at_ca.ibm.com>
Date: Wed, 12 Oct 2005 07:23:13 -0400
Message-ID: <3r4a14Fhi2lsU1_at_individual.net>
>
>
> 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).
Date: Wed, 12 Oct 2005 07:23:13 -0400
Message-ID: <3r4a14Fhi2lsU1_at_individual.net>
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).
Cheers
Serge
-- Serge Rielau DB2 SQL Compiler Development IBM Toronto LabReceived on Wed Oct 12 2005 - 13:23:13 CEST