Transactional Information Systems 第１１章演習問題解答

Transactional Information Systemsにおける第１１章演習問題の自分なりの解答。

間違っていたらご指摘ください。

11.1 Q

$s_1=w_1(x)w_1(y)r_2(u)w_2(x)r_2(y)w_2(y)a_2w_1(z)c_1$ と $s_2=w_1(x)w_1(y)r_2(u)w_2(x)r_2(y)w_2(y)w_1(z)a_1c_2$ について、

$exp(s_1),exp(s_2)$ と、対応する削減済みのスケジュールは？

11.1 A

アボートを時系列逆順の逆操作＋コミットに置き換える。 $exp(s_1)=w_1(x)w_1(y)r_2(u)w_2(x)r_2(y)w_2(y)w_2^{-1}(y)w_2^{-1}(x)c_2w_1(z)c_1$ $exp(s_2)=w_1(x)w_1(y)r_2(u)w_2(x)r_2(y)w_2(y)w_1(z)w_1^{-1}(z)w_1^{-1}(y)w_1^{-1}(x)c_1c_2$

隣接した逆操作どうしを相殺すると

$w_1(x)w_1(y)r_2(u)w_2(x)r_2(y)w_2^{-1}(x)c_2w_1(z)c_1$ $w_1(x)w_1(y)r_2(u)w_2(x)r_2(y)w_2(y)w_1^{-1}(y)w_1^{-1}(x)c_1c_2$

11.2 Q

各スケジュールのRC,ST,RG,PRED,LRC性を判定せよ。

$s_1=r_1(a)r_2(a)w_1(a)c_1c_2$

$s_2=r_1(a)w_1(a)r_2(b)w_2(b)w_2(a)c_2c_1$

$s_3=r_1(a)incr_2(a)incr_2(b)incr_3(b)c_3a_2c_1$

11.2 A

s1は、t1が書き込んだデータが終了時まで読み込まれないのでST、ゆえに自明にRCでもある。一方、t2が読み込んだデータが終了前にt1に変更されているのでRGではない。RCかつ、writeが一つしかないので自明にLRCであり、LRCかつCSRであることからPREDでもある。

よって $s_1\in ST-RG, s_1\in PRED\subset LRC$

s2は、t1が書き込んだaにt1の終了前にt2が書き込んでいるのでSTでない。一方、reads-from関係がないので自明にRCである。また、 $w_1(a)\lt w_2(a)$ なのに $c_2\lt c_1$ なのでLRCでなく、したがってPREDでもない。

よって $s_2\in RC-ST, s_2\notin LRC \supset PRED$

incr(a)はr(a)w(a)に相当する。なのでs3は、t2の書き込んだbを読んでいるt3がコミットしているのにt2がアボートしていることになり、RCでない。RCじゃないのでLRCでもなく、したがってPREDでもない。

よって $s_3\notin RC$

11.3 Q

各スケジュールのRC,ACA,ST性を判定せよ。

$s_1=w_1(x)r_2(y)r_1(x)c_1r_2(x)w_2(y)c_2$

$s_2=w_1(x)r_2(y)r_1(x)r_2(x)c_1w_2(y)c_2$

$s_3=w_1(x)r_2(y)r_2(x)r_1(x)c_2w_1(y)c_1$

11.3 A

s1は、t1が書き込んだxがt2に読み込まれるのがt1のコミット後なのでSTである。

s2は、t1が書き込んだxをt2が読み込んでいて、 $c_1\lt c_2$ を満たしているのでRCである。一方、読み込みがt1のコミット前に行われているのでACAではない。

s3は、t1が書き込んだxをt2が読み込んでいるのに $c_2\lt c_1$ なのでRCでない。

11.4 Q

RC,ACA,ST,RG,PREDはそれぞれprefix commit closedか？

※スケジュールクラス $A$ がprefix commit closed： $s \in A$ ならば、そのうちコミットされたトランザクションのみを抜き出したコミット射影の任意のプレフィクス $s'$ が $s'\in A$ を満たすこと。

11.4 A

RCはprefix commit closedである。

