###### tags: `TransactionalInformationSystems`

# 11章-1 ページモデルにおける復元可能性の定式化

## 概要

第2部ではトランザクションの並列実行の制御について述べてきたが、トランザクションのもう一つの重要な側面、どうやってロールバックするかが全く考慮されてこなかった。

トランザクションの実行が失敗したときや、デッドロックが起こってabortしたい場合など、トランザクションを実行する前の状態まで復元したい状況は多く存在する。ここからは第3部として、ロールバックを行う方法と、その理論的な性質について考えていく。

復元可能性を理論的に評価するために、まずトランザクションのabortを具体的なデータ操作(「逆操作」)として定義し、それによって拡張したスケジュールを考える。逆操作は、書き込みの内容を巻き戻して元に戻すものであり、実際にはサーバが保存するログに基づいて実現される。このようなスケジュールの拡張がいったん定義できれば、そのスケジュールのserializabilityを考えることによって復元可能性も考慮に入れることができる。

最初はページモデルで、後にオブジェクトモデルに拡張して議論する。

## 逆操作によるスケジュールの拡張

トランザクションをabortし、実行前の状態に復元するために必要なのは、全てのwrite操作を巻き戻すことになる。したがって、abortを、「全てのwriteの逆操作+commit」によって実装することとする。read操作は巻き戻しに際して考慮の必要がない。writeの逆操作は、もともとのwriteの逆順に行っていく。

---

例えば、$t_1$がabortする履歴

$$s=r_1(x)w_1(x)r_2(x)\underline{a_1}w_2(x)c_2$$

は、以下のように展開される。

$$s'=r_1(x)w_1(x)r_2(x)\underline{w_1^{-1}(x)c_1}w_2(x)c_2$$

ここで$w_1^{-1}(x)$が$w_1(x)$の逆操作を意味している。

$s$はdirty readを引き起こすスケジュールなので弾きたいのだが、$s\in CSR$であり、2PLは素通ししてしまう。その一方、$s'$は$t_1,t_2$の衝突が閉路を作っているので$s'\notin CSR$であり、これを2PLが観測すれば弾くことができる。

---

スケジューラは常に履歴のprefixを見ており、アクティブなトランザクションがcommitするかabortするかは分からないものである。このようなケースに対応するため、履歴のprefixであるスケジュールの拡張も考える。

スケジュールが与えられたときは、最終ステップの時点でアクティブなトランザクションが全てabortしたものとみなして取り扱う。つまり、それらトランザクションの逆操作を末尾に付加する。

以上を踏まえて正式にabortの拡張を定義する。

### 定義：スケジュールの拡張

$s$をスケジュールとする。$s$の拡張である$exp(s)$を以下で定義する。

1. $exp(s)$のステップは以下を満たす。
- $t_i\in commit(s)\Rightarrow op(t_i)\subseteq op(exp(s))$
- $t_i\in abort(s)\Rightarrow (op(t_i)-\{a_i\})\cup \{c_i\}\cup \{w_i^{-1}(x)\mid w_i(x)\in t_i\}\subseteq op(exp(s))$
- $t_i\in active(s)\Rightarrow op(t_i)\cup \{c_i\}\cup \{w_i^{-1}(x)\mid w_i(x)\in t_i\}\subseteq op(exp(s))$
2. $exp(s)$のステップ間の順序は以下を満たす。
- $op(s)\cap op(exp(s))$ のステップは全て$s$と同じ順序を満たす。
- $exp(s)$における逆操作($abort(s),active(s)$に由来するもの)は、全て順操作とcommitの間に位置する。
- 逆操作の間の順序は、対応する順操作と逆の順序となる。

## ページモデルにおける正当性基準

拡張したスケジュールに対して各種の正当性基準を導入し、それらの間の関係を確かめていく。

### 定義：Expanded Conflict Serializability

スケジュール$s$がexpanded conflict serializableとは、$exp(s)$がconflict serializableであることとする。

このクラスをXCSRと表記する。

---

例えば、

$$s=r_1(x)w_1(x)r_2(x)a_1c_2$$

はCSRだが、その拡張

$$exp(s)=r_1(x)w_1(x)r_2(x)w_1^{-1}(x)c_1c_2$$

は衝突サイクルを持つのでCSRでない。よって$s\in CSR$だが$s\notin XCSR$。

---

### 補題11.1

$XCSR\subset CSR$

#### 証明

衝突関係を見ると$conf(s)\subseteq conf(exp(s))$なので。strictnessは上記の例より。$\square$

XCSRは復元可能性も考慮に入れた正当性基準への第一歩だが、これは基準として厳しすぎるという問題もある。

