SQLアタマアカデミー
第5回 SQLで木構造を扱う~入れ子集合モデル (1)入れ子集合モデルとは何か
はじめに
木構造と呼ばれるデータ構造の一種があります。1つのルート
この構造は,
このように,
本稿で取り上げるのは,
- 稼働環境
- すべてのリレーショナルデータベース
入れ子集合モデルとは何か~集合vs.ポインタ~
まず,
図1 木構造のサンプル
従来,
図2 隣接リストモデルによる木構造の表現
隣接リストモデルによる木構造の表現
emp | boss | Role |
---|---|---|
足立 | NULL | 社長 |
猪狩 | 足立 | 部長 |
上田 | 足立 | 部長 |
江崎 | 上田 | 課長 |
大神 | 上田 | 課長 |
加藤 | 上田 | 課長 |
木島 | 江崎 | 社員 |
みなさんも,
一方,
- 木構造のノードを円
(集合) とみなし, 階層関係を円の包含関係として捉えなおす。
ノードを円とみなすとはどういうことか。それは,
図3 入れ子集合モデルによる木構造の表現
図4 OrgChart
OrgChart
emp | ift | rgt |
---|---|---|
足立 | 1 | 14 |
猪狩 | 2 | 3 |
上田 | 4 | 13 |
江崎 | 5 | 8 |
木島 | 6 | 7 |
大神 | 9 | 10 |
加藤 | 11 | 12 |
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 日本語版/
有澤 誠・ 和田 英一 監訳, 青木 孝・ 筧 一彦・ 鈴木 健一・ 長尾 高弘 訳/ アスキー 刊
バックナンバー
SQLアタマアカデミー
- 最終回 OLAP関数で強力な統計処理を実現!―手続き型から理解するSQL (5)集合指向と手続き型
- 最終回 OLAP関数で強力な統計処理を実現!―手続き型から理解するSQL (4)OLAP関数と集約関数を組み合わせる
- 最終回 OLAP関数で強力な統計処理を実現!―手続き型から理解するSQL (3)OLAP専用関数
- 最終回 OLAP関数で強力な統計処理を実現!―手続き型から理解するSQL (2)OLAP関数の基本構文
- 最終回 OLAP関数で強力な統計処理を実現!―手続き型から理解するSQL (1)OLAP関数とは何か
- 第10回 結合大全 (5)非等値結合
- 第10回 結合大全 (4)自己結合
- 第10回 結合大全 (3)外部結合
- 第10回 結合大全 (2)内部結合
- 第10回 結合大全 (1)クロス結合