読書会に最近出てれないので自習。

p64「Conflict Multiversion Serializability」~p65「Proposition 3.2」の手前まで読んだ。次回はp65「Proposition 3.2」から

Conflict Multiversion Serializability

multiversion view serializability の検査コストはNP-completeであることがわかっている
- これより狭く検査が容易でMulitiversion SerializabilityであるConflict Multiversion Serializabilityを考える
  - いわゆる一般的にMCSRと言われるものだと思う
Conflict Serializabilityと類似している
Theorem 2.9のnon-conflicting step交換の手順をMultiversionで考える
- Theorem 2.9に関してはこちらを参照
- 定理2.9ではconflictを壊わす交換は禁止される
  - 1.W(x)とその後ろのW(x)
  - 2.W(x)とその後ろのR(x)
  - 3.R(x)とその後ろのW(x)
- Multiversionによりこの交換ルールはどのように変わるか。
  - 1→禁止しない
    - multiversionでは上書き前のversionを読むことが可能なため。
  - 2→禁止しない
  - 3→禁止
    - 許可するとreadに対するlegal version mappingを諦めることになる。
    - readの前にwriteを持ってくると元のscheduleをmultiversionでシュミレートすることができなくなってしまう
- Multiversionのconflictは(3)のr-wのみになる。
  - 同じentityに対するr-w以外のstepを交換してserial scheduleを作ることのできるscheduleのことをconflict multiversion serializableと呼ぶ。
MCSRの例

A1:R(x)W(x)        R(y)W(z)
A2:        R(x)W(y)

W2(y)とR1(y)を入れ替えるとSerializable
W2(y)とW1(z)を入れ替えるとSerializable
R2(x)とR1(y)を入れ替えるとSerializable?
- p65:"Finally, we switch A2:R(x) with A1:R(y) and A1:W(z),"とあるがW1(z)がなんで出てくるのかよくわからない？
  - W1(z)は特に触らなくてもSerializableじゃ？