---

例えば、スケジュール
$$s=w_1(x)w_2(x)a_2a_1$$
は、どちらもabortされるので何も起こらなかったのと同じ、よって許容されてほしいものである。ただ、残念ながら

$$exp(s)=w_1(x)w_2(x)w_2^{-1}(x)c_2w_1^{-1}(x)c_1$$

なので、$s\notin XCSR$で弾かれる。

---

XCSRの厳しさを緩和するうえで着目したいのは、$w_2(x)$と$w_2^{-1}(x)$が隣接していることである。これは結局何もしていないのと同じなので、隣接する順操作と逆操作の組があった時点でそれを削除することを考える。これを行うと、上の例の$exp(s)$は最終的に空スケジュールにまで削減される。

このような考えを、可換性に基づく操作の交換+操作組の削除による削減可能性という形で定義する。

### 定義：削減可能性(Reducibility)

スケジュール$s$が削減可能とは、$exp(s)$に以下の規則を有限回適用することでserialな履歴に変換できることとする。

1. Commutativity Rule (CR)：$p,q$ が衝突しておらず、また $p<o<q$ なる $o$ が存在しないとき、$p$ と $q$ の順序を入れ替えてもよい。
2. Undo Rule (UR)：$p$ と $q$ が互いの逆操作であり、また $p<o<q$ なる $o$ が存在しないとき、$p$ と $q$ を $exp(s)$ から削除してもよい。
3. Null Rule (NR)：$p\in op(exp(s))$ が $p=r_i(x)$ かつ $t_i \in active(s)\cup abort(s)$ だったとき、$p$ を $exp(s)$ から削除してもよい。
4. Ordering Rule (OR)：可換かつ順序付けられていない操作同士は任意に順序付けてよい。

削減可能なスケジュールのクラスをREDと表記する。

XCSRはCRとORのみを考えたときの正当性基準であり、それにURとNRを追加して緩和したものがREDという見方ができる。

また、スケジューラは履歴のprefixのみ見て実行可能性の判断を下さなければならないので、それについても定義する。

---

例えば、
$$s=w_1(x)w_2(x)c_2c_1$$
は終了した履歴だけ見るとCSRなので問題ないのだが、prefix $w_1(x)w_2(x)c_2$ を見ると、その時点でabortされる可能性があり、その場合は
$$w_1(x)w_2(x)c_2w_1^{-1}(x)c_1$$
に展開されてしまい、衝突のサイクルが発生する。

prefixの時点で安全でないため弾くべきケースの例となっている。

---

### 定義：先頭削減可能性(Prefix Reducibility)

スケジュール$s$が先頭削減可能とは、$s$のprefixが全て削減可能であることとする。

このクラスをPREDと表記する。

### 補題11.2

$PRED\subset RED$

#### 証明

prefixにはスケジュール自身も含まれるため包含。strictnessは$w_1(x)w_2(x)c_2c_1$より(それ自体は削減可能だが、prefix $w_1(x)w_2(x)c_2$ がそうでない)。$\square$

以下の定理で示されるように、XCSRとPREDはREDよりも厳しい基準であり、XCSRとPREDの間には包含関係が定まらない。

### 定理11.1

1. $XCSR\subset RED$
2. XCSRとPREDは互いに包含関係を持たない。

#### 証明

(1) $s\in XCSR$とする。$exp(s)$はCSRに属するので、serialな履歴と衝突同値である。したがって、削減規則のうち1:CRと4:ORだけを使ってserialな履歴に帰着させることができ、ゆえに$s\in RED$である。strictnessは以前に述べた例$s=w_1(x)w_2(x)a_2a_1$による。

(2) $$w_1(x)w_2(x)c_2c_1 \in XCSR -PRED$$ $$w_1(x)w_2(x)a_2a_1 \in PRED - XCSR$$ $\square$

## 正常な復元のための十分条件

前節で考えたのは、任意のスケジュールを与えられたとき、それを実際に処理してみて復元にも対応可能か判定する、という意味合いでの基準だった。

本節では、スケジュール自体の形式にあらかじめ復元可能なための条件を課すことを考えていく。条件を満たすスケジュールのクラスの間の関係も考えていく。

まず、dirty readを抑止するための条件を考える。

---

### 定義：Recoverability

スケジュール$s$が復元可能(Recoverable)とは、任意の異なるトランザクション$t_i,t_j$に対して、$t_i$が$t_j$から読み込み、かつ$c_i\in op(s)$なら$c_j<_s c_i$であることとする。

---

つまり、$t_j$から読み込んだトランザクションは、$t_j$がcommitされるまでcommitしてはならないという条件になる。

