papa本第14回参加メモ - 誰にも見えないブログ

p.40 4行目「Suppose〜」からp43 「〜NP-complete.◻️」まで読んだ。

次回はp43「2.6 CONFLICT SERIALIZABILITY冒頭から」

Variable
- xiに対する割り当てとchoiseの関係
Fan-out
- variableのcopyとその接続。
  - 右にcopy:trueの変項
  - 左にcopy:falseの変項
clause
- ２変項の時は3つのbroken archの一つをleguler arcにする
p42の図の誤植
- x3のチェックが間違っている。
  - x=3なのでfan-out polygraphの(ci,bi)側のchoiseが選ばれる必要がある。
- x1の右側へのfan-outのchoiseに矢印が書かれていない

P(F) = acyclic ⇔ F is Satisfiableの証明
- P(F) = acyclic ⇨ F is Satisfiable
  - clauseに接続されている、選ばれなかったchoiseからassingmentが決まる
    - P(F)とcompatibleなDならfan-outで波及して、Fを満たす一貫したassingment Tが一意に決まる。
- P(F) = acyclic ⇦ F is Satisfiable
  - 背理法
  - satisfiableなTならclause,fan-outにローカルならcylceが存在しない
  - largeなcycleが存在するならclauseをまたぐglobalなcycleになる
    - clause間へのpathはpositiove clause → negative clauseの方向しか存在しない。
    - 再度positive側のclauseに戻るpathが存在しない
      - 存在するならclauseがsimpleではない→矛盾。
Lemma 2.4

Given any polygrap P, we can construct in polynomial time a schedule s such that s is view serializable if and only if P is acyclic.
F⇨P⇨sの多項式変換の二段目。
- 任意のacyclicなDが存在するpolygraphに対応するVSRなsが多項式時間で決まる
- P中のchoise c = (A1,A2,A3)は以下のスケジュールに置き換えられる
  - A1:R(c)
  - A2:W(c)
  - A3:W(c)
- polygraphは以下に対応する