Yabu.log

ITなどの雑記

Effecitve SQLを読書会で読み終わりました

SQL

全16回でした。毎度木村@meijikさんの博識ぶりには驚かされる勉強会でした。

Effective SQL

Effective SQL

プログラマの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述語)の使用例はこの本くらいでした。

参考

昔に背伸びして書いた記事です

qiita.com

次回

次回は曽根壮大さんの「失敗から学ぶRDBの正しい歩き方」を読むそうです。

失敗から学ぶRDBの正しい歩き方 (Software Design plus)

失敗から学ぶRDBの正しい歩き方 (Software Design plus)

同時並行で以下のものを読む計画があるそうです。

達人に学ぶSQL徹底指南書 第2版 初級者で終わりたくないあなたへ (CodeZine BOOKS)

達人に学ぶSQL徹底指南書 第2版 初級者で終わりたくないあなたへ (CodeZine BOOKS)

SQLパフォーマンス詳解

SQLパフォーマンス詳解

  • A Critique of ANSI SQL Isolation Levels

okachimachiorz.hatenablog.com

tombo2.hatenablog.com

developer.hatenastaff.com

ギター初日感想

ギター 音楽

20台後半で初めてのギターです。rock smith 2014というギターを繋げて遊ぶ音ゲーが面白そうだったので、ギターと一緒に買ったところゲームの同梱品が不足したため、遊べなかったので色々調べて家で一人で練習していました。

Rocksmith 2014 Edition Remastered

Rocksmith 2014 Edition Remastered

ギターについて

  • 1万くらいのストラトというモデルのものをamazonで買った
  • メーカーとかモデルとかはまだよくわかっていない。
  • 本当はサイレントギターが欲しかった(形がかっこいいので)

ヤマハ YAMAHA サイレントギター ナチュラル SLG200S NT

ヤマハ YAMAHA サイレントギター ナチュラル SLG200S NT

  • とりあえず音はなる
  • 意外と重い
    • ストラップ的なのは買ってよかった。(重さが肩に分散する)
  • アンプとかは買わなくても部屋が静かならある程度音が出るので大丈夫そう？
    • ヘッドホンに繋げられるアンプは近所の店には置いてなかった
  • ギタースタンドが欲しい(床直置きで起こす時結構重いので)

チューニング

チューナーは実店舗でアマゾン(1600円)より安く変えました(1500円)

D'Addario ダダリオ クリップチューナー クロマチックタイプ Eclipse Tuner フルカラーディスプレイ Purple PW-CT-17PR 【国内正規品】

D'Addario ダダリオ クリップチューナー クロマチックタイプ Eclipse Tuner フルカラーディスプレイ Purple PW-CT-17PR 【国内正規品】

細い方から1弦,2弦...6弦まである

引く前に各弦の開放弦(何も抑えていない状態)の音程をチューナーを使って以下のものに合わせる

f:id:yuyubu:20190624192214j:plain
ノーマルチューニング
-

コード

同時に弦を抑えてハーモニー的なのを出すやつ

◯は開放弦の状態で鳴らす

f:id:yuyubu:20190624195823j:plain
C

f:id:yuyubu:20190624194035j:plain
Am

f:id:yuyubu:20190624201949j:plain
G

f:id:yuyubu:20190624201118j:plain
D

G⇨D⇨Cで曲っぽいものが弾ける

  • 基本的に弦は腹ではなく指先で押さえる
  • 結構握力がいる

形は覚えたが、押さえる指が関係ない弦に当たってうまく音が出ないのがほとんど。他の弦に触れずに一本だけ触るのは慣れもあるらしいので毎日ちょっとずつ頑張ります。

  • Fというのが鬼門らしいと聞く

基本的なコード(初心者が覚える順、押す場所、押す指、開放弦)がまとまってる本が欲しい...

NP問題における決定問題とはなにか

complexity computer science

アルゴリズムの話をする際に良く出てくるPやNP、NP完全というものを一度きちんと勉強しておきたいと思いブログを書いていましたが、長くなりすぎたため4部作にしました(本記事はpart1)。本記事では下準備としてNP問題であるための条件「決定問題」というものの解説をします。学習には以下の本を使っています。

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

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

まずは決定問題が扱う「言語」という概念から説明します。

言語

計算量理論は大部分が決定問題に基づいている。実際、任意の言語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]は床関数のシンタックスです

ja.wikipedia.org

決定アルゴリズムに対して、証明検証アルゴリズムは扱える問題のインスタンスは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)とも呼ばれる

  • 証明検証アルゴリズムではX'がY'に含まれるかを計算する。この時の計算量が多項式時間で表せるものがクラスNPに属する(詳細は別エントリで)

決定問題まとめ

で、上記適当に箇条書きにしたものを整理すると、以下のことがわかる。

  • 問題、とは日曜に使う数学の問題という意味ではなく、バイナリの集合と部分集合のペア(P=(X,Y))が定義できれば問題となる
  • 部分集合のペアと言語の閉包関係は以下のようになる。{0,1}* ⊇ X ⊇ Y
  • 決定問題では任意のバイナリが問題のインスタンスであるかは多項式時間で決定できる必要がある。
  • 言語Xとその部分集合Yを定義する。アルゴリズム(関数)を使ってXの元がYに属するかの判定を{1,0}への写像で表現する。
  • 言語の包含関係{0,1}* ⊇ X ⊇ Yで後半のX ⊇ Yの決定に必要な計算量でP,NPの分類を行う。

続く。

