Re: Concurrency in an RDB

NENASHI, Tegiri wrote:
> "Aloha Kakuikanu" <aloha.kakuikanu_at_yahoo.com> wrote in
> > 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.
>
> It is almost correct but '1' (the diagonal) is not in the matrix A.

It is reflective transitive closure.

> Why you call it
> adjacency ?

http://en.wikipedia.org/wiki/Adjacency_matrix

 It is a known naive method to make the transitive closure of
> graph. The Warshall method is more effective.

Warshall method is algorithm. I share the idea expressed in one of Libkin papers that algebraic methods are superior to algorithms.

> The mtrix multiplication
> is the same find of the fixed point like the logical definition:
>
> Logical: Ta(x,y) =A(x,y) \/ exists(z) Ta(x, z) /\ A(z,x) -- Ta is the
> least fixed point
> Matrix: Ta = A + Ta*A -- Ta is the least fixed point

Why it is the "least"? A similar skewed symmetry is http://en.wikipedia.org/wiki/Principle_of_least_action Eventually it get explained
http://en.wikipedia.org/wiki/Principle_of_least_action#Further_development

> >
> > 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.
>
> When is it that the series is infinite for the finite relation ?

When graph has cycles. Received on Sat Dec 30 2006 - 19:58:28 CET