ぱと隊長日誌

ブログ運用もエンジニアとしての生き方も模索中

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

勉強会について

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

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

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

Theory of Database Concurrency Control

Theory of Database Concurrency Control

今回は以下の本も参照しています。

組合せ最適化 第2版 (理論とアルゴリズム)

組合せ最適化 第2版 (理論とアルゴリズム)

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

APPENDIX

Algorithms and Complexity

"instance" の定義は以下を参照のこと。

定義 15.7 決定問題 (decision problem) は、多項式時間で決定できる言語 X とその部分集合 Y ⊆ X の対 Ρ = (X, Y) として定義される。X の要素を Ρ のインスタンス (instance) という。Y の要素が yes-インスタンス (yes-instance) であり、X\Y の要素が no-インスタンス (no-instance) である。
組合せ最適化 第2版 理論とアルゴリズム 15.3 PとNP

directed graph を adjacency list (隣接リスト)で表現し、決定性チューリングマシンによって非循環であるかを判定できるかを考えていく。

Figure 1.3(a) を adjacency list で表現した例が以下に示されている。
v1(v2,v4);v2(v3);v3(v4);v4(v2)


[memo]
隣接リスト - Wikipedia

"Instances are represented as strings over some alphabet." は以下の説明に対応する。

以下では、入力は2進文字列として一定の効率的な符号化がなされているものと仮定する。もちろん、ときにはこのアルファベットに別のシンボルを加えて拡張することもある。
組合せ最適化 第2版 理論とアルゴリズム 15.3 PとNP

directed graph でインプットの無い node を削除していき、node が全て無くなれば非循環であり、削除できる node が見つからなければ循環がある。
このアルゴリズムは Proposition 1.1 と対応している。

Proposition 1.1: A directed graph is acyclic if and only if its vertices can be ordered so that for all arcs the tail comes before the head.


[memo]
このアルゴリズムを Figure 1.3. の adjacency list に適用します。
adjacency list のいずれの () にも含まれていない node を削除していきます。

Figure 1.3(a)
v1(v2,v4);v2(v3);v3(v4);v4(v2);
v2(v3);v3(v4);v4(v2);
⇒これ以上は削除できないので循環有りと判定されます。

Figure 1.3(b)
v1(v2,v4);v2(v3,v4);v3(v4);
v2(v3,v4);v3(v4);
v3(v4);
⇒全て削除できたので循環無しと判定されます。



NP-Completeness


[memo]
比較的信頼度が高いと思われるWikipedia及び大学のサイトで公開されているNP完全に関した資料を集めました。

言葉の定義はWikipediaで確認できます。

NP (Non-deterministic Polynomial time)
NP - Wikipedia

非決定性チューリングマシン (Non-deterministic Turing machine, NTM)
非決定性チューリングマシン - Wikipedia

NP困難 (NP-hard)
NP困難 - Wikipedia

NP完全問題 (NP-complete problem)
NP完全問題 - Wikipedia

充足可能性問題 (satisfiability problem, SAT)
充足可能性問題 - Wikipedia

Wikipediaの説明の補足として以下の資料が参考になります。
※所属は資料に記載の時点となります。

アルゴリズム入門(7)(問題の複雑さ)(京都大学・宮崎 修一)
http://www.lab2.kuis.kyoto-u.ac.jp/~shuichi/algintro/alg-7s.pdf

P, NP, NP 困難, NP 完全(東京大学・田浦 健次朗)
https://www.eidos.ic.i.u-tokyo.ac.jp/~tau/lecture/computer_software/gen/slides2/10-np-complete.pdf

計算複雑性にまつわる 10 の誤解(電気通信大学・岡本 吉央)
http://dopal.cs.uec.ac.jp/okamotoy/PDF/2013/complexity10confusions.pdf



The problem with these two algorithms is that they are too inefficient; both require a number of steps that is an exponential function of the length of the input.

inefficient = exponential と対応している。

NP complete の問題でも特殊なケースに限定し、2SATの問題にする(2SATは NP complete でない)、という手もある。

NP complete といえれば、現状で効率の良いアルゴリズムが見つかっていないともいえる。つまり、問題に真正面から取り組むのではなく、別の道を探すための理由となり得る。

2.1 INTRODUCTION

Certainly that any serial schedule is correct

順に実行したものが correct だとしている。

A schedule is correct if it is equivalent to a serial schedule.

では順に実行したスケジュールと何をもって比較して正しいと判断するのか?

2.2 FINAL-STATE SERIALIZABILITY

Definition 2.1: Let s and s' be schedules. We say that s and s' are final-state equivalent if
(a) They involve the same transactions, and
(b) For each interpretation I = {(D,Fi)} of s (which is at the same time an interpretation of s' by (a) above) and all choices X ∈ Πx∈EDx of initial values for each entity in E we have s(I,X) = s'(I,X).

(a) s と s' でオペレーションが同じ。
(b) D は domain。F は function。X は初期値。I は P8 Definition 1.3 を参照のこと。


[memo]

Definition 1.3 はエルブラン・セマンティクスに対応している。
step a が R(x) であれば、a の直前に書かれた W(x) の ws(I,X) と等しい。
write がなければ最初の初期値を読む。
write がそれまでの read に依存している。

Database Concurrency Control Papadimitriou 読書会 第2回 議論メモ - ぱと隊長日誌


"augmented schedule of s, denoted ŝ" とはスケジュール s にトランザクション A0 と A を追加したものだ。A0 は各エンティティの初期値を設定し、A は最後に各エンティティを read する。

MV だと r は単一バージョンのみ read 可能、もしくは全てのバージョンを read 可能と考えることができる。ここで全てのバージョンを read 可能とすると、MV では成立するが 1V では破綻する。この互換性の無さが悩ましい。

Hadoop で実現しているような大きいレイテンシーでの理論はあるが、数百コアの Rack Scale Architecture のような低レンテンシーで使える理論がない。


[memo]
RSA(Rack-Scale-Architecture) - 急がば回れ、選ぶなら近道


(a) If ai and aj are steps in the same transaction with i < j, ACTION(ai) = R, and ACTION(aj) = W, then we add the arc(ai,aj) to A. These arcs denote dependencies within the same transaction.
(b) IF ai and aj are steps in different transactions, with ACTION(ai) = W, ACTION(bj) = R, ENTITY(ai) = ENTITY(bj), and ai is the last step in ŝ before bj which writes ENTITY(ai), then we add the arc(ai,bj) to A. These arcs denote dependencies across transactions.

(a) 同一TXの write はそれ以前の read に依存しているので、read → write に線を引く。
(b) 異なるTX間では最後に write されたものを read するため、write → read に線を引く。

Finally, from D(s) we construct the directed graph D1(s) by deleting all nodes of D(s) from which no step of A can be reached.

D(s) は全て含む。D1(s) は最後 (A) まで到達しなかったノードを除く。

TX理論では write がそれ以前の read に依存するとしているが、実際には依存が無ければそれを分けて考えることができるはず。例えば同じTXで w(x) が r(x) のみに依存し、w(y) が r(y) のみに依存しているとすれば、この2つは別の処理をしているとみなすことができる。
(1) r(x) → w(x)
(2) r(y) → w(y)
だが、これを2つに分けて理論で扱うのは難しいので、
r(x)r(y)w(x)w(y)
のように1つのTXでまとめているのではないか?

オンラインのDBにおいて、FINALとはいつなのか?SILOであれば40msの間隔でFINALを定義できる。

関連記事

The Theory of Database Concurrency Control - nikezono
中園さんの読書メモ。