Re: Transitive Closure
From: Paul <paul_at_test.com>
Date: Fri, 14 May 2004 00:17:08 +0100
Message-ID: <OlToc.4051$NK4.344959_at_stones.force9.net>
>
> 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?
Date: Fri, 14 May 2004 00:17:08 +0100
Message-ID: <OlToc.4051$NK4.344959_at_stones.force9.net>
Mikito Harakiri wrote:
> Paul <paul_at_test.com> wrote in message news:<%4noc.3394$NK4.266295@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.
Wikipedia says: "...the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R."
So the word "smallest" should cover the case of graphs with cycles.
Paul. Received on Fri May 14 2004 - 01:17:08 CEST