多分Polygraphについて書かれた２番目の日本語のエントリー。*1

日本初のエントリー↓

内容としては先行している記事が複数の文献を参照していますが、このエントリはTheory of Database Concurrency Control p35~37の要約になっています。

polygraphとは

VSRのvalidationを行う特殊なグラフ
定義:Polygraph P=(V,A,C)
- V:vertex 頂点の集合
- A:arc (V * V)
- C:choice (V * V * V)

f:id:yuyubu:20191223001518p:plain

compatible

P=(V,A,C)と次の関係がある有向グラフD(V,B)をPとcompatibleという
- A ⊂ B
- 全てのchoice (u,v,w )⊂C ,(u,v)∈B または (v,w)∈B
具体例次のPolygraph P1はD1,D2とcompatible

f:id:yuyubu:20191223001602p:plain

f:id:yuyubu:20191223001630p:plain

次の性質を持つPolygraphをacyclicであるという

Plygraphとcompatibleなグラフの中でacyclicなものが存在すれば、polygraphはacyclicであるという

複数のトランザクションの集合をscheduleとする

schedule sの全てのトランザクションの先頭にと末尾にを含めたをVertices Vとする
- $A_0$ はs中に登場する全てのentity xに対するW(x)を含むトランザクションである
- $A_∞$ はs中に登場する全てのentity xに対するR(x)を含むトランザクションである
- $\hat{s}$ はaugmented scheduleと呼ばれることもある
Arcの作成: $\hat{s}$ に存在する全てのトランザクションA中のRに対して以下の操作を行う
- ∈の以前に存在している直近のWrite ∈からArc(,)を作成しPolygraph PのArc Aに追加する
  - 備考:通常、s中の全てのentity xに対してW(x)が $A_0$ に存在しているため、 $\hat{s}$ にはWriteに後続しないReadは存在しない=arcはs中のRの数存在している
choiceの作成:arcを作成する際に使った $W_m(x)$ < $R_n(x)$ に対してs中に $A_mA_n$ 以外のトランザクション $A_o$ に $W_o(x)$ が存在する場合、choice( $A_n,A_o,A_m$ )を作成しPolygraph PのCに追加する
- ※ $A_o$ は $\hat{s}$ ではなく、sの要素であることに注意。( $A_0,A∞$ はchoiceの中間ノードとして選択できない)
スケジュールsから作成したPolygraphをP(s)と表記する

P(s)とcompatibleなdigraph D=(V,B)はA0を支点とし、A∞を終点とするようなグラフではないといけない*2。つまり、以下に再掲するcompatileの条件にA0,A∞に関する制限が追加される｡

全てのchoice (u,v,w )⊂C ,(u,v)∈B または (v,w)∈B

P(s)のCに $A_0$ を含んでいるchoice( $A_m,A_n,A_0$ )があるとき、Bは( $A_m,A_0$ )を含んではならない
P(s)のCに $A_∞$ を含んでいるchoice( $A_∞,A_m,A_n$ )があるとき、Bは( $A_∞,A_m$ )を含んではならない
この制約がないと、前者は $A_0$ に先行するトランザクションが、後者は $A_∞$ に後続するトランザクションが存在してしまっているようなおかしなscheduleが出来上がってしまう。

s=r1(x)w2(y)w1(y)r3(x)w2(x)

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

Vertex Vはs中のA1,A2,A3にを加えた
- V={A0,A1,A2,A3,A∞}
Arc Aは中の四つのreadと同一entityに対する直近のwriteから構成される
- A={ (A0, A1), (A1, A3), (A1, A∞), (A2, A∞)}

f:id:yuyubu:20191223001705p:plain

必要な要素が出揃ったのでP(s)をビジュアライズする破線がchoiceのedge,実践がarcのedgeです。

s=r1(x)w2(y)w1(y)r3(x)w2(x)

P(s)
V={A0,A1,A2,A3,A∞}
A={ (A0, A1), (A1, A3), (A1, A∞), (A2, A∞)} 
C={(A1, A2, A0), (A3, A2, A1), (A∞, A2, A1)}

f:id:yuyubu:20191223001732p:plain

このP(s)はChoice (A1, A2, A0), (A∞, A2, A1)を含んでいる。A0,A∞とchoiceに関するルールにより、P(s)とCompatibleなdigraph(V,B)は必ずBに(A1,A2)と(A2,A1)を含んでいる。

A0,A∞とchoiceに関するルール再掲
- P(s)のCに $A_0$ を含んでいるchoice( $A_m,A_n,A_0$ )があるとき、Bは( $A_m,A_0$ )を含んではならない
- P(s)のCに $A_∞$ を含んでいるchoice( $A_∞,A_m,A_n$ )があるとき、Bは( $A_∞,A_m$ )を含んではならない

これにcompatibleなdigraphは(A1,A2)間で発生するcycleを持つためacyclicではない→P(s)はacyclicではない。

VSRの検査はNP完全です

詳しくはデヴすぴスラさんのブログを読んでください。概略だけ箇条書きしておきます

VSRのvalidationがNP完全
- VSRのvalidationはpolygraphのcycle検出に多項式変換可能。
- polygraphのcycle検出は2-3 simple CNF SATに多項式変換可能。
- 2-3 simple CNF SATはNP完全。
  - よって上記の問題は全てNP完全となる