$s\in RC$ のコミット射影のプレフィクス $s'$ を考える。

$s'$ において $w_1(x)\cdots r_2(x)\cdots c_2 \cdots$ という関係があるとき、コミット射影であることからプレフィクスを取る前は $c_1$ も含まれていたはずである。したがって、以下の２つのケースに分けられる。

$c_1\lt c_2$ のケース。少なくとも $c_2$ までのプレフィクスは $s'$ に残されているので $c_1$ も $s'$ に残されている。よってRCの条件を満たす。
もとのスケジュール $s$ のreads-from関係が異なるケース。この場合、あるコミットされていないトランザクション $t_3$ による書き込みが挟まり $w_1(x)\cdots w_3(x) \cdots r_2(x) \cdots c_2 \cdots (c_1)$ のようになるが、これは $s$ のRC性に反する（ $t_2$ が $t_3$ から読み込んでコミットしているのに $t_3$ がコミットしていない）。よってこのようなケースはそもそも発生しない。 $\square$

ACAはprefix commit closedである。

$s\in ACA$ のコミット射影のプレフィクス $s'$ を考える。

$s'$ において $w_1(x)\cdots r_2(x)$ という関係があったとき、

もとの $s$ で間に挟まる $x$ への書き込みがない場合、 $s$ でも同じreads-from関係があるので、 $s$ のACA性から $w_1(x)\cdots c_1 \cdots r_2(x)$ となって $s' \in ACA$ 。
もとの $s$ で間に挟まるコミットされていないトランザクション $t_3$ があって $w_1(x)\cdots w_3(x) \cdots r_2(x)$ となる場合、 $t_2$ は $t_3$ から読み込んでいるのに $t_3$ がコミットしないので $s$ のACA性に反する。よってこのようなケースはそもそも発生しない。 $\square$

STはprefix commit closedである。

$s'$ において $w_1(x) \lt p_2(x)~(p=r/w)$ という関係があったとき、もとの $s$ でも全く同じ関係があるので、 $s$ のST性より $s'\in ST$ である。 $\square$

RGはprefix commit closedである。

STと全く同様。 $\square$ STとRGはreads-from関係じゃなく単に衝突を問題にするので簡単。

PREDはprefix commit closedである。

PREDの性質より、 $s$ の任意のプレフィクスがreducible（可換操作と逆操作の相殺の末に逐次的なスケジュールにできる）である。

よって、そのコミット射影を取り出しても、やはりコミットされていないトランザクションが消えるだけなので明らかにreducibleである。 $\square$

11.5 Q

証明せよ。

$COCSR\cap RC \neq \emptyset,\ COCSR \nsubseteq RC,\ RC\nsubseteq COCSR$
$COCSR\cap ACA \subset ACA$
$COCSR\cap ACA \subset COCSR\cap RC$
$COCSR\cap ST \subset ST$
$COCSR\cap ST\subset COCSR \cap ACA$

11.5 A

1. $COCSR\cap RC \neq \emptyset,\ COCSR \nsubseteq RC,\ RC\nsubseteq COCSR$

$s_1=r_1(x)c_1 \in COCSR\cap RC$
$s_2=w_1(x)r_2(x)a_1c_2\in COCSR - RC$
$s_3=w_1(x)w_2(x)c_2c_1\in RC - COCSR\ \square$

2. $COCSR\cap ACA \subset ACA$

$s_4=r_1(x)w_2(x)c_2c_1 \in ACA - COCSR\ \square$

3. $COCSR\cap ACA \subset COCSR\cap RC$

$s_5=w_1(x)r_2(x)c_1c_2\in (COCSR\cap RC) - (COCSR \cap ACA) \ \square$

4. $COCSR\cap ST \subset ST$

$s_6=r_1(x)w_2(x)c_2c_1 \in ST - COCSR \ \square$

5. $COCSR\cap ST\subset COCSR \cap ACA$

$s_7 = w_1(x)w_2(x)c_1c_2 \in (COCSR\cap ACA) - (COCSR\cap ST) \ \square$

11.6 Q

