# Intro to Databases: Recursion in SQL, Basic recursive WITH statement

SQL is not a “Turing complete” language
– simple, convinient, declarative
– expressve enough for most database queries
– but basic SQL can’t express unbounded computations

Example 1: Ancestors
ParentOf(parent, child)
Find all of Mary’s ancestors

Example 2: Company hierarchy
Employee (ID, salary)
Manager(mID, eID)
Project(name, mgrID)
Find total salary cost of project ‘X’

Example 3: Airline flights
Flight(orig, dest, airline, cost)
Find cheapest way to fly from ‘A’ to ‘B’

SQL With statement
With R1(A1, A2, …, Am) As (query-1),
R2 As (query-2),
Rn As (query-n)

With Recursive R1(A1, A2, …, Am) As (query-1),
R2 As (query-2),
Rn As (query-n)

With Recursive
R As (base query (not R) Union (removes duplicates) recursive query (R))

DEMO

Example 1: Ancestors
ParentOf(parent, child)
Find all of Mary’s ancestors

with recursive
Ancestor (a, d) as (select parent as a, child as d, from ParentOf
union
select Ancestor.a, ParentOf.child as d
from Ancestor, ParentOf
where Ancestor.d = ParentOf.parent)
select a from Ancestor where d = ‘Mary’

Example 2: Company hierarchy
Employee (ID, salary)
Manager(mID, eID)
Project(name, mgrID)
Find total salary cost of project ‘X’

with recursive
Superior as (select * from Manager
union
select S.mID, M.eID
from Superior S, Manager M
where S.eID = M.mID)
select sum(salary)
from Employee
where ID in
(select mgrID from Project where name = ‘X’
union
select eID from Project, Superior
where Project.name = ‘X’ AND Project.mgrID = Superior.mID)

or

with recursive
Xemps(ID) as (select mgrID as ID from Project where name = ‘X’
union
select distinct eID as ID
from Manager M, Xemps X
where M.mID = X.ID)
select sum(salary)
from Employee
where ID in (select ID from Xemps)

Find the total salary cost of two projects ‘Y’ and ‘Z’

with recursive
Yemps(ID) as (select mgrID as ID from Project where name = ‘Y’
union
select distinct eID as ID
from Manager M, Yemps Y
where M.mID = Y.ID),
Zemps(ID) as (select mgrID as ID from Project where name = ‘Z’
union
select distinct eID as ID
from Manager M, Zemps Z
where M.mID = Z.ID)
select ‘Y-total’, sum(salary)
from Employee
where ID in (select ID from Yemps)
union
select ‘Z-total’, sum(salary)
from Employee
where ID in (select ID from Zemps)

Example 3: Airline flights
Flight(orig, dest, airline, cost)
Find cheapest way to fly from ‘A’ to ‘B’

with recursive
Route(orig, dest, total) as
(select orig, dest, cost as total from Flight
union
select R.orig, F.dest, cost+total as total
from Route R, Flight F
where R.dest = F.orig)
select min(total) from Route
where orig = ‘A’ and dest = ‘B’

or

with recursive
FromA(dest, total) as
(select dest, cost as total from Flight where orig = ‘A’
union
select F.dest, cost+total as total
from FromA FA, Flight F
where FA.dest = F.orig)
select min(total) from FromA where orig = ‘A’

or

with recursive
ToB(orig, total) as
(select orig, cost as total from Flight where dest = ‘B’
union select F.orig, cost+total as total
from Flight F, ToB TB
where F.dest = TB.orig)
select min(total) from ToB where orig = ‘A’

Beware infinite loops!

with recursive
Route(orig, dest, total) as
(select orig, dest, cost as total from Flight
union
select R.orig, F.dest, cost+total as total
from Route R, Flight F
where R.dest = F.orig)
select * from Route
where orig = ‘A’ and dest = ‘B’ limit 20

with recursive
Route(orig, dest, total, length) as
(select orig, dest, cost as total, 1 from Flight
union
select R.orig, F.dest, cost+total as total, R.length+1 as length
from Route R, Flight F
where R.length < 10 and R.dest = F.orig) select * from Route where orig = 'A' and dest = 'B'

December 4, 2011 | Comments Off on Intro to Databases: Recursion in SQL, Basic recursive WITH statement | Categories: Posts | Permalink