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
	FSR	実行結果（各要素の値）が、いずれかの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	CSR	実行上で発生する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章以降で。

 

TransactionalInformation Systems まとめ 第三章 （２）

（３） 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	FSR	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	CSR	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 スケジュール。

TransactionalInformation Systems まとめ 第三章 （１）

■第三章

１．章構成

3.1 Goal and Overview

3.2 Canonical Concurrency Problems

3.3 Syntax of Histories and Schedules

3.4 Correctness of Histories and Schedules

3.5 Herbrand Semantics of Schedules

3.6 Final State Serializability

3.7 View Serializability

3.7.1 View Equivalence and the Resulting Correctness Criterion

3.7.2 On the Complexity of Testing View Serializability

3.8 Conflict Serializability

3.8.1 Conflict Relations

3.8.2 Class CSR

3.8.3 Conflicts and Commutativity

3.8.4 Restrictions of Conflict Serializability

3.9 Commit Serializability

3.10 An Alternative Correctness Criterion:Interleaving Specifications

3.11 Lessons Learned

Exercises

Bibliographic Notes

２．概略

　（１） the most important patterns of concurrency problems

ここでは３つ紹介されている。

複数のトランザクションが並行実行され、オペレーションがインターリーブしたときに発生する。

	名称	概要	例	参照先
1	lost update	知らぬ間に上書きされてる	r1(x)r2(x)w1(x)w2(x)	P63
2	inconsistent read	いま見たら、さっきと違う	r2(x)w2(x)r1(x)r1(y)r2(y)w2(y)	P64
3	dirty read	取り消し効いてない	r1(x)w1(x)r2(x)a1w2(x)c2	P86

このみっつの中で、dirty readだけ立ち位置が異なる。abortとcommitの組み合わせによって生じる事象なので。

　　　　このあとの節でトランザクションのcorrectnessの捉え方（→serializable）を整理し、それぞれの捉え方における「上記問題を検知（→スケジューリングで実行回避）可否」を確認している。

（２） Syntax of Histories and Schedules

①historyとschedule

トランザクションは「オペレーションの集まり」で「各オペレーションの実行順序」つき。

トランザクションを複数実行する場合、「各トランザクションの各オペレーション」を並べることになる。

この複数のトランザクションを並べてできるものがhistoryやschedule。

　　　historyはトランザクション上のすべてのオペレーション（commitやabortまで）を含み、scheduleはそのprefix。

　　　※P66「histories in this senseare also called complete schedules in the literature. 」

P67 「history is also called a complete schedule in the literature.」

　　　　　②serial

スケジューリングは「オペレーションをインターリーブ（シャッフル）する」ことになる。

このため、複数のトランザクションのオペレーションが入り混じって並ぶ。

この並べ替えた結果がcorrectであるかどうかを判断する基準がserial。

serialとは「トランザクションを単純に順番に実行する」こと。

　　　　　③Transaction sets of a schedule

スケジュール上のトランザクションについて、状況に応じて４つに分類する。

	分類	定義	意味
1	trans(s)	{ti | s contains steps from ti }	すべてのトランザクション（オペレーション）
2	commit(s)	{ti ∈ trans(s) | ci ∈ s}	コミットするトランザクション
3	abort(s)	{ti ∈ trans(s) | ai ∈ s}	アボートするトランザクション
4	active(s)	trans(s) − (commit(s) ∪ abort(s))	未完了のトランザクション

　　　　　④Herbrand Semantics of Schedules

スケジュールにおけるオペレーション順序を考える際、Herbrand Semanticsを基準とする。

Herbrand Semanticsのイメージは

・readは、実行時点で最新の（＝最後にwriteされた）値をreadする。
　　　　　　　　（writeは、自トランザクションでも他トランザクションでもOK）

・writeは、実行時までに自トランザクションでreadした値をもとにwriteする。
　　　Herbrand Universeのイメージは「各データに初期値があって、read→write→read→write→…を繰り返すことで値を更新していく」もの。値の前後関係があるものだ、ということがポイント。