任意のプレフィクスがXCSRであるようなクラスPXCSRについて以下を示せ。

$PXCSR \subset XCSR$
$PXCSR \subset PRED$
$RG \subset PXCSR$
$PXCSR = ST \cap XCSR$

11.6 A

1. $PXCSR \subset XCSR$

$s_1=w_1(x)w_2(x)c_1c_2 \in XCSR - PXCSR\ \square$

2. $PXCSR \subset PRED$

$s_2=w_1(x)w_2(x)c_1c_2\in PRED -PXCSR\ \square$

3. $RG \subset PXCSR$

まず $r_1(x)w_2(x)c_2c_1 \in PXCSR - RG$ 。

次に、 $s\in RG$ を考える。競合する操作が実行されたとき、その時点で前者のトランザクションが終了している。よって、トランザクションの終了順と競合する操作の実行順が同じであり、conflict graphは閉路を持たない。よって $s\in XCSR$ であり、RGがprefix closedであることと合わせて $RG \subset PXCSR$ 。 $\ \square$

4. $PXCSR = ST \cap XCSR$

$PXCSR \subseteq XCSR$ は自明である。

まず $PXCSR \subseteq ST$ を示す。ST性に反する $w_i(x)\cdots r_j(x) \cdots c_i/a_i$ もしくは $w_i(x)\cdots w_j(x) \cdots c_i/a_i$ があったと仮定すると、 $c_i/a_i$ を含まないプレフィクスの拡張スケジュールが $t_i\rightarrow t_j \rightarrow t_i$ という競合の閉路を引き起こすため矛盾。

次に、 $s\in ST\cap XCSR$ が $PXCSR$ に属することを示す。

$s$ のプレフィクス $s'$ がXCSRでないと仮定すると、もとの $s$ でコミットだったものがプレフィクスに含まれなかったためにアボートになったことが原因になっている。そのような競合サイクルは $w_i(x) \cdots r/w_j(x) \cdots w_i^{-1}(x)$ という形であり、これはST性（書き込まれたアイテムは、トランザクションの終了時まで読み込み/書き込みされない）に反する。よって $s'\in XCSR$ 。 $\square$

11.7 Q

$Gen(SS2PL)=RG$ を示せ。

11.7 A

SS2PLの性質から、一度書き込み・読み込みされたアイテムにはトランザクションの終了時までロックが保持され続けるので、それとロックが競合するような操作はトランザクションの終了後に初めて実行される。したがって $Gen(SS2PL)\subseteq RG$ である。

一方、RGであるようなスケジュールをSS2PLスケジューラに入力すると、トランザクション終了時まで競合する操作が行われないという性質が満たされているのでロックの競合によるブロッキングが発生せず、素通しになる。よって $RG \subseteq Gen(SS2PL)$ である。 $\square$

11.8, 11.9

略

11.10 Q

全ての更新がトランザクション固有の空間で行われ、グローバルなデータへの反映がコミット時まで遅延される実装を考える。

ST, PRED, LRCの概念をこのような実装に応用できるか？それに意義はあるか？

11.10 A

コミット時に変更が一気に反映されるので、例えば $x, y$ を読みつつ変更を加えたトランザクションは $r(x)r(y)c(x,y)$ のように表記できる。ここで $c(x,y)$ は $x,y$ への書き込みとコミットを不可分に行う操作となっている。アボート時にはこの $c(x,y)$ のような操作が現れず、変更が一切関知されない。＝アボートしたトランザクションは存在していないのと同義。

コミット時点で変更が反映されるモデルにおいては、STはそもそも自動的に達成される（トランザクションの終了タイミングと書き込みの反映タイミングが同一）ので意味を持たない。

また、定義を考えてみるとLRCも意味を持たない。

PREDに関しては、まずこのケースでは元のスケジュールがREDであればプレフィクスがすべてREDなので、PREDとREDが等価である。またREDとCSRが等価である。よってPRED=CSR。LRCが意味を持たないこともこれの裏付けになっている。

u-ar.hatenablog.com

u-ar’s blog

研究や技術について。もろもろ。