###### tags: `TransactionalInformationSystems`

# 3章-2 基礎的なSerializability

ここまでの定義に基づいて、serializability(すなわち、serialなスケジュールとの同値性)を定義する。最初にいくらかシンプルなものを考える。

serializablityはなんと訳するのがベストなのか。まあそのまま書いておくか。

## Final State Serializability

### 定義

$s$と$s'$をスケジュールとする。$s$と$s'$がfinal state equivalent(最終状態同値) $s\approx_f s'$ であるとは、$op(s)=op(s')$かつ$H[s] = H[s']$ であることと定義する。

### 直感

すなわち、同じ操作の集合を持ち、Herbrandセマンティクスが同じ(同じ初期状態を与えられると、全てのデータアイテムの最終状態が同じになる)こととする。

初期化用トランザクション$t_0$と別に、便宜的に最終トランザクション$t_\infty$も定義する。これは対称的に全てのデータアイテムに対する読み込みを行う。

最終状態同値性を言い換えるために以下の定義を導入する。

### 定義：Reads-from 関係

$s$をスケジュールとする。

1. $t_j \in trans(s)$とし、$r_j(x)$を$t_j$内の読み込み操作とする。$r_j(x)$は$s$内の直前の$x$に対する書き込み操作($w_i(x)<_s r_j(x)$であるような$w_i(x)$のうち最後)の値を読み込む。
2. $s$におけるreads-from関係は $$RF(s):= \{(t_i,x,t_j)\mid r_j(x)はw_i(x)から読み込む\}$$ と定義される。つまり、値の書き込み-読み込みのリレーが行われるトランザクションの組と、媒介となるデータアイテムをまとめる。
3. ステップ$q$が、reads from $p$か、あるいは$p$が読み込みステップかつ$q$が同じトランザクション内でその後に出現する書き込みステップだった場合に$p$は*directly useful* for $q$といい、$p\rightarrow q$と表記する。
$\rightarrow$による推移・反射閉包を$\xrightarrow{*}$で表す。
4. ステップ$p$がalive(生きている)とは、$t_\infty$のいずれかのステップに対して$p$がusefulであることをいう。つまり
$$\exists q \in t_\infty,\ p \xrightarrow{*} q$$ そうでないならdead(死んでいる)
5. live reads-from関係を
$$LRF(s) :=\{(t_i,x,t_j)\mid r_j(x)は生きており、かつw_i(x)から読み込む\}$$
と定義する。

すなわち、値を使い使われる関係をusefulとして定義し、最終状態の計算に使われているステップを「生きている」とみなす。したがってLRFは、値の書き込み-読み込みのリレーが行われ、かつこの値が最終状態の生成に使われているようなトランザクションとデータアイテムの組をまとめる。

これをもとに最終状態同値性は言い換えられる。

### 定理3.1

$s$と$s'$を履歴とする。このとき

$$s \approx_f s' \Longleftrightarrow op(s)=op(s') \textrm{ and } LRF(s)=LRF(s')$$

#### 証明のスケッチ

与えられたスケジュールに対し、ステップを頂点集合、useful関係を辺としたステップグラフ$D(s)$を構成する。次に、死んだステップを全て頂点から除いた削減ステップグラフ$D_1(s)$を作る。これをもとに以下の三段論法で証明する。

1. $LRF(s)=LRF(s') \Leftrightarrow D_1(s)=D_1(s')$
2. $s\approx_fs' \Leftrightarrow op(s)=op(s')\ \textrm{and}\ D_1(s) =D_1(s')$

(usefulの関係(RF)が、Herbrandセマンティクスにおける計算-被計算関係と一致するように定義されており、それに加え、最終状態同値性で考慮に入らない孤立した計算-被計算関係(死んだステップ)を除外することで(LRF)最終状態同値と等価な条件を引き出せる)

※ステップグラフと、スケジュールの半順序は異なることに注意

### 系3.1

2つのスケジュール間の最終状態同値性は、スケジュールの長さ合計についての多項式時間で判定できる。(削減ステップグラフの比較で良いため)

最終状態同値性をもとに、最初のserializabilityを定義する。

---

### 定義：Final State Serializability

履歴$s$がfinal state serializableであるとは、serial(逐次的)な履歴$s'$で$s\approx_fs'$であるものが存在することと定義する。
final state serializableな履歴のクラスをFSRとする。

---

次の疑問として、FSRに属するかの判定をどうするか？というのが残る。トランザクションの全ての順列についてserialな履歴と多項式時間最終状態同値判定を行うbrute-forceなやり方が考えられるが、順列が組み合わせ爆発するため非効率

幸いもう少し効率的な方法への希望はある (後に述べるConflict Serializabilityがそれ)

## View Serializability

FSRでは生きたステップにのみ着目していた。
しかし、スケジュールとトランザクションの意味をブラックボックスにしている以上、データアイテムから読みだされる値はそのステップの生死にかかわらず同じ値になる必要があるという見方もある。実際、FSRではlost update問題を抑止できるが、inconsistent read問題を解決できない。
これを解決できるFSRよりもいくらか厳しい正当性基準がview serializablityとなる。

### 例：FSRが検出できるlost update問題

$$s=r_1(x)r_2(x)w_1(x)w_2(x)c_1c_2$$
はlost updateを起こしうるパターンだが、このスケジュールはFSRでない($t_1t_2$とも$t_2t_1$とも最終状態同値でない)ため弾くことに成功している

### 例：FSRが検出できないinconsistent read問題

$$s=r_2(x)w_2(x)r_1(x)r_1(y)r_2(y)w_2(y)c_1c_2$$

はinconsistent readを起こしうるパターンだが、$t_2t_1$に最終状態同値であることからFSRに属してしまっており、弾けていない

### 定義：View同値性(参照同値性)

スケジュール$s$と$s'$が参照同値 $s\approx_vs'$であるとは、以下の3条件を満たすことと定義する。

1. op(s)=op(s')
2. H[s]=H[s']
3. 全てのread/writeステップ$p$について$H_s(p)=H_{s'}(p)$

最終状態同値に加えて3の条件を足し、より厳しくした条件になる。死んだreadステップであっても関係なく一意な値にreadできる必要がある。

### 定理3.2

以下の3つの条件は全て同値である。

1. $s\approx_v s'$
2. $D(s)=D(s')$
3. $RF(s)=RF(s')$

つまり、参照同値であるにはステップグラフが削減前にも一致する必要がある。deadな部分も含めて考える。

#### 証明

1と3の同値性を示す。1と2の同値性は演習問題に譲る。

$1\Rightarrow 3$

参照同値を仮定する。readステップ$r_i(x)$を考える。仮定より $$H_s(r_i(x))=H_{s'}(r_i(x))$$
が成り立つ。Herbrandセマンティクスが一致することから、$s$で$r_i(x)$が$w_j(x)$から読み込むなら$s'$でも同様であり、逆もまた然り。任意の$r_i(x)$でそれが成り立つので、$RF(s)=RF(s')$である。

$3\Rightarrow 1$

$RF(s)=RF(s')$を仮定する。useful関係が等しいので、$t_\infty$に着目すると最終状態が等しく$H[s]=H[s']$が成り立つ。

参照同値の条件3については、実行順序に関する帰納法で示す。readステップ、writeステップについて、それ以前のuseful関係にあるステップのHerbrandセマンティクスが一致すると仮定する。

それ以外のreadステップ$r_i(x)$については、直前のwriteステップのHerbrandセマンティクスが一致することから$H_s(r_i(x))=H_{s'}(r_i(x))$が成り立つ。

writeステップについて$H_s(w_i(x))\neq H_{s'}(w_i(x))$を仮定すると、$w_i(x)$の以前に$t_i$で読み込まれる値の集合が異なることになり、$RF(s)=RF(s')$という仮定に反する。そのため$H_s(w_i(x))= H_{s'}(w_i(x))$

### 系3.2

2つのスケジュールの参照同値判定も、スケジュールのステップ数についての多項式時間で行うことができる。

---

### 定義：View Serializability

履歴$s$がview serializableとは、serialな履歴$s'$が存在して$s\approx_v s'$であることとする。
view serializableな履歴のクラスをVSRと表記する。

---

$VSR \subseteq FSR$ であることは定義から明らかだが、さらにFSRだがVSRでないスケジュール(inconsistent readを起こしうるもの)

$$s=w_1(x)r_2(x)r_2(y)w_1(y)c_1c_2$$

が存在するので、VSRは真部分集合となる。

### 定理3.3

$$VSR \subset FSR$$

### 定理3.4

死んだステップを持たない履歴$s$について、$$s\in VSR \Longleftrightarrow s\in FSR$$が成り立つ。

### VSRの「強さ」

- lost updateはFSRで既に弾けている
- inconsistent readはVSRで弾くことができる
- dirty readは？ $$D=r_1(x)w_1(x)r_2(x)a_1w_2(x)c_2$$ VSRのもとでは中断した$t_1$が考慮に入らないため、判定に使うことができない。このような障害からの回復については第3部で取り扱う。

## VSR判定の計算複雑性

VSR判定はbrute-forceにやると(トランザクションの順列数)*(多項式時間)になるわけだが、どんなに改善しても多項式時間ではできない。

### 定理3.5

履歴$s$が $s\in VSR$ か判定する問題はNP完全である。

#### 証明概要

VSR判定は、polygraphにおけるある種の閉路存在性判定に帰着され、この判定がNP完全であることを示す。polygraphは3つ組 $P=(V,E,C)$ で、$(V,E)$ はグラフ、$C$は3つ組 $(u,v,w)$ で $(w,u)\in E$ であるものの集まり

計算複雑性の観点からもVSRは正当性基準として実用的でないが、他にも理由がある。

---

### 定義：履歴クラスの単調性

履歴のクラス$E$を考える。$E$が「単調である」とは、以下が成り立つことと定義する。

$s\in E$ならば、あるトランザクションの部分集合 $T\subseteq trans(s)$ に関する射影 $\Pi_T(s)$ もまた $E$ に属する。

---

つまり、一部のトランザクションに関する射影について閉じている履歴の族が単調である。

履歴のクラスの単調性はある種望ましい性質(動的スケジューリングにおいて、射影がそのクラスに属しなかったらそれ以上の処理が意味をなさなくなってしまう)だが、VSRは単調性を満たさない。(反例：$s=w_1(x)w_2(x)w_2(y)c_2w_1(y)c_1w_3(x)w_3(y)c_3$)

従って、
- 判定がNP完全
- 単調性を満たさない

という2つの観点からVSRは好ましくない

よって、より厳しい基準が求められる。

## Conflict Serializablity

実用的なスケジューラを作る上で最も重要とのこと。判定の計算量が少なく、また豊富な性質を持ち他モデルへ応用する価値がある。

### 定義：Conflict(衝突)とConflict Relations(衝突関係)

$s$をスケジュール、$t,t' \in trans(s), t\neq t'$とする。

1. 2つのデータ操作 $p\in t$ と $q\in t'$ が「衝突している」とは、どちらも同じデータアイテムにアクセスし、また少なくとも一方が書き込み操作であることとする。$$(p=r(x) \land q=w(x))\vee (p=w(x) \land q=r(x)) \vee (p=w(x) \land q=w(x))$$

2. $conf(s) := \{(p,q)\mid p,q は衝突していて p <_s q\}$ を衝突関係とする。

衝突するかどうかの判定には、トランザクションの終了状態を考慮に入れないことに注意。中断したトランザクションを除外したいなら単に射影するだけでもよい。

---

### 定義：Conflict Equivalence (衝突同値性)

スケジュール$s$と$s'$が衝突同値 $s\approx_c s'$ であるとは、以下の条件が満たされることとする。

1. $op(s) = op(s')$
2. $conf(s) = conf(s')$

---

衝突同値性判定も、参照同値と同様にして衝突ステップグラフ $D_2(s) = (op(s),conf(s))$ を作って比較することで可能。

$$s\approx_c s' \Longleftrightarrow D_2(s)=D_2(s')$$

---

### 定義：Conflict Serializability

履歴$s$がconflict serializableとは、serialな履歴$s'$が存在して$s\approx_c s'$であることとする。
conflict serializableな履歴のクラスをCSRと表記する。

---

### CSRの「強さ」

同じデータアイテムへの操作間にしか矢印を考えないので一見VSRよりも弱いようにも見えるのだが、

- lost update $r_1(x)r_2(x)w_1(x)w_2(x)c_1c_2$ は弾ける。
- inconsistent read $r_2(x)w_2(x)r_1(x)r_1(y)r_2(y)w_2(y)$ も弾ける。

実のところ、CSRはVSRよりも厳しい条件になっている。conflict関係が一致すれば、データアイテムの読み出しと直前の書き込みが一致するため、reads-from関係も一致する。異なるデータアイテム間の相互作用について直接言及できなくてもVSRよりも厳しい条件にすることは可能らしい。

### 定理3.8

$$CSR \subset VSR$$

#### 証明

CSRがVSRの部分集合であることは、ステップグラフ$D(s)$が衝突ステップグラフ$D_2(s)$から一意に定まることによる。
(CSRに属する履歴は衝突ステップグラフがserialなものと等しい、そこから一意に定まったステップグラフも等しいのでVSRに属する)

別の証明法としては、まず$s\in CSR$とする。serialな履歴$s'$と$s\approx_c s'$である。ここで$RF(s)=RF(s')$を示せばよい。そうでないと仮定し、$RF(s)$に属するが$RF(s')$に属しない$(t_i,x,t_j)$の存在を考える。このとき、$s$においては$r_j(x)$が$w_i(x)$から読みだしたことになる。一方、$s'$においては$r_j(x)$が他の$w_k(x) (k\neq i)$から読みだしたことになる。$w_i(x)$と$w_k(x)$は定義から衝突しているので、$s\approx_c s'$である両者間で同じ順序でなければならないのだが、$s$においては$w_k(x) <_s w_i(x)$になっていて、$s'$では$w_i(x) <_{s'} w_k(x)$になってしまっている。これは矛盾である。したがって$RF(s)=RF(s')$ となる。

真部分集合であることの証明には、$VSR$に属するが$CSR$に属しない

$$s=w_1(x)w_2(x)w_2(y)c_2w_1(y)c_1w_3(x)w_3(y)c_3$$ を考えれば十分。$\square$

### 系3.3

$$CSR \subset VSR \subset FSR$$

### 定理3.9

1. $CSR$は単調である。
2. $s\in CSR \Longleftrightarrow (\forall T \subseteq trans(s))\ \Pi_T(s)\in VSR$
つまりCSRはVSRの単調な部分集合のうち最大のもの

## CSR判定の計算効率

CSRの判定は「衝突グラフ」における閉路検出を用いることで多項式時間可能である！

### 定義：Conflict Graph (衝突グラフ)

$s$をスケジュールとする。衝突グラフ$G(s)=(V,E)$を以下で定義する
$$V=commit(s) \\ (t,t')\in E \Longleftrightarrow t \neq t' \land (\exists p\in t)(\exists q \in t')\ (p,q) \in conf(s)$$

---

### 定理3.10 (conflict serializability theorem)

履歴 $s$ の衝突グラフ $G(s)$ が閉路を持たないことと $s\in CSR$ であることは同値。

#### 証明

- $s\in CSR \Rightarrow G(s)$ が閉路を持たない

serialな履歴があって$op(s)=op(s'), conf(s)=conf(s')$となる。ここで$G(s)$上の辺$(p,q)\ (p\in t, q\in t', p<_s q, (p,q)\in conf(s))$を考える。衝突関係が等しいことから$p<_{s'}q$でもある。 $s'$がserialであることから、$s'$では$t$の全ステップが$t'$のステップよりも先に実行される。

以上から分かることは、$G(s)$で辺があるとき、serialな履歴$s'$ではトランザクションがその順番で実行されるということ。

したがって、$G(s)$が閉路を持つと仮定すると、serialなはずの履歴でも循環する実行順が存在してしまい矛盾する。よって閉路が存在しない。

- $G(s)$ が閉路を持たない $\Rightarrow s\in CSR$

$G(s)$ は閉路を持たないのでトポロジカルソート可能である。そのようにソートしたトランザクション列を一つ取って$s'=t_{\rho(1)}\cdots t_{\rho(n)}$とする。$s'$はserialな履歴である。あとは$s\approx_cs'$を示せばよい。

$s$において$p\in t, q\in t'$が$p<_s q, (p,q)\in conf(s)$であるとき、$(t,t')\in E$である。すなわち$s'$において$t'$が$t$の後に並ぶ。$p,q$が衝突していることには変わりがないので$conf(s)\subseteq conf(s')$となる。逆に$(p,q)\in conf(s')$のとき、トポロジカルソートの性質から$p<_s q$なので$(p,q)\in conf(s)$が成り立ち、以上より$conf(s)=conf(s')$となる。$\square$

### 系3.4

CSRの所属判定はスケジュール内のトランザクションの数についての多項式時間で行うことができる。

---

このようなserializability theorem (serializabilityのグラフによる特徴づけ) は他にも登場する。

### CSRの別の特徴づけ

隣接する操作の可換性(同じデータアイテムのread同士、もしくは違うデータアイテムへの操作)を定義し、交換の末に辿り着きうるスケジュール同士を結び付けるとCSRと等価なものができる。こちらの方法はより一般化がしやすく、データの読みだし・書き込み以外の概念にも使える良さがあるそう。

## より厳しくしたConflict Serializability

### Order Preserving Conflict Serializability

衝突同値性だけでなく、時間的に被らないトランザクション同士の時系列を保存するという要請も付け加えたserializablity。

実用的な意味としては、serializeの順番と実際の実行順が異なると不都合が生じることがあるため、それを防げる。例えばトランザクションがシステムに提出された順番通りに実行されることを期待するユーザが、既出のトランザクションの完了まで新たな提出を待つことが考えられる。

---

### 定義：Order Preservation

履歴$s$がorder preserving conflict serializableとは、$s$があるserialな履歴$s'$と衝突同値かつ、
任意の$t,t'\in trans(s)$に対して、$t$が$s$において$t'$よりも完全に先に出現する($t$の全ステップが$t'$の開始ステップよりも先)場合、$s'$においても同じであることとする。

このクラスをOCSRとする。

---

### 定理3.12

$$OCSR\subset CSR$$

#### 証明

CSRに属するがOCSRでない反例は$s=w_1(x)r_2(x)c_2w_3(y)c_3w_1(y)c_1$。衝突グラフを見ると閉路が無く、$t_3t_1t_2$と衝突同値なのでCSRである。ただ、commitの位置を見ると、$t_3$が開始する前に$t_2$が終了しており、これとserialな履歴の実行順が一致しないためOCSRではない。$\square$

### Commitment Order Preserving Conflict Serializablity

こちらは分散システムに有用と考えられる正当性基準。「コミットの順番が衝突関係に準拠していれば、実はconflict serializableにもなる」という観察に基づいている。

---

### 定義：Commit Order Preservation

履歴$s$がcommit order-preserving conflict serializableとは、以下の条件が成り立つこととする。

任意の2つの異なるトランザクション$t_i,t_j\in commit(s)$について、$p\in t_i, q\in t_j$が存在して$(p,q)\in conf(s)$であるとき $c_i<_s c_j$ である。

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

---

つまり、衝突関係が存在するトランザクション間では、コミットの順番もその関係に準拠している場合に満たされる。

### 定理3.13

$$COCSR\subset CSR$$

#### 証明

$s\in COCSR$と、衝突グラフ$G(s)$の辺$(t_i,t_j)$を考える。衝突関係が存在することとCOCSRの定義から$c_i <_s c_j$ となる。
これを再帰的に適用することで、衝突グラフ上の$t_1$から$t_n$へのパスがあるとき、コミットにも$c_1 <_s \cdots <_s c_n$という関係が成り立つ。

ここで$G(s)$に閉路があると仮定すると、先述のコミット間の順序関係に矛盾が生じる($c_1 <_s \cdots <_s c_1$ のようになってしまう)ため矛盾する。したがって閉路はなく、$s\in CSR$。

CSRに属するがCOCSRに属さない反例としては$s=r_1(x)w_2(x)c_2c_1$が挙げられる。衝突グラフに閉路はないがコミット順が逆である。

### 定理3.14

$s$を履歴とする。$s \in COCSR$であることと以下の2つの条件を満たすことは同値である。

1. $s\in CSR$ かつ
2. serialな$s'$で、$s'\approx_c s$ を満たし、かつ全ての $t,t'\in trans(s), t <_{s'} t'$ に対して$c_t <_s c_{t'}$を満たすものが存在する。

#### 証明

$\Longrightarrow$

$s\in COCSR$とする。定理3.13より$s\in CSR$である。したがってあるserialな履歴$s'$があって$s'\approx_c s$。ここで、トランザクション$t,t'\in trans(s)$で$t <_{s'} t'$を満たすものを考える。$s$と$s'$の衝突同値性から、$p\in t$および$q\in t'$は順序を保存し、$p <_s q$である。COCSRの性質から$c_t <_s c_{t'}$が直ちに成り立つ。

$\Longleftarrow$

$s \notin COCSR$とする。このとき、$(p,q) \in conf(s)$ だが $c_j < c_i$ であるようなトランザクション$t_i, t_j$が存在する。条件2の仮定を満たす$s$衝突同値なserialスケジュールをとって$s'$とすると、こちらでは衝突関係から $t_i <_{s'} t_j$ とり、仮定から$c_i <_s c_j$ となり矛盾が生じる。以上より$s\in COCSR$。$\square$

さらにはCOCSRはOCSRよりも厳しい基準であることが分かる。

### 定理3.15

$$COCSR \subset OCSR \subset CSR$$

#### 証明

$s \in COCSR$ かつ $s \notin CSR$ と仮定して矛盾を導く。このとき、serialな履歴$s'$で、$s\approx_c s'$ だが、異なる2つのトランザクション $t_i, t_j$ で $t_i <_s t_j$ かつ $t_i \nless_{s'} t_j$ であるものが存在する。COCSRの仮定から $c_i <_s c_j$ である。

場合分けする。

1. $t_i$ と $t_j$ が衝突関係にある場合。あるデータ操作 $p\in t_i, q\in t_j$ があって$(p,q)\in conf(s)$ となる。衝突同値性から $(p,q) \in conf(s') \Rightarrow t_i <_{s'} t_j$ が成り立って矛盾する。

2. $t_i$ と $t_j$ が衝突関係にない場合。このとき、第3のトランザクション$t_k$が$t_i,t_j$とそれぞれ衝突し、媒介となって$c_j <_s c_k <_s c_i$ を起こしており矛盾。

OCSRに含まれるがCOCSRに含まれない反例は$s=w_3(y)c_3w_1(x)r_2(x)c_2w_1(y)c_1$。$\square$