*1:なぜ言語がXの適切な元かどうかを多項式時間で決定できる必要があるのかは自分が当たった本には書かれていおらず、私自身も理解できていないのでもし知っていれば教えてください

別パーティションのWindowsで使ってぃるディスクをubuntuにmount

Linux ubuntu

ubuntuとwindowsをパーティションを分けたディスクで運用しているのでその知見でも書きたいと思います。

ubuntuからwindows側のパーティションにあるファイルを見たい場合はdiskをマウントして閲覧することができます。

f:id:yuyubu:20190614150234p:plain
windowsとubuntuが乘っているnvme

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.)

f:id:yuyubu:20190614151333p:plain
エクスプローラで認識できるようになった

参考

dacelo.space

本記事方法でマントした情報はrebootすると消えますので、半永久的にOSに認識させたい場合は以下の記事を参照して/etc/fstabを編集してください。

pocke.hatenablog.com

CMU 15-445/645 (FALL 2018)Database Systems - 01 Relational Data Modelノート

DB RDBMS

TLの詳しい方が勧めていたのでちょっと見てみました。

15445.courses.cs.cmu.edu

スケジュールを見るとかなり本格的で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

Concurrency Control and Recovery in Database Systems

  • papa本はDBの基礎というには特殊な知識に偏りすぎている気がする*1

Theory of Database Concurrency Control

Theory of Database Concurrency Control

などをモチベーションに、お昼ご飯とか洗い物とか手が塞がってる時など隙間時間にちょくちょく進めてみます。

早速第一回を見た。第一回はRDBMSの歴史、リレーションとは何か、という話とリレーショナル代数の説明で終わった。

relational model

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

*1:スケジューラーの本な　のでindexなどの話はあまり出てこない

*2:SELECT句の結果、UNION演算子の結果、UNION演算子の引数に取れるもの等

Theory of Database Concurrency Control Papadimitriou 読書会 第2回ノート

DB 勉強会 Transaction

人身事故の影響で開始時間が遅れたため、あまり進んでいません(まだ1章を読み切っていない) P8 SchedulesからP12 Proposition 1.1まで読みました。

Theory of Database Concurrency Control

Theory of Database Concurrency Control

connpass.com

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

Sirish Chandrasekaran, Michael J. Franklin: PSoup: a system for streaming queries over streaming data. VLDB J. 12(2): 140-156 (2003)

スケジューラーは一貫性の保護と高い並列性の実現を目標に設計される。

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)

f:id:yuyubu:20190519010908p:plain:w500
graphの例 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

f:id:yuyubu:20190519010841p:plain:w300
Cycle?の例

  • Cycleを個別に定義せずに、順序付けできない(トポロジカルソートができない)ことからCycleの定義を導いてしまう書籍、論文だと(2)もCycleと見なしているケースがある
  • (2)のようなグラフは以下の論文に乗っているこのstep graphが該当している(勉強会後に神林さんに聞きました)

Making Snapshot Isolation Serializable

f:id:yuyubu:20190519010412p:plain
Making Snapshot Isolation Serializableのp504から抜粋

okachimachiorz.hatenablog.com

ちなみに以下の本ではCycleは3ノード以上で成り立たないとしているので、(1),(2)双方ともCycleではない。

Handbook of Graph Theory (Discrete Mathematics and Its Applications)

Handbook of Graph Theory (Discrete Mathematics and Its Applications)

knot

  • Cycleを定義している本は少ない。的な話からknotの話になった。
  • 安易にデッドロックやAnomalyの定義をサイクルに頼るのではなく、検出に必要な性質を整理した上でknotのようなcycleより厳密なグラフ構造を定義している本や論文もある。

Distributed Computing: Principles, Algorithms, and Systems

Distributed Computing: Principles, Algorithms, and Systems

  • 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があるとは限らない

yuyubu.hatenablog.com

今回はp12のProposition 1.1まで読みました。次回は1.1のProofからです。Complexity(NP,NP complete)の話がが長くなるような予感がしています。

関連:

同回他参加者のブログなどのリンクを貼っておきます

  • ぱと隊長のブログ

taityo-diary.hatenablog.jp

scrapbox.io

*1:ちなみにですが、私の身の回りではinterpretationよりエルブランセマンティクスという名称の方が一般的

*2:database stepが開始時に決まり途中で変化しないというのが現時点の私のdeterministicの理解。分岐処理や対話的な処理をトランザクションで表現できない

Theory of Database Concurrency Control Papadimitriou 読書会 第1回ノート

DB 勉強会

難しいけどなんとか付いていく感じです

Theory of Database Concurrency Control

Theory of Database Concurrency Control

前提

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

用語の定義等

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.

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)

  • (個人的にhidden restrictionの議論はLinearizabilityに近いものを感じた。)

https://scrapbox.io/nikezono/Linearizability

Mono versionから理論を出発させるのではなく、Multiversionから理論を出発させるべき。

Mono Versionの枠組みの拡張としてMultiversionを議論するべきではない、 Multiversionの枠組みで、Mono Versionをその中の一つの特殊系として理論を構築すべき、的な議論があったが、 ここは理解度が低いのでメモ程度にブログに残しておく。

この話はここに限った話ではなく、色んな所で見聞きします。

おそらくMono Versionの枠組みの拡張で何か無理が起こるものだと思うけど、多分もう少し登ると見えてくる光景なのかなと思います。

Interpretationの定義は好評でした

Conflictの判定や依存などの表現にHerbrand Semanticsはよく使われている道具だと思いますが、 本書の定義(Interpretationですが)は概ね好評な感じでした。 ただこの本が書かれた時点ではHerbrand Semanticsという名前は出てきていない。