Database Concurrency Control Papadimitriou 読会(31回)に参加

Database Concurrency Control Papadimitriou 読会(32回)に参加

• p86からp90まで読んだ。
• 次回はp90「Definition 3.4~」から

The Complexity of Reliability(続き)

• is reliable if and only if F is true
  • のonly if direction
    • reliable → F is true
  • 対偶(F is false → universal player が QSAT gameに勝つ)を示す
• PSPACE-compeleteとNP-completeはどちらが難しいかわかっていない
• が、view serializability(NPC)よりreliability(PC)の方が難しいと(papaさん達は)思っている
• Chapter 7でdistributed concurrency controlのPSPACE-completenessの例を説明する
  • 本にはchapter 6と書かれているが7の間違い

Conflicts and Reliability(p87)

• unsafe read,writesがないfulll schedulesをconservativeという(Example 3.7(p70)の議論も参照)
  • 形式的な定義
    • readはread commitedであること
    • concurrentなW(x) は存在しない
      • transactionの最終ステップではないW(x)に関して
        • s中にはあるw'の後にくるw''stepgaが存在するとき、 V(w)=w' を対応させているversion functionに置いて、w時点でsがcommitされているならVはwをw''に対応づける
        • つまり最新commmitのwriteは上書きされない？
  • standard version functionを採用する1つ以上のversion functionを含んでいる場合、reliableではない(がquasi-standardard versionn functionであればreliable)
  • Example 3.8(p71)はconservativeであるがreliableではない例
  • conflict serializable scheduleの場合、 conservativeであればreliableである。
• confllict seriazableであるとき、atomic write model,(s,V_s)はrelliable

Rollback Reliability

• A-continuation(p71)などの復讐が必要

Theory of Database Concurrency Control