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.
