組織図やコメントなど階層構造が必要なテーブルの設計とクエリを考える

## はじめに

QiitaやYahooコメントは、ユーザーが記事に対してコメントをつけられる機能があります。また、あるユーザーのコメントに対して、スレッドを立てコメントに対するコメントをすることができます。

どんどん枝分かれし、限度がないコメントたちをどのようにテーブルに落とし込んでいくのか、今回は階層構造のテーブル設計を考えます。

### 備考
MySQL形式でクエリを記述します。


### 階層構造をもつテーブル
階層構造はツリー構造とも呼びます。コメント欄を例に取ると、各コメントは**ノード**と呼ばれます。ノードは１つ以上の子と、一つの親を持てます。

#### ツリー構造の登場人物
- **根っこ（ルート）**...親を持たない最上位のノード
- **葉（リーフ）**...子を持たない、最下部のノード
- **非葉ノード**...ルートとリーフの中間のノード
- **枝（エッジ)**...ノードとノードを繋ぐ線。関係を指す。

![スクリーンショット 2023-12-05 20.58.38.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1650886/1fc4f8a3-7d7c-3702-2146-04c787a54bca.png)

階層構造をもつテーブルの例は、組織図やスレッド形式のコメント欄（掲示板）などがあげられます。


## 素朴な木（ナイーブツリー）
シンプルな案として、階層構造を、一つのテーブルで表現してみましょう。
この素朴な木と呼ばれるテーブル設計は一種のアンチパターンとされています。
しかし、アプリケーションに求められる要件が達成できる場合、その限りではありません。

### テーブル設計

コメントテーブルを考えます。カラムに、各コメントのリプライ対象として親コメントIDを持たせます。また親コメントIDには、外部キー制約としてコメントIDをつけ、存在するコメントのみ登録できるようにします。

#### Comments テーブル

| カラム        | データ型           | 　制約                        |
| ------------------ | --------------------- | ---------------------------------- |
| comment_id         | INT                   | PRIMARY KEY, AUTO_INCREMENT        |
| comment            | TEXT                  | NOT NULL                           |
| article_id         | varchar(10)           | NOT NULL, FOREIGN KEY ,`article_id` references `articles(article_id)`          |
| parent_comment_id  | INT                   | FOREIGN KEY ,`parent_comment_id` references `comments(comment_id)`                       |


SQLに直すとこうなります。

```sql
CREATE TABLE comments (
    comment_id INT AUTO_INCREMENT PRIMARY KEY,-- 主キー　コメントID
    comment TEXT NOT NULL,-- コメント
    article_id varchar(10) NOT NULL,-- 記事ID
    parent_comment_id INT,-- 親コメントID
    FOREIGN KEY (article_id) REFERENCES articles(article_id),
    FOREIGN KEY (parent_comment_id) REFERENCES comments(comment_id)
);
```

次のレコードを登録しました。

| comment_id | comment                  | article_id | parent_comment_id |
|------------|--------------------------|------------|-------------------|
| 1          | コメント1                | A001       | NULL              |
| 2          | コメント2                | A001       | NULL              |
| 3          | コメント1に対するコメント | A001       | 1                 |
| 4          | コメント2に対するコメント① | A001       | 2                 |
| 5          | コメント2に対するコメント② | A001       | 2                 |
| 6          | コメント2に対するコメント②へのコメント | A001       | 5                 |


###  素朴な木は再帰クエリ（CTE）する必要がある

ここで、1つのスレッドのすべての小孫コメントを取得するクエリを考えます。
再帰クエリ（CTE）を使って、求めます。


再帰クエリ（CTE）は、`WITH RECURSIVE`キーワードを指定し、新しい結果が見つかるまで継続的に実行するSQLクエリの書き方です。
今回は、一番初めの根コメントから孫コメントまでを継続的（再帰的）に求めます。


コメント２を含めた、コメント２に対する全ての小孫コメントを取得してみましょう。

```sql
WITH RECURSIVE CommentThread AS (
    -- 初期選択: 親コメントがNULLのもの、つまりスレッドの根コメントを選択
    SELECT comment_id, comment, article_id, parent_comment_id
    FROM comments
    WHERE parent_comment_id IS NULL AND comment_id = 2 -- コメント2を親とする
    UNION ALL
    -- 再帰選択: 前のステップで選択された根コメントに対する子コメントを選択
    SELECT c.comment_id, c.comment, c.article_id, c.parent_comment_id
    FROM comments c
    INNER JOIN CommentThread ct ON c.parent_comment_id = ct.comment_id
)
SELECT * FROM CommentThread;
```

レコードの結果は次のようになります。

![スクリーンショット 2023-12-05 22.30.02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1650886/7c4518e9-d6cf-5e1a-19af-1e9c89ff630d.png)


このように、素朴な木のテーブル設計はクエリが複雑になるデメリットがありますが、テーブル構造自体は非常に簡潔でわかりやすいです。
レコードの挿入、削除を容易に行えるほか、ノードの直近の親と子を取得するのは簡単なクエリで実現できます。

```sql
-- 「コメント２」の子コメントを取得する
SELECT * FROM comments WHERE parent_comment_id = 2;
```

## 代替ツリーモデル
階層構造をもつテーブルの設計の一つに代替ツリーモデルという方法があります。
その中でも、閉包テーブルは、テーブル構造がシンプルなだけでなく、取得クエリが非常に簡潔に書けるテーブル設計です。

閉包テーブルでは、テーブルをメインのテーブルと階層構造テーブルの2つに分けます。
階層構造テーブルは、ツリー全体のパスを格納します。

### テーブル設計　

メインのコメントテーブルには、階層構造を持たせず、コメントに関する情報のみを設定します。
階層構造テーブルでは、直近の親子関係だけでなく、枝（エッジ）情報を全て格納します。

#### ClosureComments テーブル

| カラム   | データ型         | 制約                |
|------------|------------------|---------------------|
| comment_id | INT              | AUTO_INCREMENT, PRIMARY KEY |
| comment    | TEXT             | NOT NULL            |
| article_id         | varchar(10)           | NOT NULL, FOREIGN KEY ,`article_id` references `articles(article_id)`          |

#### CommentTree テーブル

| カラム   | データ型 | 制約                |
|------------|----------|---------------------|
| ancestor   | INT      | NOT NULL, FOREIGN KEY (REFERENCES ClosureComments(comment_id)) |
| descendant | INT      | NOT NULL, FOREIGN KEY (REFERENCES ClosureComments(comment_id)) |

`CommentTree`テーブルはコメントの階層的な関係を表します。ancestorが先祖、descendantが子孫を意味します。


### クエリ
コメント２を含めた、コメント２に対する全ての小孫コメントを取得してみましょう。

```sql
SELECT
    *
FROM
    ClosureComments c
    INNER JOIN
        CommentTree ct
    ON  c.comment_id = ct.descendant
WHERE
    ct.ancestor = 2　-- 祖先にコメント2を指定
;
```

階層構造テーブルを結合し、祖先に根コメントを指定します。

結果は次のとおりです。
![スクリーンショット 2023-12-05 22.28.49.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1650886/4ff42534-b8b9-223e-34c2-21341818716e.png)


このように閉包テーブルはテーブル構造、クエリともにシンプルに記述できるため、階層構造が必要なテーブル設計において非常に有効な手段です。

## まとめ

階層構造が必要なテーブル設計として、素朴な木と閉包テーブルパターンを紹介しました。
どちらも、有効な設計ですがアプリケーションの仕様に適したテーブル設計を選んでください。

### 参考
SQLアンチパターン　2章ナイーブツリー
https://www.oreilly.co.jp/books/9784873115894/