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