NPクラスのNondeterministic polynominal algorithmについて
4部作その3。組合せ最適化のページ(p422~423)の理解メモです。100回くらい同じページを読んだ結果、本書の記述だけだと不十分に感じたの類書を参考にしています。
- 作者: B.コルテ,J.フィーゲン,浅野孝夫,浅野泰仁,小野孝男,平田富夫
- 出版社/メーカー: 丸善出版
- 発売日: 2012/02/29
- メディア: 単行本
- クリック: 5回
- この商品を含むブログ (1件) を見る
余談:NP(Nondeterministic polynominal)という特性
※重要だと思って精読しましたが、乱択アルゴリズムを考えないときはあまり重要ではないので個人の判断で読み飛ばしてください。本書でもnon-deterministic polynominalを何かの前提・準備として紹介していません。
NPで扱える決定問題の種類はdeterministicに限らない。NPのNondeterministicという名前は決定問題のアルゴリズムとして採用できるアルゴリズムの制約からきている。
以下は同値である。
非決定性アルゴリズムはランダム化アルゴリズム(randomized algorithm)の一種。
ランダム化アルゴリズムはf(s)→Tに対して以下のものと定義されています。
- 関数g:{s#r:s∈S,r∈{0,1}k(s)}→T
ランダム化アルゴリズムはある問題f(s)インスタンスのサイズに依存する多項式時間個のランダムビットrを使って元のアルゴリズムと近い決定ができるアルゴリズムです。元のアルゴリズムとどの程度精度が一致しているかで以下のように分類されています。
algorithm | definition (※全てp422からの抜粋) |
---|---|
モンテカルロアルゴリズム | インスタンスによらず少なくとも正の確率pで正しい答えを出力する |
片側誤差のあるランダム化アルゴリズム | f(s)=0となるどのs∈Sに対しても、全てのr∈{0,1}k(s)でg(s#r)=0となる |
非決定性アルゴリズム | f(s)=1となる各s∈Sに対してg(s#r)=1を満たすr∈{0,1}k(s)が少なくとも1個存在する |
ラスベガスアルゴリズム | すべてのs∈Sに対してg(s#r)=f(s)である理想的な場合 |
下図のような閉包関係があります。
ここまで読んでまともな人ならお気付きかと思いますが、非決定性アルゴリズムの
f(s)=1となる各s∈Sに対してg(s#r)=1を満たすr∈{0,1}k(s)が少なくとも1個存在する
インスタンスによらず少なくとも正の確率pで正しい答えを出力する
という特性がすでに満たしているように読めるはずです。すなわち本書の記述のみを頼りに考えると「片側誤差のあるランダム化アルゴリズム」と「非決定性アルゴリズム」の集合のサイズは完全一致になるはずです。
本棚があったので類書を少し調査してみました。
乱択アルゴリズム (アルゴリズム・サイエンス・シリーズ―数理技法編)
- 作者: 玉木久夫
- 出版社/メーカー: 共立出版
- 発売日: 2008/08/08
- メディア: ハードカバー
- 購入: 4人 クリック: 52回
- この商品を含むブログ (8件) を見る
すると、この本のp12を読むと片側誤差のあるランダム化アルゴリズムについて興味深いことがわかりました。
乱数の出方に寄らず常に正しい結果を与える乱択アルゴリズムをラスベガスアルゴリズム(Las Vegas algorithm)と呼ぶ。これに対して、乱数の出方によって誤った結果を与えることが実際にあるアルゴリズムをモンテカルロアルゴリズム(Monte Carlo algorithm)と呼ぶ。(中略) 対象とする問題が、判定問題(decision problem),つまりYESかNOと答えるタイプの問題である場合、モンテカルロアルゴリズムはさらに、片側謝りアルゴリズム(one-sideed error algorithm)と両側謝りアルゴリズム(both-sided error algorithm)の二つに分類される。真の答えがYESの時だけ、あるいはNOの時だけ誤る可能性があり、反対の場合には必ず正しく答えるアルゴリズムは片側誤りアルゴリズムである。どちらの場合にも誤る可能性のあるアルゴリズムは両側誤りアルゴリズムである。
黄色い本と白い本のone-sided error algorithm(片側謝りアルゴリズム、片側誤差のあるランダム化アルゴリズム )について定義を比較してみましょう
本 | 定義 |
---|---|
黄色い本 | f(s)=0となるどのs∈Sに対しても、全てのr∈{01}k(s)でg(s#r)=0となる |
白い本 | YESあるいはNOの時だけ誤る可能性があり、反対の場合には必ず正しく答える |
白い本のone-sided error algorithmの定義がより厳密と仮定すると、片側誤差ありアルゴリズムはYESインスタンスまたはNOインスタンスのどちらかは正しく決定することができるアルゴリズムということになります。黄色い本は"YES sideに誤差がありNo sideは完璧に答えるアルゴリズム"を暗黙の前提にしています。
上記を踏まえて乱択アルゴリズムの表は次のように再構成できます。
algorithm | definition (※全てp422からの抜粋) |
---|---|
モンテカルロアルゴリズム | インスタンスによらず少なくとも正の確率pで正しい答えを出力する |
片側誤差のあるランダム化アルゴリズム | YESインスタンスもしくはNoインスタンスのどちらかを完全に正しく決定できる |
非決定性アルゴリズム | NOインスタンスを正しく決定できる |
ラスベガスアルゴリズム | すべてのs∈Sに対してg(s#r)=f(s)である理想的な場合 |
上記の分類は黄色、白い本の内容と矛盾なく乱択アルゴリズムをうまく分類できているように思えますが、専門家ではないのですこし自信がありません。*1
非決定性アルゴリズムが存在する↔︎クラスNP なのはなぜか
証明をそのまま載せてしまうのはアレなので概略だけさっと書きます。ランダムビットrをcertificateと読み替えて、ランダム化アルゴリズムをそのまま証明検証アルゴリズムに置き換えることが出来ます。
非決定性アルゴリズムの定義
f(s)=1となる各s∈Sに対してg(s#r)=1を満たすr∈{0,1}k(s)が少なくとも1個存在する
から、NP問題の定義
任意のyes-インスタンスに対してのみ多項式時間で検証できる証明の存在だけが要求される。
補足:検証アルゴリズムの定義 Y = {y∈X:y#c∈Y'であるようなc∈{0,1}[p(size(y))]が存在する}
を導くことが出来ます。
補足情報
具体例としては以下の資料で2-SATをランダム化アルゴリズムを使って解く方法が挙げられています。
http://www-imai.is.s.u-tokyo.ac.jp/seminar/reading/resume/02summer_11.pdf
若干この本ではnondeterministicの話はわかりにくかったので、アルゴリズムイントロダクションという本を参照したところ、NP問題の特にnondeterministic側の問題に焦点を当てた本として以下のものが提示されていた。
アルゴリズムイントロダクション 第3版 総合版:世界標準MIT教科書
- 作者: Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson
- 出版社/メーカー: 近代科学社
- 発売日: 2018/01/09
- メディア: Kindle版
- この商品を含むブログ (4件) を見る
Hopcroft and Ullman [180] give a good presentation of NP-completeness in terms of nondeterministic models of computation.
- [180] John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
- 作者: John E. Hopcroft,Rajeev Motwani,Jeffrey D. Ullman
- 出版社/メーカー: Pearson
- 発売日: 2013/10/03
- メディア: Kindle版
- この商品を含むブログを見る
和訳もあるようです
オートマトン言語理論 計算論〈1〉 (Information & Computing)
- 作者: J.ホップクロフト,J.ウルマン,R.モトワニ,John E. Hopcroft,Jeffrey D. Ullman,Rajeev Motwani,野崎昭弘,町田元,高橋正子,山崎秀記
- 出版社/メーカー: サイエンス社
- 発売日: 2003/04/01
- メディア: 単行本
- 購入: 1人 クリック: 172回
- この商品を含むブログ (19件) を見る
- 作者: ジョン・E・ホッブクロフト,R・モトワニ,J・D・ウルマン,野崎昭弘,高橋正子,町田元,山崎秀記
- 出版社/メーカー: サイエンス社
- 発売日: 2003/08/13
- メディア: 単行本
- 購入: 3人 クリック: 22回
- この商品を含むブログ (11件) を見る
note:本エントリでは深入りしませんが、非決定性アルゴリズムより広い乱択アルゴリズムを考えたときの計算クラスもあるようです。
PとNPについて
4部作その2。組み合わせ最適化第二版のp419~421の理解メモです。前回の決定問題の知識を前提に記事を書いています。
- 作者: B.コルテ,J.フィーゲン,浅野孝夫,浅野泰仁,小野孝男,平田富夫
- 出版社/メーカー: 丸善出版
- 発売日: 2012/02/29
- メディア: 単行本
- クリック: 5回
- この商品を含むブログ (1件) を見る
Nondeterministicについてちょっと小話
ちょっとわかりにくいのがNPですね。Not Pではありません。この話題に入る前にNondeterministic Turing Machineはドラえもんの秘密道具並みにヤバイ存在だということを頭に入れておくと、理解が深まります。NP問題を多項式時間で解くとされる「非決定性チューリング機械」は思考実験的アナロジーであり、任意のNP問題の非決定性アルゴリズムを多項式時間で解く計算機は実存していません。
またNondeterministicという単語が一般的なシステム用語と少しスコープが違う使われ方をしているように感じます。*1
- イメージとしてはこんな感じです。
- △常に同じ答えを出さない
- ⭕️常に最良の乱数を選ぶことができる
NPとP
クラスNPでは、多項式時間アルゴリズムは要求されず、任意のyes-インスタンスに対してのみ多項式時間で検証できる証明の存在だけが要求される。(p421)
証明検証アルゴリズムの箇所にも書いたが、Pの決定アルゴリズムはそのまま判定アルゴリズムとして利用することができるのでPはNPに含まれる。
決定アルゴリズムの時点で速度が十分ある(任意の問題を多項式時間で決定できる)場合は決定アルゴリズムをそのまま証明検証アルゴリズムに流用することができる。決定アルゴリズムを使った検証では#cが不要になる。(前回エントリより)
よってNP ⊇ Pという包含関係が成り立つ。ただしこの包含関係が真部分集合であるかどうかは30年以上前からの重大な未解決問題(P ≠ NP予想)になっている。
Pが見つかっていないNPとNP完全
NPである問題に多項式時間アルゴリズムが見つかれば、その問題はPに分類することができる。
NP完全といわれるNP中の特殊なクラスの場合は少し話が違っていてPで解けるアルゴリズムが見つかった場合は全てのNP問題がPで解けるという、ある種革命的な状況が発生してしまう(P=NP)。
これ以外のNP問題、つまり現状でNP完全なのかPなのか分かっていない問題はNP-intermediateと言われている
ただしP=NPが判明すればNPIは空集合になる。P ≠ NPの場合はNPIが存在する。PapadimitriouのComputational Complexityにこのクラスの存在証明が乘っているらしい。
ぼくには簡単ではありませんが (^^;) Papadimitriou の Computational Complexity に証明が載っていました。対角線論法を使ってうまいこといったはず。
- 作者: Christos H. Papadimitriou
- 出版社/メーカー: Addison Wesley
- 発売日: 1993/11/30
- メディア: ペーパーバック
- 購入: 1人 クリック: 1回
- この商品を含むブログを見る
実際に本を確認してみたところ、以下の記述がそれらしい
Theorem 14.1: IF P ≠ NP, then there is a language in NP which is neither in P nor is it NP-complete(p330)
Theoremのあとに証明が続くが割愛
Papadimitriouの本以外にも以下の本にもNPIの章と証明はあった
Computational Complexity: A Modern Approach
- 作者: Sanjeev Arora,Boaz Barak
- 出版社/メーカー: Cambridge University Press
- 発売日: 2009/04/20
- メディア: ハードカバー
- クリック: 1回
- この商品を含むブログを見る
どの本に乗っている証明も以下の論文の引用になっていた
- Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility".
素因数分解やグラフ同型問題が今の所、このクラスだろうと考えられている
ちなみに多くの専門家はP=NPではないと予想している。(2012年時点で126/152人)
http://dopal.cs.uec.ac.jp/okamotoy/PDF/2013/complexity10confusions.pdf
ubuntu18.04で英字キーボード(101)キーボードを使う備忘録(主に日本語/英語切り替え)
日本語版ubuntuの英字キーボードのデフォルト設定に不満があったためカスタマイズしたかったが設定がわからりずらすぎて消耗したのでメモ
1.pkg-reconfigureでキーボードレイアウト設定
sudo dpkg-reconfigure keyboard-configuration
で該当するキーボードを選択。
102を勧めているqiitaがあったけど、
Shiftとzキーの間になにかキーがあればそれは102キーボードだけど、多分そのキーがない101キーボードのほうが日本では一般的なのでそちらを選択する可能性のほうが高い。(手元のキーボードの配列を調べてあってるものを選んでください。)
2.言語設定からmozc(日本語)以外をすべて削除
設定>Region & Language のinput SourcesからEnglishを削除して「日本語(Mozc)」のみの状態にする
3.mozcのツール>プロパティ>キー設定で「入力キー」hankaku/zenkakuのを切り替えに使いたいキーに入れ替える
キー設定の選択[MS-IME]は多分プリセットなので適当に自分が慣れているものを選びましょう。設定後は「カスタム」に変わるはずです。
上記手順完了のち、ログインし直して設定は完了。設定したキーで日本語英語切り替えできるようになっているはず。
Amazonで新品の本を注文したら表紙が一部破損しているものが届いた
ちょうどブログのネタになるかなと思ったので半年ほど前にあったことを書き残しておきます。
経緯
買った本はWeikum本ことトランザクションの本です。
- 作者: Gerhard Weikum,Gottfried Vossen
- 出版社/メーカー: Morgan Kaufmann
- 発売日: 2001/05/30
- メディア: Kindle版
- この商品を含むブログを見る
kindle版を持っていたが、この本は「ここで以前説明したtheorem 5.4によると...」という感じでページを行ったり来たりするので紙の本もあると良いなと思って購入した。
ちなみにこの本のKindle版は固定PDFのような形になっておりフォントサイズが変えられないため、iPadだと読めるがパソコンだと文字が小さくてかなり読みづらい。
ですので一応紙の本も買ってみる事にした。
ちなみに現在電子版を買うならDRM FREEのPDFが変えるのでそっちがおすすめ*1
で、本が届くと表紙にヒビが入っていた。
対処
この本はその重すぎる自重故に、持ち運んでいるとそのうちバラバラになってくるらしいが、そもそも最初から破れてるのはおかしいんじゃない?とのアドバイスをもらったので、一応クレームを出してみる事にした。
表紙がひび割れた状態で到着しました。新品のものを買った認識ですが、この件に関するサポートは受けられますか?
破損している商品の写真を求められたのでそちらをメールで送付した。輸送中の破損は仕方ないと思うので、売り手、買手で五分五分で手を打つのが筋なんじゃないないかと個人的に考えています。50%返金とかになるかな?
交渉
とりあえず、20%の返金で良いか?という提案がきた。なぜ20%?何を基準に?少し調べてみると、Amazonにはマーケットプレイス保証というものがある。
Amazon.co.jpのウェブサイトで出品者から商品を購入するお客様は、配送料を含めた購入総額のうち、最高300,000円まで保証されます。
「返品ポリシー」に合致して返品を却下された場合、Amazonが30万円まで保証してくれるらしい。
調べる過程で見つけましたが、amazonのseller向けフォーラムというものの存在を知り、軽く巡回してみたが以下のことがわかった
https://sellercentral-japan.amazon.com/forums/
- 返品に関しては購入者が有利になっている。
一応新品を買って破損していたので、返品に応じなければマーケットプレイス保証が使えるはず。 と言っても、返品は流石に可愛そうなので50%返金 or 交換の選択肢で交渉に挑んでみた。
20%は安すぎませんか。
ここは新品と交換が筋だと思いますが、時間がどれぐらいかかりますか?(また在庫的に可能でしょうか?)
交換が難しい場合は、50%返金でどうでしょうか。
結果
- 再送(返品不要)
という事になった。50%返金 or 交換の選択肢でなぜ再送という判断になるんだろうか。 向こうの負担的には50%返金が一番ダメージ少ない気がするけど。 tx本の在庫処分に困っていたのだろうか。
なぜか我が家にはweikum本が3冊(normal + 破損 + kindle)あるという自体に... とりあえず会社と自宅に置いておく事にした
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に割いています。(第8章 直積)直積をまる一章説明している本は珍しいのではないでしょうか。気になった人はこの章だけでも通読をおすすめします。
「項目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というのが鬼門らしいと聞く
基本的なコード(初心者が覚える順、押す場所、押す指、開放弦)がまとまってる本が欲しい...