CS145 Lecture Notes -- Recursion in SQL

Section 10.4 in the textbook covers SQL-99 recursion but assumes knowledge of "Datalog", which we have not covered. Everything you need to know about SQL-99 recursion is covered in this lecture.

Example: Ancestors

Relation: ParentOf(parent,child)
Query: Find all of Mary's ancestors

Question: Can we write the query in SQL2?

Example: Company hierarchy

Relations: Employee(ID,salary), Manager(mgrID,empID), Project(name,mgrID)
Query: What's the total salary cost of project "X"

Question: Can we write the query in SQL2?

Example: Airline flights

Relation: Flight(origin,destination,airline,cost)
Query: Find the cheapest way to fly from origin A to destination B

Question: Can we write the query in SQL2?

SQL-99 `WITH` statement

  WITH R1 AS (query),
       R2 AS (query),
       ...,
       Rn AS (query)
  <query involving R1, R2,...,Rn and other relations>

Idea:

Compute R1, R2,...,Rn into temporary relations
Evaluate the query involving R1,...,Rn and other relations
Destroy R1, R2,...,Rn

Can also specify schema for Ri's:

  WITH R1(A1, A2, ..., Am) AS (query), ...

Example:

  WITH Berk AS (SELECT ID, date FROM Apply WHERE location = "Berkeley"),
       SC AS (SELECT ID, date FROM Apply WHERE location = "SC")
  SELECT ID, Berk.date AS Bdate, SC.date AS SCdate
  FROM   Berk, SC
  WHERE  Berk.ID = SC.ID

WITH statement looks like "temporary view definitions" for syntactic convenience.
But: The Ri's can be recursive or mutually recursive.

Must tag with keyword RECURSIVE
Recursion usually achieved through UNION of base case + recursion

Example: Find Mary's ancestors from ParentOf(parent,child)

  WITH RECURSIVE Ancestor(anc,desc) AS
         ( (SELECT parent as anc, child as desc FROM ParentOf)
           UNION
           (SELECT Ancestor.anc, ParentOf.child as desc
            FROM Ancestor, ParentOf
            WHERE Ancestor.desc = ParentOf.parent) )
  SELECT anc FROM Ancestor WHERE desc = "Mary"

(show procedural evaluation with fixpoint)

Example: Total salary cost of Project "X"

  WITH RECURSIVE Superior AS
         ( (SELECT * from Manager)
           UNION
           (SELECT S.mgrID, M.empID
            FROM Superior S, Manager M
            WHERE S.empID = M.mgrID) )
  SELECT sum(salary)
  FROM Employee
  WHERE ID IN
    ((SELECT mgrID FROM Project WHERE name = 'X')
      UNION
     (SELECT empID FROM Project, Superior
      WHERE Project.name = 'X' AND Project.mgrID = Superior.mgrID))

(show example data and computation)

Alternative formulation, more specific to this query:

  WITH RECURSIVE Xemps(ID) AS
         ( (SELECT mgrID AS ID FROM Project WHERE name = "X")
           UNION
           (SELECT empID AS ID
            FROM Manager
            WHERE mgrID IN (Select ID FROM Xemps)) )
  SELECT sum(salary)
  FROM   Employee
  WHERE  ID IN (SELECT ID FROM Xemps)

(show computation)

Flights example left as exercise

Nonlinear recursion

SQL-99 only requires support of "linear" recursion: each FROM has at most one reference to a recursively-defined relation.

Example: Nonlinear version of Ancestor:

  WITH RECURSIVE Ancestor(anc,desc) AS
         ( (SELECT parent as anc, child as desc FROM ParentOf)
           UNION
           (SELECT A1.anc, A2.desc
            FROM Ancestor A1, Ancestor A2
            WHERE A1.desc = A2.anc) )
  SELECT anc FROM Ancestor WHERE desc = "Mary"

Looks cleaner
Executing as specified converges to fixed-point faster than linear version
But not required in SQL-99 because general case of nonlinear recursion is hard/expensive

Mutual recursion

Contrived example:

Relation: Sales(ID,amt)
Employees who sold > 10,000 and don't get a bonus go to the banquet
Employees who sold > 20,000 and don't go to the banquet get a bonus

  WITH RECURSIVE Banquet(ID) AS
         (SELECT ID
          FROM Sales
          WHERE amt > 10,000
          AND ID NOT IN (SELECT ID FROM Bonus)),
       RECURSIVE Bonus(ID) AS
         (SELECT ID
          FROM Sales
          WHERE amt > 20,000
          AND ID NOT IN (SELECT ID FROM Banquet))
  <any query>

Question: What's wrong?

Problem: "Bad mix" of recursion and negation (NOT IN)
Solution: SQL-99 does not allow mutual recursion if one relation depends "negatively" on another (i.e., insertions into one can cause deletions from the other)

Other tricky cases of mutual recursion also disallowed.

Example: Given relation Q(x)

  P(x) = Q(x) UNION R(x)
  R(x) = P(x) UNION sum(P(x))

Question: What happens?

CS145 Lecture Notes -- Recursion in SQL

SQL-99 WITH statement

Nonlinear recursion

Mutual recursion

SQL-99 `WITH` statement