TransactionalInformation Systems まとめ 第三章 （３）
②Serializableのクラス
前述の概要で示される各serializableのクラスを整理。
なお、ここではabortは考慮しない。
※P74 「In our exposition of this chapter, we avoid problems that may result from taking aborted (or aborting) transactions into account (see Bibliographic Notes)
by assuming that transactions are executed in a failure-free environment—in other words, that each and every transaction eventually commits.
We will returnto this discussion in particular in Part III of the book.」
-
分類
定義・条件
ポイント
グラフ
問題検知
lost update
inconsistent read
実行結果（各要素の値）が、いずれかのserialスケジュールを実行した結果と一致する。
LRF
各要素に対して最終値を確定したトランザクション（のwrite）。
readした値がserialスケジュールのreadと合致していること。
（Herbrandを満たすreadとwriteになる）
D1:read fromの関係を結んだもの。
a “step graph” D(s) = (V, E) as follows:
V := op(s)
E := {( p, q) | p, q ∈ V, p →q}
D1(s) can be derived bydropping all vertices (and their incident edges) that represent dead steps.
◯
✕
2
VSR
実行上のreadした値が、いずれかのserialスケジュールを実行した際のreadと一致する。
RF
すべてのトランザクション。
readした値がserialスケジュールのreadと合致していること。
スケジュールにおける途中過程のread・writeが合致することを保証できる。
◯
◯
3
実行上で発生するconflict（r-w,w-r,w-w)について、いずれかのserialスケジュールを実行した際のconflictと一致する（対象と順序）。
G(s)がacyclicであること。
conf(s)
{( p, q) | p, q are in conflict in s and p <s q }
※called the conflict relation of s.
D2:conflictの関係を結んだもの
D2(s) := (V, E) be defined by
V = op(s) and
E = conf(s).
Graph D2(s) is called the conflicting-step graph of schedule s.
G(s):トランザクションのconflict関係を結んだもの（Dはオペレーション単位。これをトランザクション単位にまとめたもの）
Conflict Graph (Serialization Graph)
G(s) = (V, E) of s, is defined by
V = commit(s),
(t, t′) ∈ E ⇐⇒ t = t′ ∧ (∃ p ∈ t)(∃ q ∈ t′) (p, q) ∈ conf(s)
◯
◯
4
OCSR
CSRであり、かつ、serialスケジュールとトランザクションの実行順序（※）が合致すること。
※complete beforeとなるトランザクションの実行順序。
prefix
スケジュール上「最後に完了するトランザクション」より前に完了するトランザクション。
complete before
◯
◯
5
COSCR
CSRであり、かつ、serialスケジュールとconflictの関係が合致すること。
※t1のpとt2のqが「p<q」かつconflictであった場合、「c1<c2」となっていること。
s ∈ COCSR iff
-
s ∈ CSR and
-
there exists a serial s′ such that s′ ≈c s and for all t, t′ ∈ trans(s),
t <s′ t′ ⇒ ct <s ct ′ .
2は「serialスケジュール上のトランザクション実行順序が、もとのスケジュール上のcommiの実行順序と合致する」ということ。
◯
◯
6
CMFSR
Commit serializability
A schedule s is commit serializable if CP(s′) is serializable for every prefix s′ of s.
CMFSR: class of all commit final state serializable histories
CMVSR: class of all commit view serializable histories
CMCSR: class of all commit conflict serializable histories
Closure Properties of Schedule Properties
Let E be a class of schedules.
1. E is prefix closed if for every schedule s in E each prefix of s is also in E.
2. E is commit closed iffor every schedule s in E CP(s) is also in E.
prefix commit closureであると、abort（crash含む）の際に対処しやすい。「スケジュール上のどの時点でabortが発生しても、その時点までにcommitされたトランザクションはcorrectである」と保証できるので。
-
◯
◯
7
CMVSR
◯
◯
8
CMCSR
CSRはCMCSRを満たす
※区別不要
◯
◯
-
※dirty readは11章以降で。
