実行スケジュールを動的に作成したい

Conflict Serializability(CSR)が担保される実行スケジュールはトランザクションの実装上好ましい性質を持っている。
そのCSRを動的に生成する方法の1つがTwo Phase Lock(2相ロックまたは2PL)である。
厳密にはCSRより更に狭い範囲のスケジュールしか許容しないが、詳細はリカバリなどの議論を含むため後日にする。

Two Phase Lockとは、成長相と縮退相の2相からなるロックプロトコルである。
ロックプロトコルとは、複数のロックを獲得・解放する際の取り決め（プロトコル）を規定する物であり、特定のロック実装には依存しない。

Two Phase Lockの規定するプロトコルは以下である。

成長相のあとに縮退相が来なくてはならない。
縮退相のあとに成長相が来る事は許可されていない。
成長相と縮退相はそれぞれ1つずつしか存在してはならない。
成長相はロックを獲得し続けるフェーズ。トランザクションの進行と同時に都度必要なロックを取る事を想定している。
縮退相はロックを解放し続けるフェーズ。最終的にはすべてのロックを手放す事を想定している。

図に書くと以下の様になる。

例えば2つのトランザクションが並行して走るとする。

Tx1: Read(x) Read(y) Write(x)
Tx2: Read(x) Read(y) Write(y)

スケジュール図で表すと以下のようになる。

これが並行して走る場合、2PLではこのようにロックを取る。

この2PLを実行した際の競合関係を整理すると、以下の2パターンのどちらかに限定される。どちらもCSRである。

2PLのプロトコルに従う事によって、競合関係にあるデータ群へのアクセスは完全に直列化される。
教科書では何故直列化されるかと証明する際には背理法を使う事が多い。

2PLの亜種として、Conservative Two Phase Lockというものもある。

これはトランザクション開始時に必要なロックをすべて取るという亜種である。成長相が一瞬で終了している。こちらは後に説明するデッドロックの問題が起きにくいという利点がある。
トランザクション実行前に触るデータがすべて確定はしないのではないかという懸念はある。だが

静的にトランザクション手続きを解析する
最初に取っていないロック以外を取りたくなった時は一旦全部ロックを手放してトランザクションを最初からやり直す

など、様々な工夫を用いて実用することも可能らしいが、商用システムで使っていると聞いたことは無い。
別の亜種としては**Strict Two Phase Lock(S2PL)**というものもある。

こちらはトランザクションの完了後にロックを手放せというもので、プロセス障害などからのリカバリを考えた際に理想的な特性を満たす（詳細は後日）。そのため、データベースの文脈でただ2PLと書いている場合はS2PLを指していることも多い。
より厳密に言うと、ロックはRead-Writeロックで「Read-Lockはコミット前に手放しても良い」という制約が付いたものをS2PLと呼び「Read-Lockもコミットまで手放してはならない」という制約が付いているものを**Strong Strict Two Phase Lock(SS2PL)**と呼ぶ。この特性はコミット前に手放されたRead-Lockを別のトランザクションがWriteロックで取り追い越してコミットしてきた場合に少しややこしい議論になる。詳細はリカバリに付いて書く際に触れる予定。