## 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:
1. Compute R1, R2,...,Rn into temporary relations
2. Evaluate the query involving R1,...,Rn and other relations
3. 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?
```

```