Re: Floyd's algorithm in SQL

"John Gilson" <jag_at_acm.org> wrote in message news:<ykGrd.18407$Yh2.6979338_at_twister.nyc.rr.com>...
> "--CELKO--" <jcelko212_at_earthlink.net> wrote in message
> news:18c7b3c2.0412011610.3891e0bc_at_posting.google.com...
> > I am re-doing the graphs section for the third edition of SQL FOR
> > SMARTIES and would like some feedback and help.
> >

[...]
>
> The following was tested with DB2 so it might not be fully compliant
> with Standard SQL. For example, I believe the Standard requires a
> recursive WITH to be defined as WITH RECURSIVE.
>
> Using your DDL, here's a sample graph.
>
> INSERT INTO Edges (source, destination, lgth)
> VALUES ('1', '2', 50);
> INSERT INTO Edges (source, destination, lgth)
> VALUES ('1', '3', 30);
> INSERT INTO Edges (source, destination, lgth)
> VALUES ('1', '4', 100);
> INSERT INTO Edges (source, destination, lgth)
> VALUES ('1', '5', 10);
> INSERT INTO Edges (source, destination, lgth)
> VALUES ('3', '2', 5);
> INSERT INTO Edges (source, destination, lgth)
> VALUES ('4', '2', 20);
> INSERT INTO Edges (source, destination, lgth)
> VALUES ('4', '3', 50);
> INSERT INTO Edges (source, destination, lgth)
> VALUES ('5', '4', 10);
>
> To find the shortest paths:
>
> CREATE VIEW ShortestPaths (source, destination, path_length)
> AS
> WITH Paths (source, destination, path_length)
> AS
> (
> SELECT source, destination, 1
> FROM Edges
> UNION ALL
> SELECT E1.source, P1.destination, P1.path_length + 1
> FROM Edges AS E1, Paths AS P1
> WHERE E1.destination = P1.source
> )
> SELECT source, destination, MIN(path_length)
> FROM Paths
> GROUP BY source, destination;
>

Dont you need a termination condition in case of cycles? I dont think this will terminate if you add (2,1) to the set of edges. The best condition I could think of was that we never have to walk more then the nr of edges in the graph, thus when path_length > cnt we can stop.

It would be nice to be able to do something like:

WITH Paths (source, destination, path_length) AS (   SELECT source, destination, 1 FROM Edges   UNION ALL
  SELECT E1.source, P1.destination, P1.path_length + 1   FROM Edges AS E1, Paths AS P1
  WHERE E1.destination = P1.source
    AND NOT EXISTS (

        SELECT 1 from Paths P2
        WHERE (E1.source, P1.destination) = (P2.source,

    )
)
SELECT source, destination, MIN(path_length) FROM Paths
GROUP BY source, destination;  

But that is not supported by DB2.

I BTW found another limitation for the with clause in DB2. It is not allowed to use x inner join y on ... inside the with clause.

/Lennart

[...] Received on Thu Dec 02 2004 - 21:27:25 CET