前回のまとめ
VSRを定義したけれどまだ実用性が足りない。
Conflict Equivalence
スケジュールに対して以下の条件で集合confを定義する
- 2つのトランザクション中の操作が同一の値に触れ、少なくともどちらかが
Writeである場合に競合と呼ぶ - スケジュールの中で競合している操作a,bについて操作a→操作bの順に触った場合にそれをa→bの競合関係と呼び、{a, b}と表記する
- すべての競合に対してそれを行いすべての競合関係の集合をconfとする
2つのスケジュールについてそれぞれのconfが一致する場合にConflict Equivalent（以下競合等価）と呼ぶ。
文章で読んでもピンとこないので、とあるスケジュール図Aを例に描いてみると例えばこのようになる。
並行して実行されたTx1, Tx2の2つのトランザクションについて、同一の値に対して読み書きした操作のペア(競合関係)を赤い矢印で表現している。トランザクションaのnステップ目の操作をTxa_nと表記するとして、上の図からは以下の集合conf①が得られる。
conf = ({Tx1_1, Tx2_1}, {Tx2_2, Tx1_2}, {Tx2_2, Tx1_3})
赤い矢印が3本あるので、集合の大きさも3となる。与えられた実行スケジュール2つについて、この集合が一致した場合に、2つのスケジュールはConflict Equivalentであるという。そして何らかの順序で逐次実行したトランザクションとConflict Equivalentであるスケジュールの事をConflict Serializable(以下CSR)であると言う。
conf = ({Tx1_1, Tx2_1}, {Tx1_2, Tx2_2}, {Tx1_3, Tx2_2})
conf = ({Tx2_1, Tx1_1}, {Tx2_2, Tx1_2}, {Tx2_2, Tx1_3})
conf②はTx1→Tx2の順で直列実行した場合のスケジュールであり、conf①とは内容が違う。
conf③はTx2→Tx1の順で直列実行した場合のスケジュールであり、conf①とは内容が違う。
そのためconf①を作る一番上のスケジュール図AはCSRではない。
というようにCSRであるかを検定できる。
VSRが満たされるこのスケジュールは
conf = ({Tx1_1, Tx2_1}, {Tx1_1, Tx3_1}, {Tx2_1, Tx3_1}, {Tx2_2, Tx1_2}, {Tx2_2, Tx3_2}, {Tx1_2, Tx3_2})
このconfと同一になる逐次実行パターンが存在しないのでCSRとは呼べない。
また逆に、CSRなスケジュールは必ずVSRになる。エルブランセマンティクスがReadとWriteの関係しか表現していなかったのに対し、競合関係の矢印はReadとWriteの関係だけでなくWriteとWriteの関係も表現するからである。
なのでCSRはVSRよりもさらに厳しく狭いスケジュールの集合を表すクラスであり、CSRはVSRの部分集合である。図に表すと以下のようになる。
CSRはFSRやVSRと違い、スケジュールからのCSRの判定が非常に容易である。その手順は以下である。
- 任意のスケジュールが与えられた時、そこから競合集合confを算出する
- confから競合関係を1つ取り出し、その中のTxの順序を逐次実行の順序として仮決めする
- 2を繰り返し逐次実行の順序に矛盾（順序が円環になる）が起きたらCSRではない
- confから競合関係をすべて取り出し終えても矛盾が無ければCSR
これは非常に高速に検定でき、理解しやすい。
さらにはCSRはMonotoneであるという特性を満たす。Monotoneとは「スケジュールから任意のトランザクションが消失してもスケジュールのクラスが変わらない特性であり、アボートや永続化を考える上で重要であるがそこの深追いは後の章にする。