Transactionのinterpretation(herbrand semantics)について
herbrand semanticsのメモです。主にFSRを理解するための準備です。このエントリはChristos Papadimitrioupapa:Theory of Database Concurrency Control(通称papa本)の5~9ページのまとめです。
データベースの世界にはherbrand semanticsというConflictやSerializabilityを考える時に使う便利な道具があります。いつからherbrand semanticsと呼ばれるようになったのかはわかりませんが、papa本ではinterpretationという名前で扱われています。 近年ではトランザクションの教科書にもherbrand semanticsと書かれていることもありますので、本エントリではpapa本からの引用以外はこちらの名前を使います。
weikum本寄りの解説はぱとさんがあげているので、今回はpapa本寄りのメモを書きたいと思います。
Theory of Database Concurrency Control
- 作者: Christos Papadimitriou
- 出版社/メーカー: Computer Science Pr
- 発売日: 1986/07/01
- メディア: ハードカバー
- この商品を含むブログを見る
transactionとreadとwrite
まずはトランザクションの定義から。トランザクションは任意のentityに対するreadとwriteの有限集合。
Difinition 1.1 A transaction A is a finite sequence fo steps A = a_1,a_2...a_n. The steps are assumed to be distinct symbols, and two differencttransactions cannot have steps in common. With each step a_j of A we associate an action ACTION(a_j) ∈ {W,R}, and an entity ENTITY(a_j) ∈ E.
read:対象entityの現在の値をプログラム中の変数へ割当てることを意味する。
If some step a_j reads entity x. This means that a particular program variable t_j in the underlying program is assigned the current value of x in the database: t_j := x.
write:対象entityに対するプログラムで計算した値の割り当てを意味する。
If ACTION(a_j) = W and ENTITY(a_j) = x , then the step write x. By this we mean that x is assigned a value computed by the program, which is potentially a function of all previously read(by the same program) values of entities: x := fj(t_i1,ti_2,...t_ik),where the ip's are all indices smaller than j for which ACTION(a_ip) = R
なおこのwriteで書く値の計算はwrite step以前のすべてのreadを引数にとる関数fとして定義することができる。この関数の厳密な定義がherbrand semanticsになる。
interpretation
条件分岐や繰り返しなどの制御構文を含むアプリ(プログラム)から発行されたdatabaseに対するread/writeのdatabase stepの意味をdatabase側から解釈する。プログラムが発行したdatabase stepのまとまりはtransactionになる。transactionは制御構文を持たないので、アプリとは別の解釈が必要となる。
A transaction, as defined above, is a purely syntactic object, subject to different interpretations. Intuitively, specifying an interpretation of a transaction means fixing a particular application program from which the transaction has originated, disregarding of course any control structure the program may have.
トランザクションの実行はある状態からある状態への写像と解釈する。
An interpretation of A(注:このAは任意のtransactionを指している) is a pair I = (D,F), where D = {D_x,D_y,...} is a set of domains, onefor each entity in E; each domain is a set of values for the corresponding entity. F = {f_a:a is a step of A and Action(a)=W} is a set of functions, one for each write step of A. For each such step a, f_a is a mapping
具体例として1トランザクション前提(1並列)で以下の送金プログラムで説明されている。
program transfer(amt:integer);
entities x,y: integer;
variables temp1,temp2:integer;
begin
temp1 := x;
if temp1 ≧ amt then
begin
x := tmp1 -amt;
temp2 := y;
y := temp2 + amt
end
end.
ローカル変数へのentity代入をread,entityへの値の書き込みをwriteのデータベースステップと考えると上記のプログラムは以下のschedule(Action)を作る。
A = R(x)W(x)R(y)W(y)
この時、各database stepのherbrand semanticsは以下のようになる。
t1:=x x:=f2(t1) t3:=y y:=f4(t1,t3)
f4の関数の内容はf4(t1,t3)=t3+50で、t1は一切使わないが、このt1はherbrand semanticsでは必要とする。
どのパラメータが実際に使われているかという情報はアプリ(DBMSを読み書きするプログラム)の完全な情報がないと分からない。そしてconncurency controlを考える時にアプリのコード全体が把握できるケースは極めて稀*1であるため、writeの前に発行されたreadは全てwriteを表す関数の引数として扱う。
Situations such as this of Example 1.2, in which we have complete information about the program and the value of their parameters, are rare in concurrency control
同じentityへの各database stepは1回まで
オペレーションごとにherbrand semanticsを考えることができそうだが、correctなスケジュールなら1つのentityへの複数回のread,writeは冗長なので、herbrand semanticsを考えるときは同じトランザクション内では
- read/writeは1つのentityに対して1回まで
- writeしたentityの値をreadしない
という前提を置く
It is quite natural-and, it turns out, simplifying-to make the following assumptions about the structure of the transactions.
(a)In a transaction an entity is read at most once, and is written at most once.
(b)In a transaction, no entity is read after it is written.
後述しますが、本来ならあるトランザクションの何番目のステップのfというような表記になるところを上記の前提を置くことで 、あるトランザクションのあるentityに対する操作(f)、またはあるトランザクションの何番目の操作(f)というシンタックスで表現できる。ちなみに、weikum本では前者のシンタックスを採用し、papa本では後者を採用している。*2
Hs(wi(x)) := fix(Hs(ri(y1)),...,Hs(ri(ym))), where the ri(yj), 1 ≤ j ≤ m, represent all read operations of ti that occur in s before wi(x)
weikum本より引用。のiをトランザクションの添え字、xをentityとするシンタックスにしている
Interpretationとshcedule
- トランザクション1つにつき一つのinterpretationがある。
- sheduleは1個以上のトランザクションの集合だから、shedule sのIntrepretationはsに含まれる全てのtransactionの集合になる。
If s is a schedule involving the transactions A_1,...,A_k, then an interpretation I of s is a k-tuple of interpretations I_j = (D,F_j), all with the same choice D of domains for the entities.
scheduleにinterpretationを適応すると、schedule中の任意のdatabase stepをで表現することができる。
Suppose that s is a schedule, I an interpretation, and X an initial state, that is a value for each entity. We say that every database step a of s computes a value a_s(I,X).
また、スケジュールの実行結果、つまり最終状態をs(I,X)という特別なシンタックスで表現する
The final state resulting from the execution of s, denoted s(I,X)
まとめ
- 各entityがとりうる値(domain)の集合をDとしている
- writeの関数fのすべての集合をFとしている。
- 上記二つのペアをinterpretation(herbrand semantics)としている。
- interpretationと初期値Xを使うことでtransaction中の任意のstepを関数で表現できる
Effecitve SQLを読書会で読み終わりました
全16回でした。毎度木村@meijikさんの博識ぶりには驚かされる勉強会でした。
- 作者: John L. Viescas,Douglas J. Steele,Ben G. Clothier,株式会社クイープ
- 出版社/メーカー: 翔泳社
- 発売日: 2017/12/20
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (3件) を見る
プログラマのSQLと比べると、中身が優しかったり、即効性がある情報が多いので、今すぐ役立つSQLテクニックを知りたい人にオススメです。逆にプログラマのためのSQLに出てきたような、長時間みんなで悩みながら「このクエリは何をやっているんだろう...」という難解なSQLは少ない傾向があったので、そういうのが好きな人には向かないかもしれません。
いかに個人的に面白いと思った本書の内容をまとめました。
CROSS JOIN
本書は1章丸ごとCROSS JOINに割いています。(第８章 直積)直積をまる一章説明している本は珍しいのではないでしょうか。気になった人はこの章だけでも通読をおすすめします。
「項目31 GROUP BYは短く保つ」
最近はgroup byに書いていないカラムもselect句に書いても良い 昔のMySQLの話ではない(ややこしい)
一部のDBMSでは、集約に使用されない列をGROUP BYに追加しなければならない。ただい、現在のSQL企画では、そうする必要はなくなっている
SQL/99以降では関数従属性が認識されている。したがって、現在のSQL木各区に準拠するには、実際には~のクエリで十分である
SELECT c.CustomerID, c.CustFirstName, c.CustLastName, c.CustState, MAX(o.OrderDate) AS LastOrderDate, COUNT(o.OrderNumber) AS OrderCount, SUM(o.OrderTotal) AS TotalAmount FROM Customers AS c LEFT JOIN Orders AS o ON c.CustomerID = o.CustomerID GROUP BY c.CustomerID, c.CustFirstName, c.CustLastName, c.CustState;
以下のSQLではCustomersテーブルの主キーCustomerIDで集約しているため、CustomerテーブルのカラムはGroup byに書かなくてもSELECT句に書くことができます。
SELECT c.CustomerID, c.CustFirstName, c.CustLastName, c.CustState, MAX(o.OrderDate) AS LastOrderDate, COUNT(o.OrderNumber) AS OrderCount, SUM(o.OrderTotal) AS TotalAmount FROM Customers AS c LEFT JOIN Orders AS o ON c.CustomerID = o.CustomerID GROUP BY c.CustomerID;
これがSQL99で標準化されているというのはちょっとした驚きでした。がこの本のクエリが全体的にこのGroup byの中を小さく保つ書き方がされていなかったのは少し気になりました。
あまり聞かない単語
挫折結合
LEFT JOINの適用後に右側のテーブルの主キーにnullをwhere句で指定すると、右側のテーブルに対応するデータがない左側のエンティティを絞り込むことができます。
SELECT P.ProductNumber, P.ProductName FROM Products AS P LEFT JOIN Order_Details AS OD ON P.ProductNumber = OD.ProductNumber WHERE OD.ProductNumber IS NULL;
これを挫折結合(frustrated join)というそうです。この単語はこの本で初めてみました。
sargable
出自はIBMのマニュアルのようです。意味としてはWhere句の中がB-tree indexを利用できるような述語になっているか、という意味になります。(そして本書にはSQLをsargableにするテクニックが多数紹介されています)
一般的でない誤字
order by 述語という誤字がよく出てきました。こちらは木村さんが原著を確認したところorder by predicateとなっていた(多分)ので誤訳ではなく、原著からの誤字だと思います。よくwhere文やcase文という間違い(SQLでは正しくはwhere句,case式)は結構みますが、order by述語という言い間違いは初めて見ました。わざわざ「述語」なんて言い方する人は、ある程度語句の使い方には注意しているのではないでしょうか。2019年6月時点で検索してみたら、SQLの文脈だと(order by述語)の使用例はこの本くらいでした。
参考
昔に背伸びして書いた記事です
次回
次回は曽根壮大さんの「失敗から学ぶRDBの正しい歩き方」を読むそうです。
失敗から学ぶRDBの正しい歩き方 (Software Design plus)
- 作者: 曽根壮大
- 出版社/メーカー: 技術評論社
- 発売日: 2019/03/06
- メディア: 単行本（ソフトカバー）
- この商品を含むブログを見る
同時並行で以下のものを読む計画があるそうです。
達人に学ぶSQL徹底指南書 第2版 初級者で終わりたくないあなたへ (CodeZine BOOKS)
- 作者: ミック
- 出版社/メーカー: 翔泳社
- 発売日: 2018/10/11
- メディア: 単行本（ソフトカバー）
- この商品を含むブログを見る
- 作者: Markus Winand
- 発売日: 2015/09/14
- メディア: ペーパーバック
- この商品を含むブログを見る
ギター初日感想
20台後半で初めてのギターです。rock smith 2014というギターを繋げて遊ぶ音ゲーが面白そうだったので、ギターと一緒に買ったところゲームの同梱品が不足したため、遊べなかったので色々調べて家で一人で練習していました。
Rocksmith 2014 Edition Remastered
- 出版社/メーカー: Ubisoft
- メディア: Video Game
- この商品を含むブログを見る
ギターについて
ヤマハ YAMAHA サイレントギター ナチュラル SLG200S NT
- 出版社/メーカー: ヤマハ(YAMAHA)
- 発売日: 2015/09/01
- メディア: エレクトロニクス
- この商品を含むブログを見る
- とりあえず音はなる
- 意外と重い
- ストラップ的なのは買ってよかった。(重さが肩に分散する)
- アンプとかは買わなくても部屋が静かならある程度音が出るので大丈夫そう？
- ヘッドホンに繋げられるアンプは近所の店には置いてなかった
- ギタースタンドが欲しい(床直置きで起こす時結構重いので)
チューニング
チューナーは実店舗でアマゾン(1600円)より安く変えました(1500円)
D'Addario ダダリオ クリップチューナー クロマチックタイプ Eclipse Tuner フルカラーディスプレイ Purple PW-CT-17PR 【国内正規品】
- 出版社/メーカー: D'Addario(ダダリオ)
- 発売日: 2016/10/17
- メディア: 付属品
- この商品を含むブログを見る
細い方から1弦,2弦...6弦まである
引く前に各弦の開放弦(何も抑えていない状態)の音程をチューナーを使って以下のものに合わせる
コード
同時に弦を抑えてハーモニー的なのを出すやつ
◯は開放弦の状態で鳴らす
G⇨D⇨Cで曲っぽいものが弾ける
- 基本的に弦は腹ではなく指先で押さえる
- 結構握力がいる
形は覚えたが、押さえる指が関係ない弦に当たってうまく音が出ないのがほとんど。他の弦に触れずに一本だけ触るのは慣れもあるらしいので毎日ちょっとずつ頑張ります。
- Fというのが鬼門らしいと聞く
基本的なコード(初心者が覚える順、押す場所、押す指、開放弦)がまとまってる本が欲しい...
NP問題における決定問題とはなにか
アルゴリズムの話をする際に良く出てくるPやNP、NP完全というものを一度きちんと勉強しておきたいと思いブログを書いていましたが、長くなりすぎたため4部作にしました(本記事はpart1)。本記事では下準備としてNP問題であるための条件「決定問題」というものの解説をします。学習には以下の本を使っています。
- 作者: B.コルテ,J.フィーゲン,浅野孝夫,浅野泰仁,小野孝男,平田富夫
- 出版社/メーカー: 丸善出版
- 発売日: 2012/02/29
- メディア: 単行本
- クリック: 5回
- この商品を含むブログ (1件) を見る
まずは決定問題が扱う「言語」という概念から説明します。
言語
計算量理論は大部分が決定問題に基づいている。実際、任意の言語L⊆{0,1}*は、決定問題,すなわち,与えられた0-1文字列がLに属するか(どうかを)決定する問題,と解釈できるからである。(p419)
言語とあるが、これは一般的な自然言語でもプログラミング言語の意味でもない。何らかのデータを符号化したものと考えられる。言語{0,1}*は何らかの011001011...と続く01の羅列、即ちバイナリであることを前提としている。 決定問題は上記の文通り、あるバイナリが言語Lに属するかどうかを決定する問題のこと。
決定問題の定義
決定問題(decision problem)は多項式時間で決定できる言語Xとその部分集合Y⊆Xの対P=(X,Y)として定義される。
注意)このP=(X,Y)のPは複雑性クラスのP,NPのPではありません。本中では斜体にして区別している。
ここで{0,1}* ⊇ X ⊇ Yという言語間の包含関係が成り立つ集合X,Yを定義。なお任意のバイナリが{0,1}* ⊇ Xであるかはどうかは多項式時間で決定できる必要がある*1。この事を組合せ最適化の本ではハミルトン閉路問題を例に説明している
全ての2新文字列がハミルトン閉路問題のインスタンスというわけではなく、無効グラフを表すものだけがそのインスタンスである。本書で扱うほとんどの興味深い決定問題において、インスタンスは0-1文字列集合の真部分集合である。任意の文字列が正しいインスタンスであるかどうかを多項式時間で決定できることが必要である。(p420)
インスタンス
言語Xの任意の元をインスタンスと呼ぶ。
Xの要素をPのインスタンスという
インスタンスは以下の２つのものに分類できる
Yの要素がyes-インスタンス
X/Yの要素がNo-インスタンス(p420)
補足:X/Yは集合XからYを引いた差集合のこと。
決定問題(X,Y)に対するアルゴリズム
x∈Yならばf(x)=1, x∈ X/Y ならばf(x)=0となる関数f:X→{0,1}を計算する(p420)
Xの任意の元がYに属しているかを判定するアルゴリズムのこと。
を変えてして問題の任意のインスタンスを判定できる必要がある。
証明検証アルゴリズム
P=(X,Y)に対してP'=(X',Y')という多項式時間で処理できる決定問題(証明検証アルゴリズム)を定義する。X'とY'は以下のように示される
X':={x#c: x∈X, c∈{0,1}[p(size(x))]}
Y = {y∈X:y#c∈Y'であるようなc∈{0,1}[p(size(y))]が存在する}
シンボル#,文字列cをこの順に連結した文字列を表す。(p421)
[p(size(x))]というシンタックスはxのサイズにしたがって多項式サイズで増えるという意味。[value]は床関数のシンタックスです
決定アルゴリズムに対して、証明検証アルゴリズムは扱える問題のインスタンスはyes-インスタンスの処理のみで十分でありNo-インスタンスの検証を要求されないが、処理速度は多項式時間を要求される。決定アルゴリズムの時点で速度が十分ある(任意の問題を多項式時間で決定できる)場合は決定アルゴリズムをそのまま証明検証アルゴリズムに流用することができる。決定アルゴリズムを使った検証では#cが不要になる。
決定問題P=(X,Y)とPの証明検証問題P'=(X',Y')には以下の関係がある
- X'は言語Xのインスタンスに何らかの文字列#cを追加したものを元にする集合
- XとX'は濃度は一致するが、集合間には特に部分集合であるとかそういう関係はない。(YとY'間も同様)
- Xの任意の元はX'の部分文字列になっている。x'=x + "#c" ただし(x'∈X,x∈X)
- 証明検証アルゴリズムでxが、連結されている#cによってYに属しているかどうかを判定する。
- cは証明(certificate)と呼ばれる
y#c∈Y'となるような文字列cは、(cによってy∈Yであることが証明されるので)yに対する証明(certificate)とも呼ばれる
決定問題まとめ
で、上記適当に箇条書きにしたものを整理すると、以下のことがわかる。
- 問題、とは日曜に使う数学の問題という意味ではなく、バイナリの集合と部分集合のペア(P=(X,Y))が定義できれば問題となる
- 部分集合のペアと言語の閉包関係は以下のようになる。{0,1}* ⊇ X ⊇ Y
- 決定問題では任意のバイナリが問題のインスタンスであるかは多項式時間で決定できる必要がある。
- 言語Xとその部分集合Yを定義する。アルゴリズム(関数)を使ってXの元がYに属するかの判定を{1,0}への写像で表現する。
- 言語の包含関係{0,1}* ⊇ X ⊇ Yで後半のX ⊇ Yの決定に必要な計算量でP,NPの分類を行う。
続く。
別パーティションのWindowsで使ってぃるディスクをubuntuにmount
ubuntuとwindowsをパーティションを分けたディスクで運用しているのでその知見でも書きたいと思います。
ubuntuからwindows側のパーティションにあるファイルを見たい場合はdiskをマウントして閲覧することができます。
windowsが完全に終了していないからマウント出来ない？というエラーが出ましたが、これでとりあえず閲覧(read-only)できるようになりました。
まずはマウントポイントを作ります。
$ sudo mkdir /media/winf
mountコマンドでマウントします。
$ sudo mount -t ntfs-3g /dev/nvme0n1p4 /media/winf
以下の警告が出ました。
Windows is hibernated, refused to mount. Falling back to read-only mount because the NTFS partition is in an unsafe state. Please resume and shutdown Windows fully (no hibernation or fast restarting.)
参考
本記事方法でマントした情報はrebootすると消えますので、半永久的にOSに認識させたい場合は以下の記事を参照して/etc/fstabを編集してください。
CMU 15-445/645 (FALL 2018)Database Systems - 01 Relational Data Modelノート
TLの詳しい方が勧めていたのでちょっと見てみました。
DB はこの講義を受講すればかなり詳しくなれるよ✋(´・ω・｀) https://t.co/1cI6nxWZ9a
— なゆたいむ (@nayutime) 2019年5月19日
スケジュールを見るとかなり本格的でLogging,Concurrency Control,MVCC,はたまた分散OLTP/OLAPと続き、Course informationの所に
The course is appropriate for students with strong systems programming skills.
とあるのでついていけるか不明だが、とりあえず取り組んでみようと思います。 最終的には制作課題？的な感じでC++11でstrage managerを作るらしい。
- 動機
- ちょっとだけ入門したC++を活かす機会
- 英語のリスニングの良い機会
- DBの基礎力向上
- CC本読書会がなくなった事による穴埋め
Concurrency Control and Recovery in Database Systems
- 作者: Philip A. Bernstein,Vassos Hadzilacos,Nathan Goodman
- 出版社/メーカー: Addison-Wesley
- 発売日: 1987/02/01
- メディア: ハードカバー
- この商品を含むブログを見る
- papa本はDBの基礎というには特殊な知識に偏りすぎている気がする*1
Theory of Database Concurrency Control
- 作者: Christos Papadimitriou
- 出版社/メーカー: Computer Science Pr
- 発売日: 1986/07/01
- メディア: ハードカバー
- この商品を含むブログを見る
などをモチベーションに、お昼ご飯とか洗い物とか手が塞がってる時など隙間時間にちょくちょく進めてみます。
早速第一回を見た。第一回はRDBMSの歴史、リレーションとは何か、という話とリレーショナル代数の説明で終わった。
relational model
- E.COD提唱
A Relational Model of Data for Large Shared Data Banks
tuple
- 粒度的には行に相当
- set of attribute
relation
- 粒度的には表に相当(この例えはたまに怒られますが、分かりやすく 例えると。)
- ただしunordered set
- 厳密な意味を知りたければcoddの論文を読む必要がある
- 1個以上のtupeの集合(つまりテーブル)のn項関係関係(つまりjoin)を意図しているように見える。(joinしていないテーブルも含んでいると思われる)
The term relation is used here in its accepted mathematical sense. Given sets S1 , S2, , . . . , Sn, (not necessarily distinct), R is a relation on these n sets if it is a set of n-tuples each of which has its first element from S1, its second element from S2 , and so on.(1.3. A RELATIONAL VIEW OF DATA より抜粋)
attribute
- 列に相当するもの
- 通常atomic/scalarな値をとる
- json型やArray型の登場により、現代のDBではこの制限はゆるくなりつつある。
この論文はRDBMSの源流を探る意味で読む価値はありそうだが、今回ここは掘り下げない。
リレーショナル代数
| Syntax | 意味 | SQL |
|---|---|---|
| σ | Select | WHERE句 |
| Π | Projection | SELECT句 |
| ∪ | Union | UNION演算子 |
| ∩ | Intersection | INTERSECTION演算子 |
| - | Difference | EXCEPTまたはMINUS演算子 |
| × | Product | CROSS JOIN |
| ⋈ | Join | Natural JOIN(オリジナルはこれらしい) |
Select(σ)
- Relationからtupleを述語を使って選択する。Where句に相当
- Syntax:σ predicate(R)
Projection(Π )
- 特定のattributesを使ったrelationを作成する。
- attributesの順の並び替えも可能
- 値の操作も可能。(select a-100 from t_table的な)
- SQLではSelect句に相当。
- Syntax:ΠA1,A2,…,An(R)
Union(∪)
- binary operator.(2つのテーブルをinputにとる演算子)
- どちらかのrelationまたは両方のrelationに出現するentityを表示
- Syntax:(R ∪ S)
Intersection(∩)
- binary operator
- 2つのinputのrelation双方に共通するtupleから成るrelationを生成する
- Syntax:(R ∩ S)
Difference(-)
- binary operator
- 最初のinputのrelationに存在し、かつ2つめのinputに存在しないtupleから成るrelationを作成する
- Syntax:(R - S)
Product(×)
- 2つのrelationの組み合わせから成るrelationを作成する
- Syntax:(R × S)
- 一見使えなさそうに見えるが何に役立つだろうか？という設問が投げられた
- 全組み合わせを試したいテストの時に役立つだろうという話になった。
Join(⋈)
- Syntax:(R ⋈ S)
- 最初にnatural joinを定義したらしい
- equal join, straight joinという呼び名もある
- 2つのrelationの1組み以上の共通のattributeで同じ値をもつtupleの組み合わせから成るrelationを作成する
- 要約すると、同じカラム名の列に関して同じ値を持っているtuple同士を結合させる
- 授業では以下の例で説明された
R
| a_id | b_id |
|---|---|
| a1 | 101 |
| a2 | 102 |
| a3 | 103 |
S
| a_id | b_id |
|---|---|
| a3 | 103 |
| a4 | 104 |
| a5 | 105 |
(R ⋈ S)
| a_id | b_id |
|---|---|
| a3 | 103 |
- intersectionも同じテーブルの例を使っており、結果が全く同じになってしまっていた(授業で使う例としては分かりにくい)
- 違いは何か？という質問が学生から挙げられた
- intersectionでは全てのattributeの順、値が一致するtupleのみから成るrelationを作成する
- natural joinでは共通する名前のattributeが一致すれば良い。
- 違いは何か？という質問が学生から挙げられた
Extra Operator
originalのrelational operatorで表現できなかったものが後年に追加された
- 対応しているSQLは以下のスライドなどを参考に書き足している。
https://courses.cs.washington.edu/courses/cse444/10sp/lectures/lecture16.pdf
| name | operator | SQL |
|---|---|---|
| Rename | ρ | ASに相当。DDL(ALTER)ではない |
| Assignment | R←S | INSERT |
| Duplicate Elimination | δ | distinct。UNIONなどにつけるALLではない |
| Aggregation | γ | Group by |
| Sorting | τ | Order by |
| Division | R÷S | 構文としてはない |
自分の知っている範囲では関係除算(Division)は構文としてはないのでSQL上で結合とかEXISTSとかを駆使して表現する。
感想
relation
RDBMSの文脈でRelationという言葉がよく出てくるが、正直今日までよく意味がわからなかった。
- 実装(実際のRDBMSやSQL)⇨モデル(relationa model)の順番で勉強しているのがそもそも誤解を招いている原因だと思いますが。
- テーブルのこと、や結合のこと、写像のことなど、出現する時々に様々なコンテキストを持って出てくるのでますます混乱する。
とりあえず今回はCoddのオリジナルの定義に当たれたのと、今回のビデオコースでの文脈である程度意味を絞り込りこむことができた。
関係代数はrelationを操作するためのもの。relationから値を取り出したり、新たにrelationを作るのに使う。
- この時のrelationという意味に限定して使うのがより厳密。
- SQLでは
<Query Expression>がもっとも近いと思う*2
Theory of Database Concurrency Control Papadimitriou 読書会 第2回ノート
人身事故の影響で開始時間が遅れたため、あまり進んでいません(まだ1章を読み切っていない) P8 SchedulesからP12 Proposition 1.1まで読みました。
Theory of Database Concurrency Control
- 作者: Christos Papadimitriou
- 出版社/メーカー: Computer Science Pr
- 発売日: 1986/07/01
- メディア: ハードカバー
- この商品を含むブログを見る
Schedules
トランザクション中のdatabase step(read|write)を並び替えたシーケンスのこと。
An interleaved execution of several transactions is termed a schedule.(p8) (略) Formally, a schedule of the transaciotns A1,A2,...,Ak is a sequence of steps in the shuffle A1 * A2 * ... * Ak of the transactions
shuffleされた順列の中にはinterleaveされていないスケジュールも含まれる。特にこれは Serial Schedule と呼ばれる特別なものになる。
A Serial Schedule is a schedule consisting of a succession of transactions, without any interleaving.(p9)
1つのtransactionはcorrectなので、それが直列に並んだSerial Scheduleもcorrectになる。 Serial Scheduleと同じ性質をもつScheduleもまたcorrectになる...という点を次章(2章)で踏み込む。
2章ではSerializabilityをFSR,VSR,CSRの観点から論じる。 必要な道具(エルブランセマンティクス/interpretation)の準備は終わっていると思うので、2章冒頭のFSRが待ち遠しい。
読書会中には
- transactionはcorrectなのか？
- transactionがdatabase step以外の(アプリ側から見た)依存関係を持っていた場合は？
- Nested Transactionはどうなのか?
と言った議論が起こった。この本では
- transactionはconsistencyの単位とする
- hidden restrictionがある場合はマージして1つのトランザクションにする
と言った前提をTransactionの節で引いているので、私個人はシンプルに文面を信じて読み進めています。
interpretationの拡張
p6で定義したinterpretationの定義を拡大して一般的にトランザクション界隈でエルブランセマンティクスと同等のものにまで広げている。*1
※interpretation(エルブランセマンティクス)はFSRを定義する際に重要になってくるので、 本書やWeikum本、kumagiさんのAdvent Calendarなどと比較しつつ単独で記事を書こうと思っています。 今回はざっくりした内容にしておきます。
- あるentity Xに対するreadはXに直前にwriteで書き込んだ値になる。
- ただしreadの前にwrite stepがない場合は初期値を読む
- あるentity Xに対するwriteはそれまでにreadした値を引数にとる関数(ドメインの値に写像)の結果を書き込む
という風な規則を付け加えることでscheduleとinterpretationで計算処理を初期状態と関数の組み合わせで表現することができる。
Schedulers
スケジューラーはDB内で同時実行制御の責務を持つ。
The scheduler is the part of the database system which is responsible for concurrency control.
- 入力:ユーザーが実行したdatabase stepのstream
- 出力:適当な順に並び替えたstream
streamは厳密な(一般的な)定義がないという議論になった。本書ではarriving requestsなどと書かれている点から、 non deterministicでアプリサイドから次々と到着してくるdatabase stepのrequestの流れ程度の理解で問題ないと思う。
- streamは毎度コンテキストに合った定義を用意する必要がある。
- micro batchの塊はstreamではない
- 最初から最後まで切れないものがstream(windowが作れない)
- 例:映像
- データ工学では最初にあるのがデータではなくクエリ、というのがstreamという定義がある
- ストリームとデータのJoinができるシステムの例:PSoup
スケジューラーは一貫性の保護と高い並列性の実現を目標に設計される。
The goal of the scheduler is to safeguard the consistency of the database by outputting only correct schedules.(p9)
The goal of the scheduler is to preserve consistency while maintaining a high level of parallelism or performance.(p10)
スケジューラーの優劣がわかる指標のようなものをChapter5で定義している。 現在のデータベースのベンチ周りではこの指標の定式化ができていないので、 deterministic*2という前提を引いているため、ワークロードが変わると優劣が大きく変わったりするらしい。
余談ですが、Calvinというシリアル実行していると解釈もあるシステムもある。
abstractとconclusionsしか読めてないが、
- 分散ストレージでpaxos-baseのconsistencyを持つ
- トランザクションをサポート
- TPCCの結果が結構良い
というものらしい。
Calvin: Fast Distributed Transactions for Partitioned Database Systems
graph
第一章末にはAppendixとして本書で必要となる数学的な知識、グラフ理論や複雑姓クラスのちょっとしたまとめがある。 今回はグラフ理論を半分くらい読んだ。
- vertex:グラフの頂点(ノードのこと)
- edge:2つのvertexから構成される辺のこと
グラフはvertexの集合Vとedgeの集合Eのペア。
A graph is a pair G = (V,E), where V is a finite set of nodes or vertices, and E is a set of subsets of V of cardinality two, (p11)
上記グラフは以下のようになる
G = (V,E)
V = {v1,v2,v3,v4,v5,v6}
E = {[v1,v2],[v1,v4],[v1,v3],[v2,v4],[v3,v4],[v3,v5],[v3,v6],[v4,v6],[v5,v6]}
- walk
隣接している頂点を繋いだ経路のことをwalkという。本書では私の要約より厳密に定義されている。
A walk in a graph G = (V,E) is a sequence [v1,...,vn] of vertices in V, such that for i = 1,..., n-1,[vi,vi+1]∈E (p11)
- walkの中でnodeの繰り返しがないものをpathという
- walkの中で第一nodeと最終nodeが一致しているものをcycleという
A walk in which there is no repetition of nodes is a path; if only the first and last nodes coincide, whe have a cycle.(p11)
- degree
ノードから何本edgeが生えているかをdegreeという。
directed graph
上記の無向グラフの定義を拡張して有向グラフ(directed graph)を定義する。各要素に以下の変更点が加わる
- edge → 呼称をarcに変える。矢印の根本をtail,矢印の先をheadと呼ぶ。
- degree → ノードがarcのtail側、head側それぞれを区別したdegreeを新たに定義する。
- ノードから生えているtailの数:out-degree
- ノードに刺さっているheadの数:in-degree
orderdとcycleの関係
本書では以下が同値と見なされている
- DAGであること
- グラフの頂点が順序付けが可能であること(can be ordered)
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.(p12)
対偶として以下が成り立ってしまう点で長い議論が発生した。
- 順序付け不可能である ↔︎ Cycleが存在する
様々なCycle
- Cycleを個別に定義せずに、順序付けできない(トポロジカルソートができない)ことからCycleの定義を導いてしまう書籍、論文だと(2)もCycleと見なしているケースがある
- (2)のようなグラフは以下の論文に乗っているこのstep graphが該当している(勉強会後に神林さんに聞きました)
Making Snapshot Isolation Serializable
ちなみに以下の本ではCycleは3ノード以上で成り立たないとしているので、(1),(2)双方ともCycleではない。
Handbook of Graph Theory (Discrete Mathematics and Its Applications)
- 作者: Jonathan L. Gross,Jay Yellen,Ping Zhang
- 出版社/メーカー: Chapman and Hall/CRC
- 発売日: 2014/02/11
- メディア: ハードカバー
- この商品を含むブログを見る
knot
- Cycleを定義している本は少ない。的な話からknotの話になった。
- 安易にデッドロックやAnomalyの定義をサイクルに頼るのではなく、検出に必要な性質を整理した上でknotのようなcycleより厳密なグラフ構造を定義している本や論文もある。
Distributed Computing: Principles, Algorithms, and Systems
- 作者: Ajay D. Kshemkalyani
- 出版社/メーカー: Cambridge University Press
- 発売日: 2011/03/03
- メディア: ペーパーバック
- この商品を含むブログを見る
RICHARD C. HOLT (1972)Some Deadlock Properties of Computer Systems
あるリソースモデルではWFGに存在するcycleを検査するだけでは不十分なのでより厳密なknotというものの有無を検査する
- knotはpathのクロス(結び目っぽく見える)とは関係ない
- knotとCycleは単純に比較できないが、あえて言及するならcycle ⊃ knot
- kontが存在する場合はknotを構成しているvertexからなるcycleが存在している。
- cycleがあるからといってknotがあるとは限らない
今回はp12のProposition 1.1まで読みました。次回は1.1のProofからです。Complexity(NP,NP complete)の話がが長くなるような予感がしています。
関連:
同回他参加者のブログなどのリンクを貼っておきます
- ぱと隊長のブログ
- nikezonoさんのscrapbox
