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

勉強会について

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

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

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

Theory of Database Concurrency Control

[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 ではない。

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

---

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

---

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

関連記事

papa本第16回参加メモ - 誰にも見えないブログ
@yuyabu2 さんの読書会ノート。

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

勉強会について

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

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

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

Theory of Database Concurrency Control

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

2.6 CONFLICT SERIALIZABILITY

this notion is free from negative complexity results such as those in the previous section.

ここでの "negative complexity" とは NP-complete のこと。

conflict if the following is true: Both steps read or write the same entity, and not both are read steps.

conflict とは異なるトランザクションのステップが同じエンティティに対して以下の条件を全て満たすである。

• read or write している。
• 両方とも read ではない。

---

[memo]
Example 2.5
R₁(y) R₃(w) R₂(y) W₁(y) W₁(x) W₂(x) W₂(z) W₃(x)
スケジュール A₂A₁A₃ と view equivalent であることを確認します。
A₁, A₂ は A₂ → A₁ となる必要があります。オリジナルのスケジュールでは A₁, A₂ 共に y の初期値を読んでいますが、A₁ → A₂ だと A₁ が y に値を書き込み、A₂ がそれを読んでしまうためです。
また、A₃ はスケジュールで最後になる必要があります。A₁, A₂, A₃ 共に x へ値を書き込んでいますが、VSR が FSR も満たす必要があることを考えると、オリジナルのスケジュールで最後に x へ書き込んだ A₃ が最後になる必要があります。
よって、A₂A₁A₃ が唯一 view equivalent な serial schedule とわかります。

---

MVで全てのバージョンを保持できるとすれば、「最終状態」が複数ありうると考えるのが妥当なのではないか。今の理論は「最終状態」が一つに決まる前提を置いているのが気になる。

MVSR ではTXの順序が重要となるケースを考慮していない。
同じTX群を同じプロトコルに投入したとき、deterministic であれば同じ結果になる。ただ、現実の世界では物理レベルの微妙な latency を無視することができず、異なる結果となることがある。
それでもTXの順序を守る必要があるなら、ミドルかアプリがやるしかない。だが、それはパフォーマンスを落とすことになる。
そもそも、TXの順序が重要であればDBを使う必要があるのかを考える必要がある。突き詰めればファイルでも良いのではないか？
例として株取引がある。これはDBのTXではなく、他に定められたプロトコルで約定が決まる。となると、必ずしもTXの順序を守る必要があるとは言えない。

DBは「よしなにやってくれる」とみんなが思っているが、「よしな」とは何かをちゃんと理解せずに使っている。

Oracleが「Snapshot Isolation は serializable」と言ってしまったがために未だ誤解されている。

赤い会社「完全にserializableですよ。」
その他大勢「いや、SIではfull-serializableにはならないし。」
赤い会社「いや、ほぼ同じだし。」
その他大勢「なんだよ、ほぼ同じってww」
赤い会社「だからこのベンチマーク（TPC-C）でちゃんとanomalyなしだし」
その他大勢「いやだから、そのベンチマークがそもそもだな・・・」
あれやこれや・・・
（以上、脚色なし）

Making Snapshot Isolation Serializable 再考 - 急がば回れ、選ぶなら近道

We can test in O(n²) time whether a schedule is conflict serializable.

O(n²) の n は node、つまりトランザクションの数だ。cycle を発見するために最悪 O(n²) かかるということだ。

Conflicts and Commutativity

reflexive-transitive closure は「反射推移閉包」と訳される。
reflexive closure（反射閉包）かつ transitive closure（推移閉包）なもの。

関係Rの反射推移閉包とは、Rを含み反射性と推移性の両者を満たす最小の関係のことです。

ソフトウェアの基礎

∼* を ∼ の reflexive-transitive closure とする。これは non-conflicting な step を交換したということだ。ここでの交換は step order を前提としている。

関連記事

papa本第15回参加メモ - 誰にも見えないブログ
@yuyabu2 さんの読書会ノート。

JRきっぷの発売日と学割利用の注意点

JRのきっぷ（乗車券）を購入しようとしてはまったポイントを記録しておきます。

きっぷの発売は原則として乗車当日のみ

原則としてお乗りになる日から有効な乗車券を発売します。指定券と同時にお求めの場合は1カ月前から発売します。

きっぷの発売日：JR東日本

これは原則として乗車券を乗車当日に発売するということです。乗車日を指定して事前に購入できるという意味ではありません。ただし、指定券と同時に購入するのであれば、1カ月前から乗車券も購入可能です。

私の場合、「お乗りになる日から有効な乗車券」を誤解し、「乗りたい日から有効な乗車券」を事前に購入可能と思い込んでしまっていました。指定券と同時購入なら1か月前から、という説明に違和感を感じればよかったのですが…。

学生割引のきっぷは代理で購入可能

学生割引のきっぷ（乗車券）を購入するには、あらかじめ学校で学割証（学生・生徒旅客運賃割引証）の発行を受けてください。発行された学割証に必要事項を記入し、駅や旅行会社の窓口でお買い求めの際に提出してください。
学生割引のきっぷをお買い求めいただく際には学生証を呈示いただく必要はございません。ご家族など、代理の方でもお買い求めいただけます。
一方、学生割引のきっぷをご利用の際には、必ず学生証を携帯してください。

学生割引のきっぷを購入するには、どうすればよいですか。：JRおでかけネット

JR西日本のヘルプページですが、JR東日本の駅でも同様の説明を受けました。

JR各社のヘルプページに学生割引の説明はあるのですが、代理購入可能であることや、きっぷ利用の際には学生証が必要なことなどを説明しているページは他に見当たらなかったので、参考になさってください。

なお、学生割引は適用対象に条件があることもご注意ください。

学生割引は、片道の営業キロが100キロを超える乗車券に適用され、運賃が２割引となります。片道の営業キロが600キロを超える往復乗車券の場合は、往復割引と学生割引を重複して適用いたします。
特急券・グリーン券・寝台券などは、学生割引の対象となりません。

学生割引はどのようなきっぷに適用されますか。：JRおでかけネット