Multiversion Serialization Graph(MVSG)の導入

マルチバージョンの環境でのトランザクションの順序を整理する為に、Multiversion Serialization Graphという考え方を導入する。
グラフとは頂点と辺からなる構造で、各頂点は各トランザクションの各ステップである。
辺を引くルールは簡単で

という2つのルールでトランザクションステップの間に辺を引く。文章で書くとわかりにくいので図で書いて説明すると例えば以下のようなマルチバージョンスケジュールがある。

この中で、上に書いたルールの通り辺を描画すると

このように辺が整理される。（なお初期状態はTx0というトランザクションがすべて書き込んだものとして扱い、最終状態も1つのステップと見做す）
こうして作ったグラフから、辺の関係をそのままステップからトランザクション同士の関係に持ち込むと

もう少し簡略化すると

こんな感じに整理される。(最終状態は便宜的にTx∞と書いた）
こうして作った有向グラフが円環を作らない場合、そのマルチバージョンスケジュールはMVSRである。
上の例は円環を作っているのでMVSRではない。

証明としてはその有向グラフをトポロジカルソートして得られた順列で各トランザクションをシリアルに実行した場合のスケジュールとRead-From関係が一致するからである。

眠いので続きはちょっと後で更新します