SerializabilityとMonotonicityとRigorousnessの関係

概要

motononeなスケジュールのクラスでは、スケジュールから任意のトランザクションが消失してもスケジュールのクラスが変わりません。CSRはmonotoneです。

CSRだけではabortを扱うのが難しいため、ロックによる手法を組み合わせます。SS2PLによって作られるスケジュールはCSRかつRigorousnessを満たします。

用語

VSR : View Serializable, ビュー直列可能
CSR : Conflict Serializable, 競合直列可能
詳細は以下の記事を参照ください。
Serializablitiyとは？ 2. View Serializabilityについて - Qiita
Serializablitiyとは？ 3. Conflict Serializabilityについて - Qiita

RC : Recoverability, 回復可能性
ST : Strictness
RG : Rigorousness
詳細は以下の資料を参照ください。
トランザクションの並行実行制御 rev.2
もしこの資料を難しく感じたら、まずは以下の資料を読んでみてください。
Two Phase Lock - Qiita
S2PLと永続化 - Qiita
http://db.ss.is.nagoya-u.ac.jp/~ishikawa/lectures/db16/12.pdf

SS2PL : Strong Strict Two Phase Lock
詳細は以下の資料を参照ください。
Two Phase Lock - Qiita
トランザクションの並行実行制御 rev.2

スケジュールのクラス (class of schedules) :
スケジュールのクラスとはVSR/CSR等といったものを指します。「クラス(class)」を「分類」と訳すとイメージしやすいかもしれません。

history : scheduleと同義
以下のスライドの13ページの用語解説でhistoryとscheduleは同列に並べて解説されています。
トランザクションの並行実行制御 rev.2

monotoneの定義

以下の資料を参考に説明します。
http://www.dis.uniroma1.it/~rosati/gd/1-concurrency.pdf
"Monotone classes of schedules"の章です。

t : トランザクション。後に続く数字はトランザクションの番号。
w/r/c/a : write/read/commit/abort。後に続く数字はトランザクションの番号。
S : スケジュール。()内は操作対象。
Tran(S) : Sのトランザクションのセット。
Π_T(S) : T⊆Tran(S)とし、SからTに含まれないトランザクションを削除したスケジュール。

T⊆Tran(S)とはTはTran(S)の部分集合ということです。つまり、Tran(S)={t1,t2,t3}, T={t1,t2}のような関係です。

Π_T(S)の例を資料から引用します。
S = w1(x) r2(x) w2(y) r1(y) r3(x) w1(y) w3(x) w3(y) c1 a2
T={t1,t2}
Π_T(S) = w1(x) r2(x) w2(y) r1(y) w1(y) c1 a2
Tにはt3が含まれていないため、Π_T(S)はSからt3の操作を削除しています。

スケジュールのクラスEが「全てのT⊆Tran(S)においてΠ_T(S)がEである」ときにEはmonotoneと呼ばれます。つまり、monotoneなスケジュールのクラスは任意のトランザクションが消失してもスケジュールのクラスが変わらない、ということになります。

"Transactional Information Systems"では以下の説明をしています。率直に申し上げますと、私にはうまく解釈（理解）できなかったのでそのまま引用します。もし理解の手助けとなる資料をご存知の方がいらっしゃいましたら、ぜひご教示ください。

Monotonicity of a history class E is a desirable property, since it preserves E under arbitrary projections. Taken the other way around, if a projection of some history s does not belong to a given class E in a dynamic scheduling situation, then it does not make sense to process s any further (or to extend it with additional operations).

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)

VSRはmonotoneではない

以下のスケジュールを検討します。
S = w1(x) w2(x) w2(y) w1(y) w3(x) w3(y)
まず、これがVSRであることをエルブランセマンティクスで確認します。

S = w1(x) w2(x) w2(y) w1(y) w3(x) w3(y)
Tx1_1 = F1()
Tx2_1 = F2()
Tx2_2 = F2()
Tx1_2 = F1()
Tx3_1 = F3()
Tx3_2 = F3()
x = F3()
y = F3()

次にシリアルなスケジュールS'のエルブランセマンティクスを確認します。
S' = w1(x) w1(y) w2(x) w2(y) w3(x) w3(y)
Tx1_1 = F1()
Tx1_2 = F1()
Tx2_1 = F2()
Tx2_2 = F2()
Tx3_1 = F3()
Tx3_2 = F3()
x = F3()
y = F3()

SとS'のエルブランセマンティクスが一致するため、SはVSRといえます。

ここでSとS'からt3を削除したスケジュールを考えます。

Π_{t1,t2}(S) = w1(x) w2(x) w2(y) w1(y)
Tx1_1 = F1()
Tx2_1 = F2()
Tx2_2 = F2()
Tx1_2 = F1()
x = F2()
y = F1()

Π_{t1,t2}(S') = w1(x) w1(y) w2(x) w2(y)
Tx1_1 = F1()
Tx1_2 = F1()
Tx2_1 = F2()
Tx2_2 = F2()
x = F2()
y = F2()

この場合、エルブランセマンティクスが一致しないため、Sからt3を削除したスケジュールはVSRではありません。
また、任意のトランザクション（ここではt3）を削除することでスケジュールのクラス（VSRに該当する⇒該当しない）が変わりました。これはmonotoneなクラスの定義に反しており、VSRはmonotoneではないといえます。

CSRはmonotoneである

CSRはmonotoneです。これを証明もしくは説明する資料が見つからなかったため、ここで直感的な説明を試みます。

S = r1(x) r1(y) r2(x) r2(z) w1(y) r3(y) r3(z) w3(y) w2(x) w2(z)
このときの先行グラフ(precedence graph)は下図となります。

この先行グラフにはサイクルがないため、CSRといえます。

この先行グラフからトランザクションのいずれかを削除しても、サイクルが現れることはありません。つまり、任意のトランザクションを削除してもCSRなままといえます。これからCSRはmonotoneといえます。

monotoneとアボートの関係

monotoneとアボートについて以下の説明をした記事があります。

Monotoneとは「スケジュールから任意のトランザクションが消失してもスケジュールのクラスが変わらない特性」であり、アボートや永続化を考える上で重要である
※括弧閉じを追記しています

Serializablitiyとは？ 3. Conflict Serializabilityについて - Qiita

これに関して詳細を説明する資料を探したのですが、見つけることができませんでした。そこで私なりにアボートの場合の観点から考察してみます。

まず、serializabilityの観点から考察します。
monotoneなスケジュールの任意のトランザクションが消失してもスケジュールのクラスが変わらない、ということはCSRのスケジュールで一部のトランザクションがアボートしてもCSRのままであるといえます。つまり、トランザクションがアボートした後も同じクラス（例えばCSR）であるかを検証する必要がないといえます。

次に、RC/ST/RGの観点から考察します。
CSRとRC/ST/RGは直交しています。また、RC⊃ST⊃RGの関係にあります。
詳しくは以下のスライドの26ページの図を参照ください。
トランザクションの並行実行制御 rev.2
monotoneであるCSRでRC/ST/RGと直交していることから、monotoneということだけではRC/ST/RGを保証することができないとわかります。このままだとabortを扱うのが難しくなります。

serializabilityを満たしながらabortを扱うために、スケジューリングだけでなくロックも組み合わせます。SS2PLによって作られるスケジュールはCSRかつRGを満たすことができます。