TransactionalInformation Systems まとめ 第三章 (2)
(3) Correctness of Histories and Schedules
①全体観
※P109の図ではS3とS5が逆になっている。いまのところ誤植と理解。真相知りたい。
-
分類
サンプル
補足
1
w1(x)w2(x)w2(y)c2w1(y)c1
xとyの更新結果がt1→t2,t2→t1のどちらにも合致しない。
2
w1(x)r2(x)w2(y)c2r1(y)w1(y)c1
w3(x)w3(y)c3
最後のw3(x)w3(y)c3によってxとyの更新結果が確定する。このため、t1→t2→t3,t2→t1→t3のどちらかに合致する。
3
CMFSR
w1(x)r2(x)w2(y)w1(y)c1c2
t2→t1の結果と合致するのでFSR。
prefixのw1(x)w1(y)c1もFSRなのでCMFSR。
ただし、r2(x)はw1(x)をみるのでVSRではない(t2→t1と合致しないので)。
4
VSR
w1(x)w2(x)w2(y)c2w1(y)c1w3(x)w3(y)c3
t1,t2,t3ともreadはserialと合致する(正確にはreadがないので結果的に合致とみなせる)のでVSR。
prefixのw1(x)w2(x)w2(y)c2w1(y)c1はt1→t2とt2→t1のいずれにも合致しないためVSR(FSR)とならず、CMVSRではない。
conflict「w1(x)w2(x)」がt2→t1と合致しないためCSRではない
5
CMFSR
w1(x)r2(x)w2(y)w1(y)c1c2w3(x)w3(y)c3
t2→t1→t3の結果と合致するのでFSR。
prefixのw1(x)r2(x)w2(y)w1(y)c1c2(=S3)FSRなのでCMFSR。これはVSRではないのでCMVSRではない。
r2(x)はw1(x)をみるのでVSRではない(t2→t1と合致しないので)。
6
CMVSR
w1(x)w2(x)w2(y)c2w1(y)w3(x)w3(y)c3w1(z)c1
t1,t2,t3ともreadはserialと合致する(正確にはreadがないので結果的に合致とみなせる)のでVSR。
prefixのw2(x)w2(y)c2w3(x)w3(y)c3はt2→t3でVSRとなるため、CMVSR。
conflict「w1(x)w2(x)」がt2→t1→t3と合致しないためCSRではない
7
w1(x)w2(x)w2(y)c2w1(z)c1
conflict「w1(x)w2(x)」がt1→t2と合致するのでCSR。
※OCSRでないとされるのは、completly beforeに該当するtxが存在しないから?
8
OCSR
w3(y)c3w1(x)r2(x)c2w1(y)c1
conflict「w1(x)w2(x)」が(t3→)t1→t2と合致するのでCSR。
t3はsでもs'(対応するserialスケジュール)でも先頭にある(同じ順序である)ため、OCSR。
c2のあとにc1が実行されるためCOCSRではない
9
COSCR
w3(y)c3w1(x)r2(x)w1(y)c1c2
conflict「w1(x)w2(x)」が(t3→)t1→t2と合致するのでCSR。
t3はsでもs'(対応するserialスケジュール)でも先頭にある(同じ順序である)ため、OCSR。
c1のあとにc2が実行される(commitの順序とserialオーダーが一致する)ためCOCSR。
10
serial
w1(x)w1(y)c1w2(x)w2(y)c2
t1→t2のserial スケジュール。