Re: transitive closure of a graph

vc wrote:
> Mikito Harakiri wrote:
> > Including the AB edge twice is a big problem! Apparently, the source of
> > the problem is DB2 and SQLServer 2005 artifact that they allow "union
> > all" only...
>
> The duplicates are not a problem at all. Since you represent the
> undirected graph with two bidirectional ones, the recursive query
> naturally fails as it encounters cycles. It will fail even on a
> trivial graph like that:
>
> 1---2---3
>
> ... if represented like {(1,2), (2,1), (2,3), (3,2)}

I fail to see why. Start with the temporary table

{(1,2), (2,1), (2,3), (3,2)}

First join would produce new edges

{(1,1), (2,2), (3,3), (1,3), (3,1)}

With union semantics the temporary table inflates to

{(1,1), (2,2), (3,3), (1,3), (3,1), (1,2), (2,1), (2,3), (3,2)}

Next join, however, fails to produce any new tuples. The inflation stops -- the execution terminates. Received on Thu Oct 13 2005 - 00:06:26 CEST