SQLアタマアカデミー

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

この記事を読むのに必要な時間:およそ 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になります。

著者プロフィール

ミック

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

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

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

コメント

コメントの記入