【要約】SQLアンチパターン　「ナイーブツリー（素朴な木）」

# はじめに
開発をしていく上で、SQLの非効率な書き方やDB設計のアンチパターンを知っておきたいと思いました。

著書「[SQLアンチパターン](https://www.oreilly.co.jp/books/9784873115894/)」を読んで、各部から印象に残った章の内容を抜粋してまとめていきます。

読みづらいところなどあるかと思いますが、少しでも参考になれば幸いです。

:::note info
SQLアンチパターンの要約一覧です。
他の章についても要約してます！
- [【要約】SQLアンチパターン　「ナイーブツリー（素朴な木）」](https://qiita.com/k12da/items/52c3c938d93aaf42926f)
- [【要約】SQLアンチパターン　「インデックスショットガン（闇雲インデックス）」](https://qiita.com/k12da/items/a354caf1ed6a53cb0845)
- [【要約】SQLアンチパターン　「プアマンズ・サーチエンジン（貧者のサーチエンジン）」](https://qiita.com/k12da/items/15705034678e30b1f43d)
- [【要約】SQLアンチパターン　「ディプロマティック・イミュニティ（外交特権）」](https://qiita.com/k12da/items/1c59b4c094ace27a0803)
:::

# I部 データベース論理設計のアンチパターン
## 2章 ナイーブツリー（素朴な木）
### アンチパターン：常に親のみに依存する
- **隣接リスト**
木構造やグラフ構造の階層関係を表現する際に用いられるデータ構造です。

```Trees/anti/adjancency-list.sql
CREATE TABLE Comments(
  comment_id   SERIAL PRIMARY KEY,
  parent_id    BIGINT UNSIGNED,
  bug_id       BIGINT UNSIGNED NOT NULL,
  author       BIGINT UNSIGNED NOT NULL,
  comment_date DATETIME NOT NULL,
  comment      TEXT NOT NULL,
  FOREIGN KEY  (parent_id) REFERENCES Comments(comment_id),
  FOREIGN KEY  (bug_id) REFERENCES Bugs(bug_id),
  FOREIGN KEY  (author) REFERENCES Accounts(account_id)
);
```

- 隣接リストのER図
![anti-pattern.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/677000/18f5be29-6ba8-80c5-868f-cf310eba1850.png)
一つのバグ（Bug）に対して、複数のコメント（Comment）が紐付くという階層構造です。
<br>

- 隣接リストのデータ

|comment_id  |parent_id  |発言者  |コメント|
|---|---|---|---|
|1  |NULL  |Fran  |バグの原因は？|
|2  |1  |Ollie  |ヌルポインターのせいじゃない？|
|3  |2  |Fran  |違うよ。確認済みだ。|
|4  |1  |Kukla  |無効な入力を調べたら？|
|5  |4  |Ollie  |多分、原因はそれだ。|
|6  |4  |Fran  |チェック機能を追加してもらってよき？|
|7  |6  |Kukla  |りょ。修正しました。|

#### 問題点
- より深い階層の子孫を含めれば含めるほど、再帰的なSQL文を書くことになる。結果としてクエリが複雑化してパフォーマンス低下につながる
- 階層構造が変更になったとき、親IDを更新する処理が必要となり、誤った更新をするリスクが高まる

```Trees/anti/ancestors.sql
SELECT c1.*, c2.*, c3.*, c4.*
FROM Comments c1 -- 1階層目
  LEFT OUTER JOIN Comments c2
    ON c2.parent_id = c1.comment.id -- 2階層目
  LEFT OUTER JOIN Comments c3
    ON c3.parent_id = c3.comment.id -- 3階層目
  LEFT OUTER JOIN Comments c4
    ON c4.parent_id = c3.comment.id -- 4階層目
```
隣接リストではツリーの1つの階層が1つのJOINに対応していますが、SQLを書くときにはJOINの数を固定しなければなりません。そのため上記のように４階層までのコメントしか取得できません。

#### アンチパターンを使用してもいい場面
隣接リストの長所は、**ノードの直近の親と子を簡単に取得できること**。<INS>階層構造を持つデータに対して必要な操作が限定的</INS>である場合、隣接リストは有効とのこと。

### 解決策：代替ツリーモデルを使用する
今回は、[経路列挙モデル(Path Enumeration)](#経路列挙)、[入れ子集合モデル(Nested Set)](#入れ子集合モデル)、[閉包テーブルモデル(Closure Table)](#閉包テーブルモデル)を抜粋して例に挙げます。

#### 経路列挙
あるノードから別のノードへ至る全てのパス（経路）を列挙する問題、またはそのためのアルゴリズムです。

```Trees/soln/path-enum/create-table.sql
CREATE TABLE Comments(
  comment_id   SERIAL PRIMARY KEY,
  path         VARCHAR(1000),
  bug_id       BIGINT UNSIGNED NOT NULL,
  author       BIGINT UNSIGNED NOT NULL,
  comment_date DATETIME NOT NULL,
  comment      TEXT NOT NULL,
  FOREIGN KEY  (bug_id) REFERENCES Bugs(bug_id),
  FOREIGN KEY  (author) REFERENCES Accounts(account_id)
);
```

- 経路列挙のデータ

|comment_id  |path  |発言者  |コメント|
|---|---|---|---|
|1  |1/  |Fran  |バグの原因は？|
|2  |1/2/  |Ollie  |ヌルポインターのせいじゃない？|
|3  |1/2/3/  |Fran  |違うよ。確認済みだ。|
|4  |1/4/  |Kukla  |無効な入力を調べたら？|
|5  |1/4/5/  |Ollie  |多分、原因はそれだ。|
|6  |1/4/6/  |Fran  |チェック機能を追加してもらってよき？|
|7  |1/4/6/7/  |Kukla  |りょ。修正しました。|

例えば、パスが「`1/4/6/7/`」であるコメント７の先祖を取得するには、以下のように記述します。
```Trees/soln/path-enum/ancestors.sql
SELECT *
FROM Comments As c
WHERE '1/4/6/7/' LIKE c.path || '%' ;
```
このクエリは、先祖のパスが「`1/4/6/%`」、「`1/4/%`」、「`1/%`」のパターンとマッチします。

また、LIKE術後の引数を逆にすることで、子孫を取得できます。
```Trees/soln/path-enum/descendants.sql
SELECT *
FROM Comments As c
WHERE c.path LIKE '1/4/' || '%' ;
```
パターン「`1/4/%`」は、子孫「`1/4/5/`」、「`1/4/6/`」、「`1/4/6/7/`」とマッチします。

- **経路列挙のメリット**
最短経路問題などにおいて、全ての経路の中から、最も短い経路を見つけることができる。

- **経路列挙のデメリット**
パスの正確な形成やパス値の既存ノードへの対応を保証できない。経路列挙の対象となる構造が頻繁に変化する場合、既存のパス情報が古くなり不正確となる可能性があるためです。

- **経路列挙が求められる場面**
  - **最短経路問題**: 全ての経路の中から、最も短い経路を見つける
  - **多様な経路探索**: 複数の制約条件（コスト、時間、経由地など）を考慮し、最適な経路を探す
  - **ネットワークの信頼性評価**: 複数の経路が存在することで、ネットワークの障害に対する耐性を高める

#### 入れ子集合モデル
直近の親ではなく、子孫の集合に関する情報を各ノードに格納します。
今回の例では、各ノードのnsleftおよびnsrightと呼ばれる数値で表されます。

```Trees/soln/nested-sets/create-table.sql
CREATE TABLE Comments(
  comment_id   SERIAL PRIMARY KEY,
  nsleft       INTEGER NOT NULL,
  nsright      INTEGER NOT NULL,
  bug_id       BIGINT UNSIGNED NOT NULL,
  author       BIGINT UNSIGNED NOT NULL,
  comment_date DATETIME NOT NULL,
  comment      TEXT NOT NULL,
  FOREIGN KEY  (bug_id) REFERENCES Bugs(bug_id),
  FOREIGN KEY  (author) REFERENCES Accounts(account_id)
);
```

- 入れ子集合モデルのデータ

|comment_id  |nsleft  |nsright|発言者  |コメント|
|---|---|---|---|---|
|1  |1  |14|Fran  |バグの原因は？|
|2  |2  |5|Ollie  |ヌルポインターのせいじゃない？|
|3  |3  |4|Fran  |違うよ。確認済みだ。|
|4  |6  |13|Kukla  |無効な入力を調べたら？|
|5  |8  |8|Ollie  |多分、原因はそれだ。|
|6  |9  |12|Fran  |チェック機能を追加してもらってよき？|
|7  |10  |11|Kukla  |りょ。修正しました。|

**nsleft値**（左値）にはノードより下の階層にある、全てのノードが持つ値より小さな値が、
**nsright値**（右値）にはノードより下の階層にある、全てのノードが持つ値より大きな値が与えられます。
この**左値と右値の大小関係**によって、ノード間の親子関係や兄弟関係を表します。

<br>

例えば、コメント４とその子孫は、コメント４のノードの`nsleft`と`nsright`の間にnsleftが含まれるノードを全て検索することによって取得できます。

```Trees/soln/nested-sets/descendants.sql
SELECT c2.*
FROM Comments As c1
  INNER JOIN Comments as c2
    ON c2.nsleft BETWEEN c1.nsleft AND c1.nsright
WHERE c1.comment_id = 4;
```

同様に、コメント６とその先祖は、コメント６のノードのnsleftを、`nsleft`と`nsright`の間に含むノードを全て検索することによって取得できます。

```Trees/soln/nested-sets/ancestors.sql
SELECT c2.*
FROM Comments As c1
  INNER JOIN Comments as c2
    ON c1.nsleft BETWEEN c2.nsleft AND c2.nsright
WHERE c1.comment_id = 6;
```

- **入れ子集合のメリット**
非葉ノード（＝子を持つノード）を削除する場合、そのノードの子孫（孫、ひ孫など）は、削除されたノードの親ノードの直接の子として扱われる。

- **入れ子集合のデメリット**
左値と右値の整合性を保つ必要があり、管理が複雑になる。

- **入れ子集合が求められる場面**
  - 個々のノード操作ではなく、**サブツリーに対する迅速かつ容易なクエリ実行**が重要な場合です
    - 例えば、**商品カテゴリにおける集計において、特定のカテゴリとそのサブカテゴリの商品数を集計する**などの場合

#### 閉包テーブルモデル
直接の親子関係だけではなく、ツリー全体のパスを格納します。
以下のようにCommentsテーブルに加えて、TreePathsテーブルを新たに定義します。それぞれがCommentsテーブルの外部キーである2つの列を持ちます。

```Trees/soln/closure-table/create-table.sql
CREATE TABLE Comments(
  comment_id   SERIAL PRIMARY KEY,
  bug_id       BIGINT UNSIGNED NOT NULL,
  author       BIGINT UNSIGNED NOT NULL,
  comment_date DATETIME NOT NULL,
  comment      TEXT NOT NULL,
  FOREIGN KEY  (bug_id) REFERENCES Bugs(bug_id),
  FOREIGN KEY  (author) REFERENCES Accounts(account_id)
);

CREATE TABLE TreePaths(
  ancestor     BIGINT UNSIGNED NOT NULL,
  descendant   BIGINT UNSIGNED NOT NULL,
  PRIMARY KEY  (ancestor, descendant),
  FOREIGN KEY  (ancestor) REFERENCES Bugs(comment_id),
  FOREIGN KEY  (descendant) REFERENCES Accounts(comment_id)
);
```
テーブルの各行には、先祖/子孫関係を共有するノードの組み合わせを格納します。これは、**ツリー上の離れた位置にあるノードも含めた、すべてのノードが対象**になります。

- 閉包テーブルのデータ

|先祖  |子孫  |先祖|子孫  |先祖|子孫|
|---|---|---|---|---|---|
|1  |1  |1|7  |4|6|
|1  |2  |2|2  |4|7|
|1  |3  |2|3  |5|5|
|1  |4  |3|3  |6|6|
|1  |5  |4|4  |6|7|
|1  |6  |4|5  |7|7|

例えば、コメント4の子孫を取得するには、TreePathsで先祖が４の行を探します。
```Trees/soln/closure-table/descendants.sql
SELECT c.*
FROM Comments As c
  INNER JOIN TreePaths as t ON c.comment_id = t.descendant
WHERE t.ancestor = 4;
```

コメント6の先祖を取得するには、子孫が6の行を探します。
```Trees/soln/closure-table/ancestors.sql
SELECT c.*
FROM Comments As c
  INNER JOIN TreePaths as t ON c.comment_id = t.ancestor
WHERE t.descendant = 6;
```

- **閉包テーブルのメリット**
特定のノードの全ての祖先や子孫を、一つのSQLクエリで効率的に取得できる。

- **閉包テーブルのデメリット**
全ての祖先・子孫の関係を保存するため、テーブルサイズが大きくなりやすい。

- **閉包テーブルが求められる場面**
  - **任意の祖先・子孫の情報を頻繁に取得する必要がある場合**
    - 例えば、組織図で**特定の社員の全ての直属の上司や部下を一覧表示したい場合**など

# まとめ
## 階層的なデータ設計の比較
|設計  |テーブル数  |子へのクエリ実行|ツリーへのクエリ実行  |挿入|削除|参照整合性維持
|---|---|---|---|---|---|---|
|隣接リスト  |1  |簡単|難しい  |簡単|簡単|可能|
|経路列挙  |1  |簡単|簡単  |簡単|簡単|可能|
|入れ子集合  |1  |難しい|難しい  |難しい|難しい|不可|
|閉包テーブル  |2  |簡単|簡単  |簡単|簡単|可能|

- **隣接リスト**
従来最も用いられてきた設計で、ソフトウェア開発者の多くが知っている方法です。
- **経路列挙**
「パンくず」リストなどの実装に効果的ですが、**参照整合性が保証できず**、冗長な情報を格納してしまう可能性があり、脆弱な面があります。
- **入れ子集合**
巧妙すぎる設計手法であり、こちらも同様に参照整合性が保証できない。ツリーの修正よりもツリーの検索が多い場合に適しています。
- **閉包テーブル**
唯一、ノードが複数のツリーへ所属することができる。関連付けを格納するために、**別個のテーブル**が必要。

# 所感
今回は時間の都合で抜粋してまとめました。ですが正直言って、他の章の内容も良かったので、テーマを一つに絞って書くのは難しかったです。

（個人的に、5章の「EAV(エンティティ・アトリビュート・バリュー)や6章の「ポリモーフィック関連」はもう一度読み返したい）

ただそれよりも重要なのは、「**実務や実践の場で活かす**」ことだと思っています。今後DB設計や実装をしていく中で、アンチパターンについて思い出しながら理解を深めていければと思います。

# 参考記事
[階層構造の設計パターン：隣接リスト、経路列挙、閉包テーブルの使い分け【Laravel対応】](https://techblog.asia-quest.jp/202409/design-patterns-for-hierarchical-structures)