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の取得順序が一致していない」ことを示している。