Re: Floyd's algorithm in SQL

Oops, my first attempt to answer was messed up. Here's what I was trying to post:

--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;
Celko,

I have some comments/questions regarding your Floyd procedure:

Is this procedure really DETERMINISTIC? (What it performs depends on the data in the Edges table, doesn't that mean the procedure is nondeterministic ?)

Don't you have to specify MODIFIES SQL DATA? (Since data in inserted into the Paths table.)

The WHILE loop will exit after one single turn. Because the last line "SET old_path_tally = (SELECT COUNT(*) FROM Paths);" is executed right before "WHILE old_path_tally < (SELECT COUNT (*) FROM Paths)", i.e. the WHILE loop will exit. (And if there's no rows in Paths at all, the WHILE loop will not be entered.)

Regards,
Jarl Received on Thu Dec 02 2004 - 12:28:16 CET