Database Management Systems 読書メモ

http://pages.cs.wisc.edu/~dbbook/の読書メモ。

Chapter 1

データベースマネージメントシステム(DBMS): データベースを維持・活用するためのソフトウェア。自前でアプリケーションに固有のプログラムを書いてファイルにデータを読み書きすることがDBMSを使わない場合にあたる。

1.1

リレーショナルDBMS: 今日のDBMSのタイプの中で最も主流なタイプ。

1.2

DBMSの歴史について。

1.3

DBMSを使わない場合は主記憶のサイズ、並行にアクセスされた場合の対処、システムのクラッシュに対する安全性、セキュリティーの確保などが問題となる。

1.4

DBMSを使う場合にユーザーはデータの表現の細部を気にしないで良い、効率的かつ安全にデータにアクセスできる、不変項を課すことができる。

1.5

データモデル: データの保存法などの低級な詳細事項を捨象したもので、relational data modelを基にしたものが今日では最も使われている。
セマンティックデータモデル: データモデルをさらに抽象化したもので、entity-relationshipモデル(ERモデル)が広く使われている。

1.5.1

relation: レコードの集合と考えてよい。
スキーマ: データをデータモデルで説明したもの。

Students(student-id: string, name: string, age: integer)

が例。
関係モデル - Wikipedia
階層型データモデル - Wikipedia
オブジェクトデータベース - Wikipedia

1.5.2

スキーマはexternalスキーマ、conceptualスキーマ、physicalスキーマと三つの段階に抽象化されて表現される。このうちexternalスキーマとconceptualスキーマはdata definition language(DDL)により規定される。

externalスキーマ: conceptualスキーマで定義された関係から計算できる外部に見せるものを定義。
conceptualスキーマ(logical スキーマ): エンティティと関係からなる。何をrelationとして保存するか。
physicalスキーマ: indexの付けかたなど。どうrelationを保存するか。

1.5.3

データの独立性について。

1.6

クエリ言語・データマニピュレーション言語について。

1.7

トランザクション: DBMSでユーザープログラムが一回走ること。

複数のトランザクションはそれらがシリアルに実行された時と等価になるように実行される。

1.7.1

ロック。

1.7.2

不完全なトランザクション・システムのクラッシュ。
DBMSは副作用の前にログに書き込む(Write-Ahead-Log)。また復旧の時間を削減するためにcheckpointを作成する。

1.8

DBMSの構造。

1.9

DBMSに関与する人。

Chapter 2

2.1

実体関連モデル - Wikipedia
データベースをデザインする際の6ステップ
2:semanticを決める。
3:logical(conceptual) schemaを決める。
4:schemaを改良
5:physical schemaを決める。

2.2

entity: 個別の物。Aさん。
entity set: 類似のentityをまとめたもの。Employeesなど。

entityは複数のattributesにより記述される。entity set中のentityは全て同一のattributeの組を持つ。

key: attributesの部分集合でentityをユニークに決定する最小のもの。
primary key: keyを一つ選んだもの。ERダイアグラムでは下線を引く。

2.3

relationship: 「Aさんは部局Bで働く」
relationship set: relationshipをまとめたもの。Works_inなど。

relationshipはentityのタプルとして表現される。relationshipもattributesを持ち得る(descriptive attributes)。relationshipはそのentityのみにより一意に定められる。(attributeだけが異なるrelationshipは作成できない。)

2.4

2.4.1

key constraints: A(entity set)がB(relationship set)に関してkey constraintsを課せられている時、Aのentityを要素にもつBのrelationは高々1つ(0もある)。ERダイアグラムでは矢印。

2.4.2

total participation: A(entity set)の任意のentityがB(relationship set)のあるrelationの要素である。ERダイアグラムでは太線。
partial participation: total participationでない。

2.4.3

weak entity set: weak entity setであるA(entity set)はkeyを持たず、Aの中のentityはAのあるattribute(partial key)とB(relationship set)のrelation内の別のentityのprimary keyによって一意に決まる。AはBに関してkey constraintsを課され、Bにtotal participateする。ERダイアグラムでAとBは太線で囲まれる。Aのattributeは破線で下線される。

2.4.4

継承

2.4.5

Aggregation: entityだけでなくrelationshipを要素にもつrelationshipを許す。

2.5

2.5.1

relationshipはそのentityのみにより一意に定められるため、attributeだけが異なるrelationshipは作成できない。
entityはattributesより細かく情報を記述できる。

2.5.2

2.5.3

