Redmineチケットの階層化の実装方法

Redmineチケットのテーブルissuesテーブルにlft, rgtというカラムがVer1.0からあって、何に使うのか分かっていなかったが、下記の記事を読んでようやく理解した。
ラフなメモ書き。

【元ネタ】
【Redmine】issuesテーブルのlft・rgtって？ | Roppi.net

SQLアタマアカデミー：第5回　SQLで木構造を扱う～入れ子集合モデル　（1）入れ子集合モデルとは何か ｜gihyo.jp … 技術評論社

SQLアタマアカデミー：第5回　SQLで木構造を扱う～入れ子集合モデル　（2）入れ子集合モデルにおける検索 ｜gihyo.jp … 技術評論社

SQLアタマアカデミー：第5回　SQLで木構造を扱う～入れ子集合モデル　（3）入れ子集合モデルにおける更新 ｜gihyo.jp … 技術評論社

SQLアタマアカデミー：第6回　SQLで木構造を扱う～入れ子区間モデル　（1）もしも無限の資源があったなら ｜gihyo.jp … 技術評論社

SQLアタマアカデミー：第6回　SQLで木構造を扱う～入れ子区間モデル　（2）稠密性について｜gihyo.jp … 技術評論社

SQLアタマアカデミー：第6回　SQLで木構造を扱う～入れ子区間モデル　（3）フラクタルとしての入れ子集合｜gihyo.jp … 技術評論社

Redmineでは、チケットやプロジェクトの階層を無制限に作ることができる。
モデリングにおいて、階層構造とはツリー構造のことであり、再帰構造になる。
ツリー構造はソフトウェアでは普通によく出る。
データモデリングでも、組織構造や部品表、工程表などの生産管理でツリー構造のモデルはよく出る。

RDBでは、ツリー構造の実装方法が面倒な事は以前から知られていた。
よくある例は、自分の親に当たるキーをセットして、Oracleなら再帰SQL(CONNECT BY)を使って問い合わせする。
しかし、階層構造が深くなると、再帰SQLの性能はすごく悪くなるため、テーブル構造を非正規化するバッドノウハウでモデリングする時も多かった。

再帰SQL: プログラマの思索

再帰SQL part2: プログラマの思索

PostgreSQLの再帰SQL: プログラマの思索

業務システム設計に関する本: プログラマの思索

上記の記事を読むと、階層構造は入れ子集合を使うと、ツリー構造をRDBに綺麗にマッピングできるらしい。
issues.lft, rgtは入れ子集合でツリー構造を表現した時、2次元の円の両端の座標を表している。
すると、チケットBの親がチケットAである場合、チケットA.lft＜チケットB.lft＜チケットB.rgt＜チケットA.rgtという関係が成り立つので、このルールを使ってガントチャートを階層化して表示しているわけだ。

興味深い点は、上記の記事によれば、ドナルド・クヌースの古典的な教科書『The Art of Computer Programming』において、上記のアルゴリズムは既に提示されているのに、今まで誰もうまく使いこなせていなかったこと。
RDBMSを作った人達は、ツリー構造を再帰構造で表現することにこだわりすぎて、昔から知られているアルゴリズムに気付かなかったのかもしれない。

上記の記事を読むと、lftとrgtを整数から有理数へ拡張することによって、ツリーへの挿入や削除の処理の性能が良くなる点も指摘している。
その時の考え方として、数学に出てくる「稠密性」がある。
「稠密性」の例としては、古代ギリシャのゼノンのパラドックス「アキレスは絶対に亀に追いつけない」「飛ぶ矢は静止している」がある。
要は「無限」という概念の性質を表しているわけだが、こんな所でそういう考え方が出てくるとは思わなかった。

そんなことを考えると、Redmineのコミッタは、チケットやプロジェクトの階層化の実装方法について、とてもよく考えて作った事がよく分かる。

【追記1】なお、渡辺さんがRedmineのテーブル構造について参考になる記事を書かれているのでリンクしておく。

「強制されたサロゲートキー」の事例を眺める: 設計者の発言

また、RailRoadと言うツールを使うと、Railsのコントローラやモデルなどの関連図を自動生成してくれる。

Redmineのアーキテクチャ: プログラマの思索

【追記2】
上記の記事はミックさんが書かれたらしい。
ミックさんのHPにもSQLでツリー構造を扱う内容が書かれている。

SQLで木と階層構造のデータを扱う（１）―― 入れ子集合モデル
SQLで木と階層構造のデータを扱う（２）―― 経路列挙モデル

「プログラマのためのSQL 第2版」や「達人に学ぶDB設計 徹底指南書」にも入れ子集合モデルの話が掲載されている。