Re: Transitive Closure

From: Paul <paul_at_test.com>
Date: Sat, 15 May 2004 10:22:30 +0100
Message-ID: <Ajlpc.3453$wI4.382625_at_wards.force9.net>


Mikito Harakiri wrote:
> 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?

OK I've just been reading up in this (for example Date & Darwen's "Third Manifesto" book mentions it) and the suggestion is to have a "generalized transitive closure" operator that includes these kind of aggregates along paths. For example see here: http://citeseer.ist.psu.edu/nag95implementing.html

They say "... the heavy machinery required to support general recursion is not really necessary for this particular class of recursive queries, and yet, most recursive queries that occur in practice are in fact expressible as generalized transitive closure".

I haven't found an example of a query that isn't expressible as a generalized transitive closure though, does anyone know of one?

>> 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 + ...

OK. This definition is the generalized version of transitive closure because the matrix can have values other than zero or one?

> On the other hand
> exp(A) = I + A +A^2/2 + A^3/6 + ...

OK, I don't understand the relevance of this to what we're discussing though.

> Which one is correct TC definition?

Well I guess they're equivalent for standard TC on finite relations, though yours extends to the generalized case and is constructive (in that it supplies a formula to calculate it), and the other is not (but is a definition more suited to infinite relations, not that that interests us here).

Paul. Received on Sat May 15 2004 - 11:22:30 CEST

Original text of this message