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

Transactional Information Systemsにおける第１０章・第１２章演習問題の自分なりの解答。どちらも短いので１エントリに統合。

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

10.1

Q

多重粒度ロックにおいて、lock escalationがデッドロックを引き起こすケース、引き起こさないケース

A

テーブルa1内にレコードr1,r2が、テーブルa2内にr3,r4がある状況を考える。トランザクションt1がr1,r3にwrite lockをかけ、t2がr2,r4にwrite lockをかけているとき、t1がr1のロックをa1全体に、t2がr4のロックをa2全体に昇格しようとすると、お互いにレコードレベルのロックの解放待ちになってデッドロックが起こる。

例えばこれがどちらもa1のロック昇格を望むだけなら一方がブロックされるだけなのでデッドロックにならない。

このようなデッドロックは、read/writeもしくはwrite/writeロックの競合時に起きるものなので、どちらも読み込みならば昇格も問題なく行われデッドロックは発生しない。

10.2

Q

lock de-escalation(escalationの逆、ロック粒度を細かくすること)が意味をなす例は？

A

ロックの粒度を細かくする=ロックを一部解放してしまうため、2PLのうち後半の解放フェーズに使わないと安全でない。
長いトランザクションの途中で、最初は表全体からデータを読み取り、その後に一部のレコードに対してのみ書き込みを行いたい場合が考えられるが、これは同様の機能がSIXロックモードで実現できるため意味が薄い。
- 結局よく分からなかった。SIXでいいような...？

10.3

Q

SQL標準における分離レベル（serializability, repeatable read, read committed, read uncommitted）の各クラスに属するスケジュールの例

A

$r_1(x)c_1 \in \textrm{serializability}$
$\textrm{repeatable read - serializability}$ ：後述
$r_1(x)r_2(x)w_1(x)c_1w_2(x)c_2\in \textrm{read committed - repeatable read}$ (lost updateの原因)
$w_1(x)r_2(x)c_1c_2\in \textrm{read uncommitted - read committed}$
$w_1(x)w_2(x)c_1c_2\notin \textrm{read uncommitted}$

repeatable read-serializabilityに入りうるのは、「phantom problemは起こすが他の問題は防ぐ」ようなスケジュール。phantom problemは述語指向のロックのような複雑なロックにおいて起こる問題なので、単純にページモデルでの例は挙げられない。

8章2節の内容を参照して、

$t_1$ : delete from emp where dep="Service" and pos="Manager"
$t_2$ : select name, pos, salary from emp where dep="Service"
$t_1$ : insert into emp values ("Smith", "Service", "Manager", 40000)
$t_1$ : update emp set dep="Sales" where dep="Service" and pos <> "Manager"
$t_1$ : insert into emp values ("Stone", "Service", "Clerk", 13000)

こうすると、 $t_1$ の最初のステップはService部門のManagerのレコードのみロックするため、その削除後の $t_2$ のService部門列挙クエリはロックに引っかからず実行できてしまう。実行結果がManagerのいない名簿になってしまっており、phantom problemが起こっている。

10.4

Q

snapshot isolationを満たすスケジュールのうち、データの一貫性が破壊されるものの例

A

$s=r_1(x_0)r_1(y_0)r_2(x_0)r_2(y_0)w_1(x_1)c_1w_2(y_2)c_2$

t1とt2のwrite setが互いに素でreadが最新のバージョンを読んでいるので、sはsnapshot isolationを満たしている。

一方、例えば初期値が $x_0=5, y_0=5$ で制約 $x+y\geq 0$ があった場合、 $w_1(x_1)$ と $w_2(y_2)$ がそれぞれ$x,y$から10ずつ引いてしまうことがありえる。この場合、制約を満たさなくなっておりデータの一貫性が破壊されている。

よってsnapshot isolationは正当性の面で問題を抱える。

10.5

Q

snapshot isolationを保証する同時実行制御アルゴリズム

A

各データアイテムについて、コミットされたバージョンと最新のバージョンのタイムスタンプを保持する。読み込み時にはコミットされたバージョンを読み込み、書き込みでは、書き込みたいデータアイテムの最新バージョンタイムスタンプがそのトランザクション開始タイムスタンプよりも新しいときに不正状態なのでアボートする。コミット段階で書き込んだ最新バージョンをコミットされたバージョンに変換する。

10.6

Q

MVSRとsnapshot isolationはお互いを包含しないこと

A

$s_1=r_1(x_0)r_1(y_0)r_2(x_0)r_2(y_0)w_1(x_1)c_1w_2(y_2)c_2 \in \textrm{snapshot isolation} - MVSR$ $s_2=w_1(x_1)w_2(x_2)c_1c_2 \in MVSR - \textrm{snapshot isolation}$

12.1

Q

データベースキャッシュとログバッファが非揮発性・予備電源持ちのRAMに保存されているとき、障害回復が必要になるのはどのような障害の発生時か。

A

OSやDBMS、システムソフトウェアのエラーに起因する障害。

12.2

Q

非揮発RAMに加え、仮想メモリのページ保護機能により、通常動作中のソフトウェアによるメモリアクセスが注意深く管理されていたとき、ソフトウェアエラーに起因する障害に際していえることは？

A

undoステップは必要である。クラッシュ時にアクティブだったトランザクションのロールバックが必要なのは非揮発でも変わらない。
redoステップは必要ない。クラッシュ時点までの変更は全て非揮発RAMに反映されて残っている。
データベースキャッシュのページが通常動作中に永続データベースに書き出されたとき、ログバッファを必ずしも書き出す必要はない。
データベースキャッシュのページが回復による再開中に永続データベースに書き出されたとき、ログバッファを書き出す必要がある。再開中なのでメモリアクセスへの管理がされておらず、RAMの内容がエラーで破壊される可能性がある。
トランザクションがコミットされたとき、ログバッファを必ずしも書き出す必要はない。コミットされたことを示すログエントリは非揮発RAMに反映されて残る。

u-ar.hatenablog.com

u-ar’s blog

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