この本ではweak entity setのidentifying relationshipはBinaryでなければならない。
Ternaryなrelationship setに関するkey constraintsはBinaryの時より制約が強い。

2.5.4

Aggregationを使わないと論理的に表現しづらい事項がある。

2.7

UMLとは何か？
統一モデリング言語 - Wikipedia

2.8

「attributeだけが異なるrelationshipは作成できない」を守らないデザインのまま次の章へ

Exercise 2.2

http://users.cis.fiu.edu/~vagelis/classes/COP4540/slides/COP4540%20MidtermReview.ppt
6番は直接TeacherがTeachesに結ばれているとダメなのでGroupを経由させる。

Exercise 2.3

http://pages.cs.wisc.edu/~cs564-1/ans3ed-oddonly.pdf

Chapter 3

relational model: relational modelではデータベースはrelationを集めたもの
relation: テーブルで表現できる

3.1

relation: relation schemeとrelation instanceからなる。
relation instance: テーブル
relation schema: テーブルの列情報の記述
an instance of relation: レコード（タプル）。relation instanceのテーブルの列はan instance of relationとなる。

3.1.1

SQLの簡単な説明
SQLite入門
CREATE, INSERT, DELETE, UPDATE
テーブルを作成する | SQLite入門
 データの追加(INSERT文) | SQLite入門
 データの更新(UPDATE文) | SQLite入門
 データの削除(DELETE文) | SQLite入門

3.2

DBMSはIntegrity Constraints(IC, 一貫性制約)が保たれるようにする。

3.2.1

key constraint: relationのfieldの部分集合でタプルを一意に指定するものがある制約。

key constraintが課せられていればrelationが同一のタプルを含むことはない。

primary key: keyの候補から一つprimary keyを選ぶ事が出来る。primary keyを指定するとタプルを参照する際の効率が向上する。

SQLでは「UNIQUE」を使いあるfieldの部分集合がkeyであることを宣言し、「PRIMARY KEY」を使いprimary keyを指定する。
UNIQUE制約の使い方 | SQLite入門
 PRIMARY KEY制約の使い方 | SQLite入門

3.2.2

foreign key: あるrelationのfieldの部分集合Sが他のrelationの部分集合（keyでなくても良い）であるとき、Sをforeign keyとする。

SQLでは「FOREIGN KEY」を使い指定。
FOREIGN KEY制約(外部キー制約を設定する) | MySQLの使い方

3.2.3

より一般的な制約を課す事ができる。

3.3

制約を保つ。
DBMSは制約を破るような変更を拒否する場合が多い。
あるrelation Aのforeign keyが指す別のrelationのタプルが削除される場合は、Aの対応するタプルを削除・変更する場合もある。
SQLでは「FOREIGN KEY」内で「ON DELETE」や「ON UPDATE」を指定。
FOREIGN KEY制約(外部キー制約を設定する) | MySQLの使い方

3.3.1

http://www.sqlite.org/foreignkeys.html#fk_deferred

3.4

データの取得(SELECT文) | SQLite入門
「FROM」の後に複数テーブルを指定するSELECT

SELECT * FROM A, B WHERE A.i = B.i

3.5

entity-relationship modelからrelational model(SQL)への変換。
entity setはtableに、relationship setはkey constraint及びparticipationの種別により独立したtableもしくはentity setと融合したtableとして表現する。
NOT NULL制約の使い方 | SQLite入門
weak entity setはprimary keyにforeign keyを含むようにし、on deleteをcascadeに
継承はサブクラスのみをrelationとするか、親クラスのprimary keyをサブクラスが保持するかして表現。後者の方がより適用範囲が広い。
Aggregationもrelationship setと同様に表現するが、participationの種別によりAggregationの対象となるrelationship setと融合する。

3.6

view: 保存はされないがその場で計算されるテーブル

ビューを作成する | SQLite入門
viewはlogical data independenceを保つために使用できる。また非公開の情報を隠すためにも使用できる。
viewに対するupdateやinsertが定義される場合もある。

3.7

テーブルを削除する | SQLite入門
 ビューを削除する | SQLite入門
 (移設しました)
テーブル名の変更とカラムの追加 | SQLite入門

Chapter 4

4.2

関係代数
http://mlab.cb.k.u-tokyo.ac.jp/~moris/lecture/www-database-cb/query-4-11-2005.pdf

$\sigma_{condition}$: フィルター
$\pi_{column names}$: 射影
$\times$: クロス積, 列名が重複する列はUnnamedにされる。
$\cup$: ユニオン
$\cap$: インターセクション
$-$: 差
$\triangleright\triangleleft{}_{condition}$: Condition join.

