再帰SQL -図解-

# まえがき
再帰SQLを使うと、テーブルに一時的に名前を付けることで、再帰処理(ループ)を実現できます。どのように実行されるのか難しかったため図解してみます。

# with句
メインクエリの中で同じサブクエリを何度も呼び出している場合に使われるのがwith句です。with句を使うとサブクエリに名前をつけることができるので、メインクエリから何度でも呼び出すことができます。便宜上、with句によって作られる一時テーブルを__withテーブル__と呼ぶことにします。with句を利用したクエリは、以下のように評価が進みます。

1. with句を評価し、withテーブルを作成する
2. メインクエリを実行する。

まずは簡単な例でwith句の使い方を見てみましょう。営業マンたちの月別売上を表す営業成績テーブルを考えます。

【営業成績テーブル】

| 名前     | 月  | 月次売上 |
|----------|-----|----------|
| 田中太郎 | 1月 | 1000     |
| 田中太郎 | 2月 | 2500     |
| 田中太郎 | 3月 | 3000     |
| 鈴木次郎 | 1月 | 5000     |
| 鈴木次郎 | 2月 | 1000     |
| 鈴木次郎 | 3月 | 1500     |
| 山本三郎 | 1月 | 3000     |
| 山本三郎 | 2月 | 2200     |
| 山本三郎 | 3月 | 4000     |
【問】
月次売上の合計が一番高い人は誰でしょう？
【答】

```sql
WITH	成績サマリ (名前, 売上合計)
AS
(SELECT 名前, SUM(月次売上)
FROM	営業成績
GROUP	BY 名前)
--メインクエリ
SELECT	P1.名前, P1.売上合計
FROM	成績サマリ P1
WHERE	P1.売上合計
	= (SELECT	MAX(P2.売上合計)
		FROM	成績サマリ P2);
```
【解説】
まず、with句で、営業マンごとの売上合計を表す成績サマリテーブルを作成します。

【成績サマリテーブル】

| 名前     | 売上合計 |
|----------|----------|
| 田中太郎 | 6500     |
| 鈴木次郎 | 7500     |
| 山本三郎 | 9200     |

そして、メインクエリの中で、成績サマリテーブルから売上合計が一番高い行を取得しています。
with句を使い、一時的に作成したテーブルに名前を付けることによって、メインクエリの中で何度でも呼び出すことができるようになっていますね。

# 再帰SQL
再帰SQLは、前に行った処理の結果を利用して同じ処理を繰り返す場合に使われます。例えば木構造のデータを格納しているテーブルで、根から葉までたどるような場合です。
再帰SQLは、with句の拡張であるwith recursive句を利用します。with recursive句は、UNION ALLより上にある非再帰項と、UNION ALLより下にある再帰項から成っており、再帰項のクエリは何度も実行されます。
with recursive句の実行時は、withテーブル、ワークテーブル、結果テーブルという3つのテーブルが利用されます。初期状態ではこれら3つのテーブルは空です。評価は以下のように進みます。

1. 非再帰項を評価し、withテーブルと結果テーブルに代入する
(この時点でwithテーブルには名前が付けられるので、再帰項から呼び出しが可能になる。)
2. 再帰項を評価し、その結果をワークテーブルに代入する
3. ワークテーブルが空でなければ、
    * ワークテーブルを結果テーブルにUNION(またはUNION ALL)し、
    * withテーブルをワークテーブルで置き換え、
    * ワークテーブルを空にし、2から繰り返す
4. 結果テーブルをwithテーブルに置き換える

