博士

やあ、ロボ子。今日はデータベースの逐次化可能性について話すのじゃ。

ロボ子

逐次化可能性ですか。なんだか難しそうですね。

博士

難しくないぞ！簡単に言うと、複数のトランザクションが同時に実行されても、あたかも順番に実行されたかのように見えるようにすることじゃ。

ロボ子

なるほど。トランザクション内の操作は、読み込み(r₁[x])、書き込み(w₁[x])、コミット(c₁)、アボート(a₁)があるのですね。

博士

そうじゃ！そして、履歴はトランザクションごとの順序を尊重し、競合する操作を順序付けるのじゃ。スケジューラが見て行動できることに合わせてモデル化されているのがポイントじゃな。

ロボ子

競合同値性という言葉も出てきました。これはどういう意味ですか？

博士

競合同値性じゃな。これは、二つの履歴が「同じくらい良い」状態であることを示すのじゃ。つまり、競合する操作の順序が同じであれば、結果も同じになるということじゃ。

ロボ子

なるほど。そして、シリアライゼーショングラフ（SG）というものを使うのですね。ノードはコミットされたトランザクションで、エッジは競合をキャプチャすると。

博士

その通り！T_iがxを書き込んでからT_jがxを読み書きする場合、エッジT_i → T_jを追加するのじゃ。このグラフが非巡回的であれば、履歴は逐次化可能となる。これが逐次化可能性定理じゃ！Jim Grayという人が貢献したんじゃ。

ロボ子

非巡回的ならば、トポロジカルソートして直列履歴にできるのですね。もしサイクルを持つ場合は、直列化できないと。

博士

そうじゃ！そして、回復可能性(RC)、連鎖的アボートの回避(ACA)、厳密(ST)という概念もあるぞ。定理2.2によると、ST ⊂ ACA ⊂ RCの関係があるのじゃ。

ロボ子

これらの概念は、トランザクションの安全性に関わるものなのですね。

博士

その通り！例えば、T_jがT_iから読み込む場合、T_iはT_jの前にコミットする必要がある（回復可能）。また、T_jはコミットされたトランザクションからのみ読み込むことができる（連鎖的アボートの回避）。

ロボ子

読み書き以外の操作、例えばインクリメントやデクリメントも考慮できるのですね。

博士

そうじゃ！競合の概念を適切に再定義すれば、理論は一般化できるのじゃ。2つの操作は、それらが実行される順序がデータベースの最終状態に影響を与える場合に競合するとみなすのじゃ。

ロボ子

ビュー同値性という概念も出てきました。これは競合逐次化可能性よりも許容的な代替手段なのですね。

博士

そうじゃ！2つの履歴は、ある履歴のすべての読み込みがもう一方の履歴と同じ書き込みから読み込み、各データ項目への最後の書き込みが両方の履歴で同じ場合にビュー同値となるのじゃ。ただし、VSRのテストはNP完全らしいぞ。

ロボ子

奥が深いですね。データベースの整合性を保つためには、様々な理論や技術が必要なのですね。

博士

その通り！データベースの世界は、まるで迷宮のようじゃな。でも、一つ一つ解き明かしていくのが楽しいのじゃ！

ロボ子

今日はありがとうございました、博士。とても勉強になりました。

博士

どういたしまして。最後に一つ、データベースがロックされることを、私は「データベースが恥ずかしがって顔を赤らめている」と呼んでいるのじゃ！