$A \triangleright\triangleleft{}_{c} B$
は
$\sigma_{c}(A \times B)$
と等価。

$\triangleright\triangleleft{}_{x = y}$: Equijoin. 同じ値を持つ列が存在するので落とされる
$\triangleright\triangleleft$: Natural join. 同じ名前を持つ列全てが等しい条件でEquijoin.
$/$: division.

$A/B$
は
$\pi_x(A) - \pi_x((\pi_x(A) \times B) - A)$
と等価。

$\delta$: 重複の除去

4.2.6

関係代数でのクエリの例

4.3

関係計算
関係論理 - Wikipedia
tuple relational calculusとdomain relational calculus.

4.4

関係代数と関係計算の表現力
関係計算は無限集合を返したりsafeでない場合がある。safeな関係計算の表現力は関係代数の表現力と等しい。

relationally complete: あるquery language Qが関係代数によるクエリを表現できるときQはrelationally complete.

Chapter 5

SQL: Structured Query Language

5.1

Data Manipulation Language
Data Definition Language
一貫性制約
C言語からランタイムにクエリを作り実行するなど
リモートアクセス
トランザクションの管理
セキュリティ

5.2

データ

create table Sailors(sid integer primary key, sname text, rating integer, age real);
create table Boats(bid integer primary key, bname text, color text);
create table Reserves(sid integer, bid integer, day text, primary key(sid, bid, day), foreign key(sid) references Sailors(sid), foreign key(bid) references Boats(bid));
insert into Sailors values(22, 'Dustin', 7, 45.0);
insert into Sailors values(29, 'Brutus', 1, 33.0);
insert into Sailors values(31, 'Lubber', 8, 55.5);
insert into Sailors values(32, 'Andy', 8, 25.5);
insert into Sailors values(58, 'Rusty', 10, 35.0);
insert into Sailors values(64, 'Horatio', 7, 35.0);
insert into Sailors values(71, 'Zorba', 10, 16.0);
insert into Sailors values(74, 'Horatio', 9, 35.0);
insert into Sailors values(85, 'Art', 3, 25.5);
insert into Sailors values(95, 'Bob', 3, 63.5);
insert into Boats values(101, 'Interlake', 'blue');
insert into Boats values(102, 'Interlake', 'red');
insert into Boats values(103, 'Clipper', 'green');
insert into Boats values(104, 'Marine', 'red');
insert into Reserves values(22, 101, '10/10/98');
insert into Reserves values(22, 102, '10/10/98');
insert into Reserves values(22, 103, '10/8/98');
insert into Reserves values(22, 104, '10/7/98');
insert into Reserves values(31, 102, '11/10/98');
insert into Reserves values(31, 103, '11/6/98');
insert into Reserves values(31, 104, '11/12/98');
insert into Reserves values(64, 101, '9/5/98');
insert into Reserves values(64, 102, '9/8/98');
insert into Reserves values(74, 103, '9/8/98');

5.2.1

distinctの効果

sqlite> select distinct sname, age from Sailors;
...
Rusty|35
Horatio|35
...
sqlite> select sname, age from Sailors;
...
Rusty|35.0
Horatio|35.0
Zorba|16.0
Horatio|35.0
...

sqlite> select s.sid, s.sname, s.rating, s.age from Sailors as s where s.rating > 7;
31|Lubber|8|55.5
32|Andy|8|25.5
58|Rusty|10|35.0
71|Zorba|10|16.0
74|Horatio|9|35.0
sqlite> select s.sname, t.sname from Sailors as s, Sailors as t where s.rating > 8 and t.rating < 2;
Rusty|Brutus
Zorba|Brutus
Horatio|Brutus
sqlite> select * from Sailors, Sailors;
SQL error: ambiguous column name: Sailors.sid
sqlite> select * from Sailors, Reserves where Sailors.sid = 74 and bid = 101;
74|Horatio|9|35.0|22|101|10/10/98
74|Horatio|9|35.0|64|101|9/5/98
sqlite> select sid from Sailors, Reserves;
SQL error: ambiguous column name: sid

SELECT [DISTINCT] C1, C2, ..., Cn FROM R1, R2, ..., Rm WHERE condは、
$[\delta]\left(\pi_{C1, C2,\cdots, Cn}\left(\sigma_{cond}\left(R_1 \times R_2 \times \cdots \times R_m\right)\right)\right)$
と解釈できる。

5.2.2

列名・WHEREにexpressionを指定。ASは省略可能。

