RDB의 계층 구조를 표현하려면..

역시 세상에는 똑똑한 사람이 참 많은거 같아요. RDB에서 계층구조 표현 방식이 참 애매하고 복잡하기만 했는데 이런 방식을 쓰니 아주 간단히 가능하게 되버렸네요. ^^

さて今回は、「RDBで階層構造を扱うには？」です。
あるサイトを構築中に階層構造をもったカテゴリ構造にすることになり、DBでどのよう に扱うか悩みました。
DBはMySQLを採用していたので、この時点でぱっと頭に浮かんだ選択肢は以下のようなものでした。

1. XML-DBを利用する
2. 親カテゴリレコードのプライマリIDを子カテゴリレコードに持たせる
3. 親を含めた『絶対パス』を名称として扱い、取り出した後にパース
4. ファイルシステムに同様のディレクトリ構造を作り、毎回パースする

(1)のXMLDBはオープンソースのeXistやXindice、Yggdrasillなど様々な選択肢がありましたが、カテゴリのみの利用な割 にメンテナンスコストが高すぎるので見送りました。
(2)の親ID格納の実装は容易ですが、取り出し時のクエリが何回も行われるなど、負荷がかかるうえ、何よりエレガントさがありません。
(3)は一旦採用しかけたのですが、取り出しロジックの複雑さが増すので、できればやりたくありません。
(4)は柔軟な対応や検索など相当大変な気がしたので見送り。
すべての案がボツになったところで、いいアイデアはないかとグーグル先生に聞いてみたところ、以下のページが目からウロコだったのでさっそく採用してみま した。

Storing Hierarchical Data in a Database
http://www.sitepoint.com/article/hierarchical-data-database/

英語ですが、PHPとMySQLのソースも掲載されているので、それほど難しくないと思います。
おおざっぱに説明すると、ルートを頂点として各ノードの左右に順にIDを振り、このIDを利用して範囲検索することで、柔軟な取得を可能にするというもの でした。
例となる構造をここに示します。

                     +--------+

                    1|ジョージ|20

                     +--------+

                          |

                  +-------+-----------+

                  |                   |

              +----------+        +------+

             2|ジョナサン|15    16|ディオ|19

              +----------+        +------+

                  |                   |

             +-----------+       +--------+

            3|ジョージ2世|14   17|ジョルノ|18

             +-----------+       +--------+

                  |

              +--------+

             4|ジョセフ|13

              +--------+

                  |

           +------+-------+

           |              |

       +------+      +--------+

      5|ホリィ|10  11|東方仗助|12

       +------+      +--------+

           |

     +----------+

    6|空条承太郎|9

     +----------+

           |

      +--------+

     7|空条徐倫|8

      +--------+

ルートにあたるジョージの左IDが1から始まり、左から順に子孫に番号を振りつつ、 末端の空条徐倫までたどり着くと右IDを振りつつ戻ります。
同様に、兄弟のディオの系列にも番号を振り、最終的にジョージへ戻ります。
テーブルにすると以下のようになります。

CREATE TABLE family (

  "id" INTEGER NOT NULL AUTO_INCREMENT,

  "left_id" INTEGER NOT NULL,

  "right_id" INTEGER NOT NULL,

  "name" VARCHAR(20) NOT NULL,

  "gender" CAHR(1) DEFAULT "M" NOT NULL,

  "stand" VARCHAR(100)

  PRIMARY KEY ("id")

);


+--+-------+--------+-----------+------+--------------------------+

|id|left_id|right_id|   name    |gender|           stand          |

+--+-------+--------+-----------+------+--------------------------+

| 1|      1|      20|ジョージ   |  M   |                          |

| 2|      2|      15|ジョナサン |  M   |                          |

| 3|      3|      14|ジョージ2世|  M   |                          |

| 4|      4|      13|ジョセフ   |  M   |ハーミット・パープル      |

| 5|      5|      10|ホリィ     |  F   |                          |

| 6|      6|       9|空条承太郎 |  M   |スター・プラチナ          |

| 7|      7|       8|空条徐倫   |  F   |ストーン・フリー          |

| 8|     11|      12|東方仗助   |  M   |クレイジー・ダイヤモンド  |

| 9|     16|      19|ディオ     |  M   |ザ・ワールド              |

|10|     17|      18|ジョルノ   |  M   |ゴールド・エクスペリエンス|

+--+-------+--------+-----------+------+--------------------------+

親を含めて子孫を取得する場合、左右IDの数字を指定してやれば取得できます。
例としてジョセフとその子孫を取得する場合は以下のようになります。

 SELECT left_id, right_id, name

   FROM family

  WHERE left_id BETWEEN 4 AND 13

  ORDER BY left_id ASC


+-------+--------+-----------+

|left_id|right_id|   name    |

+-------+--------+-----------+

