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→…を繰り返すことで値を更新していく」もの。値の前後関係があるものだ、ということがポイント。