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同士を結合させる
- 授業では以下の例で説明された

a_id	b_id
a1	101
a2	102
a3	103

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演算子の引数に取れるもの等

2019-05-19

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

DB 勉強会 Transaction

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

Schedules
- interpretationの拡張
Schedulers
graph
- directed graph
- orderdとcycleの関係
  - 様々なCycle
knot

Theory of Database Concurrency Control

作者: Christos Papadimitriou
出版社/メーカー: Computer Science Pr
発売日: 1986/07/01
メディア: ハードカバー
この商品を含むブログを見る

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)

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

yuyubu.hatenablog.com

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

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

DB 勉強会

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

前提
用語の定義等
他

Theory of Database Concurrency Control

作者: Christos Papadimitriou
出版社/メーカー: Computer Science Pr
発売日: 1986/07/01
メディア: ハードカバー
この商品を含むブログを見る

前提

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

https://t.co/3T7whzBZVs
本日開催です。本が世界レベルで高騰してしまったので（たぶん、この勉強会のせい。マーケット狭すぎ・・）手に入ってないひとにも問題がないようになんらか手当をする予定です。
— 御徒町＠MultiVersionConcurrentClimber(MVCC) (@okachimachiorz1) April 24, 2019

用語の定義等

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)

作者: Gerhard Weikum,Gottfried Vossen
出版社/メーカー: Morgan Kaufmann
発売日: 2001/05/24
メディア: ハードカバー
クリック: 2回
この商品を含むブログ (2件) を見る

