###### tags: `TransactionalInformationSystems`

# 11章-3 オブジェクトモデルにおける復元可能性

オブジェクトモデルへの拡張を考えていく。まず平坦なスケジュールに対して、その後に一般のスケジュールに対して考える。

## 平坦なスケジュールにおけるabort

まず逆操作の意味がページモデルと異なってくる。

---

### 定義：逆操作

操作$f'(x_1',\ldots,x_{m'}',\uparrow y_1',\ldots,\uparrow y_{k'}')$が操作$f(x_1,\ldots,x_{m},\uparrow y_1,\ldots,\uparrow y_{k})$の逆操作であるとは、可能な任意の操作列$\alpha, \omega$に対して、$\alpha ff'\omega$ と $\alpha\omega$ の返り値パラメータが同じであることとする。

このような逆操作を$f^{-1}$とも表記する。

---

返り値パラメータに含まれない副作用(履歴など)は必ずしも順操作を打ち消す必要がなく、そういった意味では厳密な「逆」でなくてよい。

なお、逆操作はそれ以下のレベルの操作を持たないことに注意。逆操作が配置される段階では具体的に低レベルの操作をどう行えばいいかが分からないため。代わりに、実行段階で動的に低レベル操作にまで展開される。

ページモデルにおける操作間の可換性を振り返ると、順操作と逆操作が全く同じ可換性を持っていた。($r$と$r^{-1} (=null)$, $w$と$w^{-1}$) ここから、このような性質を満たす操作どうしは、ページモデルのように都合よく扱えると考えられる。

---

### 定義：完全可換性

オブジェクト$x$に対する操作群の可換表が完全であるとは、その中の任意の2つの操作$f,g$に対して、

$f$と$g$が可換 $\Leftrightarrow$ $f$と$g^{-1}$が可換 $\Leftrightarrow$ $f^{-1}$と$g$が可換 $\Leftrightarrow$ $f^{-1}$と$g^{-1}$が可換

を満たすこととする。

---

完全可換性が成り立つオブジェクトに対してはS2PLが素直に適用できる。このとき、完全可換性はデッドロックの解消にメリットをもたらす。

デッドロックを検出してabortしようとする際、逆操作のために追加でロックを獲得しようとすると再びデッドロックに陥ってしまう。一方、完全可換性が成り立つ場合には、順操作が確保していたロックをそのままabortのために用いることができるため、そのような問題を起こさないのだ。

ただし、セマンティクスの豊富な操作の場合、完全可換性は達成できないこともあるので、以下の緩和も考える。

---

### 定義：完全閉包

あるオブジェクトの可換表における完全閉包とは、可換表の部分表のうち、完全であるような最大のものとする。

ここで部分表とは、あるエントリが+ならもとの表でもそのエントリが+であることとする。つまり、もとの可換性を安全な範囲で可能な限り尊重した完全な可換性が完全閉包。

---

例えば、可換表

||$Insert(x)$|$Delete(x)$|$Test(x)$|$Insert^{-1}(x)$|$Delete^{-1}(x)$|
|---|---|---|---|---|---|
|$Insert(x)$ |-|-|-|-|-|
|$Delete(x)$ |-|-|-|-|-|
|$Test(x)$ |-|-|+|-|-|
|$Insert^{-1}(x)$|-|-|-|+|-|
|$Delete^{-1}(x)$|-|-|-|-|+|

の完全閉包は

||$Insert(x)$|$Delete(x)$|$Test(x)$|$Insert^{-1}(x)$|$Delete^{-1}(x)$|
|---|---|---|---|---|---|
|$Insert(x)$ |-|-|-|-|-|
|$Delete(x)$ |-|-|-|-|-|
|$Test(x)$ |-|-|+|-|-|
|$Insert^{-1}(x)$|-|-|-|-|-|
|$Delete^{-1}(x)$|-|-|-|-|-|

完全性と別に、可換表に対する制限をもう一つ考える。

---

### 定義：正規可換表

あるオブジェクトに対する可換表が正規であるとは、任意の操作$f,g$に対し以下が成り立つこととする。

