閉包テーブル

積読していた「SQLアンチパターン」をようやく読み始めたんですが、冒頭の「閉包テーブル」でいきなりつまずいたので頭の中を整理するために書き出してみます。

全然自信ないまま書いてるので、もし間違っている点があればツッコミいただけると非常に助かります。

**注意** こんな感じなので、もし閉包テーブルについて調べようとしている方がこの記事にたどり着いたら、**若干疑いつつ読んでください**。


## 閉包テーブルとは
データの階層構造を示す表現方法のひとつ。
隣接リストや経路列挙に比べて、テーブルの変更が容易かつ参照整合性が保証しやすい。
デメリットは、テーブルが一つ増えるためデータ領域が増える点（とはいえストレージが大容量化した昨今においては大きな問題ではないと思われる)

## 組織図をつくるという前提で考えてみる
下図のような会社組織があったとして、この階層を表現するデータ構造というのを考えてみます。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/254731/1269d298-f9a6-49ce-654d-26551f5984a1.png)

念のため補足すると、右にいくほど階層が深くなるというイメージです。
役員会は社長直轄、生産技術課は、社長→事業本部→開発部→生産技術課 という階層を表しています。

## まずは各々にユニークなIDを振る
最初に、階層に関係なくIDを振ります。
さきほどの図と照らし合わせるとこんな感じですね。↓
![image.png](https://qiita-image-store.s3.amazonaws.com/0/254731/87c52116-5c60-cdde-a1ad-d041765ae15e.png)
  
実際、DBにテーブルを作る場合はこのようになります。↓
今回はこのテーブルを **組織図名称テーブル** とします。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/254731/b074f2d6-3b15-27bb-0c72-d17d16dc66ee.png)

ここまでが前提条件です。


## 閉包テーブルを作ってみる

では、前提をもとに閉包テーブルを作ります。手順は以下の通りです。

1. 親のIDと、子孫のIDを入れる列を用意する
2. 自分自身を表すデータとして、親と子孫に同じIDを入れる行を作る
3. 子孫からみて、全ての親に対し一つずつ行を作る

順番にやっていきましょう。


### 1. 親のIDと、子孫のIDを入れる列を用意する
まずはこんな感じのカラムを用意します。テーブル名は、**組織図階層テーブル** とします

![image.png](https://qiita-image-store.s3.amazonaws.com/0/254731/16bcb6f0-6c56-6784-b831-945482fc2ee1.png)



### 2. 自分自身を表すデータとして、親と子孫に同じIDを入れる行を作る
これも非常に単純で、こんな感じです。なぜ必要かは後ほどすぐわかります。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/254731/604f4b3f-ad64-91ea-f9d1-c472d967bc7c.png)

### 3. 子孫からみて、全ての親に対し一つずつ行を作る
ここからは間違えないように若干注意しつつ進めます。
「子孫からみて、全ての親に対し一つずつ行を作る」というのを、今回のテーブルで具体的に表現すると、デバイス課を子孫と見た場合、社長→事業本部→製造部→デバイス課 となるため、下記の4行が必要、ということになります。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/254731/96f8ee29-8824-cc39-c998-bef67c0443a2.png)

※上から、社長,事業本部,製造部,デバイス課

この操作を全て終えると下記のようなテーブルが出来上がります。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/254731/bba9f7b4-7327-2bef-5c40-1e209fe1e8e1.png)

## テーブルを検索してみる

例えば、設計課の階層を知りたい場合はchild_id列を設計課のidで検索すると(クエリで書くなら `select * from 組織図階層テーブル where child_id ='14'` )下図のような結果が得られます。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/254731/0401b991-725b-3444-96fc-8145ea481d39.png)

このようにparent_idを抜き出すだけで、1,9,13,14という階層になっていることがわかります。(手順1で自分自身を親と子孫に入れたのはここで表示させるため)

これに名称テーブルをJOINしてやると、このように表示できます。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/254731/584ee292-0e69-3d21-611f-35a0b0a289e6.png)

あとは順番に繋げるだけで、 社長/事業本部/開発部/設計課  という階層を出力することができます。


## 要素を増やす場合
事業本部の下に**第三営業部** が新設された、という場合を考えてみます。
下図の通りDivision_IDは22としましょう。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/254731/a053c473-f314-24eb-c757-06c6efa9e927.png)

この場合は手順は簡単で、組織図階層テーブルに同じ手順で階層のデータを追加すればOKです。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/254731/9da9d23c-1ee2-947a-f527-e041acfe9c2a.png)


## 階層を付け替える場合
さきほどの第三営業部は海外進出のために作られた部署だったのですが、業績が上がってきたので部門から切り離すことにした、という場合を考えます。
新たに**海外戦略本部**が作られ、その下に第三営業部は所属します。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/254731/4c6382d0-0f1b-6e7c-21c3-0ed86f90d7d9.png)

先ほどの通りidは23で海外戦略本部を作り、第三営業部はその下になるよう、所属を事業本部の9から23に変更します。

変更前のテーブル
![image.png](https://qiita-image-store.s3.amazonaws.com/0/254731/506eb6f9-15e4-a879-e7df-28aed4b39b69.png)


変更後のテーブル
![image.png](https://qiita-image-store.s3.amazonaws.com/0/254731/44e47a0c-9bbb-4c03-4df9-e28f0cf2d0a7.png)

ここでひとつ問題が発生します。
海外戦略本部は、第三営業部よりも後にできてしまったため、階層では第三営業部より上なのにidでは下の番号になっているため、ソートした際に矛盾が生じてしまいます。
(parent_idを抜き出すと 1/22/23 ＝ 社長/第三営業部/海外戦略本部  と出力されてしまう)

そのため、第三営業部のidが現在22となっているものを、24 (海外戦略本部の数字より大きい数）に変更する必要があります。
このテーブルだけでなく、組織図名称テーブルのDivision_IDも変更する点に要注意です。

(これ以外でなんかうまい解決方法あったら教えてください。。。。)