Re: Concurrency in an RDB

NENASHI, Tegiri wrote:
> "Aloha Kakuikanu" <aloha.kakuikanu_at_yahoo.com> wrote in
> > In matrix language transitive closure is exponent. Exponent is
> > important operator but not basic algebraic operation like addition and
> > multiplication.
>
> What is the mathrix language ? How you write the transitive closure in the
> matrix language ?

Consider adjacency matrix of a graph. It's a square matrix with dimensions equal to the number of nodes. It is conventional to enumerate graph nodes with numbers from 1 to N, therefore, matching nodes with matrix columns and rows. With this arrangement matrix entry aij naturally correspond to an edge from node i to node j. If there is indeed such an edge in a graph, then we define a_ij=1; otherwise, a_ij=0.

For our purposes the powers of adjacency matrix are especially interesting. The entry in column i and row j of the adjacency matrix raised in the n-th power is the number of paths of length n from node i to node j.

In general, the power of adjacency matrix, doesn't have be an adjacency matrix anymore. There are various ways to fix this problem, and we'll return to this later. For now, given an adjacency matrix A, consider a formal series

Ta = 1 + A + A^2 + ...

Where 1 is the identity matrix. What kind of matrix TA adding all the adjacency matrix powers produces? The reader can easily convince himself that an entry in the column i, row j of the matrix A_n is the number of paths of length n from node i to node j in the original graph. Then, an entry in the matrix TA is the number of paths [of any length] from node i to node j.

For adjacency matrices corresponding to directed acyclic graphs the powers would evaluate to 0 for sufficiently large n, and the formal series TA is finite. In other words, all the paths in a directed acyclic graph have their length bounded.

Given transitive closure series matrix Ta, if we just change any nonzero number into 1, then we'll obtain an adjacency matrix!

Next, let's arrange the matrix powers sum a little bit differently

Ta = 1 + (A + A^2 + ...) = 1 + A(1 + A + A^2 + ...)

The series in the parenthesis, is again TA, hence

Ta = 1 + A Ta

could be written as

Ta = (1 - A )^(-1)

Therefore we can apply this method to calculate transitive closure even in the case when power series is infinite. There is a snag, however. Not every matrix can be inverted! Technically, matrix should be free of 0 eigenvalues.

A natural way to overcome this difficulty is to introduce a variable scalar factor "lambda":

Ta = 1 + lambda A + lambda^2 A^2 + ...

, because for adjacency values all nonzero values are equivalent. (The rigorous way to fix this is to switch to <min,+> algebra aka tropical arithmetics). Then we could select lambda such that matrix has no deficient eigenvalues.

A more elegant way to handle this problem is to introduce constant factorial coefficients:

Ta = 1 + A + A^2/2 + A^3/6 + ...

Now Ta is well defined for any graph, and it is formally a matrix exponent. Received on Fri Dec 29 2006 - 21:23:50 CET