次に、連鎖的なabortを抑止するための条件を考える。abortに起因するabortは、データのエラーこそ起こさないもののパフォーマンスに悪影響を及ぼすため防ぎたいものである。

---

### 定義：Avoiding Cascading Aborts

スケジュール$s$が$s$ avoids cascading abortsとは、任意の異なるトランザクション$t_i,t_j$に対して、$t_i$が$t_j$から$x$を読み込むならば$c_j<_s r_i(x)$であることとする。

このクラスをACAと表記する。

---

つまり、commitされたデータしか読み込んではならないという条件である。

連鎖的なabortは防げるものの、ACAも完璧というわけではなく、以下の例で示すように複数のwriteが絡む際に問題が生じうる。

---

$$s=w_1(x)w_1(y)r_2(u)w_2(x)w_1(z)c_1r_2(y)w_2(y)w_3(u)c_3c_2$$
はACAではある。ただ、$w_2(x)$の直後に$t_1$がabortした場合を考える。このとき、$x$を最初の$w_1(x)$の前の状態に復元する必要があるわけだが、その後に$w_2(x)$が挟まってしまっているため、復元しようとするとコストが大きい。このように、ACAやRCでは複数のwriteが何度も同じデータアイテムを上書きしてしまっているため、abortの際に大きく巻き戻して既にコミットされたトランザクションを延々とやり直す必要が出てくることがあり、その悪影響は無視できない。

---

単純な逆操作だけでトランザクションの復元を可能にするために、さらなる制限を課す。

### 定義：Strictness

スケジュール$s$がstrictであるとは、任意のread/write操作$p_i(x)$に対して、$w_j(x)<_s p_i(x) (i\neq j)$ならば$a_j <_s p_i(x)$または$c_j<_s p_i(x)$が成り立つこととする。

このクラスをSTと表記する。

つまり、strictなスケジュールにおいては、トランザクションが終了するまで、それが書き込んだデータが読み込まれたり上書きされたりすることが無い。

### 定義：Rigorousness

スケジュール$s$がrigorousであるとは、$s$がstrictかつ以下の条件を満たすこととする。

$r_j(x)<_s w_i(x)\ (i\neq j)$ ならば $a_j <_s w_i(x)$または$c_j<_s w_i(x)$である。

このクラスをRGと表記する。

つまり、strictかつ、$x$を読んだトランザクションが全て終了するまで$x$が上書きされないようなスケジュールがRGである。

### 定理11.2

$RG\subset ST \subset ACA \subset RC$

#### 証明

$RG\subseteq ST$は定義より明らか。$ACA\subseteq RC$は、トランザクションの定義により常に$r_i(x)<c_i$なので明らか。

$ST\subseteq ACA$を示す。$s\in ST$をとり、$t_i$が$t_j$から読み込むとする。read-from関係の定義より、$w_j(x)<_s r_i(x)$ かつ $a_j \nless_s r_i(x)$ が成り立つ。STの定義から $c_j <_s r_i(x)$ が導かれるので、$s\in ACA$が成り立つ。

最後に包含のstrictnessは以下による。

$$w_1(x)w_1(y)r_2(u)w_2(x)r_2(y)w_2(y)w_3(u)c_3w_1(z)c_1c_2 \in RC - ACA$$
$$w_1(x)w_1(y)r_2(u)w_2(x)w_1(z)c_1r_2(y)w_2(y)w_3(u)c_3c_2\in ACA - ST$$
$$w_1(x)w_1(y)r_2(u)w_1(z)c_1w_2(x)r_2(y)w_2(y)w_3(u)c_3c_2 \in ST -RG$$

$\square$

**これらのクラスは全てprefix commit closedである**ことも特筆すべきである。

これらのクラスをCSR(CSR=commitされたものへの射影履歴がCSRであるようなスケジュールのクラス)と比較すると、RGだけがCSRに含まれる。

証拠を挙げておくと、

$$r_1(x)w_2(x)w_2(y)c_2r_1(y)c_1 \in ST - CSR$$ $$w_1(x)r_2(x)c_2c_1 \in CSR - RC$$

このことから以下のクラス関係図を得る。


なお、RGはCSRどころかCOCSRに含まれる。

### 定理11.3

$RG\subset COCSR$

#### 証明

$s\in RG$であるとき、衝突$p<_s q$が存在するなら$p$のトランザクションのcommitが$q$の前に行われることが保証されている。したがって、任意の衝突に対してcommitが衝突順と等しくなるため$s\in COCSR$である。
strictnessは$r_1(x)w_2(x)c_1c_2 \in COCSR - RG$による。$\square$

