この記事は「リレーショナルデータベース入門 第３版」のトランザクションの同時実行の章の一部のサーベイです。
はてなのtex記法が上手くいかないので、定義の部分は別でtexで書いたもののキャプチャを貼るという暴挙に出ています
トランザクションの同時実行とスケジュール
トランザクション集合{T1,...,Tn}が与えられた時、 ある時刻t1にはTiの第 j ステップを 次の時刻t2ではTkの第 l ステップを ( iとkは必ずしも異なる必要性はない) 次の時刻t3ではTiの第 j+1 ステップを という具合に複数のトランザクション実行していくことをトランザクションの同時実行という。
定義(スケジュール)
スケジュールは2次元的に表現するとわかりやすく、その例は以下のようになる
直列スケジュール
トランザクションの原則はACID特性のCにもあるように一貫性である。 そのためトランザクションが単体で実行されれば、DBの状態は一貫性が保たれる。 つまり、複数のトランザクションに対しては、それらを一つずつ順番に実行していけば一貫性が保証される。この時のスケジュールを直列スケジュールという
n個のトランザクション{T1,...,Tn}が与えられたとする。 これらを直列に実行させるとき、直列スケジュールのパターンはn!個ある。 この時それぞれのパターンはトランザクションの順番が変わるので、最終的な結果は一般には異なってくる。しかし、最終的な結果は異なっていようが実行の結果はいずれも正しく、一貫性は損なわれていないことに注意する。
スケジュールの等価性と正当性
トランザクションの処理効率（以降TPS）を向上させようとすれば、トランザクションを同時実行させたくなる。例えば、一つのトランザクションがディスクのI/Oまちになって、CPUがアイドル状態になっているならその時間を使って他のトランザクションの処理に当てたい。
しかし無秩序に同時実行させれば、さまざまな異状が発生してしまう。 例えば遺失更新異状というトランザクションの更新結果が別のトランザクションの書き込みによって上書きされてしまうなどの現象があったりする。
そこでトランザクションを同時実行させるものの、直列実行のように一貫性を損なわない実行スケジュールを考えたい。 そのような理想的なスケジュールを直列化可能スケジュールという。 そこで等価性を用いて直列化可能スケジュールを定義する。
トランザクション集合{T1,...,Tn}を同時あるいは直列に実行していくにあたり、実行開始時点でのDBの状態をDBの初期状態ということにし、DB0と表すことにする。DB0に始まり、スケジュール Sに基づいて全てのトランザクションを実行終了した時点でのDBの状態をDBの最終状態ということにし、S(DB0)とかく。
定義(スケジュールの等価性)
定義(スケジュールの正当性)
また、スケジュール Sが正当であることは直列化可能であるともいう（あくまで直列実行は正しいという認識で進む）
さてトランザクション集合が与えられた時に、あるスケジュール Sが正当であるのか、またそのようなスケジュールが存在するのかという決定問題を考える。 愚直に考えるとこの問題は、非直列スケジュールSに対してn!個の直列スケジュールを順番に等価性を確認していけば解が出るが、階乗時間の計算量になるため手に負えない。
そこでスケジュール同士の他の等価性に視点をあてて、直列化可能のための条件を見つけていく。
ビュー等価とビュー直列化可能性
スケジュールの等価性を議論するために、最初に考えることはそれぞれのスケジュールの最終書き込み集合を考える。つまり、時間的に最新の書き込みが一緒であれば等価と見做していいんじゃないかということである。しかし、直列スケジュールと最新の書き込みが同じだったとしても正当とは言えないことが知られている。そこでその条件よりも強い制約を課したビュー等価を考える。
定義(ビュー等価)
定義(ビュー直列化可能性)
実はスケジュールがビュー等価であれば、いずれのスケジュールでトランザクションを実行しても実行終了後のDBは同じ状態になる。つまりビュー直列化可能であれば正当である。
とすると次なる問題はビュー直列化可能かどうかを決定する問題はどのくらい難しいのかである。この問題は実はNP完全であることが知られている。従って、問題解決が多項式時間で解けるような次善の策を考える必要がある。
そこで相反等価という考え方を導入する。
相反グラフ、相反投下、相反直列化
定義(相反グラフ)
a~cの状況にある2つのステップは互いに相反しているという。
定理
例えば以下のようなトランザクションスケジュールがあったとする
ここから相反グラフSG(C)を作る。まず相反グラフの定義のaに注目すると、データ項目xとyに関してreadがwriteに先行しているのは(T1,T2),(T2,T4),(T3,T4),(T1,T3)。次に定義のbに該当するのは(T1,T2),(T3,T4)。最後に定義のcに該当するのは(T1,T2),(T3,T4),(T3,T2)。よってグラフは以下のようになる
ここからグラフが非巡回であることが分かる（任意のノードに対してそのノードに戻ってくるような経路が存在しないこと）。よってビュー直列化可能であることが分かる。等価な直列スケジュールをトポロジカルソートで求める。
まずグラフの中から入線のないノードを探す。この場合T1が該当する。 次にグラフからそのノードと出線を消す。この場合T2→T4とT3→T4とT3→T2が残る。 するとまた入線のないノードが生まれる。この場合T3が該当する。 また同様にグラフからそのノードと出線を消す。この場合T2→T4が残る。 するとまた入線のないノードが生まれる。この場合T2が該当する。 また同様にグラフからそのノードと出線を消す
そして消したノードを順番に並べるとT1,T3,T2,T4の直列スケジュールが手に入る。 実はこのスケジュールが元のスケジュールとビュー等価になる。 （T1→T2のような矢印はT1の動作がT2に依存しているという感覚だと分かりやすいかもしれない。グラフが巡回的だと、T1→T2→T3→T4→T1のように全てが依存しあってしまう。一方直列スケジュールはこのようなことは決して起こらない。トポロジカルソートは依存元を順番に取り除いて並べる操作ということになる。ただし、巡回的でもビュー直列化可能なものはあるのであくまで非巡回は十分条件にすぎない）
定義(相反等価)
定義(相反直列化可能)
つまり相反直列化可能であればビュー直列化可能、つまり正当であるということがわかる。
実はこの相反直列化可能かどうかを求めるアルゴリズムは多項式時間の計算量ですむ。
※これまでは盲目的書きを許した議論をしている（readしなくてもwriteができる状態）。ただし、盲目的書きを許さない場合はビュー直列化と相反直列化は同値となる。
以上が同時実行制御における「静的」なアプローチである。 ここまでのアプローチ（トランザクションを実行する前にスケジュールを立てて、それが直列化可能かどうかを調べる）をスケジュール法という。
