-- Slide 361: SQL Recursive Common Table Expressions (CTE):
-- use CTEs to express the iterated evaluation of a SQL
-- query block

-- Example: compute the transitive closure of the
-- adjacency relation GRAPH of a directed graph:

DROP TABLE GRAPH;
CREATE TABLE GRAPH(FROM CHAR(1),
                   TO   CHAR(1));      
                                        
-- Encode the following graph:                                         
--
--    a ----> b                                           
--            |                                           
--            |  
--            V  
--    d <---- c  

INSERT INTO GRAPH VALUES ('a', 'b'),     
                         ('b', 'c'),     
                         ('c', 'd');     

-- Iterations needed to compute all paths in the graph
-- (= compute the transitive closure of the adjacency relation)

DROP VIEW PATHS1;
DROP VIEW PATHS2;
DROP VIEW PATHS3;
DROP VIEW PATHS4;

-- (1) Non-recursive variant (using a non-recursive CTE
--     to name intermediate results)
WITH 
-- Iteration #0: all paths of length 1
PATHS1(FROM, TO) AS
  (SELECT *
   FROM   GRAPH),

-- Iteration #1: all paths of length 2
PATHS2(FROM, TO) AS
  (SELECT p1.FROM, g2.TO
   FROM   PATHS1 p1, GRAPH g2
   WHERE  p1.TO = g2.FROM),

-- Iteration #2: all paths of length 3
PATHS3(FROM, TO) AS
  (SELECT p1.FROM, g2.TO
   FROM   PATHS2 p1, GRAPH g2
   WHERE  p1.TO = g2.FROM),

-- Iteration #3: all paths of length 4 
PATHS4(FROM, TO) AS                      -- ⎫ for the above example 
  (SELECT p1.FROM, g2.TO                 -- ⎬ graph, this query will
   FROM   PATHS3 p1, GRAPH g2            -- ⎪ yield the empty table
   WHERE  p1.TO = g2.FROM)               -- ⎭ 

-- Compute the full transitive closure:
SELECT *
FROM   PATHS1
  UNION ALL 
SELECT *
FROM   PATHS2
  UNION ALL 
SELECT *
FROM   PATHS3
  UNION ALL 
SELECT *
FROM   PATHS4;



-- (2) Recursive variant (using a recursive CTE)
--
WITH PATHS(FROM, TO) AS
  (SELECT *                    -- ⎱ Iteration #0
   FROM   GRAPH                -- ⎰ (base case fullselect)
                              
     UNION ALL                
                              
   SELECT p1.FROM, g2.TO       -- ⎫ Iterations #1, #2, ...          
   FROM   PATHS p1, GRAPH g2   -- ⎬ (iterated fullselect,
   WHERE  p1.TO = g2.FROM      -- ⎭  may refer to PATHS recursively)
  )
SELECT *
FROM   PATHS;



-- Now introduce a cycle in the above graph (add edge c --> a)
-- (Note: leads to infinite recursion if you apply (2)!)

INSERT INTO GRAPH VALUES ('c', 'a');

-- (3)  Recursive variant (using a recursive CTE,
--      now limit the number of iterations; here: paths of
--      maximum length 10 will be computed)
WITH PATHS(FROM, TO, LENGTH) AS
  (SELECT FROM, TO, 1         -- ⎱ Iteration #0            
   FROM   GRAPH               -- ⎰ (all paths of LENGTH = 1)
  
     UNION ALL
  
   SELECT p1.FROM, g2.TO, p1.LENGTH + 1 -- ⎫ Iteration #(LENGTH + 1)
   FROM   PATHS p1, GRAPH g2            -- ⎬ (all paths of length
   WHERE  p1.TO = g2.FROM               -- ⎪ LENGTH + 1, but no
   AND    p1.LENGTH < 11                -- ⎭ longer than 10)
  )
SELECT *       -- use SELECT DISTINCT FROM, TO to obtain the 12 paths
FROM   PATHS;