$w_1(x)r_2(x)c_1c_2 \in COCSR - ST$ であることを合わせて以下の図を得る。


これらの事実から分かるのは、RGはserializabilityと復元可能性を一挙に保証できる条件であるということ。また、それよりも緩い復元条件(RC,ACA,ST)を採用する場合、serializabilityの観点からも追加でスケジュールの正当性を検査する必要があるということ。

ただし、以下のように前節で考えたPREDはRGの代替になりうる。つまりCSRを保証しつつSTとRCの中間程度の復元可能性を保証できる。

### 定理11.4

$CSR\cap ST \subseteq PRED \subseteq CSR \cap RC$

#### 証明

$s\in CSR \cap ST$を仮定し、$s$の任意のprefix $s'$ をとる。

CSRもSTもprefix closedなので$s'\in CSR \cap ST$。$s'\notin RED$を仮定する。すると、$exp(s')$は削減規則CR,UR,NR,ORを使ってserialな履歴に変形することができない。しかし、拡張しない$s'$はCSRであることから、これは隣接位置まで持っていけない逆操作の組$(w_i(x),w_i^{-1}(x))$が原因で引き起こされている。したがって、$w_i(x),w_i^{-1}(x)$と衝突する操作$p_j(x)$が間に存在する、つまり$w_i(x)< p_j(x) < w_i^{-1}(x)$となる。これは$s'$のstrictnessに反するため矛盾する。よって$CSR\cap ST \subseteq PRED$。

次に$s\in PRED$を考える。

$s\notin CSR$と仮定すると、衝突のサイクル$t_1\rightarrow \cdots \rightarrow t_n \rightarrow t_1$が存在し、これは削減規則によってserialにできないためPREDであることに矛盾する。よって$s\in CSR$。

$s\notin RC$と仮定する。RCに反する状況は以下のケースのいずれかで起こりうる。

1. $w_i(x)<r_j(x) < c_j < c_i$
2. $w_i(x)<r_j(x) < c_j < a_i$
3. $w_i(x)<r_j(x) < a_i < c_j$

1については、最初の3つを含むprefixをとると削減可能でないのでPRED性に反するので矛盾。2も同様に矛盾。3については、$a_i$を展開したスケジュールが$i<j<i$となっていて削減可能でないのでPRED性に反する。

以上より全てのケースが否定され、$s\in RC$が成り立つ。これらを踏まえて$PRED \subset CSR \cap RC$。$\square$

次に、write/write衝突に関わるトランザクション間の終了操作の順序を制限するような復元可能性を考える。これは後で見るようにPREDの正確な特徴づけになる。

---

### 定義：ログ復元可能性

スケジュール$s$がログ復元可能とは、以下の2つの性質が成り立つこととする。

1. $s$が復元可能である。つまり、$t_i$が$t_j$から読み込んで$c_i\in s$なら$c_j < c_i$。
2. write/write衝突$w_i(x)<w_j(x)$が存在したとき、
- $a_i<w_j(x)$であるか、
- $t_j$がcommitするなら$c_i < c_j$、$t_i$がabortするなら$a_j < a_i$

このクラスをLRCと表記する。

---

### 定理11.5

$s$が先頭削減可能$\Longleftrightarrow$$s$がログ復元可能かつconflict serializable

すなわち、$PRED=LRC\cap CSR$。

これを示すためには次の補題を用いる。

### 補題11.3

$s\in LRC$なら、$exp(s)$のcommitされていない操作は全てCR,UR,NR,ORを使って取り除くことができる。

#### 証明

read操作はNRによって取り除けるので、考える必要があるのはwrite操作。

commitされていない操作$w_i(x)\in op(s)$を考える。$w_i^{-1}(x)$以前に$x$に対する操作が$n$回実行されているとする。$n$についての帰納法で$w_i(x)$が取り除けることを示す。

準備として一つ定義しておく。$w_i(x)$と$w_j(x)$が$w_i(x)<_sw_j(x)$かつ$a_i\nless_s w_j(x)$を満たすとき、それらは活性衝突しているとする。つまり、活性衝突していないが$w_i(x)<_sw_j(x)$なら、$exp(s)$で$w_i^{-1}(x)<w_j(x)$。

$n=1$のときは$w_i(x)$と$w_i^{-1}(x)$を隣接されられるので、URによって取り除ける。

$n=k$以下の整数で成り立つと仮定する。(k+1)個の$x$への操作のうち最後のものを$o_j(x)\ (w_i(x)<o_j(x)<w_i^{-1}(x))$とする。

$i=j$のときは、トランザクションが複数の同じデータへのwriteを持たないことから$o=r$であり、NRから$r_i(x)$は取り除くことができ、残りのk個について帰納法仮定から$w_i(x)$は取り除くことができる。

$i\neq j$のときは以下の3つの場合に分けられる。

1. $o_j=r_j$：$t_j$がcommitされているとき、$w_i$と$r_j$の間に他のwriteが挟まっていない場合は$t_j$ reads from $t_i$であり、復元可能性に反して矛盾。他のwriteが挟まる場合には、$s\in LRC$からそのwriteもabortするのでやはりそれと$r_j$との間で矛盾を起こす。$t_j$がabortされているときには$r_j$をNRによって取り除け、残りの帰納法仮定により$w_i(x)$を取り除ける。
2. $o_j=w_j$：$w_i(x)$と$w_j(x)$が活性衝突する場合は$t_j$がcommitするとLRC性に反するため、$t_j$はcommitされない。$t_j$がアクティブでもabortでも$exp(s)$で$w_i(x)<w_j(x)<w_j^{-1}(x)<w_i^{-1}(x)$ が成り立ち、$w_j(x)$が最後のものであるという仮定に反する。$w_i(x),w_j(x)$が活性衝突しない場合には$w_i(x)<w_i^{-1}(x)<w_j(x)$で仮定に反する。
3. $o_j=w_j^{-1}$：$w_i(x),w_j(x)$が活性衝突する場合、仮定より$w_j^{-1}(x)<w_i^{-1}(x)$が存在することと合わせて$w_i(x)<w_j(x)$が成り立ち、帰納法仮定から$w_j(x),w_j^{-1}(x)$を取り除くことができ、したがってさらに帰納法仮定から$w_i(x)$も取り除くことができる。$w_i(x),w_j(x)$が活性衝突しない場合、$a_i<w_j(x)$なので$w_i^{-1}(x)<w_j(x)$となり、$w_j^{-1}(x)$が$w_i^{-1}(x)$の直前の最後の操作という仮定に反する。

$\square$

#### 定理11.5の証明 ($PRED=LRC\cap CSR$)

$s\in LRC\cap CSR$ が $s\notin PRED$と仮定する。

$s$ のprefix $s'$ で削減可能でないものが存在する。$s'$もまた$s'\in LRC\cap CSR$であり、補題11.3から$exp(s')$のcommitされていない操作を全て取り除くことができ、変形の結果を$s''$とする。$s''$にはcommitされている操作しか存在せず、$s'\in CSR$であることと合わせて、可換性に基づいて$s''$からserialな履歴に変換することができ、$s'$が削減可能となって過程に反する。よって$s^in PRED$である。

