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

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

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

8.1 Q

述語ロック (predicate locking) はOR条件や結合条件にどのように拡張できるか。

ORの例：

select name from emp 
where position = 'manager' or department = 'research';

結合の例：

select emp.name, emp.department from emp, dept
where emp.position = 'manager' and dept.city = 'Toronto' 
and emp.department = dept.department;

8.1 A

ORの方は、position='manager'とdepartment='research'に同時に述語ロックをかければよい。

結合については、empをposition='manager'で、deptをcity='Toronto'でロックすればよい。

8.2 Q

IDM トランザクションにおいては、履歴の各リレーションへの射影がserializableでも全体がserializableになるとは限らないことを、以下の反例を用いて示せ。

$t_1=m^R(A=1;A=2)m^S(C=5;C=6)$ $t_2=m^R(A=2;A=3)m^S(C=4;C=5)$ $s=m^R_1(A=1;A=2)m^R_2(A=2;A=3)m^S_2(C=4;C=5)m^S_1(C=5;C=6)$

8.2 A

スケジュール $s$ のRへの射影、Sへの射影は逐次的だが、 $s$ そのものは $t_1, t_2$ の競合が閉路を作っているのでserializableでない。

8.3 Q

IDM トランザクションから、Modify操作を除外してInsert, Deleteのみのモデルを考える。

(a) Modify操作はDelete+Insertで代替できないことを示せ。

(b) $s=i_1(1)d_2(1)i_2(2)d_1(2)i_3(1)i_3(2)\in FSR_{IDM}-CSR_{IDM}$ を示せ。

8.3 A

(a) Modify操作はDelete+Insertで代替できないことを示せ。

もともと存在していないタプルをModifyする操作をDelete+Insertに置き換えてしまうと、
- 本来のModifyでは新しいタプルは作られない
- Delete+Insertでは新しいタプルが作られてしまう

(b) $s=i_1(1)d_2(1)i_2(2)d_1(2)i_3(1)i_3(2)\in FSR_{IDM}-CSR_{IDM}$ を示せ。

$t_1t_2t_3$ を逐次的に実行した場合と最終的な状態が同じ (タプル1も2も存在する) なのでFSRに属する。

一方、 $i_1(1)\rightarrow d_2(1), i_2(2)\rightarrow d_1(2)$ がそれぞれ競合しているのでCSRでない。

(c) IDトランザクションのみの場合、 $FSR_{IDM}$ の所属は多項式時間で判定できることを示せ。

与えられたスケジュールの実行結果と同じ結果を生む逐次的なスケジュールを見つけたい。多項式時間で判定するには、全ての並びを総当たりで調べることはできない。

そこで、必要な最終結果に矛盾しないトランザクションを貪欲的に選び、それを最後に実行するよう順次スケジュールすることを考える。

まず、与えられたスケジュールを先頭から末尾までスキャンしてみて、挿入されたタプルの集合Iと削除された (挿入されなかった) タプルDを分類する。
すべてのトランザクションの中から、InsertをD内のタプルに行わず、かつDeleteをI内のタプルに行わない (=最終結果と矛盾しない) トランザクションをなんでもいいので一つ選び出し、それを最後に実行することに決める。このトランザクションがInsertしたI内のタプル、およびDeleteしたD内のタプルは、それ以前のトランザクションではどう扱ってもいいので、新たに任意操作可能なタプルの集合Nに分類し直す。
残りのトランザクションも、InsertをD内のタプルに行わず、かつDeleteをI内のタプルに行わないトランザクションを任意に選んでスケジュールしていく。Nにいったん分類されたタプルに対してはどんな操作でもよい。
この過程ですべてのトランザクションを選ぶことができたら、実行結果がもとのスケジュールと矛盾していないのでFSRに属する。
逆にそのようなトランザクションを選ぶことができなかったら、どのような並べ方をしても少なくとも一つ矛盾する結果になるタプルが存在してしまうのでFSRに属さない。

貪欲的にトランザクションを選択しているので多項式時間で実行可能である。一つスケジュールの順を決めるたび、すべてのトランザクションについて、すべての操作が矛盾しないか判定するわけなので、時間のオーダーとしてはざっくり $O(n^3)$ を超える。

8.4

冒頭に記載のHackMDリンク先の読書ノート、８章のページに記述している。

8.5 Q

IDM トランザクションについて以下を示せ。

(a) $FSR_{IDM}$ が単調でないこと。

(b) $FSR_{IDM}$ が prefix commit closed でないこと。

(d) $ECSR_{IDM}$ が単調であること。

(e) $CSR_{IDM}$ も $ECSR_{IDM}$ も prefix commit closed であること。

※Aが単調：Aに属する任意のスケジュールについて、すべての射影がAに属すること。 ※Aがprefix commit closed：Aに属する任意のスケジュールについて、コミット射影の任意のプレフィクスがAに属すること。

8.5 A

(a) $FSR_{IDM}$ が単調でないこと

$s=m_1(1;2)m_2(2;3)m_1(3;4)d_3(1)d_3(2)d_3(3)d_3(4)$

は最終状態が $t_1t_2t_3$ と等しいのでFSRだが、 $t_3$ を除いた瞬間にFSRでなくなる。よってFSRは単調でない。

(b) $FSR_{IDM}$ が prefix commit closed でないこと

(a)より。

(c) $CSR_{IDM}$ が単調であること

射影により、conflict graphにおける頂点が減るだけなので非閉路存在性は単調である。

(d) $ECSR_{IDM}$ が単調であること

(c)と同じ。

(e) $CSR_{IDM}$ も $ECSR_{IDM}$ も prefix commit closed であること

conflict graphにおける頂点と辺が減るだけなので、もとでacyclicならコミット射影のプレフィクスでもまたacyclic。

