問題の焦点（新しいモデルが必要な理由）
ツリー構造データを RDB で扱うモデルの役割を再掲します。
- ツリー構造データを RDB テーブルに格納する。
- 任意のノードについて、関連ノードを効率的に取得するクエリを記述する。
RDB でツリー構造データを扱いにくい理由が「ツリー構造データを RDB テーブルに格納する事」だけなら、世界中のデータベースエンジニアを悩ませる問題は存在しません。なぜなら、部分木を取得するための効率的な検索クエリが記述できないことが証明されている「隣接リストモデル」でも「保存した全ノードの情報から元の階層構造を復元する」のは可能だからです。
「効率的な検索クエリを記述する」のが困難である理由は、いくつかあります。
- 検索可能とするためには、各ノードとその祖先ノードの関係データを総て保存する必要がある。
- 検索用に登録するノード関係の数は、ツリーの深度が増えると指数関数的に増加する。
- データの内容によっては、階層の深度が不定になる。
- ツリー構造は二次元的な広がりを持つため、一次元のインデックスを付与するのが難しい。
- etc.
指定ノードから子孫ノードの集合を検索するケースを考えてみます。ノードごとに経路を祖先方向に辿って子孫であるかどうか判定できるのなら簡単な話です。しかし、「宣言型プログラミング」である SQL では、検索クエリの途中で各ノードの個別判定処理は実装できません。
宣言型プログラミングでは、どうすれば部分木や祖先ノードの関係性を検索クエリで表現できるのか?
これこそが、世界中のデータベースエンジニアを悩ませ続けてきた難題でした。 RDB に於けるツリー構造データの問題は、「任意のノードから関連ノードを効率的に取得する検索クエリを記述する」という一点に尽きます。