|      4|      13|ジョセフ   |

|      5|      10|ホリィ     |

|      6|       9|空条承太郎 |

|      7|       8|空条徐倫   |

|     11|      12|東方仗助   |

+-------+--------+-----------+

子孫から親をたどる場合、左IDが子ノードの左ID以下、右IDが子ノードの右以上のIDを探します。
例として東方仗助の親を探す場合は以下のようになります。

 SELECT left_id, right_id, name

   FROM family

  WHERE left_id  < 11

    AND right_id > 12

  ORDER BY left_id ASC


+-------+--------+-----------+

|left_id|right_id|   name    |

+-------+--------+-----------+

|      1|      20|ジョージ   |

|      2|      15|ジョナサン |

|      3|      14|ジョージ2世|

|      4|      13|ジョセフ   |

|     11|      12|東方仗助   |

+-------+--------+-----------+

あるノードから数えた子孫の数は、以下の計算式で算出します。

(ノード右ID - ノード左ID - 1) / 2

ジョナサンを例にすると、

(15 - 2 - 1) / 2 = 6

となり、子孫は6人となります。

また、新たにノードを増やす場合、あらかじめ左右のIDをずらしておきます。
たとえば空条徐倫に娘ができた場合は以下のようになります。

 UPDATE family SET right_id = right_id + 2 WHERE right_id > 7 ORDER BY right_id DESC;

 UPDATE family SET left_id  = left_id  + 2 WHERE left_id  > 7 ORDER BY left_id DESC;

 INSERT INTO family (left_id, right_id, name, gender) VALUES(8, 9, '徐倫の娘');

これを実行すると以下のようなデータになります。

+--+-------+--------+-----------+------+--------------------------+

|id|left_id|right_id|   name    |gender|           stand          |

+--+-------+--------+-----------+------+--------------------------+

| 1|      1|      22|ジョージ   |  M   |                          |

| 2|      2|      17|ジョナサン |  M   |                          |

| 3|      3|      16|ジョージ2世|  M   |                          |

| 4|      4|      15|ジョセフ   |  M   |ハーミット・パープル      |

| 5|      5|      12|ホリィ     |  F   |                          |

| 6|      6|      11|空条承太郎 |  M   |スター・プラチナ          |

| 7|      7|      10|空条徐倫   |  F   |ストーン・フリー          |

| 8|     13|      14|東方仗助   |  M   |クレイジー・ダイヤモンド  |

| 9|     18|      21|ディオ     |  M   |ザ・ワールド              |

|10|     19|      20|ジョルノ   |  M   |ゴールド・エクスペリエンス|

|11|      8|       9|徐倫の娘   |  F   |                          |

+--+-------+--------+-----------+------+--------------------------+


-- 徐倫の娘の親をたどる

 SELECT left_id, right_id, name

   FROM family

  WHERE left_id  < 8

    AND right_id > 9

  ORDER BY left_id ASC

+-------+--------+-----------+

|left_id|right_id|   name    |

+-------+--------+-----------+

|      1|      22|ジョージ   |

|      2|      17|ジョナサン |

|      3|      16|ジョージ2世|

|      4|      15|ジョセフ   |

|      5|      12|ホリィ     |

|      6|      11|空条承太郎 |

|      7|      10|空条徐倫   |

|      8|       9|徐倫の娘   |

+-------+--------+-----------+

この更新方法にはパフォーマンス上の様々な意見があるので、 このモデルをさらに推し進めた方法も存在するようです。
今回はleft_idとright_idに整数値を利用しましたが、ノード追加時に更新が発生するのを防ぐため小数値を利用する方法もあります。
具体的には左IDを8,右IDを9ではなく、左IDを7.3、右IDを7.6にすることで、他レコードへの更新を防ぎINSERT文1度で済むようにす る、という方法です。
この方法であれば、親子関係は維持したまま、だいぶパフォーマンスでは有利になります。
私の場合はそれほど頻繁に更新しないのと、小数だと全体の見渡しがよくなくなると考えたため、この方法は採用しませんでした。

私は上記サイトでこの設計を知ったのですが、後になってWEB+DB PRESSを見直した所 同様の記事を見つました。(Vol49, 50の『SQLアタマアカデミー』著：ミック) 英語が苦手な方は是非こちらをお勧めします。
また筆者の方のWEBサイトにはより詳細に網羅的に記載があります。

SQLで木と階層構造のデータを扱う（１）―― 入れ子集合モデル
http://www.geocities.jp/mickindex/database/db_tree_ns.html

概念自体は古くからあるようなのでご存知の方は多いと思いますが、 今回の自分のように目からウロコがボロボロ落ちる方がいるかもしれないと思い エントリーを書き起こしました。
よいSQLライフを！

[23:52] 「徐倫の娘」(ノード追加) についての実行結果と、小数を利用した方法を追記しました。