SQLアタマアカデミー

第5回 SQLで木構造を扱う~入れ子集合モデル (1)入れ子集合モデルとは何か

この記事を読むのに必要な時間:およそ 1.5 分

はじめに

木構造と呼ばれるデータ構造の一種があります。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レベルの小さな木です。

図1 木構造のサンプル

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

図2 隣接リストモデルによる木構造の表現

隣接リストモデルによる木構造の表現

emp
(社員名)
boss
(上司の名前)
Role
(役職)
足立NULL社長
猪狩足立部長
上田足立部長
江崎上田課長
大神上田課長
加藤上田課長
木島江崎社員

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

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

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

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

図3 入れ子集合モデルによる木構造の表現

図3
 入れ子集合モデルによる木構造の表現

図4 OrgChart

OrgChart

emp
(社員名)
ift
(左端座標)
rgt
(右端座標)
足立114
猪狩23
上田413
江崎58
木島67
大神910
加藤1112

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 日本語版/有澤 誠・和田 英一 監訳,青木 孝・筧 一彦・鈴木 健一・長尾 高弘 訳/アスキー 刊

著者プロフィール

ミック

SI企業に勤務するDBエンジニア。主にデータウェアハウス業務に従事している。自身のサイト「リレーショナル・データベースの世界」でデータベースとSQLについての技術情報を公開している。『Web+DB Press』で「SQLアタマアカデミー」を連載中。

著書:『達人に学ぶ SQL徹底指南書』(翔泳社、2008)訳書:J.セルコ『SQLパズル 第2版』(翔泳社、2007)

SQLアタマアカデミー:サポートページ

コメント

  • 第五のモデル

    「隣接リストモデル」「経路列挙モデル」「入れ子集合(区間)モデル」「閉包テーブルモデル」に続く、第五のモデルを発見しました。

    ◆ Fertile Forest Model(肥沃な森林モデル)
    http://lab.kochlein.com/FertileForest

    現時点で採用率では圧倒的シェアの入れ子集合モデルですが、いずれ FF Model とのシェア争いになると予言しておきます。

    未来のことは、占い者でもない限り分かりませんが。

    Commented : #1  Stew Eucen (2015/10/24, 17:41)

コメントの記入