整理やtexの変換が終わってないが、ここはそういう雑なものを置いておく場所なのでとりあえず投稿。 読んだ範囲p103 "Exclusive and Shared Locks"~ 排他ロックと共有ロック 2つのトランザクションが同時にロック(片方が排他)を獲得していないスケジュールは…

p96 4.2 Lockingからp103 Exclusive and Shared Lockの手前まで。 次回はp103 Exclusive~から connpass.com Schedulerの3つのモード(個人的な復習) Dynamic mode 初期状態で何の情報も持たない。 Transacionのstepが順次到着するが、そのstepの情報のみ(操作…

Database Concurrency Control Papadimitriou 読会(32回)に参加 p86からp90まで読んだ。 次回はp90「Definition 3.4~」から The Complexity of Reliability(続き) is reliable if and only if F is true のonly if direction reliable → F is true 対偶(F is…

主にreliability保証がPSPACE完全であることを示すためにQSATをreliability gameに帰着させる手順の解説を読んだ。QSATの用語とreliability gameの用語とgadgetの用語が混ざっている上に図がほとんどないのでかなり分かりにくい。加えて私はgadgetの理解がい…

papa本27 p76 「Our proof~」から読んだ 次回はp80「The Reduction」から 久々に全然わからなかった。 connpass.com gadget続き Reliabilityの計算量がPSPACEになることを示そうとしている。 何を問題意識に議論しているのか全くわからなかった。 時系列でst…

connpass.com p74「The Gadget」から読んだ。 次回はp76 「Our proof~」から PSPACE polynnomial amounnt of space で解決できる問題 P ⊂ NP ⊂ PSPACE 復習 P:任意の問題を多項式時間で解ける NP:certificate付きのyes-setを多項式時間で検証できる Gadget t…

読書会に最近出てれないので自習。 p64「Conflict Multiversion Serializability」~p65「Proposition 3.2」の手前まで読んだ。次回はp65「Proposition 3.2」から Conflict Multiversion Serializability multiversion view serializability の検査コストはNP…

1H 読んだ範囲p69~71｡ note:※historyはscheduleの内､terminate operationを含んでいるものであるから､書中でhistory and scheduleと書いてあるところは本ブログでは特に断り無くscheduleのみの表記とする｡ (partial order)historyの性質 a:含まれるトランザ…

時間1H 範囲p65~p70 schedules:transactionの終了情報を含む(commit,abort operation) commitとabortはdata operation (read write)と区別するためにtermination operationと呼称する deterministicなscheduleをhistoryと呼ぶ termination operationを含んだ…

加筆中｡ p59「A schedule together ~」から「p62 Proposition 3.1 」まで読んだ。 Multiversion(Version funtionまで考慮したschedule)のcorrectnessを定義したり、storage costなどについて学んだ。storageコストは若干不評気味だった。 勉強会開始前にスト…

ついにマルチバージョンに入りました。今回は主にVersion Functionのところで議論が紛糾し、あまり進捗はない(2ページ+α)感じです。今回のVersion FunctionはWeikumの"Transactional Information Systems"などで既に学習している人にとっても取っ付きにくい…

ポスト忘れてました｡1Hくらいで書いたのでまとめきれてません｡ Lemma 2.5 2.7 SPECIAL CASES No Blind Writes Lemma 2.6 Theorem 2.11 The Action Model Theorem 2.12 他 2章の振り返り 英語 p49"Proof"からp56のchapter最後まで読んだ｡きりが悪いのでこのノ…

今日はCSRの定義が3つもあることを知ることができた。雑なので後日結構手を入れてfixするかも。 connpass.com Conflicts and Commutativity(可換を使ったCSRの2つ目の定義) 定理2.9s~*s'が成り立つ ↔︎s とs'がConflict equivalentである 新しい定義を使ったu…

例のトランザクション勉強会。前回までVSR=NP completeの証明に勉強会4回ほど費やしたのち、今回ついにCSR入った connpass.com CSR Conflict Conflict equivalent VSR⊃CSR Theorem 2.8 CSR iff G(s) is asyclic CSRの計算コスト Conflicts and Commutativity…

p38「proof」から p39「Proof of the Lemma」まで読んだ。次回はp40 4行目「Suppose that ...」から これまでの勉強会で一番面白かったです。 毎度適当なメモなんで読むのに適さないですです。 Theory of Database Concurrency Control作者: Christos Papadi…

FSR読み切った! 連絡 次回(7/10)は神林さんが出張なので一回休み 次の回は7/24(詳しくはconnpass要確認) 今回読んだ範囲は p26 2.3 THE CRITIQUE OF FINAL-STATE SERIALIZABILITYから p30 Incorrect Viewsまで 次回は p31 2.4 VIEW SERIALIZABILITYから ノー…