待ちグラフとは？まちグラフ
待ちグラフとは、実行中のトランザクションをノード、「AがBの保持するロックの解放を待っている」という関係を有向辺として表した有向グラフ。閉路があればデッドロックが生じていると判定でき、DBMSはこれを周期的に、あるいはロック待ちが発生した時点で調べる。閉路を見つけたら、その中の1つを犠牲者に選んでロールバックし、辺を切って解消する。
最終更新：2026-10-06
この語が出る過去問を解く →背景
デッドロックを完全に予防しようとすると、必要な資源を事前に全部宣言させるか、獲得順序を全アプリで統一するしかなく、開発の自由度を大きく削る。実際にはデッドロックはまれにしか起きないので、多くのDBMSは起きるに任せて、起きたときだけ壊す方針を採る。そのために「待ち」という関係だけを抜き出して閉路の有無に還元したのが待ちグラフである。
具体例
T1→T2→T3→T1という閉路が検出されたら、ロールバックの費用がいちばん小さいものを犠牲者に選んで取り消す。PostgreSQLはロック待ちが一定時間続いたときにこのグラフを調べ、デッドロックと判定するとエラーを返す。
試験での引っ掛け
待ちグラフはデッドロックの検出手法であって、予防（回避）の手法ではない。予防側はタイムスタンプの順で待つか殺すかを決める方式（wait-die／wound-wait）や、資源への一方向の順序付けである。閉路があって初めてデッドロックであり、辺が何本あっても閉路が無ければ待っているだけで進む。
関連用語
出た過去問
出典：平成28年度 春期 データベーススペシャリスト試験 午前Ⅱ 問13（IPA）
DBMSにおいて、トランザクション間でデッドロックが発生していることを検出するために使用するものはどれか。
正解：待ちグラフ
要点：待ちグラフの閉路でデッドロックを検出する
待ちグラフは、トランザクションをノード、ロック解放を待っている関係を有向辺として表したグラフである。このグラフに閉路が生じていれば互いに待ち合う状態、すなわちデッドロックが発生していると判定できる。
出典：平成30年度 春期 データベーススペシャリスト試験 午前Ⅱ 問16（IPA）
DBMSにおいて、デッドロックを検出するために使われるデータ構造はどれか。
正解：待ちグラフ
要点：待ちグラフの閉路がデッドロックの判定材料になる
待ちグラフは、トランザクションをノード、あるトランザクションが別のトランザクションのロック解放を待っている関係を有向辺として表す。このグラフに閉路があれば互いに待ち合っている状態であり、デッドロックの発生と判定できる。
出典：平成31年度 春期 データベーススペシャリスト試験 午前Ⅱ 問10（IPA）
出典：令和6年度 秋期 データベーススペシャリスト試験 午前Ⅱ 問13（IPA）
トランザクションA〜Gの待ちグラフにおいて、永久待ちの状態になっているトランザクション全てを列挙したものはどれか。ここで、待ちグラフのX→Yは、トランザクション…
正解：B, C, D, F
要点：永久待ちは待ちグラフの閉路とそこへ到達する待ち全部
待ちグラフに閉路があると、その閉路上のトランザクションは互いのアンロックを待ち続けるためデッドロックとなる。さらに、閉路上のトランザクションを待っているトランザクションも、閉路が解消されない限り永久に待たされる。したがって永久待ちは閉路の構成メンバーと、そこへ到達する矢印を持つものの合計になる。閉路に含まれず一方向に待つだけのものは、いずれ解放されるので永久待ちではない。
出典：令和7年度 秋期 データベーススペシャリスト試験 午前Ⅱ 問17（IPA）
DBMSにおいて、トランザクション間でデッドロックが発生していることを検出するために使用するものはどれか。
正解：待ちグラフ
要点：デッドロックの検出は待ちグラフの閉路で判定する
待ちグラフは、各トランザクションをノードとし、あるトランザクションが別のトランザクションの保持するロックの解放を待っている関係を辺として表した有向グラフである。このグラフに閉路が現れれば、互いに待ち合って進めない状態、すなわちデッドロックが発生していると判定できる。検出後はいずれかを強制終了して閉路を断つ。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。