はじめに

木構造と呼ばれるデータ構造の一種があります。1つのルート（根）と呼ばれるノードを始点として，（通常）複数のリーフ（葉）と呼ばれるノードまでを経路で結んでできるデータ構造です。その名のとおり自然界にある「木」の構造ですし，学校時代，確率の授業で樹状図を書いた経験のある人もいるでしょう。

この構造は，私たちの周囲にとてもたくさん存在します。家系図や組織図も木ですし，IT関連の例では，ヒープやRDBのインデックス，ディレクトリ（フォルダ）によるファイルシステムやXMLも木構造です。Webの掲示板でも，最初の書き込みをルートとしてそれに対してコメントがつけられ，そのコメントにまたコメントがつけられるというプロセスで木構造を形成します。ここでは1つの書き込みがノードになります。

このように，IT技術と木構造は切っても切れない関係にありますし，多くの分野で応用されてもいるのですが，実は長いあいだ，木構造の扱いはRDBにとって大きな弱点と言われてきました。二次元表で木のような再帰的構造を表現するうまい方法が見つからなかったからです。

本稿で取り上げるのは，この長年のRDBの弱点を克服できる可能性を秘めた新しい方法論です。その方法の名前は，「入れ子集合モデル（Nested Sets Model）」と言います。新しいといっても，提唱されたのはもう10年以上前のことですが，日本ではまだあまり知られていません。このモデルを考案したのは，データベース界のグルの一人，J.セルコです。以下，彼が2004年にこの方法論を集大成した『Joe Celko's Trees and Hierarchies in SQL for Smarties』（参考資料）を参考として，この魅力的で興味深いモデルを解説していきます。

稼働環境

• すべてのリレーショナルデータベース

入れ子集合モデルとは何か～集合vs.ポインタ～

まず，木構造の具体例として，図1のような簡単な組織図を使います。階層の深さ4レベルの小さな木です。

従来，こういう木構造をRDBで表現するには，隣接リストモデルを使用していました（図2）。

みなさんも，一度は見たことがあると思います。各社員が，自分の上司（木構造では必ず親ノードは1つ）の情報をboss列に持つ，という形式で，これを手がかりとして階層をたどるわけです。いわばRDBが意図的に排除したポインタ概念をこっそり密輸入した方法で，このモデルを使ったときの検索や更新のクエリはかなり複雑で非効率的なものになります。しかし，これ以外にやり方がなかった，というのもまた事実で，しかたなくDBベンダは，このモデルでもうまくSQLで扱えるよう，独自拡張を進めてきました（OracleのCONNECT BYなどがそうです）。

一方，入れ子集合モデルは，RDBの寄って立つ集合概念を，そのまま木構造の記述にも応用できないだろうか，という発想で作られました。その根幹のアイデアは非常に簡単で，次の一文で表現できます。

• 木構造のノードを円（集合）とみなし，階層関係を円の包含関係として捉えなおす。

ノードを円とみなすとはどういうことか。それは，図3と，それを表現したテーブル（図4）を見てもらえばわかります。

1行が1人の社員を表すことは，隣接リストモデルと変わりません。違うのは，一次元の点として表現されていたノードを，直径と面積を持つ二次元の円，すなわち集合に見立てることです。上司は部下を自分の円の内部に抱え込むことになるので，文字通り「腹心」です。lftとrgtの座標は，円の左端と右端のx座標に相当します（注1）。

非常に大胆な視点の転換と思うかもしれませんが，実は，セルコが自分で断り書きをしているように，木構造を入れ子集合で表現するというアイデアそのものは，彼が思いついたわけではありません。ドナルド・クヌースの古典的な教科書『The Art of Computer Programming』第1巻（注2）において，すでにこの考え方が解説されています。セルコは，このアイデアをデータベースに応用したわけです。このモデルは，その集合指向的な発想によって，RDBと非常に相性がよい表現方法なのです。次に，モデルを利用した検索や更新の方法を見ていきましょう。

注1）

最初にこの座標を決める方法としては，一度，隣接リストモデルのテーブルを作り，そこから入れ子集合モデルのテーブルに変換する，という方法が簡単です。ただし，紙幅がないため，この方法は割愛します。詳細を知りたい方は，参考資料の筆者のWebサイトを参照してください。

注2）

The Art of Computer Programming Volume1 Fundamental Algorithms Third Edition 日本語版／有澤 誠・和田 英一 監訳，青木 孝・筧 一彦・鈴木 健一・長尾 高弘 訳／アスキー 刊