8.6 Q

IDM トランザクションモデルにSELECT操作を導入し、適切な可換性を追加で定義せよ。

8.6 A

タプル集合 $C$ をSELECTする操作 $s(C)$ を新たに定義する。

最終状態には一切関係しないためFSRには影響を与えず、またlost updateなどの可能性があるため適切でもない。

一方、操作間の可換性に基づくCSRの定義は、 $s(C)$ を含むように拡張することが可能である。

$s(C_1)i(C_2)\approx i(C_2)s(C_1)~(C_1\cap C_2=\emptyset)$
$s(C_1)d(C_2)\approx d(C_2)s(C_1)~(C_1\cap C_2=\emptyset)$
$s(C_1)m(C_2;C_3)\approx m(C_2;C_3)s(C_1)~(C_1\cap C_2=\emptyset, C_1\cap C_3=\emptyset)$
$s(C_1)s(C_2)\approx s(C_2)s(C_1)$

8.7 Q

例8.13のトランザクションにおいて、 $t_{11}$ のさらなる分割はもはや正当なトランザクション分割を生まないことを示せ。

8.7 A

分割して $t_{111}, t_{112}$ にすると、 $t_2$ との間でsc閉路が生じるので正当でない。

8.8 Q

$t_1 = r_1(x)w_1(x)r_1(y)w_1(y)$

$t_2 = r_2(x)$

$t_3 = r_3(y)w_3(y)$

$t_1$ を3つのトランザクションに分割せよ。

8.8 A

$t_1 = r_1(x)|w_1(x)|r_1(y)w_1(y)$ が正当な分割。

8.9 Q

定理8.5を示せ。

（分割グラフがsc閉路を持たないとき、そのトランザクション分割が正当であること）

8.9 A

対偶を示す。トランザクション分割が正当でないと仮定する。このとき、各トランザクション片がCSRスケジューラに基づいて制御されたスケジュールのうち、逐次的なスケジュールとconflict equivalentでないようなものが存在する。

これは、各トランザクション片を独立なトランザクションとみたときにはconflict graphに閉路が存在しないが、同じトランザクションに由来するトランザクション片の頂点を全て縮約すると閉路が生まれることを意味する。

これを分割グラフで見ると、異なるトランザクション間の競合に由来する $c$ 辺だけでは閉路が存在しないが、それに同じトランザクションに由来する片間に引かれる $s$ 辺を加えると閉路が生まれることを意味する。少なくとも一つずつ $c$ 辺も $s$ 辺も含まれるので、sc閉路が存在する。

8.10 Q

分割されたトランザクション群がsc閉路を持つとき、トランザクションをそれ以上分割しても分割グラフはacyclicにならないことを示せ。

8.10 A

sc閉路に属するトランザクション片をさらに分割しても下図のケースのいずれかになり、結局sc閉路は存在する。

8.11 Q

パラメータを持つプロシージャpurchase(i,p)を考える。

if (p > cash) rollback;
else inventory[i] = inventory[i] + p;
cash = cash - p;

どのような条件、どのような範囲でトランザクション分割が適用できるか？

8.11 A

inventory[i] = inventory[i] + p; と cash = cash - p; の間で、p + q < cash かつ i≠j であるような purchase(j,q) を混ぜることは許容される。

u-ar.hatenablog.com

u-ar’s blog

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

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

8.1 Q

8.1 A

8.2 Q

8.2 A

8.3 Q

8.3 A

(a) Modify操作はDelete+Insertで代替できないことを示せ。

(b) $s=i_1(1)d_2(1)i_2(2)d_1(2)i_3(1)i_3(2)\in FSR_{IDM}-CSR_{IDM}$ を示せ。

(c) IDトランザクションのみの場合、 $FSR_{IDM}$ の所属は多項式時間で判定できることを示せ。

8.4

8.5 Q

8.5 A

(a) $FSR_{IDM}$ が単調でないこと

(b) $FSR_{IDM}$ が prefix commit closed でないこと

(c) $CSR_{IDM}$ が単調であること

(d) $ECSR_{IDM}$ が単調であること

(e) $CSR_{IDM}$ も $ECSR_{IDM}$ も prefix commit closed であること

8.6 Q

8.6 A

8.7 Q

8.7 A

8.8 Q

8.8 A

8.9 Q

8.9 A

8.10 Q

8.10 A

8.11 Q

8.11 A

8.1 Q

8.1 A

8.2 Q

8.2 A

8.3 Q

8.3 A

(a) Modify操作はDelete+Insertで代替できないことを示せ。

(b) を示せ。

(c) IDトランザクションのみの場合、 の所属は多項式時間で判定できることを示せ。

8.4

8.5 Q

8.5 A

(a) が単調でないこと

(b) が prefix commit closed でないこと

(c) が単調であること

(d) が単調であること

(e) も も prefix commit closed であること

8.6 Q

8.6 A

8.7 Q

8.7 A

8.8 Q

8.8 A

8.9 Q

8.9 A

8.10 Q

8.10 A

8.11 Q

8.11 A

(b) $s=i_1(1)d_2(1)i_2(2)d_1(2)i_3(1)i_3(2)\in FSR_{IDM}-CSR_{IDM}$ を示せ。

(c) IDトランザクションのみの場合、 $FSR_{IDM}$ の所属は多項式時間で判定できることを示せ。

(a) $FSR_{IDM}$ が単調でないこと

(b) $FSR_{IDM}$ が prefix commit closed でないこと

(c) $CSR_{IDM}$ が単調であること

(d) $ECSR_{IDM}$ が単調であること

(e) $CSR_{IDM}$ も $ECSR_{IDM}$ も prefix commit closed であること