閉包テーブルの再帰クエリ

# 概要
弊社業務にて閉包テーブルを使った設計を取り入れました。
この時閉包テーブルがどういったものなのか、またSQLを書く際にどのように考えていけばいいのか少し苦戦したのでまとめておきます。
使用しているDBはpostgresql ver14.4です。

# 閉包テーブルとは

RDBで階層構造を表現する際に用いられるデータモデルです。
一つのレコードに対して、また別のレコードが連なっていくことで階層構造を表現することができます。
イメージしやすいのは会社の組織でしょうか。

# ER図

会社組織を参考に、閉包テーブルを考えてみます。
基本的なER図は下記のようになります。

- departments: 組織の部署など役割を表す
- department_closure_tables: 組織の階層構造を表現する
    - ancestor: 祖先を表す
    - descendant: 子孫を表す
    - path_length: 祖先 ~ 子孫までの距離を表す

```mermaid
erDiagram

departments ||--|{ department_closure_tables: ""

departments {
  string key  pk
  string name
}

department_closure_tables {
	string ancestor_key fk
  string descendant_key fk
  int path_length
}
```

# 実際に階層構造をレコードで表現してみる

簡単にするために下記のようなごく単純な階層を表現してみます。
```mermaid
graph TD;
    社長
    社長-->開発部;
    社長-->営業部;
	開発部-->toC開発課;
```

#### departmentsテーブル

| key | name |
| --- | --- |
| top | 社長 |
| department1 | 開発部 |
| department2 | 営業部|
| devision1 | toC開発課 |


#### department_closure_tables

これだけの構造を表現するだけでもレコード数が多くちょっと大変ですね・・。
ポイントは階層構造を表現するために`ancestor_key`と`descendant_key`と組み合わせを網羅する必要があることかなと思います。

No| ancestor_key | descendant_key | path_length |
|---| --- | --- | --- |
1| top | top | 0 |
2| top | department1 | 1 |
3| top | devision1 | 2 |
4| department1 | department1 | 0 |
5| department1 | devision1 | 1 |
6| devision1 | devision1 | 0 |
7| top | department2 | 1 |
8| department2 | department2 | 0 |

# 閉包テーブルのSQL

実際にSQLを書いてみようと思います。
再帰参照などを用いた複雑なクエリになることが多いです。

### あるancestorを起点に、ある深さまで階層を取得する

上記のようなレコードを取りたい場合、下記のようなクエリになります。

```sql
WITH RECURSIVE tree as (
	SELECT
		0 AS depth,
		dcs.ancestor_key AS ancestor_key,
		dcs.descendant_key AS descendant_key,
		dcs.path_length AS path_length
	FROM department_closure_tables dcs
	WHERE
		dcs.ancestor_key = ${from} AND dcs.path_length = 0
UNION ALL
	SELECT
		depth + 1 AS depth,
		dcs2.ancestor_key,
		dcs2.descendant_key,
		dcs2.path_length
	FROM department_closure_tables dcs2
	JOIN tree t ON t.descendant_key = dcs2.ancestor_key AND dcs2.path_length = 1 AND t.depth < ${to}
)
SELECT
    t.depth, t.ancestor_key AS ancestor_key, t.descendant_key AS descendant_key, r.name AS department_name
FROM tree t
INNER JOIN departments d ON d."key" = t.descendant_key
;
```

### クエリの実行結果

変数を下記のように設定した場合の実行結果です。
- from = 'top'
- to = 2

| depth | ancestor_key | descendant_key | resource_name |
| --- | --- | --- | --- |
| 0 | top | top | 社長 |
| 1 | top | department1 | 開発部 |
| 1 | top | department2 | 営業部 |
| 2 | department1 | devision1 | toC開発課 |

# クエリの解説

#### 非再起のクエリ部分

- 起点となる階層を選んでいる この時のdepthを0とする

```sql
	SELECT
		0 AS depth,
		dcs.ancestor_key AS ancestor_key,
		dcs.descendant_key AS descendant_key,
		dcs.path_length AS path_length
	FROM department_closure_tables dcs
	WHERE
		dcs.ancestor_key = 'top' AND dcs.path_length = 0
```

| depth | ancestor_key | descendant_key | path_length |
| --- | --- | --- | --- |
| 0 | top | top | 0 |

#### 次に再起的に実行する部分

- 起点の子孫(descendant_key)からpath_length = 1 のレコードを探します。
- これを検索結果が空になるまで(depthが2より小さい間)続けます。

```sql
	SELECT
		depth + 1 AS depth,
		dcs2.ancestor_key,
		dcs2.descendant_key,
		dcs2.path_length
	FROM department_closure_tables dcs2
	JOIN tree t ON t.descendant_key = dcs2.ancestor_key AND dcs2.path_length = 1 AND t.depth < 2
```

depth = 0 の時、実行結果はdepth = 1になる

| depth | ancestor_key | descendant_key | path_length |
| --- | --- | --- | --- | 
| 1 | top | department1 | 1 |
| 1 | top | department2 | 1 |

depth = 1 の時、実行結果はdepth = 2 になる

| depth | ancestor_key | descendant_key | path_length |
| --- | --- | --- | --- |
| 2 | department1 | devision1 | 1 | toC開発課 |


#### 検索結果を統合する部分

- 上記の検索結果全てをUNION ALLする
- このUNION ALLしたテーブルをtreeと名付ける

```sql
WITH RECURSIVE tree as (
	SELECT
		0 AS depth,
		rcs.ancestor_key AS ancestor_key,
		rcs.descendant_key AS descendant_key,
		rcs.path_length AS path_length
	FROM resource_closure_tables rcs
	WHERE
		rcs.ancestor_key = 'org1' AND rcs.path_length = 0
UNION ALL
	SELECT
		depth + 1 AS depth,
		rcs2.ancestor_key,
		rcs2.descendant_key,
		rcs2.path_length
	FROM resource_closure_tables rcs2
	JOIN tree t ON t.descendant_key = rcs2.ancestor_key AND rcs2.path_length = 1 AND t.depth < 2
)
```

treeテーブル

| depth | ancestor_key | descendant_key | path_length |
| --- | --- | --- | --- | 
| 0 | org1 | org1 | 0 | 
| 1 | org1 | loc1 | 1 | 
| 1 | org1 | loc2 | 1 | 
| 2 | loc2 | pos1 | 1 | 

#### selectで欲しい値を取得する部分

上記で取得したtreeテーブルと、departmentsテーブルをJOINします。
その後SELECTで欲しいカラムを指定しています。

```sql
SELECT
    t.depth, t.ancestor_key AS ancestor_key, t.descendant_key AS descendant_key, r.name AS department_name
FROM tree t
INNER JOIN departments d ON d."key" = t.descendant_key
```

# まとめ
閉包テーブルの再帰参照について書きました。
再帰クエリは使う機会が少ないこともありあまり慣れておらず、文法もクセがあるので理解するまでに少し時間がかかりましたが、使えるようになると非常に便利だなと感じました。
今回の記事では記載しなかったのですが、閉包テーブルを用いることで階層の末尾に新しいレコードを追加したり、階層の中間に新しいレコードを追加したりかなり自由度高く表現することができます。

# さいごに

トレタでは一緒に開発する仲間を募集しています。<br>
興味がある方は是非カジュアル面談へお越しください！

https://www.wantedly.com/companies/toreta/projects