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

強連結成分解析【午前2解説】

正解の理由

解法ステップ

1. 永久待ちの定義を確認する
   • 待ちグラフにおける「永久待ち＝デッドロック」は、X→...→X のような有向閉路が存在することと同値である。
   • 実務・試験では「強連結成分（SCC）のサイズが 2 以上＝閉路がある」として判定するのが確実。
2. 図の矢印を正確に追う
   • 図上の矢印の向きを見て、各ノードからどこへ到達できるかを調べる。
   • 到達可能性を組み合わせることで「互いに到達できるノード集合（SCC）」を抽出する。
3. SCC 検出（手順の一例：Kosaraju 法）
   • 第1段階：元グラフで DFS を行い、終了時刻順（スタック）を得る。
   • 第2段階：グラフの辺の向きを逆にした転置グラフで、スタックの順に DFS を行い、到達したノード群ごとに SCC を取得する。
   • 図に従って適用すると、{B, C, D, F} が一つの SCC（サイズ 4）になり、他ノードはそれぞれ単独の SCC になる。
4. 永久待ち判定
   • SCC のサイズが 2 以上であれば、その構成トランザクション群は永久待ちとなる。よって B, C, D, F が永久待ち。

選択肢別の誤答解説

• ア: A, B, C, D
  • 誤り。A はその集合の一員ではない。A へは到達する辺が入っていても、A から他ノードへ戻る辺がない場合は SCC に含まれず、永久待ちではない。
• イ: B, C, D
  • 誤り。B, C, D は互いに関係が深いが、F も同じ閉路に含まれているため F を抜かすと SCC が不完全になり閉路を表現できない。
• ウ: B, C, D, F
  • 正解。これらが互いに到達可能な強連結成分を作り、デッドロック（永久待ち）を形成する。
• エ: C, D, E, F, G
  • 誤り。E や G は D から到達される下流ノードであり、上流に戻る辺がないため同一の閉路には含まれない（SCC のサイズは 1）。

よくある誤解

• 「到達できれば永久待ち」ではない
  • 単に A→B という一方向のパスがあるだけでは永久待ちとは言えない。相互到達（閉路）が必要。
• 辺の向きを読み間違える
  • 待ちグラフは矢印の向きが重要。向きを逆に読むと誤って閉路を見逃したり、存在しない閉路を作ってしまう。
• SCC の定義を見落とす
  • SCC は「互いに到達可能な最大集合」。部分的な到達可能性で判断せず、必ず最大集合として確認する。

補足コラム

• SCC 検出アルゴリズム比較
  • Kosaraju 法：グラフを二度走査（元グラフと転置グラフ）。実装が比較的直感的。計算量 O(N+M)。
  • Tarjan 法：1 回の DFS で SCC を検出。スタックと低リンク値（low-link）を利用。実装はやや複雑だが効率的。
• デッドロック解消の実務対策（代表）
  • タイムアウトやロールバックで一部トランザクションを中断して閉路を破る。
  • ロック順序を定めて循環を設計で防ぐ（資源獲得順序の統一）。
  • 事前に待ちグラフを監視して自動的に解消する仕組みを導入する。

FAQ