ゼロ知識モデルでできなくなること
前回のポストで書いた、アプリケーションに対するゼロ知識がどれくらい強い制限なのかについての補足です。
ちなみに、前回のポストのメインの主張（以下）には反例がありそうでした。こちらは後日まとめたいと思います。
アプリケーションプログラムに対する知識（前提）をスケジューラが持たない場合、アプリケーション（複数）が発行する各トランザクションを、直列化可能なスケジュールで並行にかつ常に成功裡に実行・完了させることはできない。
反例とは、アプリケーションに対する知識がゼロであっても、直列化可能で直列化失敗を引き起こさないスケジューリングが、部分的には並行に（インターリーブ）できるという意味です。
続きを読む3-CNF SATからpolygraphのacyclicity判定問題への帰着
このポストは、papa本で証明されている「スケジュールsが与えられとき、それがview serializableであることのテストはNP完全である」の証明の一部を構成する、3-CNF SAT問題からpolygraphのacyclicity判定問題への帰着についてのメモです。
papa本は以下の本のことです。
Theory of Database Concurrency Control
- 作者: Christos Papadimitriou
- 出版社/メーカー: Computer Science Pr
- 発売日: 1986/07/01
- メディア: ハードカバー
- この商品を含むブログを見る
証明の流れ
- スケジュールsがview serializableである iff polygraph P(s)が非巡回である （Theorem 2.4）
- polygraphが非巡回であることのテストはNP完全である（Theorem 2.5）
- 3-CNF Fが充足可能 iff polygraph P(F)が非巡回である（本ポストの内容）
- 3-CNF Fからpolygraph P(F)が多項式時間で構築できる
- polygraph Pが与えられたとき、「Pが非巡回である iff スケジュールsがview serializableである」ようなスケジュールsをPから構築できる（Lemma 2.4）
トランザクションの単位とhidden restrictions
このポストは、papa本読書会第1回目で読んだ範囲における、トランザクションの単位とトランザクション間のhidden restrictionsについてのまとめです。
議論としては2回目の内容も含んでいます。話題としては2回目の内容を含んでいます。ポストの内容は個人的なもので読書会の総意ではありません。
具体的には、こだわっているトランザクション間の依存関係の話です。
papa本は以下の本です。
続きを読む
serializableとconsistent state
このポストはpapa本読書会第1回目で読んだ部分のうちのconsistent stateについてのメモです。p.8くらいまでの範囲です。
このポストではpapa本は以下の本のことです。
大学の図書館においてあったりします。研究目的なら大学等に所属していなくても図書館を利用できることが多いです。
続きを読む