Reducibility
Conflict Serializability(CSR)の特性を説明するためのConcept．
Definition 3.17 Communtativity Based Reducibility
A history $ s is commutativity based reducible if there is a serial history $ s' such that $ s \stackrel{*}{\sim} s', i.e., $ s can be transformed into $ s' thrtough a finite number allowed transformation steps according to rules C1, C2, C3, and C4.
Let "$ \stackrel{*}{\sim}" denote the reflexive and transitive closure of "$ \sim", i.e., s $ \stackrel{*}{\sim} s' if $ s' can be obtained from $ s by a finite number of applications of C1, C2, C3, and C4.
用語の定義を洗いながら説明する．
1. $ \stackrel{*}{\sim}
Commutativity Based Equivalenceという等価性．
Let $ s and $ s' be two schedules such that $ op(s) = op(s').
Define $ s \sim s' if $ s' can be obtained from $ s by a single application of C1, C2, C3 or C4 to the steps of the schedule.
まず ，C1~C4と呼ばれるルールを一つ適用すれば$ op(s) = op(s')になるならば，$ s \sim s'と表記される．
ちなみに$ opはWeikum本p66 Definition 3.1から初出．スケジュールに含まれる命令列の集合を指す． 2. C1, C2, C3, and C4
以下のルールに従うとき，その命令ペアは可換(Commutative)である．
Rule C1: $ r_i(x) r_j(y) \sim r_j(y) r_i(x) if $ i \ne j
Rule C2: $ r_i(x) w_j(y) \sim w_j(y) r_i(x) if $ i \ne j, x \ne j
異なるタプルに対するreadとwriteのpair.
Rule C3: $ w_i(x) w_j(y) \sim w_j(y) w_i(x) if $ i \ne j, x \ne j
異なるタプルに対するwriteとwriteのpair.
このCommutativity rulesに従えば，任意のスケジュール/ヒストリを別のスケジュール/ヒストリに変換できる．
$ s = w_1(x) r_2(x)w_1(y) w_1(z)
$ s' = w_1(x) w_1(y) r_2(x) w_1(z)
$ s \sim s'
C4だけが特殊なルールとして存在する．
C1,C2,C3は暗黙的にスケジュール/ヒストリの命令列に全順序があることを要求している．
しかしConcurrency Controlではタプルごとの命令の半順序しか得られないことが多い．
半順序から全順序を生成するルールが以下のC4.
Rule C4: $ o_i(x), p_j(y) unordered
$ \leadsto o_i(x) p_j(y) if $ x \ne y \lor (o = r \land p = r)
つまり二つのconflictしていないoperation あるいは readのpairは自由な並びにしてよい．
ここでTheorem 3.11が出てくる．
Theorem 3.11
Let $ s and $ s' be schedules such that $ op(s) = op(s').
Then s $ s \approx_c s' iff $ s \stackrel{*}{\sim} s'
つまり，Conflict EquivalentならCommutativity Based Equivalentである，ということ．
さらに言い換えると，CSR == Commutativity Based Reducible であるということ． この定理の証明はなんと演習問題にされてしまっている．おかしいだろ...
Commutativity Rulesの大きな効能として，タプルごとの半順序から全順序ヒストリを生成できることがある．
つまり，タプルごとのロックしか持たないアルゴリズムでも，ヒストリのSerializabilityを証明できる．
ということは，Commutativity Rulesで禁止されているペアだけをtrackできれば，CCアルゴリズムが作れる．
具体的には，同じタプルに対するConflictと，同じトランザクション内での命令の順序を守ればよい．