$f$と$g$が可換でないなら、$f^{-1}$と$g$が可換でなく、$f$と$g^{-1}$も可換でない。

---

完全可換表は正規可換表であるが、逆は必ずしも成り立たない。(完全可換性の方が厳しい条件)

---

### 定義：Strictness

平坦なスケジュール$s$がstrictであるとは、任意の$L_1$操作$p_i$と$q_j$で$p_i$がupdate操作かつ$p_i$と$q_j$が非可換なものに対し、$p_i<_s q_j$ならば、$c_i<_s q_j$または$a_i<_s q_j$が成り立つこととする。

このクラスをページモデルと同様にSTと表記する。

---

ページモデルと同様、書きこんだトランザクションが終了するまで、その書き込みと干渉するような操作が実行されないというような条件がstrictnessとなっている。ページモデルでは$CSR\cap ST\subset PRED$なのと同様に以下が成り立つ。

### 定理11.9

完全な可換表を持つ平坦なスケジュール$s$で、conflict serializableかつstrictであるようなものは、先頭削減可能である。

## 一般のスケジュールにおけるabort

一般のオブジェクトモデルスケジュールにおいては、トランザクション全体に限らず、一部のサブトランザクションをロールバックすることも考えられ、これができればパフォーマンスの観点から有用である。

---

### 定義：サブトランザクション完結

オブジェクトモデルの履歴がサブトランザクション完結とは、各内部ノード$p_w$が、他の全ての子の後に続くような子$a_{\omega\nu} / c_{\omega\nu}$を持つこととする。

オブジェクトモデルのスケジュールがサブトランザクション完結とは、サブトランザクション完結な履歴のprefixであることとする。

---

要は、サブトランザクションが全て独自の終了操作を備えていることとする。以降ではサブトランザクション完結なスケジュールのみ考えていく。

### 定義：拡張オブジェクトモデルスケジュール

$s$がサブトランザクション完結なオブジェクトモデルスケジュールとする。その拡張$exp(s)$は、以下の手順で拡張された履歴として定義される。

1. commitの子を持つ操作は$exp(s)$に含まれる。
2. abort操作$a_{\omega\nu}$を子に持つような操作$p_\omega$に対して、abort操作$a_{\omega\nu}$を除く$(\nu-1)$個の順操作に対する逆操作が新たに$p_\omega$の子として追加される。ただし、この$(\nu-1)$個のカウントからabortした子は除く(そのような子は再帰的に下のレベルで逆操作を追加される)。逆操作は順操作の逆順に配置される。$p$のabortが$q$の先に実行されるなら、$p$の新たな子も全て$q$より先に実行される。
3. $active(s)$に属するトランザクションに対しては、対応する逆操作とcommit操作が新たな子として追加される。

### 定義：拡張木削減可能性

オブジェクトモデルスケジュール$s$が拡張木削減可能とは、$exp(s)$に以下の規則を有限回適用して、commitされたトランザクションの根の列に変形できることとする。

1. 隣接する葉で衝突していないものは交換できる。
2. 孤立した部分木は枝刈りできる(トランザクションの$L_i$操作が全て孤立しているなら、$L_{i-1}$操作を全て取り除いてよい)
3. 隣接する葉で互いに逆の操作$p, p^{-1}$は同時に取り除ける。
4. read-onlyな操作は取り除ける。
5. 順序付けられていない葉には任意に順序付けてよい。

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

これは木削減可能性を4のnull ruleと3のundo ruleで拡張したものとなっている。

### 定理11.10

階層的なスケジュール$s$は、$s$の層間スケジュールが全てconflict serializableでstrict、かつ$s$が衝突忠実であるとき、拡張木削減可能である。

### 定理11.11

階層的なスケジュール$s$は、$s$の層間スケジュールが全てorder preserving conflict serializableでstrictであるとき、拡張木削減可能である。

## 復元可能なオブジェクトモデルスケジューラ

階層的なスケジュールに絞って着目する。定理11.11から分かるように、層間スケジュールに適用するS2PLはOCSR性とST性を保証する→全ての層に適用すれば全体の木削減可能性が保証される。

### 定理11.12

$Gen(S2PL)\subseteq ETRED$