========================================================================= LECTURE NOTES - RECURSION IN SQL3 ========================================================================= ** Section 5.10 in the textbook covers SQL3 recursion but assumes knowledge of "Datalog", which we have not covered. Everything you need to know about SQL3 recursion is covered in this lecture. Ex: Ancestors Relation: ParentOf(parent,child) Query: Find all of Mary's ancestors Q: Can we write the query in SQL2? Ex: Company hierarchy Relations: Employee(ID, salary) Manager(mgrID, empID) Project(name, mgrID) Query: What's the total salary cost of project "X" Q: Can we write the query in SQL2? Ex: Airline flights Relation: Flight(origin, destination, airline, cost) Query: Find the cheapest way to fly from origin A to destination B Q: Can we write the query in SQL2? SQL3 WITH statement ------------------- WITH R1 AS (query), R2 AS (query), ..., Rn AS (query) 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), ... Ex: 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 Ex: 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" Ex: 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(Employee.salary) FROM Project, Superior, Employee WHERE Project.name = "X" AND Project.mgrID = Superior.mgrID AND (Employee.ID = Superior.empID OR Employee.ID = Superior.mgrID) 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) Nonlinear recursion ------------------- - SQL3 only requires support of "linear" recursion: each FROM has at most one reference to a recursively-defined relation. 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 it literally converges to fixed-point faster than linear version -> But not required in SQL3 because general case of nonlinear recursion is hard/expensive Mutual recursion ---------------- Contrived example: 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)), Q: What's wrong? Problem: "Bad mix" of recursion and negation (NOT IN). Solution: SQL3 does not allow mutual recursion if one relation depends "negatively" on another (i.e., insertions into one can cause deletions from the other other) - Other tricky cases of mutual recursion also disallowed. Ex: Given Q(x) P(x) = Q(x) UNION R(x) R(x) = P(x) UNION sum(P(x)) Q: What happens?