第5回　SQLで木構造を扱う～入れ子集合モデル　（2）入れ子集合モデルにおける検索

入れ子集合モデルにおける検索

ルートとリーフを求める

まず入れ子集合の検索で基本となる考え方を理解しましょう。それは「包含関係を調べる」ことです。

たとえば、ルート（ここで言う足立社長）とリーフ（猪狩、木島氏ら）を求めることを考えます。リーフの円は、自分の中に下位の円を一つも含まないという特性を持ちます。したがって、NOT EXISTSによって表現できます（リスト1、図5⁠）⁠。

リスト1　リーフの円を求める

SELECT *
  FROM OrgChart Boss
 WHERE NOT EXISTS
       (SELECT *
          FROM OrgChart Workers
         WHERE Workers.lft > Boss.lft
           AND Workers.lft < Boss.rgt);

図5　リスト1の実行結果

emp	lft	rgt
猪狩	2	3
木島	6	7
大神	9	10
加藤	11	12

反対に、ルートの円は、ほかのどんな円にも含まれないという特性を持ちます。したがって、BossとWorkersを引っ繰り返せばOKです（リスト2、図6⁠）⁠。

このように、階層関係を包含関係で捉え直す考え方が、このモデルのポイントです。

リスト2　リルートの円を求める

SELECT *
  FROM OrgChart Workers
 WHERE NOT EXISTS
       (SELECT *
          FROM OrgChart Boss
        WHERE Workers.lft > Boss.lft
          AND Workers.lft < Boss.rgt);

図6　リスト2の実行結果

emp	lft	rgt
足立	1	14

ノードのレベルを求める

次に、木の中で、ノードがどのレベル（階層）にいるかを調べましょう（リスト3、図7⁠）⁠。この例だと、足立氏が最浅の1、木島氏が最深の4です。この場合もやはり、包含関係が鍵になります。というのも、レベルとは（自分を含めて）自分を包含している円の数で求められるからです。たとえば、大神氏なら、（⁠足立、上田、大神）でレベルは3です。

リスト3　木の深さを求める

SELECT Children.emp , COUNT(Parents.emp) AS level
  FROM OrgChart Parents, OrgChart Children
 WHERE Children.lft BETWEEN Parents.lft AND Parents.rgt
GROUP BY Children.emp;

図7　リスト3の実行結果

emp	level
足立	1
上田	2
猪狩	2
江崎	3
加藤	3
大神	3
木島	4

「自分」もカウント対象ですので、不等号ではなくBETWEENを使っています。このクエリの結果にMAX関数を適用することで、木の高さが4であることもわかります（高さは、最深の木島氏のレベルと同じだからです⁠）⁠。

直属の上司・部下を調べる

隣接リストモデルの場合、直属の上司をデータとして持っていたので、非常に簡単に求められました。一方、入れ子集合モデルの場合は、「⁠自分を含む円のうち、左端座標が最大の円が直属の上司である」という考え方で求められます（ここでも鍵は包含関係です⁠）⁠。

まず、上司を主軸として、それにぶらさがる直属の部下を得るには、リスト4、図8のようになります。

リスト4　上司を軸にぶらさがる部下を得る

SELECT Boss.emp AS boss, Worker.emp AS worker
  FROM OrgChart Boss
       LEFT OUTER JOIN OrgChart Worker
       ON Boss.lft = (SELECT MAX(lft) ←左端座標が最大
                     FROM OrgChart
                    WHERE Worker.lft > lft
                      AND Worker.lft < rgt);

図8　リスト4の実行結果

emp	worker
足立	猪狩
足立	上田
猪狩
上田	江崎
上田	大神
上田	加藤
江崎	木島
大神
加藤
木島

外部結合を使っているのは、部下を持たない猪狩氏なども結果に表示するためです。こういう人々が不要なら、内部結合でかまいません。反対に、部下を主軸として上司を表示する場合は、外部結合の主従を逆転してリスト5、図9のように書けばOKです。

リスト5　部下を軸に上司を表示


SELECT Worker.emp AS worker, Boss.emp AS boss
  FROM OrgChart Worker
       LEFT OUTER JOIN OrgChart Boss
         ON Boss.lft < Worker.lft
        AND Boss.lft = (SELECT MAX(lft)
                          FROM OrgChart
                         WHERE Worker.lft > lft
                          AND Worker.lft < rgt);

図9　リスト5の実行結果

emp	boss
足立
猪狩	足立
上田	足立
江崎	上田
大神	江崎
加藤	上田
木島	上田

今度は、上司を持たない足立社長のboss列だけがNULLになります。