Re: Transitive Closure

"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? Received on Fri May 14 2004 - 11:40:34 CDT