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 …

（このポストはトランザクションとは関係ありません） トランザクションをTXと略すことがある。 これはtransactionを、同じ発音で読めるtranxtion（またはtranxaction）と書いたときの音節ごとの先頭文字をとってきたものである。 一方、トランザクションをX…

0. まとめ 0.1 P, NP, NP完全 計算複雑度のクラスP (complexity class P)とは、多項式時間で解ける問題の集合である。 計算複雑度のクラスNP (complexity class NP)とは、多項式時間で検証可能な問題の集合である。 問題を解くより検証の方が簡単なので、 ま…

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

概要 プログラミング言語やUDF機能を提供するシステムにおいて関数が持っていると嬉しい性質として以下の2つがある。 関数の返す値は、関数の引数に与えた値だけに依存して決まる（参照透過性がある）。 関数は、値を返す以外の作用（副作用）を行わない（副…

トライ木（Trie）というデータ構造がある。トライ木についてはWikipedia (ja)、Wikipedia (en)を参照。

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さんが詳しく書いているので引っ掛かったところだけメ…

作ってみた