Papadimitriou - Theory of Database Concurrency Control読書会17回:VSRの近似計算,2章まとめ

ポスト忘れてました｡1Hくらいで書いたのでまとめきれてません｡

p49"Proof"からp56のchapter最後まで読んだ｡きりが悪いのでこのノートはp49のproofの次のlemmaから書いてある

Lemma 2.5

• xにおいてconflict(w-w or r-w or w-r)しているトランザクションA,Bがあるとする
  • xはA,B以外のトランザクションによるwriteはない｡

• この時､A､B含むsに対応する任意のSeriall Schedule s'ではかならずA,Bのxにおけるconflicting stepは同じ順序で出現する

• proof略

  • ごめんなさい｡時間があるときに書くかも

2.7 SPECIAL CASES

• VSRやFSRのSerializable ValidationはNP完全問題である
  • その近似解を考える

No Blind Writes

• 各トランザクション内のwrite stepの前には必ず何らかのread stepがあると仮定する

  • corecctnessが簡潔になる
    • 計算量が減る?

• 以後､Blind Writesを含まないセマンティクスをrestricted modelと呼ぶ

Lemma 2.6

restricted modelではSerial Schedule s の[tex:\hat{s}([tex:R_0,R_∞を含んでる)から作成されるDigraph D任意のentity xに対する任意のW(x)間の順序を決定できるpathが存在している｡

• proof略

Theorem 2.11

restricted modelではsがVSRであることとCSRであることは同値である｡

• proof略

The Action Model

• read stepとそれに依存するwrite stepの間隔が極端に短いモデルを考える
  • 恒等写像(readした値をそのままwriteする)も含む
• このr-wペアをActionと呼ぶ｡
• 上記のActionに制限したstepしかないモデルをAction Modelと呼ぶ
• このモデルではAction R(x)W(x)をatomic action A(x)に書き換えることができる
  • 例略

Theorem 2.12

Action ModelではFSR,VSR,CSRが一致する

• proof略

他

• Action modelは3章でも利用される

2章の振り返り

• correctnessについて学んだ｡
• FSR:ここから始めた｡
• VSR:チェックがNP完全問題である
• CSR:よりきついcorrectness

英語

• 英語力が上がってきたのか､わからない単語が少なくなってきた｡

• irons out:解決する?といういみらしい｡辞書ではアイロンがけするという意味も出てきた｡

  • p52:"~,the simplicity of the action model irons out the complexities of serializability,~"

Theory of Database Concurrency Control