Database Concurrency Control Papadimitriou 読書会第16回議論メモ

勉強会について

Database Concurrency Control Papadimitriou 読会第16回 - connpass の議論メモです。

自分のメモをベースにまとめています。発言の聞き間違い、解釈違いの可能性があることをご了承ください。

特記の無い引用は本で議論した箇所を示しています。

Theory of Database Concurrency Control

作者:Christos Papadimitriou
出版社/メーカー: Computer Science Pr
発売日: 1986/07/01
メディア: ハードカバー

[memo]は私のメモです。勉強会で議論された内容ではないことにご注意ください。

2.6 CONFLICT SERIALIZABILITY

Conflicts and Commutativity

s ∼* s' if s can be transformed to s' via zero or more switchings of non-conflicting steps.

Proof では "Among the pairs of steps which are out of order in s', choose a pair of steps which are consecutive in s'." としており、交換するステップは consecutive であることが必要なはず。Theorem 2.9 でも省略せずに記載すべきだ。

Theorem 2.9 Proof

Let k be the number of pairs of steps of the two schedules which occur in different order in s than in s'.

k = 0 は s と s' が同じとき。
k = 1 は隣り合うステップが1つだけひっくり返ったとき（例：123 → 132）。

conflict を定義すれば conflict serializable か否かを判定できる。read / write で考える必要がない。
これにより、mono-version なのか multi-version なのかを意識する必要がなくなる。

Example 2.6 のスケジュールにおける "c" は "c" であり、commit の意味ではない。

[memo]
Example 2.6 について。
conflict はステップの交換ができない。なので、オリジナルのスケジュールのオーダーを保つことになる。
これを踏まえ、conflict をスケジュールのオーダーで記述すると以下の結果となる。
{b1, a2}, {a2, c1}, {b1, c1}, {c4, b3}
これをグラフにすると figure 2.11 となる。

PostgreSQLのストアドプロシージャはループがあったとしても1つのTXで処理する。ただ、ループ内の処理がパラレルに実行可能であれば、パラレルに実行したい。これが今は実現できない。

Definition 2.7 の "set of transactions" の "set" は部分集合のこと。

monotonic であれば、一部のTXを抜いても conflict serializable といえるが、view が変わることになるので view serializable とは言えない。
view serializable で monotonic なケースを考えると、一部のTXを抜き出せばそれまでの view が壊れる。だが、残されたTXだけで考えると view serializable ではあるし、monotonic でもある。

[memo]

view serializability is not a monotonic property.

これは view serializable でも monotonic なときはあるが（例：conflict serializable）、必ずしもそうとは言えない、と言いたいのではないか。

Not only is conflict serializability a monotonic property and view serializability is not, but the set of conflict serializable schedules is the largest monotonic subset of view serializability.

CSR でない VSR は monotonic ではない。

f:id:pato_taityo:20191214005159p:plain

monotonic であれば abort の処理が楽になる。

[memo]
以前に monotone について調べてまとめた記事があります。
SerializabilityとMonotonicityとRigorousnessの関係 - ぱと隊長日誌

スケジュールの "c" を commit ではなく、「TXのコマンドがこれ以降無い（最後である）」という pre-commit として扱うことも出来るのではないか。つまり、pre-commit は commit する意思を示すもので commit できることを確約するものではない。依存関係を表すものとして扱わないということだ。