Re: Concurrency in an RDB

From: NENASHI, Tegiri <tnmail42_at_gmail.com>
Date: Sat, 30 Dec 2006 20:34:57 +0100 (CET)
Message-ID: <Xns98A99467F621asdgba@194.177.96.26>

"Aloha Kakuikanu" <aloha.kakuikanu_at_yahoo.com> wrote in news:1167505108.559571.271200_at_n51g2000cwc.googlegroups.com:

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

Very well.

>

>> Why you call it
>> adjacency ?

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

You called the transitive closure matrix the adjacency matrix after you mapped non-zeros to ones. Why ?

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

I do not. It is a claim without meaning.

>

>> 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"?

You know what is the least fixed point and how it is in connection to recursion ?

>A similar skewed symmetry is
> http://en.wikipedia.org/wiki/Principle_of_least_action

I do not know what "Principle_of_least_action" it does not sound like mathematical words. The fixed point is a mathematical conception.

> Eventually it get explained
> http://en.wikipedia.org/wiki/Principle_of_least_action#Further_developm
> ent
>

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

If the multiplication is the boolean 'and', the product has the least fixed point and the recursion is finite and it is more effective than the exponent.

>
>
Received on Sat Dec 30 2006 - 13:34:57 CST