# Re: Transitive Closure

Date: Fri, 14 May 2004 19:51:39 +0300

Message-ID: <40a4f84f$1_at_post.usenet.com>

- Post for FREE via your newsreader at post.usenet.com ****

"Mikito Harakiri" <mikharakiri_at_iahu.com> wrote in message
news:JO6pc.21$7Q3.228_at_news.oracle.com...

*>
*

> "Paul" <paul_at_test.com> wrote in message

*> news:OlToc.4051$NK4.344959_at_stones.force9.net...
**> > Mikito Harakiri wrote:
**> > > Paul <paul_at_test.com> wrote in message
**> news:<%4noc.3394$NK4.266295_at_stones.force9.net>...
**> > >
**> > >>But we can extend our DBMS by explicity including a "TClose" operator
**> > >>that takes a (two-columned) relation as its argument and returns a
**> > >>relation that is the transitive closure.
**> > >
**> > > Is TClose a well defined operator? For a relation with 2 attributes we
**> > > could interpret it as Edges and look after TC of graph, but how is it
**> > > defined when there is a third column? For one thing, that relation
**> > > can't be interpreted as Edges anymore. Next, how is TClose defined for
**> > > graphs with cycles?
**> >
**> > Well, it would have to only be used for relations with two attributes
**> > that are of the same type, which does kind of break the symmetry of the
**> > other relational operators I must admit. Alternatively you could say it
**> > takes 3 arguments: one relation and two column names.
**>
**> How about 3 column relation
**>
**> table WeightedGraph (
**> head integer,
**> tail integer,
**> weight real
**> )
**>
**> Naturally, TC should be 3 column relation as well with aggregated weights
**> along the paths. Can you express this query with "aggregate agnostic"
**> transitive closure operator?
**>
**> > Wikipedia says: "...the transitive closure of a binary relation R on a
**> > set X is the smallest transitive relation on X that contains R."
**>
**> I have better definition. Assume that graph adjacency matrix is A. Then,
**> transitive closure is
**>
**> (1-A)^(-1) = I + A + A^2 + A^3 + ...
**>
**> On the other hand
**>
**> exp(A) = I + A +A^2/2 + A^3/6 + ...
**>
**> Which one is correct TC definition?
*

What type have the elements of A ?

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

- Usenet.com - The #1 Usenet Newsgroup Service on The Planet! *** http://www.usenet.com Unlimited Download - 19 Seperate Servers - 90,000 groups - Uncensored -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=