例のトランザクション勉強会。前回までVSR=NP completeの証明に勉強会4回ほど費やしたのち、今回ついにCSR入った

p43「2.6 CONFLICT SERIALIZABILITY」から「Conflicts and Commutativity」まで読んだ次回はp46「Theorem 2.9」から

CSR

VSR＝NP完全なので代替策を考える
CSR
- VSRより強い
  - VSRで不整合となるスケジュールを含まない
  - ただしSerialization空間は狭い
- パフォーマンスが許容範囲である*1

Conflict

Conflictの定義:2つのトランザクションが同じentityに対するreadまたはwrite操作を含んでいる。ただし両方ともread以外である
- conflict
  - w-w
  - r-w
  - w-r
CSRの基準となる考え方
concurrent processesのinnteractionに似た考えである
- 意見:interactionがない→関係ない、という意味ではない。
  - co-interaction,つまり関係がない、という関係がある

Conflict equivalent

conflict stepの実行順序が同じであれば良い
定義:同じトランザクションを含んでいて任意のconflicting stepのペアの実行順序が同一であるとき、conflict equivalentという。
theorem 2.7:D2(s)=D2(s')のとき、sとs'はconflict equivalentである
- 補足:D2(s):schedule sのstepから構成されるconflict graph
- serial schedule s'とconflict equivalentであるschedule sはconflict serializableである

VSR⊃CSR

propotision 2.1:VSR⊃CSR
例
- s
  - A1:R(y) W(y) W(x)
  - A2:R(y) W(x) W(z)
  - A3:R(w) W(x)
  - A2A1A3はVSRだけどCSRではない

    - s
        - A1:R(y)           W(y) W(x)
        - A2:          R(y)          W(x) W(z)
        - A3:     R(w)                         W(x)

conflictは以下のようになる

Conflicts:
    {
        <R2(y),W1(y)>,
        <W1(x),W2(y)>,
        <W2(x),W3(x)>
    }

<W1(x),W2(y)>のconflictがTransaction order A2 A1 A3に反する⇨CSRではない
- VSRである
  - 根拠:W1(x),W2(x)の後にreadが来ない、かつ,W3(x)に上書きされる→Dead stepである

Theorem 2.8 CSR iff G(s) is asyclic

Theorem 2.8:sがconflict serializableであることと　conflict graph G(s)がacyclicであることは同値である
- 証明:
  - only-if side(⇨):
    - sがconflict serialzableであると仮定する
      - D2(s)=D2(s')となるconflict equivalentなs'が存在する
      - そのようなsとs'はG(s)=G(s')となる　
        
        なぜならG()はD2()の全てのステップを属するトランザクションにshrinkした(1ノードに凝縮した)ものであるからである。
        
        G(s')はasyclicである必要がある
        
        G(s)はasyclicである[^1]
  - if side(⇦):(背理法)
    - G(s)がacyclicであると仮定する(背理法の仮定)
      - G(s)をトポロジカルソートしたsの全順序が存在する
        
        このtotal orderはserial schedule s'である。
        
        でないとG(s)がcyclicになる(背理法の仮定に矛盾)□

f:id:yuyubu:20191121153224j:plain — shrinkの例。step間のcycleは無いがshinkするとTransaction間にcycle(A1,A2)が発生している

CSRの計算コスト

directed graphのcycle検出なので高々O(n²)
- O(V+E)
  - V+Eは最悪でO²になる(らしい)

Conflicts and Commutativity(可換を使ったCSRのもう一つの定義)

s~s:non-conflicting stepsを交換したスケジュールのこと
example

s
A1:R(x)        W(x)
A2:    R(x)W(y)

s'
s
A1:R(x)    W(x)
A2:    R(x)    W(y)

交換したW1(x)とW2(y)はconflictな関係ではないのでこの交換操作のスケジュール関係はs~s'
この交換ルールをさらに拡張する(~⇨~*)
s~*s
- ~*
  - reflexive-transitive closure
    - reflexive:任意のaにおいてaRa=true
    - transitive:aRb;bRc ⇨ aRc
    - closure:上記が成り立つ元に制限した集合
      - 推移的・反射的な交換が成り立つ？
  - reflexiveにより交換が発生しなくてもsとs'(s)に~*関係がある
  - 推移律により交換操作を複数行っても推移的に交換関係を解決できれば~*が成り立っているといえる

他

説教
- 世の開発者はtransactionを全然勉強していない
- ユーザーはともかく、開発者はread only anomalyくらいの理解は必要
- 世間的にはDBに放り込んだら"よしなに"やってくれる程度の理解
  - "よしな"がどういう範囲か理解されてない。
  - serializableでも同じ操作が違う結果になることがある。
- snapshot isolationはserializableではない
- Oracleの採用しているSerializableはSerializableではない
  - サイベースとOracleで過去に論争があったらしいだそうです。

okachimachiorz.hatenablog.com

前提知識はMVCC（MVTO、SSN、SSIとかその辺）。

うーんきつい

[^1]Furthermore, the conflict graph G(s') of the serial schedule s' is necessarily acyclic, since it.must be a subgraph of the total order under which the transactions are executed in s'.We conclude that G(s) is acyclic.