TransactionalInformation Systems まとめ 第四章 （２）

（３） Locking Schedulers

①locking protocolの全体観

	分類				名称	定義
							Gen()
1	Pessimistic	Locking	Two-phase	LR1 LR2 LR3 LR4		A locking protocol is two-phase if for every output s and every transaction ti ∈ trans(s) it is true that no qli step follows the first oui step, o, q ∈ {r, w}. A two-phase locking protocol is abbreviated 2PL or 2PL scheduler.	⊆ CSR.	⊂ OCSR
2				LR1 LR2 LR3 LR4	C2PL	Conservative 2PL Under static or conservative 2PL (C2PL) each transaction sets all locks that it needs in the beginning, i.e., before it executes its first r or w step. This is also known as preclaiming all necessary locks up front.
3				LR1 LR2 LR3 LR4	S2PL	Strict 2PL Under strict 2PL (S2PL) all (exclusive) write locks that a transaction has acquired are held until the transaction terminates.	⊂ Gen(2PL)
4				LR1 LR2 LR3 LR4	SS2PL	Strong 2PL Under strong 2PL (SS2PL), all locks (i.e., both (exclusive) write and (shared) read locks) that a transaction has acquired are held until the transaction terminates.	⊂ Gen(S2PL)	⊂ COCSR
5				LR1 LR2 LR3 LR4 OS1 OS2 2PL property compatibility(※）	O2PL	Two locks on the same data item, whether due to conflicting operations or not, can be held simultaneously by distinct transactions as long as the lock operations and the corresponding data operations are executed in the same order. Note that the corresponding scheduler thus needs to be more sophisticated than a “pure” lock manager, as it needs some bookkeeping about the ordering of operations in addition to the lock table. We call this third mode ordered sharing and denote the corresponding relationship between lock operations by pli (x) →ql j (x), i ≠ j . Thus, given aschedule s, pli (x) →ql j (x) implies pli (x) <s ql j (x) and pi (x) <s qj (x). 【背景】 2PL cannot generate all schedules in the class OCSR。 This example, history s = w1(x)r2(x)r3( y)c3r2(z)c2w1( y)c1 is not in Gen(2PL), since an initial write lock of t1 on x would block t2. On the other hand, s ∈ CSR and even s ∈ OCSR.	= OCSR	Gen(LTi ) ⊆ CSR
6				AL1 AL2 AL3 AL4	AL Altruistic Locking	a scheduler operates according to the AL protocol (or is an AL scheduler) if it is a 2PL scheduler and obeys the AL rules AL1.AL4. 【キーワード】 donate, in the wake , indebted 【背景】 unlike 2PL, and similar to ordered sharing discussed　in the previous subsection, several transactions may hold conflicting locks on an item simultaneously under certain conditions.	⊂ CSR ※not in COCSR	Gen(2PL) ⊂ Gen(AL)
7			Non-Two-phase	LR1 LR2 LR3 LR4 WTL1 WTL2	Write-only tree locking	lock requests and releases must obey the locking rules LR1–LR4 and the following additional rules for each transaction:	⊆ CSR
8				LR1 LR2 LR3 LR4 WTL1 WTL2 RWTL1	Read Write-only tree locking	RWTL protocol. The rules for each transaction ti are those of the WTL protocol with the addition of one extra rule:RWTL1	⊆ CSR
9		Nonlocking			Timestamp Ordering	TOは「conflictのopererationがすでに実行済であれば、スケジューラはデータマネージャにopererationを送る」。 （２PLは「lockがholdされていたら（opererationがすでに実行されていても）、スケジューラはデータマネージャにopererationを送らない」。） If pi (x) and qj (x), i = j , are operations in conflict, the following has to hold: pi (x) is executed before qj (x) iff ts(ti ) < ts(t j )	⊆ CSR
10					Serialization Graph Testing	Whenever a new operation pi (x) arrives from the transaction manager, the scheduler 1. creates a new node for transaction ti in the current graph G if pi (x) is the first operation it sees from ti ; 2. inserts edges of the form (t j, ti ) into Gfor each operation qj (x) that is in conflict with pi (x), i = j , and that has been output previously; now two cases can arise: (a) The resulting graph Gis cyclic. If pi (x) were executed, the resulting schedule would no longer be serializable. Thus, pi (x) is rejected and ti aborted, and the node for ti and all its incident edges are removed from G. (b) Gis (still) acyclic. Then pi (x) can be output—that is, added to the schedule already output—and the	= CSR
11	Optimistic				BOCC	自トランザクションがreadしているitemについて、他のトランザクションがwriteしていたら自トランザクションをabortする。 a transaction t j is positively validated (or “accepted”) if one of the following holds for each transaction ti that is already committed (and hence has previously been accepted): ti has ended before t j has started (which implies that all of ti has been executed before all of t j ); in this case, if there is a conflict between operations from t j and ti , the corresponding conflict edge will be of the form (ti, tj ), and not vice versa. Otherwise, RS(t j ) ∩ WS(ti) = ∅, and the val-write phase of ti has ended prior to the val-write phase of t j (assuming a “critical section” as discussed earlier). Thus, t j has not had a chance to read from ti , and again if there are conflicts at all, they give rise to an edge from ti to t j , but one in the opposite direction is impossible.	⊆ CSR
12					FOCC	自トランザクションがwriteしているitemについて、他のトランザクションがreadしていたら自トランザクションをabortする。 Let RSn(ti ) denote the read set of ti at some time n. Then t j is accepted under FOCC at that time n if the following holds for all transactions ti that are still reading at time n: WS(t j ) ∩ RSn(ti ) = ∅	= COCSR
13	★				Geometry of locking	THEOREM 4.13 A schedule s for two transactions t1 and t2 is in CSR iff the curve representing s does not separate any two conflict points. THEOREM 4.14 Let s be a schedule for two transactions t1 and t2 containing lock and unlock operations for the transactions. Then DT(s) ∈ CSR iff the curve representing s does not separate conflict regions.	CSR？

※８つの種類のうち、どれかを選択する（トランザクションの性質に応じて決める）

★本の体系図では、Geometry of lockingが含まれていない。節は存在するので、ここでは13として追加。