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の実行結果
| 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になります。
SQLアタマアカデミー
- 最終回 OLAP関数で強力な統計処理を実現!―手続き型から理解するSQL (5)集合指向と手続き型
- 最終回 OLAP関数で強力な統計処理を実現!―手続き型から理解するSQL (4)OLAP関数と集約関数を組み合わせる
- 最終回 OLAP関数で強力な統計処理を実現!―手続き型から理解するSQL (3)OLAP専用関数
- 最終回 OLAP関数で強力な統計処理を実現!―手続き型から理解するSQL (2)OLAP関数の基本構文
- 最終回 OLAP関数で強力な統計処理を実現!―手続き型から理解するSQL (1)OLAP関数とは何か
- 第10回 結合大全 (5)非等値結合
- 第10回 結合大全 (4)自己結合
- 第10回 結合大全 (3)外部結合
- 第10回 結合大全 (2)内部結合
- 第10回 結合大全 (1)クロス結合

