Talk:Celko's SQL Puzzle

From IBM Database Magazine Wiki

Ask a question, give a hint, or just make a comment about Celko's SQL Puzzle #1.

---

G'day Joe, excellent puzzle.

I'm a big fan of Recursive Common Table Expressions (aka Recursive SQL) for solving problems such as this. My first attempt at writing an RCTE worked against the sample rows given. However, further testing showed that the statement would enter an infinite loop if certain relationships were added to the graph.

The second attempt maintains the node path followed through the graph. The path is then checked to ensure the current node has not already been seen. This stops the RCTE from entering into an infinite loop.

Here's the statement...

with rcte ( source_node, dest_node, wgt, path ) as
(   select source_node
         , dest_node
         , wgt
         , ',' || varchar(rtrim(source_node),1000) || ','
      from graph
  union all
    select a.source_node
         , b.dest_node
         , a.wgt + b.wgt
         , a.path || rtrim(b.source_node) || ','
      from rcte a
         , graph b
     where b.source_node = a.dest_node
       and b.dest_node <> a.source_node
       and locate(',' || rtrim(b.source_node) || ',', a.path) = 0
       and not exists ( select 1
                          from graph c
                         where c.source_node = a.source_node
                           and c.dest_node = b.dest_node
                           and c.wgt <= a.wgt + b.wgt )
)
select source_node
     , dest_node
     , min(wgt) min_wgt
  from rcte
 group by source_node
        , dest_node
 order by source_node
        , dest_node

Running this statement against the data set...

insert into graph
  values ( 'a', 'b', 1 )
       , ( 'b', 'c', 1 )
       , ( 'c', 'd', 1 )
       , ( 'd', 'e', 1 )
       , ( 'e', 'a', 1 )
       , ( 'c', 'a', 1 )
       , ( 'e', 'd', 1 )

Gives the following result set...

SOURCE_NODE DEST_NODE MIN_WGT
----------- --------- -----------
a           b                   1
a           c                   2
a           d                   3
a           e                   4
b           a                   2
b           c                   1
b           d                   2
b           e                   3
c           a                   1
c           b                   2
c           d                   1
c           e                   2
d           a                   2
d           b                   3
d           c                   4
d           e                   1
e           a                   1
e           b                   2
e           c                   3
e           d                   1

Rob.