sqlite> select sname, rating / age as rate_per_year from Sailors where rate_per_year * 10 > 5;
Zorba|0.625

データを取得する(SELECT文) | MySQLの使い方
 パターンマッチングで比較(LIKE句) | SQLite入門

5.3

UNION, INTERSECT, EXCEPT
別々に取得したデータを結合して取得する(UNION句) | MySQLの使い方

sqlite> select sid from Reserves, Boats where Reserves.bid = Boats.bid and color = 'red'
   ...> intersect
   ...> select sid from Reserves, Boats where Reserves.bid = Boats.bid and color = 'green';
22
31

デフォルトで重複が除かれる。重複を除かないためには「UNION ALL」などとする。

5.4

ネストしたクエリ
IN, EXISTS, UNIQUE, op ANY(op SOME), op ALL,
指定した値のリストと比較する(IN演算子) | MySQLの使い方

sqlite> SELECT S.sid FROM Sailors S WHERE S.sid IN
   ...> (SELECT R.sid FROM Reserves R);
22
31
64
74
sqlite> SELECT S.sid FROM Sailors S WHERE EXISTS
...> (SELECT R.sid FROM Reserves R WHERE R.sid = S.sid);
22
31
64
74

サブクエリを使った検索条件の設定 | MySQLの使い方
 サブクエリを使った検索条件の設定 | MySQLの使い方
 http://www.dbonline.jp/mysql/select/index23.html

5.5

Aggregate
指定したカラムまたはテーブル全体の行数をカウント(count関数) | SQLite入門
 指定したカラムに含まれる値の合計を取得(sum関数, total関数) | SQLite入門
 指定したカラムに含まれる値の平均を取得(avg関数) | SQLite入門
 指定したカラムに含まれる値の最大値と最小値を取得(max関数, min関数) | SQLite入門

sqlite> SELECT AVG(age), MAX(age), MIN(age), COUNT(*) FROM Sailors AS S;
36.9|63.5|16.0|10

データをグループ化する(GROUP BY句) | MySQLの使い方
 グループ化したデータを取得する条件を設定する(HAVING句) | MySQLの使い方
 sql - HAVING ANY and HAVING EVERY - Stack Overflow
GROUP

5.6

NULL
値がNULLのものを取得(IS NULL句) | SQLite入門
NOT NULL制約
NOT NULL制約(カラムにNULLの格納を許可するかどうか) | MySQLの使い方
 テーブルの結合 | SQLite入門
(LEFT|RIGHT) OUTER JOIN

sqlite> SELECT DISTINCT Sailors.sname FROM Sailors NATURAL JOIN Reserves NATURAL JOIN Boats WHERE Boats.color = 'red';
Dustin
Lubber
Horatio

5.7

CHECK制約の使い方 | SQLite入門

CREATE DOMAIN: CHECK付きのドメイン.互換性のある型との演算は制約されない。
CREATE TYPE: 他の型との演算が制約される型

CREATE ASSERTION

5.8

trigger: INSERTやUPDATE,DELETEの際に自動で実行されるコマンドを決定できる。再帰的なtriggerも存在する。

トリガーの作成 | SQLite入門

Chapter 6

Chapter 7

Chapter 8

8.1

ディスクからページ(4KB,8KB,...)を単位としてデータが読み込まれる。
物理的に連続したページからの読み込みは相対的にコストが低い。
ファイル中のレコードはrecord idを持つ。ridによりそのレコードを含むページを特定できる。

8.2

heap file: unordered file
index: 取得操作を最適化するためのデータ構造

indexはいくつも作る事が出来る。search keyに基づいて取得する。

data entry: indexに保存された情報

data entryとして

データそのものを保存する
ridを保存する
ridのリストを保存する

と三種類の方法が存在。

8.2.1

clustered: data entryと実際のデータの並び順がほぼ等しいこと

実用上は(1)の方法のみがclustered fileで、(2),(3)はunclustered。

8.2.2

primary index: search keyとしてprimary keyを含む
secondary index: primary keyを含まないindex

とこの本では定義。
(1)の方法をprimary、(2),(3)をsecondaryと呼ぶ流儀もあり。

unique index: searh keyに関してduplicatesがないindex

8.3.1

Hash based indexing

8.3.2

Tree based indexing
B+木 - Wikipedia

8.4

データ構造の比較
(P.291)

