SQLアタマアカデミー

第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の実行結果
emplftrgt
猪狩23
木島67
大神910
加藤1112

反対に、ルートの円は、ほかのどんな円にも含まれないという特性を持ちます。したがって、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の実行結果
emplftrgt
足立114

ノードのレベルを求める

次に、木の中で、ノードがどのレベル(階層)にいるかを調べましょうリスト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の実行結果
emplevel
足立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の実行結果
empworker
足立猪狩
足立上田
猪狩 
上田江崎
上田大神
上田加藤
江崎木島
大神 
加藤 
木島 

外部結合を使っているのは、部下を持たない猪狩氏なども結果に表示するためです。こういう人々が不要なら、内部結合でかまいません。反対に、部下を主軸として上司を表示する場合は、外部結合の主従を逆転してリスト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の実行結果
empboss
足立 
猪狩足立
上田足立
江崎上田
大神江崎
加藤上田
木島上田

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

おすすめ記事

記事・ニュース一覧