SQL : 再帰を図解する

## 背景

　SQL の再帰は，なかなか分かりにくいです．
　そこで，自分なりに図解してみました．

## 準備

　以下の図のような木構造のデータを考えます．
<img width="200" alt="tree.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/43248/3b4377d9-1fe1-3d8e-6c85-57b923b21504.png">
　これを，以下のようになテーブルで表すとします．
　p は 親(parent)， c は 子(child)， n は必要な個数とします．
　A を作るのに B が 1つ， C が 4つ 必要であることを示しています． C は， A を作るときにも B を作るときにも使います．ネジみたいな感じです．
<img width="979" alt="struct.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/43248/f160413a-f000-92e2-900a-e6c429051bdb.png">

## 再帰する SQL
　再帰の処理として，以下の SQL を考えます．

```sql
WITH RECURSIVE r AS (
    SELECT * FROM tree WHERE p = "A"
  UNION ALL
    SELECT tree.* FROM tree, r WHERE tree.p = r.c
)
SELECT * FROM r
```
　では，処理を追いかけてみます．
### 最初のステップ
　先の SQL で， `UNION ALL` の上の部分

```sql
    SELECT * FROM tree WHERE p = "A"
```
は，(ORACLE では？)初期化ブランチと呼ばれており，ここが最初に実行されます．
　その結果が，  `WITH` で指定された `r` というテーブルに書き込まれます．
<img width="６００" alt="step01.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/43248/fe4fdf5c-e992-c5b4-81cf-c318324ae32f.png">

### 再帰 1回目
　先の SQL の， `UNION ALL` の下の部分

```sql
SELECT tree.*
FROM tree, r
WHERE tree.p = r.c
```
は，(ORACLE では？)再帰的ブランチと呼ばれており，ここが再帰的に実行されます．

 まず 1回目として，

```sql
FROM tree, r
```
に従って，`tree` と，上で生成された `r` から，直積のテーブルが生成されます．
　そして

```sql
WHERE tree.p = r.c
```
により `tree.p` と `r.c` が一致するレコードが選択され，

```sql
SELECT tree.* 
```
により `tree` の部分だけ取り出されます．
　これが `r` に書き込まれますが，前の `r` と区別するために `r1` に書き込まれることとします，

<img width="503" alt="step02.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/43248/f035cbd8-602c-636d-a497-e39f7253552c.png">

### 再帰 ２回目

 再帰処理ですので，次は，

```sql
FROM tree, r
```
の処理を，`tree` と，上で生成された `r1` に対して行います．
しかし，`tree` と `r1` の直積のテーブルには， `tree.p` と `r.c` が一致するレコードがないため，次の `r` ここでは `r2` を呼ぶこととしますが，これには何も書き込まれません．

　結果が空だったので，ここで再帰は終了します．

<img  width="８００"　alt="step03.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/43248/b32a1928-8d86-9052-d122-63e31b1214f2.png">

### 結合

 最後に

```sql
  UNION ALL
```
によって， `r`, `r1`, `r2` が結合され，以下のような出力が得られます．

<img width="182" alt="step04.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/43248/8eaf68b6-a43e-1d61-396c-414ae3182d82.png">


## UNION と UNION ALL

　`UNION` と `UNION ALL` の違いを見てみましょう．

　再帰の処理として，以下の SQL を考えます．

```sql
WITH RECURSIVE r AS (
    SELECT c FROM tree WHERE p = "A"
  UNION ALL
    SELECT tree.c FROM tree, r WHERE tree.p = r.c
)
SELECT * FROM r
```
　この SQL は，`r` へ `c` のみを出力します．
　このため，上で追いかけた処理は，以下のようになります．

再帰 1回目
<img width="442" alt="step11.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/43248/f5112b01-22c1-9609-3ec7-a841baac2411.png">

再帰 ２回目
<img width="482" alt="step12.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/43248/7f148524-9a04-18c2-37be-baeece9a5f92.png">

　この結果が結合されますが，
　　`UNION` は重複を排除する
　　`UNION ALL` は重複を排除しない
という処理になることから，以下のように， `r` `r1` で重複している 値C の出力が異なることになります．

<img width="241" alt="union.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/43248/b69564ff-d27b-3258-cc86-87c8f8880234.png">


## まとめ

 　SQLの再帰を図解しているものをいくつか見ましたが，途中で再帰的に生成されるテーブルを書いた方が分かりやすいかなと思い，自分なりに図解してみました．

　最後に，再帰的ブランチを

```sql
    SELECT tree.* FROM tree, r WHERE tree.p = r.c
```
のように，直積(クロス結合)で書いている例がほとんどですが，個人的には

```sql
WITH RECURSIVE r AS (
    SELECT * FROM tree WHERE p = "A"
  UNION ALL
    SELECT tree.* FROM tree INNER JOIN r ON tree.p = r.c
)
SELECT * FROM r
```
のように，内部結合で書いた方が分かりやすいんじゃないかと思っています．