勉強会について
Database Concurrency Control Papadimitriou 読書会 第2回 - connpass の議論メモです。
自分のメモをベースにまとめています。発言の聞き間違い、解釈違いの可能性があることをご了承ください。
特記の無い引用は本で議論した箇所を示しています。
Theory of Database Concurrency Control
- 作者: Christos Papadimitriou
- 出版社/メーカー: Computer Science Pr
- 発売日: 1986/07/01
- メディア: ハードカバー
- この商品を含むブログを見る
[memo]は私のメモです。勉強会で議論された内容ではないことにご注意ください。
1.2 THE MODEL
Schedules
スケジュールは複数のトランザクションをまとめたもの。log や history と呼ばれることもある。
[memo]
Schedule と History を区別する場合もあります。詳細は以下の記事を参照ください。
History - nikezono
if A = a1a2a3a4 and B = b1b2b3 are transactions, then s = a1b1b2a2a3a4b3 and s' = b1b2a1b3a2a3a4 are schedules.
s も s' も subsequence (A, B) の順は維持している。
If s is a schedule involving the transactions A1, ... , Ak, then an interpretation I of s is a k-tuple of interpretations Ij = (D, Fj), all with the same choice D of domains for the entities.
read や write は F で定義できる。Definition 1.2 を参照のこと。
Dに添字がないのは各エンティティの取り得る値が固定と言うこと。
Definition 1.3 はエルブラン・セマンティクスに対応している。
step a が R(x) であれば、a の直前に書かれた W(x) の ws(I,X) と等しい。
write がなければ最初の初期値を読む。
write がそれまでの read に依存している。
read せずに write することをエルブラン・セマンティクスでどう表現するのか？read しているけどその結果を無視すると解釈するのはどうか？もしくは r1, ... , rk の k が0である空集合とすればよいのでは？
[memo]
エルブラン・セマンティクス(Herbrand Semantics)理解メモ - ぱと隊長日誌
read せずに write することについては初期値と同様に表現できると考えています。
つまり、
Hs(w0(x)) = f0x()
この式で表せることになり、「k が0である空集合」と考えて良いのではないかと思われます。
トランザクション間に依存関係があるときはどうするのか？前回（Theory of Database Concurrency Control Papadimitriou 読書会 第1回ノート - Yabu.log）の "hidden restrictions と Transaction chopping" の議論にあったように、そのようなトランザクションは一つにまとめなければいけない。
アプリが consistent を保証しなければいけない。これについてはDBが面倒をみない。"each transaction is correct" とはそういう前提がある。
nested transaction が実現可能であれば、SAVEPOINT は不要になる。ネストしたトランザクションの commit は pre-commit のように扱われる。最も外側のトランザクションが rollback されたら、全て rollback となる。
ネスティッドトランザクションとは，トランザクションをネストさせることができるモデルです。トランザクションをネストさせると，部分的なロールバックができます。一つの大きなトランザクション処理を幾つかの処理単位に分割し，ある処理単位が失敗した場合に，その処理単位だけを部分的にロールバックして代替処理を行い，全体のトランザクションをコミットさせます。このため，部分的な障害をトランザクション全体に影響させないようにできます。
トランザクションモデル
（中略）
サブトランザクションがロールバックすると，先祖のトランザクションの意思に関係なく，そのサブトランザクションで行った処理はロールバックされます。サブトランザクションがコミットした場合，その時点では実際にコミットするかロールバックするかは決定されないで，そのサブトランザクションの先祖の意思にゆだねられます。すべての先祖がコミットすればそのサブトランザクションもコミットされますが，先祖のうち一つでもロールバックした場合はそのサブトランザクションもロールバックされます。したがって，あるトランザクションが完了（コミットまたはロールバック）するには，そのすべての子トランザクションが完了していなければなりません。
神林さんの実体験として、数分程度で終わる処理なら一気に実行し、ダメなら rollback してやり直す。でも、数時間単位でかかる処理なら中間状態を保持しておき、ダメならそこに戻したりする。全体を rollback すると時間がかかりすぎたりするため。
単一のトランザクションとはスケジュールの特殊なケースだ。
アプリがトランザクションの実行する順序を守りたいなら、それはアプリが保証しなければならない。DBは関知しない。
"all serial schedules" とは正しい状態が複数あることを指している。実行のたびに結果が変わることもありうる。
Schedulers
スケジューラの仕事は correct schedule を作ること。最も単純なのは全てのトランザクションをためておき、シリアルなスケジュールにすればいい。ただ、これは最悪のケース。
では、良いスケジューラとは何か？実測ではなく、理論的に定式化したい。papa本5章で評価の指標と仕組みが示されている。
CPUも命令の実行順の最適化をしており、パフォーマンスの良し悪しを評価できるが、その定式化はなされていなさそう。
APPENDIX
Graph Theory
degree とは node（もしくは vertex）につながっている線の数といえる。
vertex を sequence に辿ることを walk（もしくは chain）と呼ぶ。
cycle とは walk の始点と終点が同じこと。
papa本では cycle の定義がなされている。他の本では cycle について言及する時にも cycle の定義がなされていないことがほとんど。グラフ理論の本ですら回れば cycle、ぐらいの定義だったりする。
walk で同じ点に戻ってくることをノット（結び目）という。
[memo]
デッドロック検出におけるknotとcycleの違いについて - Yabu.log
Proposition 1.1
directed graph が acyclic であれば vertices を order できる。また、order 出来る場合が acyclic である。
ただ、神林さんはここで order の定義が無いことを気にしている。例えば vertex が1つしかないと order できないが、これを定義していない。
可能性のある order 全てを表現する記法を考える難しさ。
order の可能性として 1→2→3 もしくは 1→3→2 があるとする。これを 1<(2,3) と表現することは出来るかも知れない。でも、分岐したり合流したりを繰り返したときに全パターンを表現しきれない。
簡潔データ構造を使えばリストで DAG (Directed acyclic graph) に近いことを表現できる。ただし、このデータ構造は最初から order を全て与えられていなければいけないなど、制約もある。
数学での理論は order が全て与えられた前提となっている。TXのようにちょこちょこと追加されるケースに対しての理論は無いかもしれない。
