Re: Demo: Modelling Cost of Travel Paths Between Towns

"--CELKO--" <jcelko212_at_earthlink.net> wrote in message news:18c7b3c2.0411081414.2f0f8b8e_at_posting.google.com...
> That gets all the (travel_cost = 1) edges in the graph. Next, use
> Warshall's algorithm to fill in travel costs on ('c', 'a'), ('d', 'b')
> and so forth. This will work for any adjacency list model. I would
> do the matrix multiplications in a host language like FORTRAN, C or
> Pascal, but I can do it in pure SQL if I have to (see that section in
> SQL FOR SMARTIES).
Matrix product is indeed a nice relational expression (with aggregation and grouping). That would take care of the 2 inner loops in the Warshall's algorithm. What about the outer loop?

From another perspective, given graph adjacency matrix A, transitive closure graph could be expressed by adjacency matrix TA like this:

TA = 1 + A + A^2 + A^3 + ...

In theory, there is an infinite sum on the right side. In practice, A is finite dimensional so that we can stop after n steps.

The above expression uses + sign. This means that adjacency matrix definition should be extended in order to allow integers greater than 1. As usual, value > 0 is interpreted as a directed link between the nodes, 0 being no such link.

The formal expression containing infinite sum is appealing because it formally equals to

(1-A)^(-1)

That's right, transitive closure could be computed as an inverse matrix. Next, inverse matrix is just a ratio of 2 determinants. The question then is if determinant or invers matrix calculation can be carried over in relational algebra (with aggregation). I asked Leonid Libkin this question some time ago, and his answer was resound "no". Received on Mon Nov 08 2004 - 23:55:18 CET