Re: Transitive Closure

• 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 -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=