アプリケーションに対するゼロ知識モデルにおける同時実行制御のトレードオフ
1行で
アプリケーションプログラムに対する知識（前提）をスケジューラが持たない場合、アプリケーション（複数）が発行する各トランザクションを、直列化可能なスケジュールで並行にかつ常に成功裡に実行・完了させることはできない。
<追記 2020-04-29>反例がありました。後日まとめます</追記>
1 1行の言い換え
以下の4つの性質のうち、最大3つまでしか同時に満たせない、という主張。
もしくは以下の3つの性質のうち、最大2つまでしか同時に満たせないという主張。
- 失敗を引き起こさない直列化可能スケジューリング
- トランザクションの実行の並行性
- アプリケーションに対するゼロ知識
2 用語
2.1 アプリケーション、トランザクション、データベースステップ
アプリケーション（アプリケーションプログラム）はデータベースを操作しようとする主体であり、アプリケーションはデータベースに対して、データベースを操作するための命令列（命令のシーケンス）を発行する。
この各命令を データベースステップ（database step） と呼ぶ。モデルによるが、例えばread や write などの操作の種別と対象となるデーベースの要素の識別子のペアがデータベースステップである。
あるアプリケーションが発行する一連のデータベースステップの列を トランザクション（transaction） と呼ぶ。
2.2 トランザクションの直列実行および並列実行
複数のトランザクションを1つずつ実行すること、あるトランザクションが開始して完了するあいだ別のトランザクションを実行させないような実行のことをトランザクションの 直列実行（serial execution） と呼ぶ。
対して、あるトランザクションが実行中でも別のトランザクションが開始・実行できることをトランザクションの 並列実行（parallel execution） と呼ぶ。並列実行では異なるトランザクションのデータベースステップがインターリーブする。
2.3 スケジュール、スケジューラ、スケジューリング
複数のアプリケーションが発行するトランザクション内の各データベースステップは、実際にはある順序でデータベースに適用される*1。
データベースステップの順序を決めることを スケジューリング（scheduling） と呼び、その順序における（複数のトランザクションからなる）データベースステップの列を スケジュール（schedule） 、もしくは出力スケジュールと呼ぶ。
並行にやってくる複数のトランザクションのデータベースステップの適用順序を決定するのが スケジューラ（scheduler） である。スケジューラはすべてのトランザクションのデータベースステップを受け取りスケジュールを出力する。
補足
スケジューラはDBMSの1つのコンポーネントに過ぎない。
一般のDBMSにある、制約違反を検出する機構などはスケジューラの範囲外であり、スケジューラにとってはアプリケーション（アプリケーションロジック）に属する扱いである。
2.4 直列スケジュール、直列化可能、直列化失敗、アボート、失敗回避性、成功裡に完了する
複数のトランザクションをある順序（全順序）で、１つずつ順に実行した場合のスケジュール（トランザクション間のインターリーブがないスケジュール）を 直列スケジュール（serial schedule） と呼ぶ。
スケジューラが生成する（実際の）スケジュールが、同じトランザクション群から構成される、ある直列スケジュールと何らかの観点で等価である場合、そのスケジュールは、実際には直列に実行されていないが、 直列化可能（serializable） であるという。
直列化可能なスケジュールだけを生成しようとするスケジューラが、すでに出力してしまった（出力スケジュール内の）データベースステップをなかったことにしない限りは、直列化可能なスケジュールが存在しえない状況に陥ってしまうことがある*2。
このとき、いくつかのトランザクションを失敗させることで、出力済みの（失敗させたトランザクション以外の）データベースステップを含めて直列化可能な状態を維持させようとする。この失敗を 直列化失敗（serialization failure） と呼ぶ。
失敗させられたトランザクションの実行はなかったことになる。これをトランザクションの アボート（abort） と呼ぶ。
トランザクションがアプリケーションの意思によらず失敗しないことを、本ポストでは 失敗回避性（failure avoidance） と呼ぶことにする。
ここで失敗は直列化失敗だけを考え、データベース状態の制約違反による失敗などは考えない*3。
トランザクションがアボートされず完了することを、成功裡に完了すると表現する*4。
2.5 アプリケーションに対するゼロ知識
トランザクションを発行するアプリケーションに対する何の知識も持たないこと（何の前提も置かないこと）を本ポストでは、アプリケーションに対する ゼロ知識（zero-knowledge） と呼ぶことにする*5。
例えば以下は、アプリケーションについての知識（前提）を持っているとみなす。
- アプリケーションプログラムの内容（コード、疑似コード、ロジック等）を事前に知っている。
- 接続されるアプリケーションは固定で、勝手に新しいアプリケーションが接続することはないと知っている（前提とする）。
- アプリケーションが読込み操作しか発行しないこと（read-only トランザクションであること）を知っている（前提とする）。
- アプリケーションプログラムには条件分岐がないことを知っている（前提とする）。
- アプリケーションが発行する読込命令に同じ値を返せば、アプリケーションは常に同じ振舞いをすると知っている（前提とする）。
3 主張の解説
4つの条件のうち、同時に3つしか同時に満たせないという主張であるので、それぞれ1つずつあきらめると以下となる。
- スケジュールの直列化可能性をあきらめる
アプリケーションに対する知識なしに、複数のトランザクションをアボートせずに並列に実行すると、直列化可能でないスケジュールが生成される。直列化可能なスケジュールであることもあるが保証はされない。 - トランザクションの実行の並行性をあきらめる
アプリケーションに対する知識がなくても、複数のトランザクションを直列に実行すれば、アボートせずとも直列化可能なスケジュールが得られる。 - トランザクションの実行の失敗回避性をあきらめる
アプリケーションに対する知識がなくとも複数のトランザクションを直列化可能なスケジュールで並列に実行できるが、トランザクションはアボートすることがある。 - アプリケーションに対するゼロ知識をあきらめる
複数のトランザクションを直列化可能なスケジュールで並列に、かつアボートせずに実行するためにはアプリケーションの知識が必要である。
1の「直列化可能性をあきらめる」という選択は、SQLでいえば低い分離レベルを選択することに相当する*6。
2の「並列実行をあきらめる」は直列に実行するのだからどんなアプリケーションであっても直列化可能なのは当たり前ではあるが、正しくかつ失敗なしに結果が得られる点では貴重である*7。
3の「失敗回避性をあきらめる（アボートを許容する）」は、高い分離レベル（例えばSERIALIZABLE ）の選択に相当する。つまり SERIALIZABLE ではアボートする可能性をゼロにできない。
4の「アプリケーションに対するゼロ知識をあきらめる（知識を持つようにする）」という選択は、マルチスレッドプログラムなどの通常（？）の並列処理に相当する。
マルチスレッドプログラミングでは通常、インタラクションするすべてのスレッドのロジックを互いに知ったうえで作られている、完全知識モデルである。
完全な知識があれば、並列に実行するスケジューリング（が存在するならそれ）を常に生成することができる（はずである）。
データベースの同時実行制御は、上記のうちの3を選択したモデルである。
「直列化可能性をあきらめる」「並列性をあきらめる」を論外とすれば、このモデルは「ゼロ知識をあきらめる（完全知識モデル）」モデルの対となるモデルである。
つまり、「アプリケーションに対する知識を必要としないがアボートを許容する」モデルと「常に成功するがアプリケーションに対する知識を必要とする」モデルという2つの大きな選択が両極として存在する。
| Database Concurrency Control | Parallel Programming | |
|---|---|---|
| Possibility of transaction abort | can be aborted | no abort |
| The need for knowledge of application | zero-knowledge | perfect-knowledge |
直列化可能性に基づく正しさ、および並行性も加えてプロジェクトマネジメントのトライアングルをまねると、以下のようなイメージになる（主語が大きい）。
4 背景や参考文献など
後述の本を読んだ限りでは、DBMSを作るベンダーとアプリケーションを作るユーザ企業が異なること、および複数のベンダーが作るDBMSと複数のユーザ企業の組合せが固定でないことなどから、DBMSがアプリケーションに前提を置くことができない、というあたりに、データベースの同時実行制御に関する要求があったようです。
一方で、アプリケーションに対する完全な知識があれば失敗しないスケジューリングが可能であることはおそらく自明であったので、それに対抗する（反対の極の）ものとしてデータベースの同時実行制御理論のモデル（ゼロ知識モデル）を選択しているようにも思われました（主観です）。
なので、「データベースではアプリケーションに対する知識を要求してはいけない」というわけではなく、実用においては、この両極端の理論のなかのちょうどよい選択を見つけて実装しろ、ということだと思います。
「SERIALIZABLEならアボートを許容せざるを得ない」 は悲観的な結論に思えますが、そうではなくて「SERIALIZABLE であってもアプリケーションの知識があればアボートを回避できる、もしくは確率を減らせる」のであって、そのための落としどころとしてどんな知識が必要なのかを探っていく必要があるのではと思いました。
このポストにおけるほとんどの用語の定義は以下の本 Christos Papadimitriou, The Theory of Database Concurrency Control, 1986. から持ってきています。
Theory of Database Concurrency Control
- 作者:Papadimitriou, Christos
- 発売日: 1986/07/01
- メディア: ハードカバー
（通称？はpapa本） 実際の書影はこちら。
このポストの内容自体は、この本（のChapter 2までの間）には直接は書かれていませんが、著者やデータベースの同時実行制御の理論を研究している人にとっては（理論の動機からして）自明であってあえて書く必要がなかったのかもしれません。
が私が簡単に確認した範囲では見つからなかったのでまとめてみました。
この主張の証明はいつかまとめるかもしれません（証明できたとは言っていない）。
それよりは、アプリケーションの知識によってアボートを回避できる例を集めてまとめたいです。
あと、私はアプリケーションを開発する側ではないので、アプリケーションにとってアボートがどれくらい嫌なものなのか、もしくはアボートしたくないがために分離レベルを下げている実態があるのか、といった感覚が知りたいです。
*1:適用自体も並行に行われているかもしれないがそれと同じとみなせる順序
*2:先行するがこの状況に陥ることが避けられないというのが本ポストの主題である
*3:直列化可能であれば、データベース状態の制約違反はアプリケーション側でチェックできるはずである
*4:これ以降出てこないかも
*5:暗号の分野でゼロ知識証明とよぶ問題があるようで、そこから拝借しました。検索ノイズになったらごめんなさい
*6:READ COMMITTED なら、アボートさせられることなくスケジューリング可能だと思うが特に確認していない
*7:ちなみにこのようなスケジュールを生成するスケジューラのことを、後述のpapa本では trivial scheduler と呼んでいた
