Recursion in SQL

有限范围的查询可以通过多次 Join 实现，但如果不知道范围则需要引入 Recursion
树，图 结构类型的数据经常有 Recursion 的需要
Stanford CS145 PS1

SQL Recursion 语法

With Recursive
    R As (base query
          Union
          recursive query )
<query involving R (and other tables)>

用 SQL 计算 factorial number

WITH RECURSIVE
    factorials(n,x) AS (
        SELECT 1, 1
        UNION
        SELECT n+1, (n+1)*x FROM factorials WHERE n < 5)
SELECT x FROM factorials WHERE n = 5;

上述 SQL 执行的流程是这样的：

1. 先 base case, 然后将 (1, 1) 插入 factorials 表
2. 从 factorials 中取出 (1, 1)，计算 (1+1, (1+1)*1) = (2,2)， 然后插入 factorials
3. 不断循环，由于用的是 Union，会自动过滤掉重复的结构，因此每次只要从 factorials 取出最近插入的那个元素就行了
4. 直到不满足 n < 5 退出
5. 最后从 factorials 表中取出n为5时的x值 (此时factorials 中有的元素有 (1, 1), (2, 2), (3, 6), (4, 24), (5, 120))

可以发现 SQL 的 Recursion 与其他语言的不同
其他语言的 Recursion 都是 top-down 形式
而 SQL 的 Recursion 从 base case 开始不断 Union
给我的感觉更像动态规划。选择 Union 而不是 Union all 类似 动态规划中记录子问题

拿如下 Python 计算 factorial number 的例子进行比较。发现的确很像。。。

def factorial(n):
    memo = [1] * (n+1)
    i = 1
    while i <= n:
        memo[i] = memo[i-1] * i
        i += 1
    return memo[n]

最后放上 SQL Recursion 的一些例子

/**************************************************************
  EXAMPLE 1: Ancestors
  Find all of Mary's ancestors
**************************************************************/

create table ParentOf(parent text, child text);

insert into ParentOf values ('Alice', 'Carol');
insert into ParentOf values ('Bob', 'Carol');
insert into ParentOf values ('Carol', 'Dave');
insert into ParentOf values ('Carol', 'George');
insert into ParentOf values ('Dave', 'Mary');
insert into ParentOf values ('Eve', 'Mary');
insert into ParentOf values ('Mary', 'Frank');

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
  Find total salary cost of project 'X'
**************************************************************/

create table Employee(ID int, salary int);
create table Manager(mID int, eID int);
create table Project(name text, mgrID int);

insert into Employee values (123, 100);
insert into Employee values (234, 90);
insert into Employee values (345, 80);
insert into Employee values (456, 70);
insert into Employee values (567, 60);
insert into Manager values (123, 234);
insert into Manager values (234, 345);
insert into Manager values (234, 456);
insert into Manager values (345, 567);
insert into Project values ('X', 123);

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 );

/*** Alternative formulation tied specifically to project 'X' **/

with recursive
  Xemps(ID) as (select mgrID as ID from Project where name = 'X'
                union
                select 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);