有限范圍的查詢可以通過多次 Join 實現(xiàn)，但如果不知道范圍則需要引入 Recursion
樹，圖 結(jié)構(gòu)類型的數(shù)據(jù)經(jīng)常有 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 執(zhí)行的流程是這樣的：

1. 先 base case, 然后將 (1, 1) 插入 factorials 表
2. 從 factorials 中取出 (1, 1)东且，計算 (1+1, (1+1)*1) = (2,2)， 然后插入 factorials
3. 不斷循環(huán)沦寂，由于用的是 Union谐丢，會自動過濾掉重復(fù)的結(jié)構(gòu)，因此每次只要從 factorials 取出最近插入的那個元素就行了
4. 直到不滿足 n < 5 退出
5. 最后從 factorials 表中取出n為5時的x值 (此時factorials 中有的元素有 (1, 1), (2, 2), (3, 6), (4, 24), (5, 120))

可以發(fā)現(xiàn) SQL 的 Recursion 與其他語言的不同
其他語言的 Recursion 都是 top-down 形式
而 SQL 的 Recursion 從 base case 開始不斷 Union
給我的感覺更像動態(tài)規(guī)劃其监。選擇 Union 而不是 Union all 類似 動態(tài)規(guī)劃中記錄子問題

拿如下 Python 計算 factorial number 的例子進(jìn)行比較萌腿。發(fā)現(xiàn)的確很像。抖苦。毁菱。

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