Linear Recursion
R As (base query (not R) Union (removes duplicates) recursive query (one reference to R))
Example 1: Ancestors
ParentOf(parent, child)
Find all of Mary’s ancestors
Linear
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’;
Non-Linear
with recursive
Ancestor (a, d) as (select parent as a, child as d from ParentOf
union
select A1.a, A2.d
from Ancestor A1, Ancestor A2
where A1.d = A2.a)
select a from Ancestor where d = ‘Mary’
Nonlinear (versus linear)
+ query looks cleaner
+ converges faster
– harder to implement
SQl standard only requires linear
Mututal Recursion
With recursive
R1(A1, A2, …, Am) As (query-1), – R2
R2 As (query-2), – R1
Rn As (query-n)
Example: Hubs and Authorities
Link(src, dest)
HubStart(node)
AuthStart(node)
Hub points to >= 3 Authority
Authority points to >= 3 Hub
with recursive
Hub(node) as (select node from HubStart
union
select src as node from Link L
where dest in (select node from Auth)
group by src having count(*) >= 3),
Auth(node) as (select node from AuthStart
union
select dest as node from Link L
where src in (select node from Hub)
group by dest having count(*) >= 3)
select * from Hub;
with recursive
Hub(node) as (select node from HubStart
union
select src as node from Link L
where src not in (select node from Auth)
and dest in (select node from Auth)
group by src having count(*) >= 3),
Auth(node) as (select node from AuthStart
union
select dest as node from Link L
where dest not in (select node from Hub)
and src in (select node from Hub)
group by dest having count(*) >= 3)
select * from Hub;
non-detirministic, not supported by SQL standard.
Recursion with Aggregation
Example:
P(x)
with recursive
R(x) as (select x from P
union
select sum(x) from R)
select * from R;
FAIL, disallowed in SQL standard
SQL Recursive With Statement
Extends expressiveness of SQL
– basic functionality: linear recursion
– extended functionality: nonlinear recursion, mutual recursion
– Disallowed: negative recursive subqueries, Aggregation