前提

MVCCはPhil BernsteinとPapadimitriouの２者の貢献が大きい。Weikum本のMVCCもこの本の引用が多く含まれる
特にMVCCを理解するにはPapadimitriouの本書を避けて通れない(多分)
今回は本書全体で使う概念の定義などがメイン
最初から~p8のSchedulesの手前まで読みました。
本は価格が高騰していますが、入手できなくても来ると何らかの手当がある!?

https://t.co/3T7whzBZVs
本日開催です。本が世界レベルで高騰してしまったので（たぶん、この勉強会のせい。マーケット狭すぎ・・）手に入ってないひとにも問題がないようになんらか手当をする予定です。
— 御徒町＠MultiVersionConcurrentClimber(MVCC) (@okachimachiorz1) April 24, 2019

用語の定義等

entity

本書ではデータベースが扱うデータの定義をページでもオブジェクトでもなく、entityを採用する。

A database represents a part of the world, and this representation is done in terms of a complex data structure. This data structure cnsists of elementary parts called entities in this book ( any subdivision of the data structure into entities is relevant). (p2 The Problem of Concurrencyより抜粋)

一般的なDB用語でいうところのentityと若干違うので注意。

加算無限な集合
- ただしある瞬間においては有限の集合になる
不可分かつ重複がない
単一の操作でアクセス(read,write)される
entityの更新には副作用がない(更新対象外のentityに影響を与えない)

read

アプリ側の変数にentityの現在の値を割り当てること

assign the currenct value of the entitiy to a program variable.

write

アプリ側で計算した値にentityの値を変えること

change the current value of the entity to a value previously computed by the program.(p5)

transaction

プログラムの実行の結果から作成される一連のreadとwriteのシーケンスのこと。

A transaction is a sequence of database steps resulting from the execution of a program.(p5)

transactionは制御構文(if,for)を持たない
database step間での計算の整合性なども気にしない。
- セマンティックスを扱わない。

state

entitiyへの値の割当のこと

A state is an assignment of values to the entities.(p2 The Problem of Concurrency)

integrity constraint

実世界のデータ整合性のこと。本書では預金額がマイナス以下になったり、飛行機の乗客席以上の予約を受け入れているような状態をDBに保持しないことを例に上げて説明されている。

Not all possible combinations fo value of entities represent a legal state of the world.For example...(略) Such real-world restriction are called the integrity constraints of the database.

consistent

データベースのstateは各entityに割当可能な値の集合D(domain)の直積の内どれかにになる。
integrity constraint C はドメインの直積の部分集合になる。
データベースのstateがC内の要素と一致する時、consistentであるという

interpretation(Herbrand Semantics)

An interpretation of A is a pair I = (D,F)

F= {fa: a is a step of A and ACTION(a) W}

以前に読んだentityのドメインの直積から、write対象のエンティティのドメインへの写像をInterpretationと定義している。

これがWriteのセマンティックスであり、Herbrand Semanticsの厳密な定義であるらしい。

In other words, it fills in the missing semantics of the transaction.(p6)

classicalなconncurrency controlとの違い

classicalなconncurency controlは以下の目標があった

リソース利用や並列性を高める
p同士の連携(interaction)の調停
resouce(printer,memory,processors)にrobustnessがある

databaseのconncurency control(transaction)

isolateして動く(interactionはない)
robustnessがない。よりdelicateにする必要がある
- 失敗時は不整合データの伝搬などが起こる可能性がある。

議論

DBのほうがOSより難しい的な感じの論調になっている
FS(ファイルシステム)はDB寄り
FSはメタデータが壊れると致命的
最近のFSはWALなどを持っている

他

enumerable setとcounterble setの違いは?

<要加筆>

hidden restrictions と Transaction chopping

T1とT2に"hidden restrictions"な前後関係があった場合、まとめて一つのトランザクションとしなければならない。

A transaction is a unit of consistency, a grouping together of several database steps, the combined execution of which is known to preserve the integrity constraints. A consequence is that threre can be no "hidden restrictions" on inter-transaction behavior.for example , if correctness requires that steps from "two transactions are executed in some predefined order, then these "two transactions" are in fact a single transaction.

最悪のケースとして1トランザクションになる恐れがあるのではないか？という議論があった。
トランザクションはコミットのアボートや単位だが、その粒度が混ざるのはどうなのか？
トランザクションになってしまうようなrestrictionがある場合は、1トランザクションにならざるを得ない、と思う。
今回はスケジューラの話が難しくなることを防止するためにこのような定義をしているだけなのではないか。
トランザクションを細かくできる話もある。(このとき、hidden restrictionが許されるのかは私にはわからない。)Transaction choppingという

Transaction Chopping Weikum本に書かれているTransaction Chopping

Assume that there are n transaction program that can execute within some give interval, leading to n possibly concurrent transaction executions. if a program can gbe invoked multiple times within the considered interval, we treat it as if there were two differenct programs. we futher assume that each program consists of a straight-line sequence of SQL statements with parameterless where clauses.Decomposing , or Chopping , atransaction programamounts to changing the program as follows:

Definition 8.8 Transaction Chopping

Let ti be a transaction program. A chopping of ti is a decomposition of ti into ordered pieces ti1 ... tik(k >= 1, most often k >=2) such that every database operation invoked by ti is contained in exactly one piece, and the order of operation invocations is preseved.