TransactionalInformation Systems まとめ 第四章 （６）
④Deadlock Handling
デッドロックは、ふたつのシチュエーションから発生しうる。
・複数のitemに対して、複数のトランザクションが「相互に入り繰った順序」でロックした場合
・複数のitemに対して、複数のトランザクションが「lock conversion」を伴ってロックした場合
（t1がr(x)を実行し、t2もr((x)を実行する。これはOK。このあとにt1がw(x)を実行し、t2もw((x)を実行する。
このとき、どちらもlock conversionが発生し、お互いに相手のread lockの解除を待ち合う）。
dead lock detectionは複数の手法がある。おおまかにはperiodicかcontinuous。
-
分類
概要
名称
定義
方式
victim selection
1
Last blocked
Pick the transaction that blocked most recently, that is, the
one that just blocked in the case of continuous detection.
2
Random
From those involved in a deadlock cycle, pick one transaction
randomly.
3
Youngest:
Pick the transaction with the most recent start-up time, that
is, the one that began running most recently.
4
Minimum locks:
Pick the transaction that holds the fewest locks.
5
Minimum work:
Pick the transaction that has consumed the least amount
of resources (e.g., CPU time) so far.
6
Most cycles:
Pick the transaction that breaks the largest number of cycles
7
Most edges:
Pick the transaction that eliminates as many edges as possible.
prevention
1
Wait-die:
If a lock request from transaction ti leads to a conflict with
t j , resolve as follows: if ti started before t j , it is blocked (ti “waits for”t j ); otherwise, it is restarted (ti “dies”). In other words, a transaction can only be blocked by a younger transaction.
2
Wound-wait:
If a lock request from transaction ti leads to a conflict with another transaction t j , resolve as follows: if ti started before t j , then t jis restarted (ti “wounds” t j ); otherwise, ti is blocked (ti “waits for” t j ). Thus, a transaction can only be blocked by an older transaction, and a transaction can kill any younger one it conflicts with.
3
Immediate restart:
If a lock request from ti leads to a conflict with another transaction t j , simply restart ti . Thus, no transaction is ever blocked.
4
Running priority:
If a lock request from ti results in a conflict with t j , resolve as follows: if t j is currently waiting due to another conflict, then restart t j and grant ti ’s lock request; otherwise, block ti . Thus,
blocked transactions are not allowed to impede the progress of active
ones.
timeout
timeout strategy:
For each transaction t the scheduler maintains a timer that is
activated as soon as a step of t is blocked. If the timer times out, t is aborted under the assumption that it has been involved in a deadlock. Clearly, this decision may be wrong, so the choice of the time period for which the timer runs is crucial. Again observe that an aborted transaction has not necessarily been involved in a deadlock.
（４） Hybrid Protocols
①conflictベース
concurrency controlはふたつの問題にわけることができる。
1. rw (and wr) synchronization: read operations are synchronized against write operations, or vice versa;
2. ww synchronization: write operations are synchronized against otherwrite operations, but not against reads.
このふたつの問題への対処それぞれを組合せることを、Hybrid protocolと呼ぶ。
If these synchronization tasks are distinguished, a scheduler can be thought of as consisting of two components, one for each of the respective synchronization tasks.
Since the two components need proper integration (as demonstrated by way of examples shortly), such a scheduler is called ahybrid scheduler.
それぞれについて、以下のように定める。
For rw (and wr) synchronization: two operations are in conflict if theyaccess the same data item, and one is an r step, the other a w step.
For ww synchronization: two operations are in conflict if they access the same data item, and both are write operations.
-
例
rw synchronization へのprotocol
ww synchronization へのprotocol
補足
１
2PL
SGT
２
SS2PL
TO
３
SS2PL
Thomas’ Write Rule (TWR)
Let t j be the Thomas’ Write
transaction that has written x and that has the largest timestamp prior to the Rule (TWR)
arrival of wi (x). If ts(ti ) > ts(t j ), then wi (x) is processed as usual; otherwise, it
is ignored, and the execution of ti continues. Notice that TWR applies to pairs
of write steps only.
②partitionベース
データの分類によって適用するprotocolを分けることもできる。
D, into disjoint subsets D1, D2, . . . , Dn (with n≥ 2, Di ∩ Dj = ∅ for i = j , and Ui=1 to nDi = D).
③specific access characteristicsベース
データのアクセス内容や頻度に応じて分けることもできる。
For example, a data server may manage a small set of very frequently modified data items—so-called hot spots—that constitute subset D1, a large set of less frequently modified data items that form subset D2, and a remaining subset D3 of data items that are never updated online.
-
例
D1
D2
補足
１
SGT
FOCC
However, we need to ensure that this combination preserves the acyclicity of the global conflict graph that is formed by the union of the two conflict graphs for D1 and D2. This is all but trivial for the two considered protocols, and may in fact require some additional cycle testing across both partitions. Such global overhead may, however, render the use of the “lightweight” FOCC protocol pointless, as the overhead of cycle testing would eventually be incurred for all of D1 ∪ D2.
2
SS2PL
FOCC
In this case, the fact that both protocols are commit order preserving conflict serializable (COCSR) eliminates the need for global checks.
TransactionalInformation Systems まとめ 第四章 （５）
・Write-Only Tree Locking
この節では、対象とするデータ構造をhierarchicalに限定している。
we will first assume that the access patterns follow a hierarchical organi ation of the data items; that is, the data items are viewed as the nodes of a tree, and accesses have to follow a path down the tree.
また、readを実行しないトランザクションを対象に議論している。
（トランザクションをwrite onlyに限らなくても成立するが、lockの発生が「many」かつ「unacceptable duration」となる）
we consider a restricted transaction model in which read operations are missing. Thus, a transaction can write a data item
２PLとの違いは「次（children）のlockを取得したら、前（parent）のlockは解放する」こと。
Lemmna4.6にて「If transaction ti locks x before t j does, then each successor v of x in the ata tree that is locked by both ti and t j is also locked by ti before it is
locked by t j .」。これによって、アクセス順序が保証され、deadlock freeが担保される。
-
分類
概要
定義
意味
WTL1
lockする条件
If x is any node in the tree other than the root, wli (x) can be set only if ti currently holds a write lock on y, where y is the parent of x.
parentのlockを取得済の場合にかぎり、lockできる。
WTL2
lock回数の制限
After a wui (x), no further wli (x) is allowed (on the same data item x).
ひとつのトランザクションでは、ひとつのitemへのアクセス（write）は一回のみ
THEOREM 4.11
The WTL protocol is deadlock free.
Proof
If ti waits for a lock on the root, it cannot have set any other lock yet. If ti waits-for a lock held by t j (on a node that is not the root), then t j unlocks
the root before ti locks it. Again by induction we may then conclude that if the waits-for graph has a cycle involving ti , then ti unlocks the root before
ti locks it, a contradiction.
・Timestamp Ordering
【Basic timestamp ordering (BTO)】
1. max-r -scheduled(x): the value of the largest timestamp of a read operation on x already sent to the data manager;
2. max-w-scheduled(x): the value of the largest timestamp of a write operation on x already sent to the data manager.
When some operation pi (x) arrives, then ts(ti ) is compared to max-qscheduled( x) for each operation q that is in conflict with p.
If ts(ti ) < max-qscheduled(x) holds, pi (x) is rejected, since it has arrived too late. Otherwise it is sent to the data manager,
and max-p-scheduled(x) is updated to ts(ti) if ts(ti ) > max-p-scheduled(x).
・Optimistic Protocols
トランザクションを３つのフェーズに分類する。
transaction’s execution as taking place in three phases (see Figure 4.19):
1. Read phase: The transaction is executed, but with all writes applied to a workspace that is private to the transaction only (not to the database). So the private “versions” of data items written by a transaction are not visible to other transactions (yet). Notice that at the end of the read phase of a transaction t, its read set RS(t) as well as its write set WS(t) are known.
2. Validation phase: A transaction that is ready to commit is validated; that is, the scheduler tests whether its execution has been “correct” in the sense of conflict serializability, and whether the transaction’s result can be copied into the database. If this is not the case, the transaction is aborted; otherwise, the next phase is entered.
3. Write phase: The workspace contents are transferred into the database to conclude the transaction’s commit.
３つのフェーズのうち、ValidationとWriteはひとつにまとめて「val-write phase」として考える。
We here assume as a simplification that phases (2) and (3) are executed indivisibly as a noninterruptible “critical section,” meaning that all other transactions are suspended during such a critical section. We correspondingly call this combined phase the val-write phase. Note that the indivisibility of this phase may be quite problematic in a real implementation.
FOCCについては、read onlyトランザクションの取り扱いが特に有効。
Notice that this condition is immediately satisfied if t j is read-only, a particularly nice property. The following can now be verified:
THEOREM 4.18
FOCC validation produces acyclic conflict graphs only, i.e., Gen(FOCC) ⊆CSR.
・Read/Write-Only Tree Locking
WTLprotocolではうまくいかないケースがある。ポイントは「conflictする要素が複数あるとき、parent（以前）の要素がunlockされる」こと。
そこで、pitfallベースでconflictの制御を行う。
pitfallの定義は
The read set RS(t) of t is the set of items read by t, and the write set WS(t) of t is the set of items written by t.
In the presence of a tree, RS(t) spawns a subtree that will generally split into a number of connected components, say, C1, . . ., Cm.
（connected componentは、RS(t)のなかで「つながっている要素をグループ分け」したもの）
A pitfall of t is a set of the form Ci ∪ {x ∈ WS(t) | x is a child or parent of some y ∈ Ci }, 1 ≤ i ≤ m
-
分類
概要
定義
意味
RWTL1
pitfallの制御
The transaction has the two-phase property on each of its pitfalls;
that is, for each pitfall the transaction follows a two-phase rule
with respect to setting and releasing locks on elements of that
pitfall.
pitfallのtwo-phase propertyをみる。
※これによって「treeをすべてtraverseすることなく、conflict対象のチェックをかけられる」ようになる。
LEMMA 4.7
Let T be a given database tree, and let t be a transaction on T that obeys the rules of the RWTL protocol. Let V ⊆ RS(t) ∪ WS(t) span a connected
subtree of T. Then the restriction V(t) of t to V also follows the rules of RWTL.
→あるtree上でRWLTにしたがうトランザクションは、tree上の部分集合V（トランザクションのオペレーションのProjection）でもRWLTにしたがう。
LEMMA 4.8
Assume that transaction t has the two-phase property on V ⊆ RS(t) ∪ WS(t), and letW⊆RS(t) ∪ WS(t). ThenW(t) has the two-phase property on V ∩W.
→tree上の部分集合V（トランザクションのオペレーションのProjection）がRWLTにしたがえば、さらにその部分集合もRWLTにしたがう。
・Geometry of Locking
【この説明における前提】簡易な説明となるよう「平面」にて扱う＝トランザクションはふたつ。
We restrict our attention to the case of two transactions for reasons of simplicity; however, what we present in this subsection can be generalized to more than two transactions. We assume that our two transactions are completely known.
【説明】平面の縦軸と横軸にトランザクションのオペレーションをとる。それぞれのオペレーション実行ごとに、縦軸横軸を移動し、折れ線を描く。
For each transaction its sequence of steps is represented as a sequence of equidistant integer points on one of the axes spanning the Euclidean plane. The two transactions then define a rectangular grid in that plane, and a schedule becomes a monotone curve starting in the origin of the coordinates.
A grid point is a conflict point if the two steps corresponding to its coordinates (one on the x axis, the other on the y axis) are in conflict.
Aschedule for two transactions separates given conflict points if, informally, these points occur on both sides of the curve
このとき
・lockとunlockは各operationの間に差し込む。
・lockとunlockで、lock期間を表す。
・縦軸と横軸に対して、同じitemへのlock期間を重ねあわせて、部分平面をつくる → これがconflictを表す。
・スケジュールにしたがって、縦軸と横軸のオペレーションに基づいた折れ線を描く。
・この折れ線に対して、上述の部分平面が「同じ側」に収まっていなかったらconflict。
これは「このスケジュールでは、conflictするitemについて、それぞれのlockの取得順序が一致していない」ことを示している。
TransactionalInformation Systems まとめ 第四章 （４）
③Rules for locking
・well-formed locking
-
分類
概要
定義
意味
LR1
lockとunlockのタイミング
If ti contains a step of the form ri (x) [wi (x)], then schedule s also contains a step of the form rli (x) [wli (x)] before the data operation (i.e., a lock on x is held at the point of the operation on x). Moreover, s contains a step of the form rui (x) [wui (x)] somewhere after the operation.
operationに対して、lockは先に、unlockはあとに
LR2
lockの回数
For each x accessed by ti , schedule s has at most one rli (x) and at most one wli (x) step; in other words, locks of the same type are set at most once per transaction and per data item.
１つのitemに対して、lockは「１トランザクション中に１回のみ」。readとwrite、それぞれ。
LR3
unlockの回数
No step of the form rui (.) or wui (.) is redundant (i.e., executed per transaction more than once).
１つのitemに対して、lockは「１トランザクション中に１回のみ」。readとwrite、まとめて。
LR4
lockとconflict
if x is held locked by both ti and t j for ti, tj ∈ trans(s), i = j ,
then these locks are not in conflict (i.e., they are compatible).
１つのitemに対して、複数のトランザクションでlockしていた場合、conflictしていない。
・well-formed locking
-
分類
概要
定義
意味
OS1
lockとopの順序
In a schedule s, for any two operations pi (x) and qj (x), i = j , such that pli (x) →ql j (x) is permitted, if ti acquires pli (x) before
t j acquires ql j (x), then the execution of pi (x) must occur before the execution of qj (x).複数のトランザクションで同じitemへのoperationが発生した場合、lockの順序とoperationの順序が一致すること。
OS2
lockの保持期間
While a transaction is on hold, it cannot release any of its locks.
※on holdとは
So for a correct protocol, we need a rule for unlocking. If we have a relationship pli (x) →ql j (x) of ordered sharing between two transactions ti and t j ,and ti has not yet released any lock, t j is called order dependent on ti . If ther eexists any such ti , transaction t j is on hold.
先行してlockを取得したトランザクションのunlock待ち（on hold）の間は、自トランザクションもunlockを実行しない。
※on holdの間は、先行したトランザクションが「許容不可となるoperationを実行する（＝not CSRになる）」かもしれない。このため、on hold側のトランザクションも待つ必要がある。
・Altruistic locking
ALは新たなoperationとして「donate」を導入する。unlockをしなくても、他のトランザクションがitemにlockとoperationを実行できるようにする。
「donate」は「lockの使用権限を与える」ことを表す。conflictしているトランザクションにlockの権利を渡すことで、並行実効性を高めるもの。
AL uses a third access control operation, besides lock and unlock, which is called donate. The donate operation is used to inform the scheduler that access to a data item is no longer required by the transaction that has currently locked the item, so that the item can be “donated” for access to another transaction. The donating transaction is free to acquire other locks in the future, so that lock and donate operations do not need to follow a twophase rule; but other than that, the transaction still has to be two-phase with respect to unlock operations.
in the wake と indebted
in the wakeはdonateされたitemをlockしていた、先行トランザクションがunlockしていない状態。
indebtedはin the wakeにあるoperationがconflictしていること。直接的か、間接的（他のトランザクションのoperationを介して）か。
★【要確認】in the wakeは「read - read」のケースも含んでいると思われる → なので、indebtedを別に設けて区別していると思われる。
intuitively, if transaction t j locks a data item that has been donated and not yet unlocked by transaction ti , i ≠= j , we say that t j isin the wake of ti . More formally, we have the following:
-
An operation pj (x) from transaction t j is in the wake of transaction ti , i ≠j , in the context of a schedule s if di (x) ∈ op(s) and di (x) <s pj (x) <s oui (x) for some operation oi (x) from ti .
-
A transaction t j is in the wake of transaction ti if some operation from t j is in the wake of ti . Transaction t j is completely in the wake of ti if all of its operations are in the wake of ti .
-
A transaction t j is indebted to transaction ti in a schedule s if oi (x), di (x), pj (x) ∈ op(s) such that pj (x) is in the wake of ti and either oi (x) and pj (x) are in conflict or some intervening operation qk(x) such that di (x) <s qk(x) <s pj (x) is in conflict with both oi (x) and pj (x).
-
分類
概要
定義
意味
AL1
donateとopの関係
Items cannot be read or written by ti once it has donated them; that is, if di (x) and oi (x) occur in a schedule s, o ∈ {r, w}, then oi (x) <s di (x).
donateはoperationの後に実行する
AL2
donateとunlockの関係
Donated items are eventually unlocked; that is, if di (x) occurs in a schedule s following an operation oi (x), then oui (x) is also in s and di (x) <s oui (x).
donateはunlockの前に実行する。
※unlockが先にできるのなら、donateはいらない。AL3
別トランザクションによるlock
Transactions cannot hold conflicting locks simultaneously, unless one has donated the data item in question; that is, if oi (x) and pj (x), i ≠j , are conflicting operations in a schedule s and oi (x) <s pj (x), then either oui (x) <s pl j (x), or di (x) is also in s and di (x) <s pl j (x).
トランザクション間でconflictするoperationが実行されるのは、以下のいずれかとなる。
①先行するoperationがunlockされた
②先行するoperationがdonateされた
AL4:
トランザクション間のop順序
When a transaction t j is indebted to another transaction ti , t j must remain completely in the wake of ti until ti begins to unlock items.
That is, for every operation pj (x) occurring in a schedule s, either
pj (x) is in the wake of ti or there exists an unlock operation oui ( y) in s such that oui ( y) <s o j (x).
トランザクションがindebted（in the wakeかつconflict）であるとき、indebtedなトランザクションのopはすべて以下のいずれかとなる。
①in the wake
②実行済のoperationに対して、すべてunlockされている
TransactionalInformation Systems まとめ 第四章 （３）
②Lock mode compatibility
ロックの分類をテーブルで定義したもの。「現在のロック状態」と「実行するオペレーション」に応じて、どの種類のロックを取得するかを
定めるもの。
・ベーシックなもの
-
Lock requested
rli (x)
wli (x)
Lock held
rl j (x)
+
−
wl j (x)
−
−
・Selective use of ordered sharing in lock tables.
order sharingで使用するlock table。sharingを許容する度合いに応じて対象を選択する。
-
LT1
Lock requested
rli (x)
wli (x)
Lock held
rl j (x)
+
−
wl j (x)
−
−
-
LT2
Lock requested
rli (x)
wli (x)
Lock held
rl j (x)
+
→
wl j (x)
−
−
-
LT3
Lock requested
rli (x)
wli (x)
Lock held
rl j (x)
+
−
wl j (x)
→
−
-
LT4
Lock requested
rli (x)
wli (x)
Lock held
rl j (x)
+
−
wl j (x)
−
→
-
LT5
Lock requested
rli (x)
wli (x)
Lock held
rl j (x)
+
→
wl j (x)
→
−
-
LT6
Lock requested
rli (x)
wli (x)
Lock held
rl j (x)
+
−
wl j (x)
→
→
-
LT7
Lock requested
rli (x)
wli (x)
Lock held
rl j (x)
+
→
wl j (x)
−
→
-
LT8
Lock requested
rli (x)
wli (x)
Lock held
rl j (x)
+
→
wl j (x)
→
→
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として追加。
TransactionalInformation Systems まとめ 第四章 （１）
１．章構成
-
4.1 Goal and Overview
4.2 General Scheduler Design
4.3 Locking Schedulers
4.3.1 Introduction
4.3.2 The Two-Phase Locking Protocol
4.3.3 Deadlock Handling
4.3.4 Variants of 2PL
4.3.5 Ordered Sharing of Locks
4.3.6 Altruistic Locking
4.3.7 Non-Two-Phase Locking Protocols
4.3.8 On the Geometry of Locking
4.4 Nonlocking Schedulers
4.4.1 Timestamp Ordering
4.4.2 Serialization Graph Testing
4.4.3 Optimistic Protocols
4.5 Hybrid Protocols
4.6 Lessons Learned
Exercises
Bibliographic Notes
２．概略
この章ではCSRのスケジュールを生成することをターゲットにする（we will concentrate on schedulers that produce conflict-serializable schedules）
（１） Criteria
スケジュールをverifyするにあたっては、safeとpowerをcriteria。
how to designscheduling protocols in general, and on how to verify a given protocol and prove it correct.With respect to the latter, we will be interested in two criteria:
First, each protocol that we present has to be safein the sense that all histories it outputs have to be members of CSR, the class of conflict-serializable schedules.
Second, we are interested in thescheduling powerof a protocol, or in its ability to produce some class of serializable histories (e.g., class CSR) in its entirety or partially only.
（２） Transactionの状態遷移モデル
図は別途作成予定。
TransactionalInformation Systems まとめ 第三章 （４）
（４）An Alternative Correctness Criterion: Interleaving Specifications
単純にトランザクション単位でserialとするのではなく、もう「トランザクションの部分単位」でserialにすることを考える。
この緩和を取り入れることで並行性を向上できる。
①Indivisible Units
上述の「トランザクションの部分」を定めるもの。「これ以上は分解できない（相互にinterleaveしあうことができない）」ことを基準に分割する。
Let T = {t1, . . . , tn} be a set of transactions. For ti, tj ∈ T, i = j, anindivisibleunit of ti relative to t j is a sequence of consecutive steps of ti such that
no operations of t j are allowed to be executed within this sequence.
Let IU(ti , t j ) denote the ordered sequence of indivisible units of ti relative to t j , and let IUk(ti , t j ) denote the k-th element of IU(ti , t j ).
②Relative Serializability
Relatively Serial Scheduleは不可分なoperation集合には、conflictとなる他トランザクションのオペレーションが挟み込まれないもの。
A schedule s such that trans(s) = T is relatively serial if for all transactions ti, tj ∈ T, i = j , the following holds:
if an operation q ∈ t j is interleaved with IUk(ti , t j ) for some k,
then there is no operation p ∈ IUk(ti , t j) (p ∈ ti ) such that p ∗ q or q ∗ p.
※記号に注意。「*」は、本来は「→」の曲線版に「*」が付与されたもの。
Relative Serializability
A schedule s is relatively serializable if it is conflict equivalent to somerelatively serial schedule.
③Push Forward and Pull Backward
Indivisible Unitの「先頭（Foward)」と「末尾(Backward)」を表す。interleaveの境界を示すものとして、correctnessの判定する際に使う。
「該当するIndivisible Unitにconflictするオペレーション」は、この両端の外に寄せる（追い出す）必要がある。
Let ti and t j be distinct transactions, and let IUk(ti, tj ) be an indivisible unit of ti relative to t j . For an operation pi ∈ IUk(ti , t j )(pi ∈ ti ) let
1. F (pi, tj ) be the last operation in IUk(ti, tj ),
2. B(pi, tj ) be the first operation of IUk(ti, tj ).
④RSG（Relative Serialization Graph）
「If s is relatively serial, then RSG(s) is acyclic」となる。RSGは以下のようにして作成する。
Let s be a schedule. The relative serialization graph RSG(s) = (V, E) of s is defined by V := op(s) and E ⊆ V × V containing four types of edges as follows:
1. if p and q are consecutive operations of the same transaction in s, then ( p, q) ∈ E (internal or I edge);
2. if p ∗ q for p ∈ ti , q ∈ t j , i = j , then ( p, q) ∈ E (dependency or D edge);
3. if ( p, q) is a D edge such that p ∈ ti and q ∈ t j , then (F ( p, t j ), q) ∈ E (push forward or F edge);
4. if ( p, q) is a D edge such that p ∈ ti and q ∈ t j , then ( p, B(q, ti )) ∈ E(pull backward or B edge)
