Go to Qiita Advent Calendar 2024 Top
LoginSignup
5
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

株式会社PRUMAdvent Calendar 2024

Day 15
@k12da(K Yoshida)in株式会社PRUM

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

Last updated at Posted at 2024-12-14

はじめに

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

著書「SQLアンチパターン」を読んで、各部から印象に残った章の内容を抜粋してまとめていきます。

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

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
    一つのバグ（Bug）に対して、複数のコメント（Comment）が紐付くという階層構造です。

  • 隣接リストのデータ
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の数を固定しなければなりません。そのため上記のように４階層までのコメントしか取得できません。

アンチパターンを使用してもいい場面

隣接リストの長所は、ノードの直近の親と子を簡単に取得できること。階層構造を持つデータに対して必要な操作が限定的である場合、隣接リストは有効とのこと。

解決策：代替ツリーモデルを使用する

今回は、経路列挙モデル(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値（右値）にはノードより下の階層にある、全てのノードが持つ値より大きな値が与えられます。
この左値と右値の大小関係によって、ノード間の親子関係や兄弟関係を表します。


例えば、コメント４とその子孫は、コメント４のノードの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対応】

5
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?