heap file 空間使用量が効率的・挿入が速い
sorted file
clustered B+ tree file 等号条件、範囲条件での検索が速い・最大一つのindexしかclusteredにできない
heap file with unclustered B+ tree index　等号条件での検索が速い・index-onlyでない範囲条件での検索が遅い
heap file with unclustered hash index　等号条件での検索が速い・範囲条件での検索が遅い

8.5

インデックスとパフォーマンス
clusteredかunclusteredによりパフォーマンスが大きく変わる。
条件に適合するレコードの割合によりパフォーマンスが大きく変わる。
index-only evaluationでは実際のレコードにアクセスする必要がないので、unclusteredなindexでも速い場合がある。

composite search keys: indexのkeyとして二つ以上のフィールドを使用。index-only evaluationのチャンスは増えるが、updateやdeleteに時間がよりかかるように。

Chapter 9

9.1 9.2

計算機の記憶の階層的構造・RAID

9.3

disk space managerによるハードウェアとOSの隠蔽・ページの管理
pageはディスクのblockと同じサイズ

9.3.1

空きスペースの管理

リストを作る
bitmapを作る

9.3.2

OSにdisk spaceをmanageさせる選択肢もある。同一ファイルの中を連続して読めばたいてい連続したblockを読むことになる。

OSへの依存度が高まる
OSの機能の制限が波及する

9.4

buffer management

buffer: 主記憶中のページを置くための場所
frame: pageが入るスロット

buffer managerのおかげで、上層のコードはメモリ中にpageがあるかどうか、pageに対する副作用がディスクに反映されるかを気にしないでよい。
参照カウント(pin count)と副作用が入ったかを確認するビット(dirty bit)により管理。
WALの遂行
ロックは上層コードの責任。

9.4.1

buffer replacement policy

Least Recently Used
Most Recently Used
FIFO
Random
Clock

どれも一長一短

9.4.2

OSの仮想メモリとの比較
自前のbuffer managerは、

今後どういったアクセスがあるか把握できるために、OSの仮想メモリより効率がよい。またWrite Ahead Loggingを遂行できる。
prefetchできる。(prefetch中にはCPUは別のことをできる)
ディスクに変更をforceできる。

9.5

9.5.1

heap fileの実装

二重リンクリスト
ディレクトリ（ビットマップ）

9.6

pageの構造
recordをたくさん持つ。

record id
slot: レコードを入れるいれもの

9.6.1 固定長レコード

空きスペースをどう管理するか

先頭に詰める
bitmap

9.6.2

page中へのポインター（オフセット）+レコード長をディレクトリ方式で管理

削除の際ridを変えられない場合はディレクトリからエントリを削除できない。
ridを変えていい場合は、ディレクトリのポインタをいじるだけで並び替えができる。

9.7

recordの構造
固定長のデータは先頭に、可変長のデータはポインターとしておく。ポインターはnullを効率的に扱える。
可変長のデータの問題点

サイズが変更によって大きくなることがある。
（さらに）ページからあふれる。

ページからあふれ、またridを変えられない場合、転送先のページを確保してそこにレコードを置く。
ページより大きいレコードは分割されLinkedListになる。

Chapter 10

ISAM

leaf pageにのみdata entryが蓄えられる。insertionはleafからのびるLinked Listに。primary leaf pageの数は固定。データのサイズが静的な場合に良い。non-leaf-pageは変更されないためロックが単純。Linked Listは連続的に確保できる（のでアクセスが効率的）。

B+ Tree

挿入と削除のアルゴリズム

キーの圧縮

Treeの高さをなるべく小さくするためにnon-lead pageでのキーは大小関係が調べられるだけの情報を残して、他は削除してよい。

Bulk Loading

あらかじめ存在するデータのコレクションに対して、B+ Treeのインデックスを作る際に使う。
まず対応するdata entryをソートする。それから小さいものから順に挿入する。挿入順が仮定できるのでより速く挿入できる。

・

可変長のレコードが存在するため、実際には木の次数は動的に決定する。
clustered indexの場合、挿入・削除に応じてridが変化するので他のindexのアップデートを要する。

Chapter 11

Static Hashing

Extendible hashing - Wikipedia

ハッシュ値の下2bit->3bit->4bitというふうにバケツが溢れて分割されるごとにテーブルを広くする。

Linear hashing - Wikipedia

Chapter 12

スキーマはそれ自体がrelationとしてsystem catalogに登録される。

index nested loop join
sort merge join
pushing selections
pipelining

Chapter 13

外部ソート

Blocked IO: 連続して取得する方が早い
Double Buffering: IO中にソート
B木を使ったソート: ClusteredかUnclusteredによって速度に大きな違い