## CS145 Lecture Notes (14) -- 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 Berk.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?
```

```