データベーススペシャリスト 2024年 午前2 問08

リーフノード抽出【午前2解説】

正解の理由

解法ステップ

1. 隣接リストの子ノード全体を取得する
   SELECT 子ノード FROM 隣接リスト
2. 隣接リストの親ノード全体を取得する
   SELECT 親ノード FROM 隣接リスト
3. 子ノード集合から親ノード集合を差し引く（子 − 親）
   この差を表すのが EXCEPT（ア）なので、順序は必ず「子ノード側を先に、親ノード側を後に」書くこと。

SELECT 子ノード FROM 隣接リスト
EXCEPT
SELECT 親ノード FROM 隣接リスト;

選択肢別の誤答解説

• ア EXCEPT
  正解。集合差（左側から右側を取り除く）を実現するので「子集合から親集合を引く」ことができる。
• イ INTERSECT
  共通部分（子かつ親）を返す。内部ノード（親でもあり子でもあるノード）を返すためリーフ抽出には逆効果。
• ウ UNION
  和集合（重複排除）を返す。子と親の全てをまとめてしまうため、リーフの抽出にはならない。
• エ UNION ALL
  和集合のうち重複排除を行わない版。重複をそのまま残すため結果が冗長になる上、リーフ抽出にならない。

よくある誤解

• EXCEPT の順序を逆に書いてしまう（親 EXCEPT 子）
  これをやると「親であって子でない」ノードが残り、リーフではなく根や中間の親のみが返る。正しくは「子の集合」から「親の集合」を引く。
• NULL の扱いを混同する
  親ノード列に NULL（ルートの親）が存在しても、子ノード列の値と NULL は等しくないため差集合処理に誤りは生じない。ただし NULL の比較や集計を扱う場合は実際のDB挙動に注意する（DBによって NULL の扱い差はある）。
• 結果の順序を期待してしまう
  EXCEPT は集合演算のため順序は保証されない。ソートが必要なら ORDER BY を付与する。

補足コラム

• Oracle では集合差に MINUS を使います（SELECT 子ノード FROM 隣接リスト MINUS SELECT 親ノード FROM 隣接リスト）。
• MySQL 等で EXCEPT/MINUS 未対応の場合は NOT EXISTS や LEFT JOIN を使う方法が一般的で、いずれも意図は「その子ノードを親列に持つ行が存在しない」ことの確認です。

-- NOT EXISTS（多くのDBで推奨される方法）
SELECT c.子ノード
FROM 隣接リスト c
WHERE NOT EXISTS (
  SELECT 1 FROM 隣接リスト p WHERE p.親ノード = c.子ノード
);

-- LEFT JOIN を使う方法（結合結果が存在しない行を抽出）
SELECT c.子ノード
FROM 隣接リスト c
LEFT JOIN 隣接リスト p ON p.親ノード = c.子ノード
WHERE p.子ノード IS NULL;

FAQ