Re: transitive closure of a graph

From: Serge Rielau <srielau_at_ca.ibm.com>
Date: Thu, 13 Oct 2005 17:19:13 -0400
Message-ID: <3r81aoFhcff9U1_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).

>
>
> See your article. Unfortunately, understanding code in C is beyond my
> capabilities. What is "binary-encoded path"? Suppose we have
>
> Name Sal
> ------------ ---
> KING 100
> --> SMITH 50
> -----> JONES 20
> -----> JAMES 30
>
> What is the binary-encoded path for JAMES node is?
>
Teh binary encoded path is a concatenation of INTEGERs. So in "SOURCE" I number the input with ROW_NUMBER() OVER(). Assuming the rows get numbered 1. KING, 2. SMITH, 3. JONES, 4. James. With 256 Bytes / 4 Bytes Integers => 64 Levels So James is be:
0x000000010000000200000004
King is:
0x000000010

Cheers
Serge

-- 
Serge Rielau
DB2 SQL Compiler Development
IBM Toronto Lab

Received on Thu Oct 13 2005 - 23:19:13 CEST