Serializability
具体的には，並列/並行実行した際に問題がないかという特性を意味する．
> When transactions execute concurrently, the interleaved execution of their reads and writes by the DBS can produce undesirable results.
> Concurrency Control is the activity of avoiding such undesirable results.
> Specifically, the goal of concurrency control is to produce an execution that has the same effect as a serial(noninterleaved) one. Such executions are called Serializable. すなわち，「並列/並行実行しなかった際と同じであるか」ということ．
複数のデータをアトミックに操作できる，というメモリモデルを考えたときの，メモリ一貫性を考えればよい．
correct関数
では，「並列/並行実行したときと同じか」を判定する，ということをする．
具体的には，まず「直列実行と同じ」を判定する関数$ correctを定義する．
あるデータベースの実行履歴(Historyという)を$ Hとして，$ correct(H)がtrueならHは直列化可能性を満たす． つまり，Serializableである，というのは，あるデータベースの全ての実行履歴が$ correct(H)でtrueを返すという意味だ，と厳密に定義する． ここまでは当たり前で，重要なのは$ correct関数とは具体的に何か，ということだ．
実は$ correct関数は複数あり，分類が細かくある．
以下が分類．使うcorrect関数によって○○ Serializability(○○SR)と呼ばれる．
https://gyazo.com/8153a93d9233dd30f4dfab64969aefb8
この図は空間の広さを示していて，包含関係があるように見える．以下でそれを説明する．
また，($ H)は有限の命令の全順序となる．
すなわち，命令数を$ nとすると$ nPn = n!の組み合わせのHが存在しうる．
このうち，どれだけの$ Hを$ correctとできるか，というのが上図の空間の広さである．
$ Serialつまり単純に全トランザクションを直列にシングルスレッド上で実行した場合が最も実行パターンは少ない．
いくつか並列実行したトランザクションが混ざっていると，より広いSerializabilityとなる．
さて，あるHistory $ Hが，$ correctであるかを検証する方法はわかった．
が，当然，$ n!回も$ correct関数を実行するのはあまりにもしんどい．
さらに，correct関数も複数あるので，correct関数の数をkとすると，最悪計算量は$ O(k(n!))となる．
そこまでやって得られた「直列化可能性を満たす」スケジュール$ Hが「Serialでした」となったら，最初からシングルスレッドで実行していればよかったということになる．
そこで，「このプロトコル/アルゴリズムに従えば必ず生成されたHistoryはSerializabilityを満たす」というアルゴリズムを作れば，計算量を削減できる．