RDB に於けるツリー構造データ
ツリー構造データは「階層構造データ」とも呼ばれます。ツリー構造データを RDB で扱うモデルの役割は、次の二項に要約されます。
- ツリー構造データを RDB テーブルに格納する。
- 任意のノードについて、「部分木」や「親ノード」「子ノード」「祖先ノード」「子孫ノード」などの関連ノードを効率的に取得するクエリを記述する。
1. ツリー構造データを RDB テーブルに格納する
ひとつめの項目「ツリー構造データを RDB テーブルに格納する」という機能をモデルが有しているかどうかの基準は、次のように定義できます。
保存した全ノードの情報から元の階層構造を再生できること。
ツリー構造データをデータベースに保存したはいいけど、元のツリー構造が再生できないのでは保存したことにはなりません。改めて記述する必要もないほど基本的な事なので、ここに異論を挟む人はいないでしょう。
2. 任意のノードについて、関連ノードを効率的に取得するクエリを記述する
ふたつ目の項目は、ツリー構造データを活用する際に、「関連性のあるノード集合を効率的に取得する検索クエリ」が書けるかどうかです。下図のツリー構造データで説明してみます。
[A]
|
+---+---+
| |
[B] [C]
| |
+-+-+ +-+-+
| | | |
[D] [E] [F] [G]
|
+-+-+
| |
[H] [I]
「ノード[C]の部分木を取得したい」という場合、人が目視で検索する場合は、ツリー構造図上で[C]から下方に伸びる枝を辿って全ノードをピックアップします。この例では、[C]の部分木の集合は次のようになります。
[C]
|
+-+-+
| |
[F] [G]
|
+-+-+
| |
[H] [I]
これは単純作業なので、法則性をコンピュータに教えれば全自動で検索してくれるだろうと考えるのが現代の情報処理の常識です。データ集合から指定条件にマッチする集合を検索するのはデータベースの本領ですので、「ツリー構造データをデータベースに入れれば簡単に検索できるようになるはずだ」と、誰もがそう考えるでしょう。
ふたつ目の項目で肝となるのは「効率的に」というフレーズです。目的のノード集合を検索するための検索時間が実用レベルで収まるなら、それは効率的であると言えるでしょう。
ツリー構造データを活用する際、以下のような集合が頻繁に検索されます。先程の図における例を記載しました。部分木は「基点ノード＋子孫ノード」と同義です。
集合|基点ノード|集合
----+:-------:+:--:
親ノード|[B]|[A]
子ノード|[B]|[D] [E]
先祖ノード|[H]|[A] [C] [G]
子孫ノード|[C]|[F] [G] [H] [I]
部分木|[C]|[C] [F] [G] [H] [I]
問題の焦点（新しいモデルが必要な理由）
RDB では、ツリー構造データを扱いにくいことが知られています。もし扱いにくさに関する問題が、ひとつ目の項目「ツリー構造データを RDB テーブルに格納する事」だけなら、世界中のデータベースエンジニアを悩ませる問題は存在しません。なぜなら、部分木を取得するための効率的な検索クエリが記述できないことが証明されている「隣接リストモデル」でも「保存した全ノードの情報から元の階層構造を再生する」のは可能だからです。
ツリー構造データで「効率的な検索クエリを記述する」のが困難である理由は、「任意のノードが有する子孫ノードの階層の深度が固定数ではないこと」が筆頭に挙げられます。指定ノードの子孫ノードの集合を検索する場合、全ノードでノードごとに経路を祖先方向に辿って子孫であるかどうか判定するのなら簡単な話です。しかし、「宣言型プログラミング」である SQL では、検索クエリの途中で個別判定処理は実装できません。
宣言型プログラミングでは、どうすれば部分木や祖先ノードの関係性を検索クエリで表現できるのか？
これこそが、世界中のデータベースエンジニアを悩ませ続けてきた難題でした。RDB に於けるツリー構造データの問題は、「任意のノードから関連ノードを効率的に取得する検索クエリを記述する」という一点に尽きます。
リンク
- ツリー構造データをRDBで扱うための第五のモデル
- RDB に於けるツリー構造データ (1)
- RDB に於けるツリー構造データ (2)
- モデルデザイン
- ノード検索＜祖先ノード系＞
- ノード検索＜子孫ノード系＞
- ノード検索＜親戚ノード系＞
- ノード追加
- ノード移動