図解するとこんな感じです。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/201287/188b59b9-e22f-04d9-3990-1d068b39cccb.png)
![image.png](https://qiita-image-store.s3.amazonaws.com/0/201287/0cfe67f1-b19a-333e-40be-182cdc3509d6.png)
![image.png](https://qiita-image-store.s3.amazonaws.com/0/201287/fc7ce1c2-93e5-4688-b50b-61db710242e4.png)
![image.png](https://qiita-image-store.s3.amazonaws.com/0/201287/3022d7ab-4f26-ae0a-cda8-dcf2fdbf1926.png)
![image.png](https://qiita-image-store.s3.amazonaws.com/0/201287/01644ce5-64bd-29c7-f7d0-fdf8031509f3.png)
![image.png](https://qiita-image-store.s3.amazonaws.com/0/201287/fc215dc6-1ec8-3f90-5315-2e5429bfbe25.png)
![image.png](https://qiita-image-store.s3.amazonaws.com/0/201287/a015d7b3-f549-a620-ec89-624390c6f2e6.png)

例として、以下の図のような上司と部下というリレーションを持っている営業マンを考えます。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/201287/5cf3fe50-f334-ee86-b3c2-d74849d58ee2.png)

営業成績テーブルは上の図の関係を隣接リストモデルで表しており、名前と上司、そして年次売上を格納しています。

【営業成績テーブル】

| 名前     | 上司名 | 年次売上 |
|----------|--------|----------|
| 部長     | NULL   | 15000    |
| 課長A    | 部長   | 12000    |
| 課長B    | 部長   | 13000    |
| 田中太郎 | 課長A  | 6500     |
| 鈴木次郎 | 課長A  | 7500     |
| 山本三郎 | 課長B  | 9200     |
【問】
各営業マンの年次売上を求めなさい。ただし、部下の売上や部下の部下の売上も自分の売上に加算してよい。
【答】

```sql
with recursive 成績サマリ(部下名, 上司名, 売上総和) AS (
--非再帰項
SELECT 	営業成績.名前, 営業成績.名前, 営業成績.年次売上
FROM 	営業成績
UNION ALL
--再帰項
SELECT	営業成績.名前, 成績サマリ.上司名, 年次売上
FROM	営業成績, 成績サマリ
WHERE	営業成績.上司名 = 成績サマリ.部下名)
--メインクエリ
SELECT		上司名,SUM(売上総和) 売上総和
FROM		成績サマリ
GROUP BY	上司名;
```
【解説】
まず、非再帰項を評価し、成績サマリテーブルと結果テーブルに代入します。

【成績サマリテーブル①】

| 部下名   | 上司     | 年次売上 |
|----------|----------|----------|
| 部長     | 部長     | 15000    |
| 課長A    | 課長A    | 12000    |
| 課長B    | 課長B    | 13000    |
| 田中太郎 | 田中太郎 | 6500     |
| 鈴木次郎 | 鈴木次郎 | 7500     |
| 山本三郎 | 山本三郎 | 9200     |
【結果テーブル①】

| 部下名   | 上司     | 年次売上 |
|----------|----------|----------|
| 部長     | 部長     | 15000    |
| 課長A    | 課長A    | 12000    |
| 課長B    | 課長B    | 13000    |
| 田中太郎 | 田中太郎 | 6500     |
| 鈴木次郎 | 鈴木次郎 | 7500     |
| 山本三郎 | 山本三郎 | 9200     |
次に、再帰項を評価します。営業成績テーブルの上司名と、成績サマリテーブルの部下名で結合するのでワークテーブルは次のようになります。

【ワークテーブル①】

| 部下名   | 上司     | 年次売上 |
|----------|----------|----------|
| 課長A    | 部長     | 12000    |
| 課長B    | 部長     | 13000    |
| 田中太郎 | 課長A    | 6500     |
| 鈴木次郎 | 課長A    | 7500     |
| 山本三郎 | 課長B    | 9200     |

ワークテーブルは空ではないので、結果テーブルにUNION ALLします。成績サマリテーブルをワークテーブルに置き換えます。

【結果テーブル②】

| 部下名   | 上司     | 年次売上 |
|----------|----------|----------|
| 部長     | 部長     | 15000    |
| 課長A    | 課長A    | 12000    |
| 課長B    | 課長B    | 13000    |
| 田中太郎 | 田中太郎 | 6500     |
| 鈴木次郎 | 鈴木次郎 | 7500     |
| 山本三郎 | 山本三郎 | 9200     |
| 課長A    | 部長     | 12000    |
| 課長B    | 部長     | 13000    |
| 田中太郎 | 課長A    | 6500     |
| 鈴木次郎 | 課長A    | 7500     |
| 山本三郎 | 課長B    | 9200     |
【成績サマリテーブル②】

| 部下名   | 上司     | 年次売上 |
|----------|----------|----------|
| 課長A    | 部長     | 12000    |
| 課長B    | 部長     | 13000    |
| 田中太郎 | 課長A    | 6500     |
| 鈴木次郎 | 課長A    | 7500     |
| 山本三郎 | 課長B    | 9200     |

そして再度、再帰項を評価します。

【ワークテーブル②】

| 部下名   | 上司     | 年次売上 |
|----------|----------|----------|
| 田中太郎 | 部長     | 6500     |
| 鈴木次郎 | 部長     | 7500     |
| 山本三郎 | 部長     | 9200     |
ワークテーブルは空ではないので、結果テーブルにUNION ALLします。成績サマリテーブルをワークテーブルに置き換えます。

【結果テーブル③】

| 部下名   | 上司     | 年次売上 |
|----------|----------|----------|
| 部長     | 部長     | 15000    |
| 課長A    | 課長A    | 12000    |
| 課長B    | 課長B    | 13000    |
| 田中太郎 | 田中太郎 | 6500     |
| 鈴木次郎 | 鈴木次郎 | 7500     |
| 山本三郎 | 山本三郎 | 9200     |
| 課長A    | 部長     | 12000    |
| 課長B    | 部長     | 13000    |
| 田中太郎 | 課長A    | 6500     |
| 鈴木次郎 | 課長A    | 7500     |
| 山本三郎 | 課長B    | 9200     |
| 田中太郎 | 部長     | 6500     |
| 鈴木次郎 | 部長     | 7500     |
| 山本三郎 | 部長     | 9200     |

【成績サマリテーブル③】

| 部下名   | 上司     | 年次売上 |
|----------|----------|----------|
| 田中太郎 | 部長     | 6500     |
| 鈴木次郎 | 部長     | 7500     |
| 山本三郎 | 部長     | 9200     |

そして再度、再帰項を評価します。すると、ワークテーブルは空になります。なので、成績サマリテーブルは出来上がった結果テーブルで置き換えます。ここでwith句の処理は終了です。
最後に、メインクエリで総和をとれば完成です。

## 補足１
with recursive句を使ったクエリでは以下が成り立ちます。

1. N番目のwithテーブル = N-1番目のワークテーブル
2. N番目の結果テーブルはN番目までのwithテーブルのUNION[ALL]になっていること

再帰項を評価する際は、前回の再帰項の評価結果を参照していることと、評価結果がどんどん積みあがっていることがわかりますね。

## 補足２
今回with recursive句で作成した成績サマリテーブルは閉包テーブルという構造をしています。隣接リストモデルから閉包テーブルへの変換に必要なのは、営業成績テーブルを部下名と上司名で自己結合することを繰り返すことです。部下の部下は自分の部下、その部下も自分の部下、、、ということをうまく表現できていますね。