Re: transitive closure of a graph

Adam Machanic wrote:
> "Mikito Harakiri" <mikharakiri_nospaum_at_yahoo.com> wrote in message
> news:1129086273.571304.231100_at_f14g2000cwb.googlegroups.com...
> >
> > If I see the problem correctly, here is step-by-step execution
> >
> > 1.
> > AE, EA, AB, BA, CD, DC, BE, EB, CE, EC -- all included;
> > the other edges in the candidate set
> > AA, BB, CC, DD, EE -- all excluded as invalidating tail <> head
> > predicate
> >
> > 2. AE+EB=AB, AE+EC=AC, ..., AD, DA, AC, CA, BD, DB, BC, CB, -- all
> > included;
>
> Assume the following recursive CTE:
>
> with TransClosedEdges (point1, point2) as
> ( select point1, point2 from Edges
> where point1 <> point2
> union all
> select e.point1, ee.point2 from Edges e, TransClosedEdges ee
> where e.point2 = ee.point1
> and e.point1 <> ee.point2
> )
> select distinct * from TransClosedEdges
>
> What actually happens is:
>
> 1.
> AE, EA, AB, BA, CD, DC, BE, EB, CE, EC -- all included;
+ED, DE

>
> 2. For each anchor row, the recursive part is called. We'll follow the AE
> row, and then only follow one other row from each recursive part:
> - AE is used as anchor
> - AB, ED
> - AB is used as anchor
> - BE, BA
> - BE is used as anchor
> - EA, EB
> - EA is uned as anchor
> - AE, AB

I dont't understand this explanation at all.

On the other hand, it is obvious, that the union semantics would have taken care of the problem automatically, so that even my very first solution doesn't need any correction. Since the number of distinct pairs of nodes is limited, inflating temporary table should terminate.

> ... and we've now found ourselves in an endless loop. But we don't have
> enough data to get out of the loop. We only see the anchor row. We have no
> access to the previous rows. Thus the need for string or binary
> concatenation.
>
>
> > P.S. Please don't remove the crossposts, as I might be lazy to look
> > each of the 3 groups for followups.
>
> I'm posting from the Microsoft public news server so I don't have the
> comp.databases hierarchy. Sorry!
>
>
> --
> Adam Machanic
> SQL Server MVP
> http://www.datamanipulation.net
> --
Received on Wed Oct 12 2005 - 07:05:06 CEST