入れ子集合モデルにおける検索
ルートとリーフを求める
まず入れ子集合の検索で基本となる考え方を理解しましょう。それは「包含関係を調べる」ことです。
たとえば、ルート(ここで言う足立社長)とリーフ(猪狩、木島氏ら)を求めることを考えます。リーフの円は、自分の中に下位の円を一つも含まないという特性を持ちます。したがって、NOT EXISTSによって表現できます(リスト1、図5)。
図5 リスト1の実行結果
emp | lft | rgt |
猪狩 | 2 | 3 |
木島 | 6 | 7 |
大神 | 9 | 10 |
加藤 | 11 | 12 |
反対に、ルートの円は、ほかのどんな円にも含まれないという特性を持ちます。したがって、BossとWorkersを引っ繰り返せばOKです(リスト2、図6)。
このように、階層関係を包含関係で捉え直す考え方が、このモデルのポイントです。
ノードのレベルを求める
次に、木の中で、ノードがどのレベル(階層)にいるかを調べましょう(リスト3、図7)。この例だと、足立氏が最浅の1、木島氏が最深の4です。この場合もやはり、包含関係が鍵になります。というのも、レベルとは(自分を含めて)自分を包含している円の数で求められるからです。たとえば、大神氏なら、(足立、上田、大神)でレベルは3です。
図7 リスト3の実行結果
emp | level |
足立 | 1 |
上田 | 2 |
猪狩 | 2 |
江崎 | 3 |
加藤 | 3 |
大神 | 3 |
木島 | 4 |
「自分」もカウント対象ですので、不等号ではなくBETWEENを使っています。このクエリの結果にMAX関数を適用することで、木の高さが4であることもわかります(高さは、最深の木島氏のレベルと同じだからです)。
直属の上司・部下を調べる
隣接リストモデルの場合、直属の上司をデータとして持っていたので、非常に簡単に求められました。一方、入れ子集合モデルの場合は、「自分を含む円のうち、左端座標が最大の円が直属の上司である」という考え方で求められます(ここでも鍵は包含関係です)。
まず、上司を主軸として、それにぶらさがる直属の部下を得るには、リスト4、図8のようになります。
図8 リスト4の実行結果
emp | worker |
足立 | 猪狩 |
足立 | 上田 |
猪狩 | |
上田 | 江崎 |
上田 | 大神 |
上田 | 加藤 |
江崎 | 木島 |
大神 | |
加藤 | |
木島 | |
外部結合を使っているのは、部下を持たない猪狩氏なども結果に表示するためです。こういう人々が不要なら、内部結合でかまいません。反対に、部下を主軸として上司を表示する場合は、外部結合の主従を逆転してリスト5、図9のように書けばOKです。
図9 リスト5の実行結果
emp | boss |
足立 | |
猪狩 | 足立 |
上田 | 足立 |
江崎 | 上田 |
大神 | 江崎 |
加藤 | 上田 |
木島 | 上田 |
今度は、上司を持たない足立社長のboss列だけがNULLになります。