データベース

RDBで階層構造を扱う方法 †

カテゴリーとか階層構造を持ったデータをMySQLで扱いたい。
どうすりゃいいのさ？

リンク †

まずは、Google検索！
MySQL 階層構造 - Google検索

いろいろヒットしました！

• リレーショナル・データベースの世界
  http://www.geocities.co.jp/mickindex/database/idx_database.html
  http://mickindex.sakura.ne.jp/database/idx_database.html

• SQLで木と階層構造のデータを扱う（１）――入れ子集合モデル
  http://www.geocities.co.jp/mickindex/database/db_tree_ns.html
  http://mickindex.sakura.ne.jp/database/db_tree_ns.html
  http://gihyo.jp/dev/serial/01/sql_academy2/000501
• SQLで木と階層構造のデータを扱う（２）――経路列挙モデル
  http://www.geocities.co.jp/mickindex/database/db_tree_pe.html
  http://mickindex.sakura.ne.jp/database/db_tree_pe.html
• SQLで木と階層構造のデータを扱う（３）――入れ子区間モデル
  http://gihyo.jp/dev/serial/01/sql_academy2/000601

• MySQLで階層化データを使うには
  http://www.makizou.com/archives/1616
  https://www.makizou.com/1616

  リレーショナルデータベースの機能内で階層データを扱う方法は以下の３モデルがあります。

  - 隣接リストモデル [Adjacency List Model]

  - 入れ子集合モデル [Nested Set Model]

  - 経路列挙モデル [Path Emuneration Model]（もしくは、経路実体化モデル [Materialized Path Model]）

隣接リストモデル †

それぞれのノード（階層データを構成する個々の要素）が親を保存しておきツリー構造をたどることによりデータ構造を表現します。
Oracleの階層問い合わせのようにSQL拡張がない場合（MySQLにはありません）は、別途プログラム等でループを組む必要がある場合があり、パフォーマンスが良くありません。
比較的理解しやすいですがMySQLで利用するには用途が限られます。

入れ子集合モデル †

ノードを円と見なし親子関係を左右の番号を使用し円の包含関係として捉える事によりデータ構造を表現します。
検索に関しては隣接リストモデルと違い圧倒的有利であるが、直接の親・子やツリー構造をたどるのは複雑になります。
また、親子関係を左右の番号が追加、削除を繰り返すことにより歯抜けになります。（歯抜けが気持ち悪ければ正規化が必要）
構造は面白いが理解しづらくパフォーマンスが良くないところが見られますが、MySQLでも利用できます。

経路列挙モデル †

各ノードに絶対パスをデータとして保存しデータ構造（UNIXのファイルシステムやURLの構造にそっくり）を表現します。
ノード自身のレコードに親子関係がパスとして含まれているので、SQL文が簡素になります。
また、パスは一意なりますし、MySQLでも正規表現を扱えるようになりましたので、極めて高い親和性と高いパフォーマンスが望めます。
MySQLで利用するには、この経路列挙モデルが一番親和性が高いように思います。

経路列挙モデルでOK

経路列挙モデル †

位置情報をファイルシステムと同じ方法で持つ。直観的に分かりやすいので良さげ。

• 経路列挙モデル（準備編）：MySQLで階層化データを使う
  http://www.makizou.com/archives/1662
  https://www.makizou.com/1662
• 経路列挙モデル（検索編）：MySQLで階層化データを使う
  http://www.makizou.com/archives/1670
  https://www.makizou.com/1670
• 経路列挙モデル（更新編）：MySQLで階層化データを使う
  http://www.makizou.com/archives/1674
  https://www.makizou.com/1674

経路列挙モデルの並び替え †

経路列挙モデルで、同じ階層のデータ（同じ親ノードにぶら下がっている子ノード同士）を並び替えるにはどうしたら良いか？

sortフラグを持たせて、大小の数値を付与すればいいの？
並び順まで考えたら、入れ子モデルの方が良いだろうか？

経路列挙モデルは、階層構造の上下関係のデータを持っているけど、並び順のデータは表現できない。

並び順を指定するには、入れ子モデルの方が簡潔だろうか？
…ということで入れ子モデルに変更ｗ

入れ子モデル †

入れ子モデルには、

• 入れ子集合モデル
• 入れ子区間モデル
  の二つが紹介されていました。

入れ子区間モデル †

SQLで木と階層構造のデータを扱う（３）――入れ子区間モデル

入れ子集合モデルには、整数を座標に使っているため、更新時のパフォーマンスが悪いという欠点がありました。それを克服するため、整数から有理数へ一般化したモデル。

第6回　SQLで木構造を扱う～入れ子区間モデル　（1）もしも無限の資源があったなら
http://gihyo.jp/dev/serial/01/sql_academy2/000601

• 入れ子集合モデル（準備編）：MySQLで階層化データを使う
  http://www.makizou.com/archives/1621
  https://www.makizou.com/1621
• 入れ子集合モデル（検索編）：MySQLで階層化データを使う
  http://www.makizou.com/archives/1637
  https://www.makizou.com/1637
• 入れ子集合モデル（更新編）：MySQLで階層化データを使う
  https://makizou.com/1674

データの追加を繰り返すと、識別子の少数化がどんどん進むので、整数を振り直す（正規化）する処理を追加してみるとか。
＝[lft][rgt]を整数に直す処理

並替え可能な経路列挙モデル †

ここまで考えて、経路列挙モデルでsortするアイデアを思いついてしまった！！！

• sortフラグを持たせ、並び順を示す数値を入れる。
• sortフラグの数値は、整数ではなく実数を使う。
  ＝入れ子区間モデルと同じアイデア
• 実数で見づらければ、整数に正規化する処理を入れる。

並び替えの処理 †

これはSQLだと複雑になりそうなので、プログラム側で処理させる。

• 同じ階層のデータ同士は並び替え可能にする。
• 異なる階層のデータ同士は並び替えを不可能にする。
  その判別処理をプログラムで行なう。

テーブル設計 †

参考書 †

達人に学ぶDB設計 徹底指南書 初級者で終わりたくないあなたへ ミック 翔泳社 2012-03-16 ￥ 2,808

「第9章　一歩進んだ論理設計～SQLで木構造を扱う」に、RDBで階層構造を扱う方法が紹介されています。