SQLアタマアカデミー

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

初出：WEB+DB PRESS Vol.49（2009年2月24日発売）

SQL, データベース, 木構造, 入れ子集合モデル

この記事を読むのに必要な時間：およそ 1.5 分

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

ルートとリーフを求める

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

たとえば，ルート（ここで言う足立社長）とリーフ（猪狩，木島氏ら）を求めることを考えます。リーフの円は，自分の中に下位の円を一つも含まないという特性を持ちます。したがって，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になります。

SQL, データベース, 木構造, 入れ子集合モデル

著者プロフィール

ミック

SI企業に勤務するDBエンジニア。主にデータウェアハウス業務に従事している。自身のサイト「リレーショナル・データベースの世界」でデータベースとSQLについての技術情報を公開している。『Web+DB Press』で「SQLアタマアカデミー」を連載中。

著書：『達人に学ぶ SQL徹底指南書』（翔泳社、2008）訳書：J.セルコ『SQLパズル 第2版』（翔泳社、2007）

SQLアタマアカデミー：サポートページ