データベーススペシャリスト 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