Re: transitive closure of a graph

From: Serge Rielau <srielau_at_ca.ibm.com>
Date: Wed, 12 Oct 2005 21:02:58 -0400
Message-ID: <3r5q2aFhpulgU1_at_individual.net>

vc wrote:

> 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
>>
>>Unless I missed something it's a complete and generic mapping up to
>>Oracle 10gR2.

> 
> 
> How do you implement depth first traversal without a UDF ?

Where did I say I excluded UDFs? I like UDF :-) Cheers
Serge

-- 
Serge Rielau
DB2 SQL Compiler Development
IBM Toronto Lab

Received on Thu Oct 13 2005 - 03:02:58 CEST