Re: transitive closure of a graph

Mikito Harakiri wrote:
> 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)}

The first join will produce

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

Since we eliminate self-loops, it's actually {(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)}

No matter the 'union', the next join will produce {(2,3), (2,1}} and so on:

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

>
> Next join, however, fails to produce any new tuples. The inflation
> stops -- the execution terminates.

No.

Even if we used 'union' instead of 'union all', the execution would not terminate unless we apply an effort to do so (although the set would not grow). Received on Thu Oct 13 2005 - 02:02:29 CEST