Re: Concurrency in an RDB

"Aloha Kakuikanu" <aloha.kakuikanu_at_yahoo.com> wrote in news:1167423830.038947.326860_at_a3g2000cwd.googlegroups.com:

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

It is correct.

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

It is almost correct but '1' (the diagonal) is not in the matrix A.

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

It is correct.

>
> Given transitive closure series matrix Ta,

It is not the transitive closure because the diagonal is not in the matrix A and it is in the matrix Ta.

>if we just change any
> nonzero number into 1, then we'll obtain an adjacency matrix!

No it is a transitive closure matrix plus the diagonal. Why you call it adjacency ? It is a known naive method to make the transitive closure of graph. The Warshall method is more effective. 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

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

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

Why it is more elegant ? It is the Taylor series for the exponential. The coefficients do not have no information for the transitive closure and '1' is incorrect. The exponent will need more steps to converge, it is not very effective. It is used in software mathematical packages if Warshall is not there.

>
> Now Ta is well defined for any graph, and it is formally a matrix
> exponent.

It is not if the relation is not reflexive.

>
>
Received on Sat Dec 30 2006 - 19:30:23 CET