$s\in PRED$ が $s\notin LRC \cap CSR$と仮定する。

$s\notin CSR$ならば明らかに$s\in PRED$であることに反するので、$s\notin LRC$を考えればよい。この$s$が満たさないLRCの条件がwrite/write衝突に関するものであるとき、以下の2つの条件のいずれかを満たす$w_i(x)w_j(x)$という形の衝突が少なくとも一つ存在する。

1. $t_j$がcommitし、
- $t_i$がcommitしないか
- $t_i$が$t_j$の後にcommitする。
2. $t_i$がabortし、
- $t_j$がabortしないか
- $t_j$が$t_i$の後にabortする。

まず1の場合を考える。$t_j$がcommitして$t_i$がcommitしなかった場合、$exp(s)$で$w_i(x)<w_j(x)<w_i^{-1}(x)$のようになるので削減可能でなく、矛盾する。$t_i$が$t_j$の後にcommitする場合、$w_i(x)<w_j(x)<c_j<c_i$となる。このうち$c_j$までを含むprefixを考えるとこれは削減可能でなく、したがって矛盾する。

次に2の場合を考える。$t_i$がabortして$t_j$がabortしなかった場合、$t_i,t_j$は活性衝突になるので$w_i(x)<w_j(x)<a_i$。$t_j$がcommitした場合には$exp(s)$で$w_i(x)<w_j(x)<w_i^{-1}(x)$となり、activeな場合には$exp(s)$で$w_i(x)<w_j(x)<w_i^{-1}(x) < w_j^{-1}(x)$となる。いずれにせよ削減可能でなく、矛盾する。最後に、$a_i<a_j$の場合、$a_i$までを含むprefixが削減可能でなく、したがって矛盾する。

同様に、$s$が満たさない条件がRCに関するものであるとき、reads-from関係が存在して$w_i(x)<r_j(x)<c_j<c_i$となり、$c_j$までのprefixが削減可能でないため矛盾する。

以上より$s\in LRC \cap CSR$である。$\square$

ここまでの議論をまとめると以下の包含関係を得る。