###### tags: `TransactionalInformationSystems`

# 2章 ページモデル/オブジェクトモデルの定義

5ステップをたどってアプローチする

1. データオブジェクトへの基本的な操作の定義。どのようなオブジェクトにどのような操作をするかは任意で、それが後のpage modelとobject modelの違いにつながる。
2. トランザクションの定義。1の操作の連続。
3. スケジュール(or ヒストリー)の定義。いくつかのトランザクションを並列実行する概念の抽象化。トランザクションをいわばシャッフルして巨大な基本的操作の集合としたもの。
4. 構文的に正当なスケジュールの中から、ACID特性を満たすスケジュール(一貫性が損なわれていないetc)を特定する。
5. アプリケーションからリクエストされた操作をオンラインに正当なスケジュールに並べて実行するためのアルゴリズムを考える。

本書で取り扱われるデータ操作のモデルには2つある

### page model(read/write model)

DBMSのstorage layerに着目し、データページにどのようにアクセスするかを考えるためのモデル。データの基本単位がページ。CCとrecoveryの本質をとらえるには十分だが実装に適用するには原始的

### object model

access layerやquery processing layerに着目し、少し抽象化レベルを上げたモデル。データの基本単位がオブジェクト。

トランザクションには全順序の場合と半順序の場合がある。

### 全順序トランザクションのシンタックス

トランザクション$t$を、複数の操作列

$$t=p_1\ldots p_n$$

とする。各$p_i$は$r(x)$または$w(x)$の形をしていて、それぞれアイテム$x\in D$への読み込みもしくは書き込みに相当する。$p_{ij}$のように表記したときは$i$番目のトランザクションの$j$番目の操作を表す。

### セマンティクス

$p_j=r(x)$のとき、読み込み結果を局所変数$v_j$に束縛する。

$$v_j:=x$$

$p_j=w(x)$のとき、それまで得た局所変数を加工してxに書き込む。

$$x:=f_j(v_{j_1},\ldots ,v_{j_k})$$
$$\{j_1,\ldots , j_k\} = \{j_r \mid p_{j_r} が読み込みかつj_r < j\}$$

より一般的には全順序である必要もないので、同じアイテムへのreadとwriteの組、もしくはwrite同士の組、の間にのみ順序を定めて、操作全体は半順序になっている操作体系をトランザクションと定義してもよい

トランザクション内で複数回readしても同じ値になるし、複数回writeしたら最後writeした値に固定される(ACID特性を満たしていたら)。冗長性を除くため、各トランザクション内での仮定を設ける

- トランザクション内で、同じアイテムに対するreadとwriteはそれぞれ高々1回ずつまでしか実行されない
- トランザクション内で一度writeされたアイテムは、二度とreadされない。

ただしreadしてないアイテムへのwrite(blind write)の可能性は排除していない

### object modelの導入

オブジェクトへの操作が、より基礎的なページ指向の操作を複数回必要としたりする。それを表現するため、トランザクション内の操作を木構造で階層化したものがobject model

- 例えばトランザクションラベル$t_1$が木の根、ノード$Search("Austin")$の子に、レコードAustinに対応するページの読み込みが並ぶ。葉の操作は全てpage modelにおける基礎的な操作とする。

こちらでもpage modelと同様、必ずしも操作が全順序で並んでいる必要が無い

#### object model transaction の定義

トランザクション$t$とはラベル付きの木で、

- ルートノードのラベルが$t$で、
- 呼び出された操作の名前が内部ノードのラベルになっていて、
- 葉ノードのラベルがページモデルにおけるread/write操作になっているもの

であり、同じページに対するreadとwrite、もしくはwriteとwriteの間に順序が定められているもの。

内部ノード操作間の順序は、ノード以下の葉ノード間に全て順序が決まっていた場合のみに定まる。それ以外のケースには全て並列実行しうる操作となる。

## 演習

### 2.1

prefix order (aがbのprefixならa<b) が半順序であることの証明

- aはaのprefixなのでa<a。
- aがbのprefixかつbがaのprefixだったとき、a=c.b, b=d.a (cとdは長さ0以上の文字列)となるのでa=c.d.aとなりc=d=空文字列。
よってa=b
- a<bかつb<cのときb=d.a, c=e.bとなるのでc=e.d.aとなりa<c。

### 2.2

べき集合上で、包含関係が半順序であることの証明

- $P\subseteq P$
- $P\subseteq Q, Q\subseteq P$ のとき$P=Q$
- $P\subseteq Q, Q\subseteq R$ のとき$P\subseteq R$

### 2.3

ページモデルトランザクション
$$t = r(x)r(y)r(z)w(u)w(x)r(v)w(y)w(v)$$
への形式的および意味的な議論

- $r(x)r(y)r(z)$、$w(u)w(x)$、$w(y)w(v)$はそれぞれ順序を入れ替えても問題ない。これはシンタックス的にもそうであるし、セマンティクス的にも問題ない。
- $w(x)$を$r(x)$の直後の位置まで持ってくるのは、シンタックスの観点からは許される($x$に対するread/writeもしくはwrite/writeが入れ替わっていないため)のだが、$w(x)$にそれ以前の$r(y)r(z)$という情報を用いていたかもしれず、セマンティクス的に問題が生じうる。

### 2.4

$$t = r(x)r(y)r(z)r(u)r(v)$$

5つのページからの読み出し。これはどの順番で実行しても全く問題ない。

### 2.5

$$t = w(x)w(y)w(z)w(u)w(v)$$

5つのページへの書き込み。これもどの順番で実行しても全く問題ない。

### 2.6

- no blind writesモデル：任意の$x$について、$w(x)$が存在するなら$r(x)$も存在し、$r(x)<w(x)$である。
- two-stepモデル：任意の$x,y$と$r(x),w(y)$について、$r(x)<w(y)$である。
- actionモデル 任意の$x$について、$r(x),w(x)$のいずれかが存在するとき、どちらも存在して$r(x)<w(x)$、かつ$r(x)<o(y)<w(x)$であるような別の操作$o(y)$が存在しない。

two-stepモデルでは、前半のread区間とwrite区間のそれぞれの中ではいくらでも順序を変えて問題ないが、区間を越えた交換をした瞬間セマンティクス的に問題が生じうる。

actionモデルはno blind writesモデルよりも厳しくなったモデルであり、もはやどんなaction間の入れ替えもセマンティクス的に問題が生じうる。シンタックス的には、異なるアイテムへのaction間の入れ替えであれば許容される。