0. はじめに 過去の投稿の以下の主張の条件付き証明と条件を満たさない場合の反例の存在の証明です。 以下の4つの性質のうち、最大3つまでしか同時に満たせない、という主張。 スケジュールの直列化可能性 トランザクションの実行の並行性 トランザクション…

前回のポストで、アプリケーションに対するゼロ知識モデルではトランザクション間に隠れた制約（hidden restrictions）があると考えざるを得ないと書きました。 本ポストでは、トランザクション間の隠れた制約（が限定的であること）をどのように表現してス…

前回のポストで書いた、アプリケーションに対するゼロ知識がどれくらい強い制限なのかについての補足です。 ちなみに、前回のポストのメインの主張（以下）には反例がありそうでした。こちらは後日まとめたいと思います。 アプリケーションプログラムに対す…

1行で アプリケーションプログラムに対する知識（前提）をスケジューラが持たない場合、アプリケーション（複数）が発行する各トランザクションを、直列化可能なスケジュールで並行にかつ常に成功裡に実行・完了させることはできない。 <追記 2020-04-29>反…

このポストは、papa本で証明されている「スケジュールsが与えられとき、それがview serializableであることのテストはNP完全である」の証明の一部を構成する、3-CNF SAT問題からpolygraphのacyclicity判定問題への帰着についてのメモです。 papa本は以下の本…

このポストは、papa本読書会第1回目で読んだ範囲における、トランザクションの単位とトランザクション間のhidden restrictionsについてのまとめです。 議論としては2回目の内容も含んでいます。話題としては2回目の内容を含んでいます。ポストの内容は個人的…

このポストはpapa本読書会第1回目で読んだ部分のうちのconsistent stateについてのメモです。p.8くらいまでの範囲です。 このポストではpapa本は以下の本のことです。 Theory of Database Concurrency Control作者:Papadimitriou, ChristosComputer Science …

トランザクションの参照透過性と副作用 前回のポストでは、関数の参照透過性と副作用について書きました。 本ポストでは、（データベースにおける）トランザクションの参照透過性を以下のように定義する。 トランザクションのすべての作用が、トランザクショ…

db tech showcase 2018 Tokyoの以下のセッションを聴講したメモです。 A13 今後のDBのトランザクション処理のあり方について徹底討議する ～"InvisibleWriteRule: トランザクションの書込み最適化" を中心に C33 MVCCにおけるw-w/w-r/r-wのあり方とcommit or…

Making Snapshot Isolation Serializable 再考 - 急がば回れ、選ぶなら近道 で紹介されている2つの論文を読んだのでメモ。 Making Snapshot Isolation Serializable Alan Feketeの論文。 okachimachiorzさんが詳しく書いているので引っ掛かったところだけメ…