Re: So let me get this right: (Was: NFNF vs 1NF ...)

"paul c" <toledobythesea_at_oohay.moc> wrote in message news:CTQOd.357547$Xk.278687_at_pd7tw3no...
> "what is the theoretical problem with RVA's?"
>
> not to mention opportunities (recursion? parts explosion?).

One doesn't have to go outside classic relational model in order to approach transitive closure. I could suggest only a glimpse of a theory here, but the idea is to watch the analogy with matrix algebra.

Binary relation A(x,y) can be naturally interpreted as an adjacency matrix A(i,j) where A(i,j) = 1 for all the tuples (i,j) in the relation A and 0 otherwise. Then, transitive closure of the adjacency matrix is matrix TCA calculated as an infinite sum

TCA(i,j) = I + A + A^2 + A^3 + ...

where I is the identity matrix.

It is likely that some TCA elements would no longer be 0 and 1. The interpretation of those values, however, is very natural: TCA(i,j) is an aggregate flow from node i to node j in the original graph. What matters is whether this flow is 0 or not. Therefore, changing all the nonzero elements of the TCA matrix into 1s would produce adjacency matrix for transitive closure relation.

Next, even though it is very suggestive to rewrite TCA matrix as

TCA(i,j) = (I-A)^(-1)

I would prefer another route. Indeed, one have to worry about conditions when matrix inversion is legal (and this is normally a problem for graphs with cycles), whereas if we consider

TCA(i,j) = I + A + A^2/2! + A^3/3! + ...

then TCA exists for any matrix A. Note, that we distinguish if the matrix entries are 0 or not, - this is why all those factors don't really matter.

In the last formula, the infinite series for matrix exponent is too obvious to be ignored.

That's it: transitive closure is an exponent operator. Now, in standard math exponent can't be written as a finite closed form expression with multiplication and addition. Nobody suggests, however, abandoning the realm of numbers in favor of some fancy numbers that merely *have a potential* to accomodate exponent. Math folks just live with infinite series.

P.S. The analogy between matrices and graphs becomes even more evident when we consider tropical arithmetics instead of classical one. Received on Thu Feb 10 2005 - 23:45:26 CET