(個人的に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という名前は出てきていない。

2019-04-16

「ふつうのLinuxプログラミング第2版」を読んだ

Linux

本書はシステムコールとlibcのAPIなどを使ったLinuxで動作するコマンドの作成を通して、 Linuxについて深く知ろうという趣旨の本です。

読んだきっかけ
雑感
感想
次に読む本

ふつうのLinuxプログラミング第2版 Linuxの仕組みから学べるgccプログラミングの王道

作者: 青木峰郎
出版社/メーカー: SBクリエイティブ
発売日: 2017/09/22
メディア: 単行本
この商品を含むブログを見る

読んだきっかけ

本書を読んだきっかけは自分のlinux力があまりにも低すぎると感じたため。具体的に言うと、cmakeに-CMAKE-INSTALL_PREFIXをつけずにビルドして、/usr/localに実行バイナリをおいてしまった。この件に関して「これじゃぁ他のユーザーに影響でちゃうよ。」と怒られたが、

Linuxのフォルダ構成について何も理解していない。
-CMAKE-INSTALL_PREFIXをつけるのはかなり基本的なことっぽい。

の２点からググってネット上のコマンドをコピペするしか能のない自分のLinux力を猛省したところ、本書を見つけた。

TLの強めのエンジニアがリコメンドしている
最近改版された。
自分が分からなかったフォルダ構成について書かれている
会社に1版に大量の付箋がついているものが存在している(おそらくこれで猛勉強した同僚がいる(いた？))

の４点から、本書を学習してみることにした。

雑感

include<stdio.h>を呪文とすることなく順序立てて初心者にも理解できるように解説している。

1.システムコールやそのAPIのmanコマンド読み方
2.実際にシステムコールなどを使ってみる小さなコードを作る
3.システムコールだけで実現できない動作をバッファなどを実装して自前で作る
4.3で作った相当のものがライブラリとして用意されていることをmanコマンドで説明する

という流れでstdioのprintfの解説を試みている。本や大学の授業などでこの部分の解説を受けたことがなかったので、ここの流れは見事だなと思った。

manコマンドのセクションについて

manコマンドで実行コマンドまたはライブラリの関数等の使い方を調べることができます。

調べる対象のコマンド名のほかにもセクション番号を引数で渡すことができます。引数としてなにがあり、どの数字に対応しているかはman manで調べることができます。

$man man
・・・(略)
       1   Executable programs or shell commands
       2   System calls (functions provided by the kernel)
       3   Library calls (functions within program libraries)
       4   Special files (usually found in /dev)
       5   File formats and conventions eg /etc/passwd
       6   Games
       7   Miscellaneous (including macro packages and conventions), e.g. man(7), groff(7)
       8   System administration commands (usually only for root)
       9   Kernel routines [Non standard]
・・・(略)

名前がかぶっているもの、例えばprintfなどはstdioで定義されている関数以外にもユーザーコマンドとして存在しているため、manコマンドで調べると、ライブラリの関数よりも先にユーザーコマンドのセクションがヒットして表示されてしまいます。

$man printf

PRINTF(1)  User Commands  PRINTF(1)

NAME
       printf - format and print data

ライブラリの関数を調べたいときはman 3 prinftと引数にセクション番号を渡すことで表示できます。

$man 3 printf

PRINTF(3)  Linux Programmer's Manual  PRINTF(3)

NAME
       printf, fprintf, dprintf, sprintf, snprintf, vprintf, vfprintf, vdprintf, vsprintf, vsnprintf - formatted output conversion

SYNOPSIS
       #include <stdio.h>

       int printf(const char *format, ...);
・・・(略)

本書ではライブラリ関数やユーザーコマンドを見分けるため、printf(1)やprintf(3)といった書き方に統一しています。これは分かりやすく、ほかの本でも見かける*1ので、知らない人は覚えておくとよいと思います。

本書を読むまではmanはコマンドの意味を調べるもの、という理解でしたが、実際は更に協力なものでした。ちょっとTIPS的な要素ですが、man asciiと打つとアスキーコード表が出てきます。

Linux世界を構成する3つの概念とは

ファイルシステム

プロセス

ストリーム

Linux世界はこの3つの概念によって成立しています。つまりLinuxプログラミングを理解するためにはこの3つの概念をよく理解しなければならないということです。そしてそれことが本書の目的です。*2

ストリームとは

ファイルディスクリプタで表現され、read()またはwrite()で操作できるもののこと(p82)

STDIO,STDOUT
ネットワーク
ファイル

などを抽象化したインターフェースのことです。

ファイルディスクリプタとは

OSがストリームに対して割り当てる番号(int)のこと。この割り当てられたファイルディスクリプタに対して、read(2),wreite(2)を使って入出力を制御します。 read(2)やwrite(2)は引数として操作対象としてフアィルディスクリプタを引数に取ります。

       #include <unistd.h>

       ssize_t read(int fd, void *buf, size_t count);
       ssize_t write(int fd, const void *buf, size_t count);

open(2)でストリームを作成し、ディスクリプタを得る。close(2)でストリームを破棄する。

stdioとFILE型

C言語にはファイルディスクリプタをラップし、内部でバッファ管理している標準ライブラリがあります。それがstdioです。

       #include <stdio.h>

       size_t fread(void *ptr, size_t size, size_t nmemb, FILE *stream);

       size_t fwrite(const void *ptr, size_t size, size_t nmemb,
                     FILE *stream);

unistd.hのread(2),write(2)等はUNIXのシステムコールであり、なるべく移植性が高いstdioの関数を使うように本書に記されています。

read()やwrite()は基本的にはUNIXのシステムコールであり、ほかのOSでも存在するとは限りません。しかし、fread()やfwrite()はC言語の標準関数ですから、より多くの環境で使えることが期待できるのです。(p121)

stdioではファイルディスクリプタではなく、それをラップしたFile型を使います。

File型からファイルディスクリプタを得るにはfileno(3)を使います。逆にファイルディスクリプタからFile型を作るにはfdopen型を使います。

以下のプログラムではSTDOUTにはファイルディスクリプタ=1がデフォルトで割り当てられていますが、こちらをラップしたFILE型を作ってfwriteで書き込みを行っています。

#include<stdio.h>
#include<unistd.h>
#include<string.h>

int main(){
                 FILE *stdout_file = fdopen(STDOUT_FILENO,"r+");
                 char *hello = "hello world\n";
                 fwrite(hello,strlen(hello),1,stdout_file);
}

ヘッダファイルは必要になったときに書けば良い。無理して関数とヘッダファイルの対応は覚えなくてOK

大学時代はstdlibはとりあえず書いとけ、みたいな雑な教え方をされた覚えがある。プログラムを写経して覚えるスタイルだと、そんなかんじで最初に書くことになるのがヘッダファイルのインクルードになるが、これから各プログラムに何が必要で、それを予め書いておくというプログラミングスタイルに固執する必要はなさそうだと思いました。

manを見れば必要なヘッダファイルはかいてありますから、コードを書いていて新しいAPIが必要になった時点でmanを参照すればいいのです。関数とヘッダファイルの対応をう躍起になって覚える必要はありません。記憶力はもっと有意義なところに使いましょう(p93)

Linuxやlibcに足りないものが沢山見えてくる。

printf()が濫用される理由

これはちょっとした雑学ですが。

printf()はフォーマット付きの出力用のAPIなのですから、 HelloWorldプログラムのようにフォーマット機能が必要ないときに、printf()を使う必然性はないはずです。それでも何かとprintf()が使われています。このようにprintf()が乱用されるのは「標準出力に文字列をそのまま出力するAPIがstdioにないことが原因でしょう。fputs()だと標準入出力を明示的に指定しないといけませんし、puts()だけだと改行が内化されるのが邪魔です。(p118より)

コマンドライン引数のフォーマットに統一性がない。

古いunixのコマンドなどは前述のgetopt(3)を使わずに自前で引数をパースしているものも多いようです。そのようなツールでは一般的なコマンドライン引数の扱いとは違ったルールで動作している可能性があります。本書では今linuxツールを作るならgetoptを利用することを推奨しています。

例外処理の仕組み

これは本書に書かれていることではありませんが、自分の感触です。

erronoを使った例外処理なんかはAPI自体がグローバル変数を強要してくる作りになっていて、あまり綺麗なAPIになっていないと思いました。*3

ディレクトリツリーの標準規格FHS(The FilesystemHierarchy Standard)

読む動機となった/usr/localなどのフォルダ役割についてのまとめ。ディレクトリツリーの標準規格から、主要なディレクトリとその用途。主に９章の内容をまとめたもの

/                   # ルートディレクトリ。bin,etc,dev,proc,sysあたりがまともな動作に必須
├── bin           # ブートするときに必要なコマンド
├── boot          # カーネルのプログラム
├── dev           # デバイスファイル
├── etc           # マシンごとの設定ファイル
├── lib           # ライブラリ置き場(ディストリビューションが管理)
├── proc          # プロセスファイル
├── sbin          # (ブート時も必要となる)管理者用コマンド
├── sys           # デバイスやデバイスドライバの情報 
├── tmp           # 一時ファイルやリカバリファイル
├── usr           # NFSで共有する前提のものを置く。(単ノード利用前提は/var配下に)
│   ├── bin      # コマンド(ディストリビューションが管理)
│   ├── include  # システムのヘッダファイル    
│   ├── local    # ユーザーが管理しても良い。(/usr直下はディストリビューション管理)
│   │   └── bin # コマンド(ユーザーが管理)
│   ├── sbin     # 管理者用コマンド
│   ├── share    # ドキュメント。(manやinfo)
│   │   └── man # manページ。roff形式
│   └── src      # linuxカーネルのソースなどのシステムが使うコード置き場
└── var           # 頻繁に書き換えるファイル・複数マシンで共有しないファイル等
    ├── log       # サーバープロセスのログ
    ├── spool     # メールやプリンタの入力
    └── run       # 起動中のサーバープロセスのPIDファイル
    └── tmp       # 一時ファイルやリカバリファイル

感想

本書はC言語文法の解説などはほとんど書かれておらず、全くの初心者向け、というわけではありませんし、ライブラリの中の実装などを詳しく説明するなどもないため、上級者向けというわけでもありません。自分のようにOSやC言語の本を適当に読み漁り、中途半端に知識はついているが基礎が出来ていない人にちょうどいいのかなと思います。本書は割と細かく丁寧に書かれており、printfに辿り着くまでに100ページ以上あるので、それが我慢できない人にはおすすめしません。

C言語の入門書を１冊読み終わった人
Linuxを仕事で使い始めた人

あたりにおすすめです。

というわけで全く新しく知ること、はあまり書かれていませんでしたが、過去の経験の蓄積からなんとなく、そうなんだ、こういうふうになっているんだ、と思い込んでいた事象について、はっきりと仕組みの解説などが書かれていて、いい加減な知識を補強する土台のようなものが出来、安心することができました。個人的にはmanコマンドを引く癖がついたのが一番でかい収穫だと思います。

Linuxのユーザーとしてはまだまだ知識が足りない気がする。LPICの勉強でもすればいいのかな。

次に読む本

シェルスクリプト書けないとやっていけないよ、とのことなので

入門UNIXシェルプログラミング―シェルの基礎から学ぶUNIXの世界

作者: ブルース・ブリン,Bruce Blinn,山下哲典
出版社/メーカー: ソフトバンククリエイティブ
発売日: 2003/02
メディア: 単行本
購入: 18人クリック: 331回
この商品を含むブログ (64件) を見る

*1:紹介システムパフォーマンスとか

*2:p5の1.1本書の概要より引用

*3:この仕組みはマルチスレッド化した際に利用できなくなるケースがあるらしい

2019-04-12

time(2)を使って手軽に実行時間、メモリ最大使用量、CPU利用率を知りたい

time(2)コマンドには2種類あります。

bash組み込みのtimeコマンド
gnuのtime

gnuのtimeコマンドはcpu使用率や平均メモリ利用量、最大メモリ使用量などを計測することができます。デフォルトの出力フォーマットが見にくいですが、利用者が独自フォーマットを定義して必要な情報のみを選択する事ができます。

FORMATTING THE OUTPUT

%	A literal `%'.
C	Name and command line arguments of the command being timed.
D	Average size of the process's unshared data area, in Kilobytes.
E	Elapsed real (wall clock) time used by the process, in [hours:]minutes:seconds.
F	Number of major, or I/O-requiring, page faults that occurred while the process was running. These are faults where the page has actually migrated out of primary memory.
I	Number of file system inputs by the process.
K	Average total (data+stack+text) memory use of the process, in Kilobytes.
M	Maximum resident set size of the process during its lifetime, in Kilobytes.
O	Number of file system outputs by the process.
P	Percentage of the CPU that this job got. This is just user + system times divided by the total running time. It also prints a percentage sign.
R	Number of minor, or recoverable, page faults. These are pages that are not valid (so they fault) but which have not yet been claimed by other virtual pages. Thus the data in the page is still valid but the system tables must be updated.
S	Total number of CPU-seconds used by the system on behalf of the process (in kernel mode), in seconds.
U	Total number of CPU-seconds that the process used directly (in user mode), in seconds.
W	Number of times the process was swapped out of main memory.
X	Average amount of shared text in the process, in Kilobytes.
Z	System's page size, in bytes. This is a per-system constant, but varies between systems.
c	Number of times the process was context-switched involuntarily (because the time slice expired).
e	Elapsed real (wall clock) time used by the process, in seconds.
k	Number of signals delivered to the process.
p	Average unshared stack size of the process, in Kilobytes.
r	Number of socket messages received by the process.
s	Number of socket messages sent by the process.
t	Average resident set size of the process, in Kilobytes.
w	Number of times that the program was context-switched voluntarily, for instance while waiting for an I/O operation to complete.
x	Exit status of the command.

(man 2 timeから抜粋)

環境変数の$TIMEにフォーマットを登録するか-f optionでフォーマットを指定することができます。

export TIME="time result\ncmd:%C\nreal %es\nuser %Us \nsys  %Ss \nmemory:%MKB \ncpu %P"

もしくは

time -f "time result\ncmd:%C\nreal %es\nuser %Us \nsys  %Ss \nmemory:%MKB \ncpu %P" <command>

実行結果(sleep コマンドを実行しています)

$ /usr/bin/time sleep 1
time result
cmd:sleep 1
real 1.00s
user 0.00s 
sys  0.00s 
memory:2128KB 
cpu 0%

2019-04-06

gdbを使ってsegmentation faultを調べる

gdb デバッグ

いきなりsegmentation fault (core dump)と端末に表示されて異常終了をするプログラムに頭を悩まされていました。

...(順調に処理中)...
/home/yuyabu/3d/bin/02.sh: 42 行: 58161 浮動小数点例外   (コアダンプ) openMVG/Linux-x86_64-RELEASE/openMVG_main_IncrementalSfM -i result/sfm_data.json -m matches -o out

C/C++でLinuxな環境であり、かつ自分で作ったファイルまたはオープンソースなどでバイナリに対応したファイルが用意できれば、gdbを使ってエラーが発生している箇所がわかるかもしれません。

ちなみに今回の対象ソースはOpenMVGという3Dを処理するOSSです。

1.core fileが作成されるように設定する

Unix系のOSではプログラムが異常終了したときにメモリなどの情報を「corefile」として吐き出す機能があります。こちらはデフォルトの状態では出力サイズが制限されており作成されないようになっているので、ulimit -c unlimitedで corefileを無制限に作成できるように設定します。

 ulimit -a
core file size          (blocks, -c) unlimited
data seg size           (kbytes, -d) unlimited
scheduling priority             (-e) 0
file size               (blocks, -f) unlimited
pending signals                 (-i) 4124107
max locked memory       (kbytes, -l) unlimited
max memory size         (kbytes, -m) unlimited
open files                      (-n) 1024
pipe size            (512 bytes, -p) 8
POSIX message queues     (bytes, -q) 819200
real-time priority              (-r) 0
stack size              (kbytes, -s) 8192
cpu time               (seconds, -t) unlimited
max user processes              (-u) 4124107
virtual memory          (kbytes, -v) unlimited
file locks                      (-x) unlimited

これでcoredump発生時に実行時のカレントディレクトリにcorefileが作成されるようになります。

2.セグメンテーションフォルトが発生するプログラムをDEBUGビルドする

エラーが発生しているバイナリのソースをデバッグビルドしますデバッグビルドができるようなオプションをつけてビルドツールを実行してください。こちらは調査対象のアプリやビルドツールによって色々なので各自調べてください。

今回私が調査したopenMVGの場合は以下ビルド方法の「3.Configure and build」のオプション-DCMAKE_BUILD_TYPEをRELEASEからDEBUGに変えるだけです。

github.com

$ cmake -DCMAKE_BUILD_TYPE=DEBUG ../openMVG/src/
$ cmake --build . --target install

3.gdbで調べる

gdb <実行バイナリ> <corefile>

gdb ../build/openMVG/Linux-x86_64-DEBUG/openMVG_main_IncrementalSfM ./core 
GNU gdb (Ubuntu 8.1-0ubuntu3) 8.1.0.20180409-git
Copyright (C) 2018 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from ../build/openMVG/Linux-x86_64-DEBUG/openMVG_main_IncrementalSfM...
done.

warning: core file may not match specified executable file.
[New LWP 58245]
...(略)...
[New LWP 58268]
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Core was generated by `/home/yuyabu/3d/build/openMVG/Linux-x86_64-DEBUG/openMVG_main_IncrementalSf'.
Program terminated with signal SIGFPE, Arithmetic exception.
#0  0x000055dc1f18c7e6 in Eigen::internal::gebp_kernel<double, double, long, Eigen::internal::blas_data_mapper<double, long, 0, 0>, 12, 4, false, false>::operator() (this=0x7f2af88ccf0c, res=..., blockA=0x7f2af88cd340, blockB=0x7f2af88cd3a0, rows=3, depth=0, cols=3, alpha=-1, strideA=0, strideB=0, offsetA=0, offsetB=0)
    at /home/yuyabu/3d/src/openMVG/src/third_party/eigen/Eigen/src/Core/products/GeneralBlockPanelKernel.h:926
926       const Index actual_panel_rows = (3*LhsProgress) * std::max<Index>(1,( (l1 - sizeof(ResScalar)*mr*nr - depth*nr*sizeof(RhsScalar)) / (depth * sizeof(LhsScalar) * 3*LhsProgress) ));
[Current thread is 1 (Thread 0x7f2af88ce700 (LWP 58245))]
(gdb)

backtraceを取って該当の処理がどこから呼ばれたのか？ということもある程度わかります。

(gdb) bt
#0  0x000055dc1f18c7e6 in Eigen::internal::gebp_kernel<double, double, long, Eigen::internal::blas_data_mapper<double, long, 0, 0>, 12, 4, false, false>::operator() (this=0x7f2af88ccf0c, res=..., blockA=0x7f2af88cd340, blockB=0x7f2af88cd3a0, rows=3, depth=0, cols=3, alpha=-1, strideA=0, strideB=0, offsetA=0, offsetB=0)
    at /home/yuyabu/3d/src/openMVG/src/third_party/eigen/Eigen/src/Core/products/GeneralBlockPanelKernel.h:926
#1  0x000055dc1f2ef74a in Eigen::internal::triangular_solve_matrix<double, long, 2, 2, false, 1, 0>::run (size=3, otherSize=3, _tri=0x7f2af88cdb30, triStride=3, _other=0x7f2af88cdd00, otherStride=3, blocking=...) at /home/yuyabu/3d/src/openMVG/src/third_party/eigen/Eigen/src/Core/products/TriangularSolverMatrix.h:324
#2  0x000055dc1f3214ef in Eigen::internal::triangular_solve_matrix<double, long, 1, 1, false, 0, 1>::run (size=3, cols=3, tri=0x7f2af88cdb30, triStride=3, _other=0x7f2af88cdd00, otherStride=3, blocking=...) at /home/yuyabu/3d/src/openMVG/src/third_party/eigen/Eigen/src/Core/products/TriangularSolverMatrix.h:32
#3  0x000055dc1f36ef5a in Eigen::internal::triangular_solver_selector<Eigen::Transpose<Eigen::Matrix<double, 3, 3, 1, 3, 3> const> const, Eigen::Matrix<double, 3, 3, 1, 3, 3>, 1, 1, 0, -1>::run (lhs=..., rhs=...) at /home/yuyabu/3d/src/openMVG/src/third_party/eigen/Eigen/src/Core/SolveTriangular.h:102
#4  0x000055dc1f36cf13 in Eigen::TriangularViewImpl<Eigen::Transpose<Eigen::Matrix<double, 3, 3, 1, 3, 3> const> const, 1u, Eigen::Dense>::solveInPlace<1, Eigen::Matrix<double, 3, 3, 1, 3, 3> > (this=0x7f2af88cd4e0, _other=...) at /home/yuyabu/3d/src/openMVG/src/third_party/eigen/Eigen/src/Core/SolveTriangular.h:179
#5  0x000055dc1f36ad71 in Eigen::TriangularViewImpl<Eigen::Transpose<Eigen::Matrix<double, 3, 3, 1, 3, 3> const> const, 1u, Eigen::Dense>::solveInPlace<Eigen::Matrix<double, 3, 3, 1, 3, 3> > (this=0x7f2af88cd4e0, other=...) at /home/yuyabu/3d/src/openMVG/src/third_party/eigen/Eigen/src/Core/TriangularMatrix.h:511
#6  0x000055dc1f368157 in Eigen::LLT<Eigen::Matrix<double, 3, 3, 1, 3, 3>, 2>::solveInPlace<Eigen::Matrix<double, 3, 3, 1, 3, 3> > (this=0x7f2af88cdb30, bAndX=...) at /home/yuyabu/3d/src/openMVG/src/third_party/eigen/Eigen/src/Cholesky/LLT.h:496
#7  0x000055dc1f366674 in Eigen::LLT<Eigen::Matrix<double, 3, 3, 1, 3, 3>, 2>::_solve_impl<Eigen::CwiseNullaryOp<Eigen::internal::scalar_identity_op<double>, Eigen::Matrix<double, -1, -1, 1, -1, -1> >, Eigen::Matrix<double, 3, 3, 1, 3, 3> > (this=0x7f2af88cdb30, rhs=..., dst=...) at /home/yuyabu/3d/src/openMVG/src/third_party/eigen/Eigen/src/Cholesky/LLT.h:476
#8  0x000055dc1f3653de in Eigen::internal::Assignment<Eigen::Matrix<double, 3, 3, 1, 3, 3>, Eigen::Solve<Eigen::LLT<Eigen::Matrix<double, 3, 3, 1, 3, 3>, 2>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_identity_op<double>, Eigen::Matrix<double, -1, -1, 1, -1, -1> > >, Eigen::internal::assign_op<double, double>, Eigen::internal::Dense2Dense, void>::run (dst=..., src=...)
    at /home/yuyabu/3d/src/openMVG/src/third_party/eigen/Eigen/src/Core/Solve.h:147
#9  0x000055dc1f364a1d in Eigen::internal::call_assignment_no_alias<Eigen::Matrix<double, 3, 3, 1, 3, 3>, Eigen::Solve<Eigen::LLT<Eigen::Matrix<double, 3, 3, 1, 3, 3>, 2>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_identity_op<double>, Eigen::Matrix<double, -1, -1, 1, -1, -1> > >, Eigen::internal::assign_op<double, double> > (dst=..., src=..., func=...)
    at /home/yuyabu/3d/src/openMVG/src/third_party/eigen/Eigen/src/Core/AssignEvaluator.h:836
#10 0x000055dc1f363a90 in Eigen::PlainObjectBase<Eigen::Matrix<double, 3, 3, 1, 3, 3> >::_set_noalias<Eigen::Solve<Eigen::LLT<Eigen::Matrix<double, 3, 3, 1, 3, 3>, 2>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_identity_op<double>, Eigen::Matrix<double, -1, -1, 1, -1, -1> > > > (this=0x7f2af88cdd00, other=...)
    at /home/yuyabu/3d/src/openMVG/src/third_party/eigen/Eigen/src/Core/PlainObjectBase.h:728
#11 0x000055dc1f362cbd in Eigen::PlainObjectBase<Eigen::Matrix<double, 3, 3, 1, 3, 3> >::PlainObjectBase<Eigen::Solve<Eigen::LLT<Eigen::Matrix<double, 3, 3, 1, 3, 3>, 2>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_identity_op<double>, Eigen::Matrix<double, -1, -1, 1, -1, -1> > > > (this=0x7f2af88cdd00, other=...)
    at /home/yuyabu/3d/src/openMVG/src/third_party/eigen/Eigen/src/Core/PlainObjectBase.h:537
#12 0x000055dc1f361f70 in Eigen::Matrix<double, 3, 3, 1, 3, 3>::Matrix<Eigen::Solve<Eigen::LLT<Eigen::Matrix<double, 3, 3, 1, 3, 3>, 2>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_identity_op<double>, Eigen::Matrix<double, -1, -1, 1, -1, -1> > > > (this=0x7f2af88cdd00, other=...) at /home/yuyabu/3d/src/openMVG/src/third_party/eigen/Eigen/src/Core/Matrix.h:379
#13 0x000055dc1f360df1 in ceres::internal::InvertPSDMatrix<3> (assume_full_rank=true, m=...) at /home/yuyabu/3d/src/openMVG/src/third_party/ceres-solver/internal/ceres/invert_psd_matrix.h:60
#14 0x000055dc1f389aaf in ceres::internal::SchurEliminator<2, 3, 6>::Eliminate (this=0x7f2af88cdcb0, A=0x7f2af88cdd60, b=0x55dc208c71f0, D=0x55dc20595f50, lhs=0x7f2af88cdb40, 
    rhs=0x55dc1f38b360 <ceres::internal::SchurEliminator<2, 3, 6>::ChunkDiagonalBlockAndGradient(ceres::internal::SchurEliminator<2, 3, 6>::Chunk const&, ceres::internal::BlockSparseMatrix const*, double const*, int, Eigen::Matrix<double, 3, 3, 1, 3, 3>*, double*, double*, ceres::internal::BlockRandomAccessMatrix*)+552>)
    at /home/yuyabu/3d/src/openMVG/src/third_party/ceres-solver/internal/ceres/schur_eliminator_impl.h:273

