Database Concurrency Control Papadimitriou 読書会第7回議論メモ

勉強会について

Database Concurrency Control Papadimitriou 読書会第7回 - connpass の議論メモです。
※第6回は休講でした。

自分のメモをベースにまとめています。発言の聞き間違い、解釈違いの可能性があることをご了承ください。

特記の無い引用は本で議論した箇所を示しています。

Theory of Database Concurrency Control

作者: Christos Papadimitriou
出版社/メーカー: Computer Science Pr
発売日: 1986/07/01
メディア: ハードカバー
この商品を含むブログを見る

[memo]は私のメモです。勉強会で議論された内容ではないことにご注意ください。

2.4 VIEW SERIALIZABILITY

Definition 2.3: Suppose that a transaction A has k read steps, r¹, r², ... , r^k. The view of A in a schedule s under interpretation I and initial state X is the k-tuple (r¹_s(I,X), ... , r^k_s(I,X)) of the values of the variables read by the read steps of A in s. Two schedules s and s' are called view equivalent if
(a) They are final-state equivalent, and
(b) Under any interpretation and initial state, the views of each transaction in both schedules are the same.

(b) は両方のスケジュールの全てのトランザクションでviewが一致していること、としている。

一見すると (b) だけでも view equivalent が成り立ちそうだ。ここであえて (a) を含めているのは final-state equivalent の定義 (Definition 2.1) が含まれていることを言いたいのではないか。

from D(s) we construct the directed graph D₁(s) by deleting all nodes of D(s) from which no step of A_∞ can be reached.
（中略）
Theorem 2.1: Two schedules s and s' are final-state equivalent if and only if they involve the same transactions, and D₁(s) = D₁(s').
（中略）
Theorem 2.2: Two schedules s and s' are view equivalent if and only if they involve the same set of transactions and D(s) = D(s').

Theorem 2.1, Theorem 2.2 はほぼ同じ形となっており、D₁ と D の違いがある。

Definition 2.5 の "programs with loops, after these loops have been "unwound""とはループ展開（ループ展開 - Wikipedia）を行ってループをなくすということ。

Figure 2.3. A Free Schema のパスの例として以下が挙げられている。
1. R(x)W(y)W(z)
2. R(x)W(y)R(z)W(x)
これ以外にも以下のパスが存在しうる。
3. R(x)W(y)R(z)W(z)

namely that no read step is preceded by a read or write step on the same entity, and likewise no write step is preceded by a write step on the same entity.

これは以前に出てきたトランザクションの定義に沿っている。

[memo]
P6 に該当すると思われる定義の記載があります。

It is quite natural - and, it turns out, simplifying - to make the following assumptions about the structure of the transactions.
(a) In a transaction, an entity is read at most once, and is written at most once.
(b) In a transaction, no entity is read after it is written.

Definition 2.6: Let A be a transaction. A full interpretation I of A consists of
(a) A free schema S_A such that A is a path in S_A;
(b) For each entity x ∈ E, a domain D_x;
(c) For each write step W(x) appearing in S_A, we have in I a function f : Π_iD_yi → D_x, where the y_i's are the entities read by the read steps preceding W(x) in S_A; and
(d) For each predicate P of S_A, I contains a subset p of Π_iD_yi, where the y_i are the entities in the read steps preceding P in S_A (this subset contains the combinations of values that make P true).

We say that s is legal for I and X if for each transaction A of s and each predicate P in S_A the following holds: Transaction A corresponds to a path of S_A which, for each predicate P of S_A, takes the left branch at P if (v¹_s(I,X), ... , v^k_s(I,X)) ∈ p, and the right branch otherwise, where the vⁱ's are the read steps which precede P in A, and p is the interpretation of P.

スケジュールが "legal" であるとは、そこまでに read した結果に応じて P が正しく動いたということ。つまり、スケジューラに P に反するようなステップが来たときは legal ではない。

トランザクション毎に Free Schema がある。そして、与えられた view によって P が決まる。Free Schema 通りに動くならスケジュールは legal だ。