Re: Floyd's algorithm in SQL

--CELKO-- wrote:
> I am re-doing the graphs section for the third edition of SQL FOR
> SMARTIES and would like some feedback and help.
>
> Here is a version of Floyd's algorithm to find the transitive closure
> of a graph. You can also look up Warshall's algorithm, which is an
> earlier and more specialized version of Floyd's algorithm. Given a
> directed graph G represented by an adjacency matrix A[i, j], WHERE
> A[i, j] = 1 if the edge (i, j) is in the graph, compute the matrix P
> of paths with their lengths. Now put it into SQL:
>
> CREATE TABLE Paths
> (source CHAR(1)NOT NULL,
> destination CHAR(1) NOT NULL,
> lgth INTEGER DEFAULT 0 NOT NULL);
>
> CREATE TABLE Edges
> (source CHAR(1)NOT NULL,
> destination CHAR(1)NOT NULL,
> PRIMARY KEY (source, destination),
> lgth INTEGER DEFAULT 1 NOT NULL);
>
> INSERT INTO Edges (source, destination) VALUES ('a', 'b');
> INSERT INTO Edges (source, destination) VALUES ('b', 'c');
> INSERT INTO Edges (source, destination) VALUES ('c', 'd');
> INSERT INTO Edges (source, destination) VALUES ('d', 'a');
> INSERT INTO Edges (source, destination) VALUES ('a', 'e');
>
> The algorithm extends each known path by one edge at a time. Since
no
> path can be longer than the number of nodes in the graph, we have an
> upper bound on iterations. But we can also stop when the INSERT
> statement adds no new paths.
>
> CREATE PROCEDURE Floyd()
> LANGUAGE SQL
> DETERMINISTIC
> BEGIN
> DECLARE old_path_tally INTEGER;
> SET old_path_tally = 0;
> DELETE FROM Paths; -- clean out working table
> INSERT INTO Paths SELECT * FROM Edges; -- load the edges
>
> -- add one edge to each path
> WHILE old_path_tally < (SELECT COUNT(*) FROM Paths)
> DO INSERT INTO Paths (source, destination, lgth)
> SELECT E1.source, P1.destination, (E1.lgth + P1.lgth)
> FROM Edges AS E1, Paths AS P1
> WHERE E1.destination = P1.source
> AND NOT EXISTS -- path is not here already
> (SELECT *
> FROM Paths AS P2
> WHERE E1.source = P2.source
> AND P1.destination = P2.destination);
> SET old_path_tally = (SELECT COUNT(*) FROM Paths);
> END WHILE;
> END;
>
> You could also have used a SQLSTATE code to detect any empty
> insertion. I am not sure if that would actually be faster or not.
>
> SELECT * FROM Paths;
> source destination lgth
> =========================
> a b 1
> a e 1
> b c 1
> c d 1
> d a 1
> a c 2
> b d 2
> c a 2
> d b 2
> d e 2
> a d 3
> b a 3
> c b 3
> c e 3
> d c 3
> a a 4
> b b 4
> b e 4
> c c 4
> d d 4
>
> What I'd like to know is:
>
> 1) Can I put Paths in a VIEW defined by a recursive WITH operator? I
> don't have a copy of a product that implements this SQL-99 feature.
>
> 2) Can I modify my SQL-92 code or the SQL-99 to handle the lowest
cost
> problem? That is, each edge has a positive cost; what is the
CHEAPEST
> path from x to y, not the SHORTEST path?
>
> There is fame, glory and virtual beer in this puzzle.
Received on Thu Dec 02 2004 - 12:22:04 CET