参考: qiita.com

なおデバッグビルドしたバイナリがなくても-cオプションでcorefileだけでgdbを起動できます。

$man gdb
...(略)
OPTIONS
...(略)
       -core=file
       -c file
           Use file file as a core dump to examine.

ただし関数名などがわからないのでアドレスみたらわかるマンじゃないときついと思います。

$ gdb -c core
・・・(略)
[New LWP 58268]
Core was generated by `/home/yuyabu/3d/build/openMVG/Linux-x86_64-DEBUG/openMVG_main_IncrementalSf'.
Program terminated with signal SIGFPE, Arithmetic exception.
#0  0x000055dc1f18c7e6 in ?? ()
[Current thread is 1 (LWP 58245)]

2019-04-03

約2年間続いた読書会で「プログラマのためのSQL」を読み終わりました

勉強会日記

本日がラスト39回目で最終回。翻訳者のミックさんが参加され翻訳者後書きを読んでもらえました。非常に感慨深いものがありました。

初回が2017年3/1で二年と１ヶ月、全39回で読み終わりました。私は15回から参加しています。ちなみに私は目黒バイナリ勉強会で参加数2位のようです。(一位は@quwaharaさん)

meguro-binary-study.connpass.com

会場は中目黒でした。寒いためか花見客が少なかった？そうです。

打ち上げ。シリコンバレーのエンジニア事情などの話題で盛り上がりました。

本書について

プログラマのためのSQL 第4版

作者: ジョー・セルコ,Joe Celko,ミック
出版社/メーカー: 翔泳社
発売日: 2013/05/24
メディア: 大型本
この商品を含むブログ (16件) を見る

本書はSQLをメインテーマに書かれた和書で最も分厚いと思います(多分)。

本書に掲載されているクエリからはこんなこともできるのか!と感じさせるほどSQLの威力が存分に発揮されていますが、一方でSQLの利用はデータ取り出しにとどめておいて、複雑なことは専用のミドルウェアやアプリでやるべきという主張も読み取れます。普段書かないようなクエリを通してSQLとは何か？に迫る本書はSQLの入門マニュアルでも百科事典でもなく、SQLのエッセンスに迫れる数少ない一冊であると思います。特にNullについて書かれている13章はSQLに関わる全エンジニアにお勧めです。

プログラマのためのSQLでは