データベーススペシャリスト 2013年 午前2 問10

待ちグラフのノード割当【午前2解説】

正解の理由

解法ステップ

1. 待ちグラフの矢印の意味を確認する。矢印 T_i → T_j は「T_i が T_j のロック解放を待っている」ことを表す。
2. スケジュールのロック取得・更新の時刻を順に確認する。特に排他ロック（update）を試みたときに既存のロックによって待ちが発生する箇所を探す。
3. 各有向辺とスケジュールの対応を照合する。
   • グラフの c → d：c が d を待つ。スケジュールで T₃ は t3 に select(A)、t9 に update(A) を試みる。T₁ は t1 に select(A) を取り、t10 の commit まで保持するため、T₃（update(A)）は T₁ を待つ。よって c = T₃、d = T₁。
   • グラフの b → a：b が a を待つ。スケジュールで T₄ は t4 に select(B)、t5 に update(B) を試みる。T₂ は t2 に select(B) を取り t2 以降保持しているため、T₄ の update(B) は T₂ を待つ。よって b = T₄、a = T₂。
   • グラフの a → d：a が d を待つ。上で a = T₂、d = T₁ となる挙動は、T₂ が t7 に select(C)（共有）を取り t8 に update(C) を試みるが、T₁ が t6 に select(C) を取り t10 まで保持しているため、T₂ が T₁ を待つことと一致する。
4. 以上よりノード割当は a=T₂, b=T₄, c=T₃, d=T₁ となる。

選択肢別の誤答解説

• ア: T₁
  T₁ は t1, t6 に select を取得し、t10 に commit するまでロックを保持している側であり、他を待つ（矢印の開始点になる）挙動はスケジュール上ほとんど見られない。グラフで a は誰かを待っている（a → d）ので T₁ を a に当てると一致しない。
• イ: T₂
  先述の通り、T₂ は C の update を試みる際に T₁ の共有ロックを待つ（a → d）ほか、B では他に共有ロックを与えており、グラフの構造と完全に整合するため正しい。
• ウ: T₃
  T₃ は A の update(t9)で T₁ の共有ロックを待つ挙動（c → d）を示すため c に対応する。a（待つ側で B/C に関与）には合致しない。
• エ: T₄
  T₄ は B の update(t5)で T₂ の共有ロックを待つ挙動（b → a）を示すため b に対応する。したがって a にはならない。

よくある誤解

• 矢印の向きを逆に解釈する：矢印を「ロックを持っている側が待たれている」と読み違えるとノード割当を逆にしてしまう。矢印は「待っている側 → 待たれている側」。
• 共有ロック同士も待つと考える：共有ロック（select）は基本的に互いに競合しないため、共有取得同士では待たない。待ちが生じるのは通常排他（update）を取得しようとしたとき。
• コミットでしかアンロックされない点を忘れる：合致する待ちが生じるのは、ロックを保持している側がまだ commit していない場合に限られる。

補足コラム

FAQ