CMU 15-445 Concurrency Control Theory

  • トランザクションの性質としてACIDがある
  • 一番簡単な方法はシングルスレッドで実行して、データベースファイルをコピーして、書き換えてスワップすること
  • Aを守る方法としては shadow paging と logging がある
  • schedule について
  • serial schedule とはトランザクションを一つずつ実行するスケジュール
  • equivalent schedules とは実行結果が同じになるスケジュール達のこと
  • serializable schedule とは serial schedule と同じ結果になるスケジュールのこと
  • conflict とは R-W, R-W, W-W を起こすようなオペレーションの組
    • これが起こると anomaly が置きてうれしくない
    • R-W だと2回読むと異なるデータが読めちゃう
  • conflict serializable とは conflict の順を保ったまま serial schedule に並び治せるスケジュール
    • dependency graph を作って循環がないかみれば効率的に判定できる
  • view serializable とは conflict serializable に加えて blind write を許すスケジュール
    • dependency graph が循環しても許される場合がある
    • 効率よく判定することができないので使われていないらしい