Zenn
Open15

増永良文著「リレーショナルデータベース入門」の読書メモ

glassonion1glassonion1

データベーススペシャリスト試験の勉強のために購入

増永良文著「リレーショナルデータベース入門: データモデル・SQL・管理システム・NoSQL」を読んで学んだことのメモ。
https://amzn.to/4d3mEjr
データベーススペシャリスト試験の対策本にもリレーショナル理論の説明があるが数学的に厳密に書かれているわけではないので説明が曖昧でわかりにくい。リレーショナル理論について数学的に厳密に説明がされている本を読んで勉強を進める。

集合論の事前学習が必要

この本を読み進めるにあたって集合論の知識が必要になる(集合論の知識0で本書を読むのは非常に勿体無い)。集合論については以下の書籍で事前学習済み
https://amzn.to/3MCwzSu

グラフ理論の知識があるとなお良い

第11章トランザクションの同時実行制御を読むにあたりグラフ理論の知識があったほうがよい。無向/有向グラフ、巡回/非巡回あたりの用語がわかる程度でよい。

glassonion1glassonion1

第1章: データベースとは何か

全体的に座学中心。P2の情報とデータの違いは重要。

glassonion1glassonion1

第2章リレーショナルデータモデル

リレーションの定義。ドメイン、リレーション名と属性名、基本的な用語の定義が多い。第1正規形の定義は冪集合を理解してないと辛いかも。キー制約まわりの説明も集合を使って説明されている。曖昧さがないのでとてもわかりやすい。

重要ポイント

2.3 リレーション

直積集合の概念についての理解が重要

2.4 属性名とリレーション名

特に定義2.2の理解が重要、4章に出てくる各種定理の理解の基本となる定義なのでここが曖昧だと後々辛くなる。

[定義2.2] (属性名とリレーション名を使ったリレーションの定義) Rをリレーション名、A_1, A_2,...,A_nを属性名、domをドメイン関数とするとき、リレーションR(A_1, A_2,...,A_n)は直積dom(A_1)\times dom(A_2)\times \dots\times dom(A_n)の有限部分集合である。

2.6 第1正規形

正規化の出発点となるものなのでしっかり理解をしておくこと

2.7 主キーとキー制約

候補キーが重要

glassonion1glassonion1

第3章リレーショナルデータベースのデータ操作言語

集合はデータの重複がない。これはSQLと大きく違うところ。データの重複を考慮しなくて良いのは楽だなと感じた。

重要ポイント

3.3 リレーショナル代数

8つの集合演算、試験でもよく問われるやつなんでひとつ残らず理解すること。商演算は特に理解するのが難しいが数学的に厳密に説明があるので対策本でなんとなく理解するよりも理解しやすい。
リレーショナル代数は慣れればわりと書けるようになる。SQLよりも記述が簡単なので良い。

3.6 リレーショナル論理

リレーショナル論理(タップルリレーショナル論理とドメインリレーショナル論理)
リレーショナル論理は述語論理で問い合わせを書くのでむずい。

3.7 リレーショナル代数とリレーショナル論理の等価性

表現方法は違うけど同じ事象について表現できる。

glassonion1glassonion1

第4章リレーショナルデータベースの設計論理

この章で難易度がだいぶ上がる。再び第1正規形が出てくる。更新時異状の解説と情報無損失分解がポイント。

重要ポイント

4.4 リレーション(スキーマ)の情報無損失分解

P82、情報無損失分解から自然結合を使って再びデータを元の状態に戻している説明がとても良かった。自然結合がなんたるか本質をついた説明だと感じた

[命題 4.1] R\subseteq R_1 * R_2 が常に存在する

4.5 多値従属性

P85、多値従属性を使って情報の無損失分解の基本定理が展開されている。
多値従属性の定義

[定義4.2]（多値従属性）リレーションスキーマR(A_1,A_2,...,A_k,B_1,B_2,...,B_l,C_1,C_2,...,C_m)の任意のインスタンスRが、その2つの射影R[A_1 A_2\cdots A_k B_1 B_2\cdots B_l]とR[A_1 A_2\cdots A_k C_1 C_2\cdots C_m]に情報無損失分解されるとき、及びそのときのみRに多値従属性A_1 A_2\cdots A_k \twoheadrightarrow B_1 B_2\cdots B_lが存在するという

情報無損失分解の基本定理

[系 4.1] リレーションスキーマR(A_1,A_2,...,A_k,B_1,B_2,...,B_l,C_1,C_2,...,C_m)の任意のインスタンスRが、2つの射影R[A_1 A_2\cdots A_k B_1 B_2\cdots B_l]とR[A_1 A_2\cdots A_k C_1 C_2\cdots C_m]に情報無損失分解されるための必要かつ十分条件は
Rに多値従属性
A_1 A_2\cdots A_k \twoheadrightarrow B_1 B_2\cdots B_l
が存在すること

多値従属性のこの\twoheadrightarrow矢印が全射の矢印と同じだと気づいた(多値従属性って全射なのかな。いや違うか)。

4.6 関数従属性

関数従属性は多値従属性の特殊な形態。関数従属性はリレーションの情報無損失分解の十分条件を与える、これが地味に重要(高次正規形で起こる問題に関連している)。多値従属性よりもわかりやすい概念であり、第2正規形からボイスコッド正規形までは関数従属性に着目して正規化していくので多値従属性よりも関数従属性の理解を優先した方が良い。

4.7 アームストロングの公理系と多値従属性の公理系

アームストロングの公理系の証明まで理解できたかは怪しいがこのアームストロングの公理系がなんで必要かはなんとなく理解できた。
陽に宣言された(自明でない)関数従属性の集合Fはアームストロング公理の反射律、添加律、推移律を適用すれば、全てを過不足なく導出することができる。という理解をした。
はじめ閉包の意味が全然わからなくてかなり苦労した。別の本ではあるがこの説明がわかりやすかった。

（データベース実践講義・117ページ）
従来の算術において数値閉包が重要であることと同様の理由により、閉包はリレーショナ ルモデルでも重要である。ただし、従来の算術では、閉包が正しく作用しない状況が 1 つ ある。それは、ゼロによる除算である。リレーショナル代数にも似たような状況が存在するか。
データベース実践講義

多値従属性の公理系は推移律が若干特殊だった。

4.8 関数従属の諸性質

Xの閉包X^+を計算する問題。X^+を求めるアルゴリズムからの候補キーを求める方法について理解するのが重要。Fの極小被覆を求める問題も重要、リレーションから自明でない関数従属を洗い出すにあたり無駄な関数従属を取り除くためのアルゴリズムという理解。
X^+を求めるアルゴリズムの理解が重要、特にステップ2の再帰処理の数式が重要
X^{(i)}=X^{(i-1)}\cup \{A|A\in Z\land Y \to Z\in F\land Y\subseteq X^{(i-1)}\}(i\geq 1)

4.9 - 4.11 第2正規形、第3正規形、ボイスコッド正規形

第2正規形からボイスコッド正規形(BCNF)までの正規化は関数従属性に着目して分解していく。

正規形 説明
第2正規形分解 候補キーの一部から非キー属性への関数従属を取り除く
第3正規形分解 非キー属性から非キー属性への関数従属(推移的関数従属)を取り除く
BCNF分解 非キー属性から候補キーへの関数従属を取り除く

BCNF分解が関数従属性保存ではない問題、「関数従属性はリレーションの情報無損失分解の十分条件を与える」という性質と関係している。BCNF分解により情報の無損失分解はできるものの関数従属性が保存されないという問題が発生する。

4.12 第4正規形

多値従属性型をつかった正規化。リレーション、フライト(フライト番号, クルー名, 乗客名)の例。フライト番号\twoheadrightarrowクルー名 | 乗客名の多値従属性に注目する。第4正規形分解は自明でない多値従属性を取り除く作業。

4.13 第5正規形

リレーションから結合従属性を取り除く作業。リレーション R(X, Y, Z) を3つの射影 R[X, Y], R[Y, Z], R[Z, X] に分解する。R[X, Y], R[Y, Z] ではないというのがポイント。

4.14 合成的手法によるリレーショナルデータベース設計

第3正規形より高次な正規形は関数従属性が保存されなくなるという問題がある。
バーンシュタインが示した合成的手法は第3正規形、関数従属性保存、情報無損失分解を保持したデータベース設計ができる。以下はリレーションSCT(学生名, 科目名, 教員名), F=\{\{学生名, 科目名\}\to 教員名, 教員名\to 科目名\}の例

BCNF 合成的手法
SCT[学生名, 教員名]
SCT[教員名, 科目名]		 SCT[学生名, 科目名, 教員名]
SCT[教員名, 科目名]
合成的手法はデータに冗長性があることを許容するのがポイント。これにより更新時異常を防ぐことができる。
glassonion1glassonion1

第5章SQL

5.6 入れ子型質問

相関を有する入れ子型質問(いわゆる相関幅問い合わせ)。SQL流のスループ処理

glassonion1glassonion1

第6章データベース管理システムの標準アーキテクチャと機能

ANSI/X3/SPARK 3層アーキテクチャの解説

6.3 ANSI/X3/SPARKのDBMSの3層スキーマ構造

  • 概念スキーマ(実リレーション)
  • 内部スキーマ(RDBの実装空間)
  • 外部スキーマ(ビュー、仮想データベース)

6.5 DBMSの3大機能

  • メタデータ管理
  • 質問処理
  • トランザクション管理
glassonion1glassonion1

第7章ビューサポート

ビューはANSI 3層スキーマの外部スキーマに当たる

7.3 論理データ独立性の達成のためのビューサポート

7.4 ビューの更新問題と論理的データ独立性

実務でビューを更新することはほとんどないんだけど、試験で頻出するやつ

7.7 マテリアライズドビュー

データ分析でよく使う。ビューはデータ実態がないがマテリアライズドビューはデータ実態がある。検索パフォーマンスに優れているがデータが冗長になるなどトレードオフがある

glassonion1glassonion1

第8章ファイル編成とアクセス法

内部スキーマの話

8.2 物理的データの独立性

物理的データの独立性は常に達成される。ビューサポートによる論理的データの独立性の達成は限定的(更新問題などがあるため)だったので対照的。

8.6インデックス法

ISAMの説明。非平衡木、レコードによってツリーの深さがちがう。

8.7 B+木

ISAMとのちがい。両方とも多段インデックスであるが、ISAMは非平衡木、B+木は平衡木。レコードの更新や削除時のツリーの再編集処理はISAMよりも重い。

8.8 ハッシュ法

静的ハッシュと動的ハッシュ。

glassonion1glassonion1

第9章リレーショナルDBMSの質問処理とその最適化

SQLは非手続的。一般的なプログラミング言語と違う特徴。リレーショナルDBMSが処理コスト最小の内部スキーマレベルの手続的コードを生成する。

9.2 質問処理とその最適化

質問処理とはユーザが発したクエリをリレーショナルDBMSが処理して所望の結果を返すこと。4段階に分けて処理をする.

  • SELECT文の解析
  • 最適化
  • 内部スキーマレベルのオブジェクトコードの生成
  • オブジェクトコードを実行し導出表を返す

9.3 質問処理とそのコスト

質問処理のコスト算出方法。3つの算出方法がある。

  • 単純質問
  • 結合質問
  • 入れ子質問

9.3.3結合質問処理とそのコスト式

結合処理をナイーブに実装すると直積になる。直積はバカみたいに処理コストが高いから避けたい。結合質問の最適化手法として以下3つがある。

  • 入れ子ループ法
  • ソートマージ法
  • ハッシュ結合法(ただし等結合のみ)

試験で頻出の話題なので押さえておくこと。

glassonion1glassonion1

第10章トランザクションと障害回復

リレーショナル理論の理解と同じくらい大事な話題といえばこれ。ACID特性の深く理解すること。

10.3 ACID特性

  • 原子性(Atomicity)
  • 一貫性(Consistency)
  • 隔離性(Isolation)
  • 耐久性(Durability)

10.4 トランザクション指向の障害時回復

障害の分類。REDOとUNDOがどの障害のときにどのように実行すべきか理解すること。

  • トランザクション障害
  • システム障害
  • メディア障害

システム障害の理解が重要。システム障害とはDBMSやOSの障害でシステムが暴走したりフリーズしたり、ハードウェアの誤作動や電源断で揮発性の主記憶上のデータが消えて、システムを再スタートしないといけない状況に陥る場合をいう。2次記憶のデータは残っている。UNDO/REDOや後に出てくるチェックポイントなんかはシステム障害時にどうするかという話である。

10.5 ログ法

WAL(Write Ahead Log)。2次記憶に書き込む前にログに書き込む。

10.5.3 コミット時点

コミットをしてもデータが2次記憶に書き込まれる保証はない(OSの仕事、DBMSは制御できない)。DBMS
的にはコミット時にログにデータ書き込まれたことをもってコミット完了とみなす。これをコミット時点という。ログへの書き込みが完了していれば、2次記憶にデータが書き込まれていなくても障害復旧処理でデータを復元できるからログ書き込みを持ってデータ永続化されたとみなして良い。

10.5.5 チェックポイント法

障害復旧の効率化のための仕組み。チェックポイント以前のトランザクションはデータベースへのデータ書き込みが保証されているので、システム障害が起きてもログから復旧する必要がない。

glassonion1glassonion1

第11章トランザクションの同時実行制御

11.2 同時実行制御の必要性

複数のトランザクションが一つのデータベースを共有しながら同時に無秩序に実行されると様々な異状が発生する。

  • 遺失更新異状
  • 軽い/重い汚読異状
  • 反復不可能な読みによる異状
  • 不整合検索異状

11.3 スケジュールの直列化可能性

11.3.2 トランザクションの同時実行とスケジュール

同時実行(concurrent execution)の「同時」とはconcurrent(並行)でありparallel(並列)ではない。つまりある時刻tに着目すると実行されているのはある一つのトランザクションのあるステップだけで複数のトランザクションの複数のステップが並列実行されているわけではない。

11.3.4 スケジュールの等価性と正当性、そして直列化可能スケージュール

スケージュールが等価とは

[定義11.2] (スケジュールの等価性) スケージュールSとS'が等価であるとは、S(DB_0)=S'(DB_0)がいかなるデータベースの初期状態DB_0についても成立するときをいう。

トランザクションを複数同時実行させつつデータベースの一貫性を損なわない実行スケジュールを直列化可能スケジュールという。あるスケジュールS(非直列スケジュール)が与えられた時、Sに等価な直列化可能スケジュールは存在するか。

  1. 最終状態直列化可能性
  2. ビュー直列化可能性
  3. 相反直列化可能性

1は正当ではない。2は正当ではあるがNP完全(多項式時間で解けるアルゴリズムが存在しない)、2の制約を強めて正当かつ効率的なアルゴリズムを求める必要がある。3は2の制約を強めて効率的なアルゴリズムを求めたもの。

11.3.7 相反グラフ, そして相反等価と相反直列化可能性

相反グラフを作成すればスケージュールの直列化可能性を静的に判定することができる(相反グラフ解析)。
相反グラフが全然理解できなかったけどこの動画観て理解できた。有向辺を張って巡回したら競合直列可能ではない(要するにデッドロックするってこと)。有向グラフの巡回=デッドロック。
https://youtu.be/DBiM0ranCbM?si=WlftZ-Mdbj7vis5T
以下の定理が重要

[定理11.1] スケジュールSの相反グラフCG(S)が非巡回なら、Sはビュー直列化可能である。このとき、Sにビュー等価な直列スケジュールはCG(S)をトポロジカルソートすることにより得られる。

盲目的書きとスケジュールの直列化可能性

相反グラフ解析の注意点として、定理11.1の逆は成立しないということ。ビュー直列化可能であれば非巡回かといえばそうではない。トランザクションが盲目的書きである場合(データの書き込みにデータの読み込みを前提としない)にこの状態になる。相反グラフが非巡回であることはスケジュールがビュー直列化可能であるための充分条件に過ぎない。

制約的書きとスケジュールの直列化可能性

盲目的書きを許さない=制約的書きという条件をつけると必要かつ十分条件になる。制約的書きという条件のもとビュー直列化可能であれば非巡回であるといえる。

[定理11.3] トランザクションに制約的書きしか許さなければ、スケジュールがビュー直列化可能であるのはそれが相反直列化可能であるとき、及びそのときのみである。

以下が成立する。
制約的書き \land ビュー直列化可能 \leftrightarrow 相反直列化可能

11.4 ロック法

スケジュール法は静的な同時実行制御。トランザクション実行前にスケジュールを立てるのではなく時間の経過とともにトランザクションステップをあるプロトコルに従って実行させるアプローチ。
動的同時実行制御プロトコルの種類

  • ロッキングプロトコル
  • 時刻印順序プロトコル(分散データベース)
  • 楽観的制御法
  • 多版同時実行制御法

11.4.3 2相ロッキングプロトコル

すべてのトランザクションにおいて読み書きのために必要な全てのロックが完了する以前にそれらがアンロックされることはない。トランザクションが必要なデータ項目をどんどんロックしていく段階を第1相(成長相)、一方不要となったデータ項目をどんどんアンロックしていく段階を第2相(縮退相)という。
2PLに従ってトランザクションを同時実行していく限り、相反直列化可能性を保証する。

11.4.4 デッドロック

デッドロック=待ちグラフが循環する。デッドロック防止法、トランザクションに時刻印を付与する。

  • 待つ-死ぬ方式
  • 傷つける-待つ方式
    アボートされたトランザクションは再実行される。

11.4.5 ロッキングプロトコルの効率改善

共有ロックと専有ロック、データを読み込むときは共有ロック、データを書き込むときは専有ロックする。共有ロックは書き込みを禁止する。専有ロックは読み込みと書き込みを禁止する。ロッキングプロトコルの効率改善のための仕組み(TPS向上)。

11.5 多版同時実行制御(MVCC)

同じデータ項目の異なる版を用意することによってトランザクションの隔離性を向上させ、同時実行性を高める。

11.6 SQLの隔離性水準

下にいくほど隔離性水準が高い。

  • READ UNCOMMITTED
  • READ COMMITTED
  • REPEATABLE READ
  • SERIALIZABLE

SERIALIZABLE水準よりも低い水準に設定すると次の3つの異常が段階的に発生する

  • 汚読(ダーティーリード)
  • 反復不可能な読み
  • 幽霊(ファントム)

SERIALIZABLE

直列化可能。2PL+述語ロックで実現可能。述語ロックとはSQLのWHERE句(SELECT/UPDATE)の条件に該当する行をロックすること。述語ロックは充足可能性問題(NP完全)があり実装はわりと大変。

REPEATABLE READ

2PLで実現可能。2PLだけだとファントムが発生する可能性がある。

READ COMMITTED

2PLの実装を緩めて、共有ロックのかかった行について読み込みが完了したらすぐにアンロックする。ファントム及び反復不可能な読みが発生する可能性がある。

READ UNCOMMITTED

2PLの実装をさらに緩めて、専有ロックのみ行う。ファントム及び反復不可能な読み、汚読が発生する可能性がある。

MVCCと隔離性水準

SQLの隔離性水準はロック法を念頭に策定された。MVCCを採用した場合SQLの隔離水準のどのレベルを実現できるか。MVCCにぴたりとあった隔離性水準はない。研究の結果スナップショット隔離性という水準が明らかにされている。スナップショット隔離性はREAD COMMITTEDよりは強い水準だがREPEATABLE READとは強弱を比較的ない性質がある。スナップショット隔離性では書き込みスキューと読み取り専用トランザクション異状が発生する。直列化可能スナップショット隔離性はこれらの異状を排除して直列化可能にする。

glassonion1glassonion1

第12章分散型データベース管理システム

分散型データストア(NoSQL)の話題とは違うので注意。CAP定理とかBASE特性はあとのNoSQLで出てくる。実務においてそこまで重要な話題ではない(内容的に古い)から用語だけ押さえておけば良いかな。ややこしい用語があるので混同したいために用語を押さえておく。

透明性の達成

  • 位置に対する透明性
  • 分割に対する透明性
  • 複製に対する透明性

分散型質問処理

分散型データベースの結合処理

  • 分散型入れ子型ループ結合法
  • 分散型ソートマージ結合法
  • 準結合演算

分散型トランザクション管理

2相コミットプロトコル。2相ロッキングプロトコルとは別の概念。ややこしいので注意。

  • 第1相、投票相
  • 第2相、決定相
glassonion1glassonion1

第13章クライアント/サーバコンピューティングとデータベース

これも今時クラサバでシステム構築することは稀なんで、古臭い内容かなと思ったが、Webで構築する場合でも利用する技術や概念が多かった。

データベースとの接続

ODBC。じつはマイクロソフトの登録商標。データベースドライバの実装。

OLTPとOLAP

OLTPはトランザクション処理が中心、期間業務システムなど。OLAPはデータ分析が中心、多次元データベース。OLAPはコッドが提唱した(意外)、インモンが提唱したデータウェアハウスと同じ。

glassonion1glassonion1

第14章ビックデータとNoSQL

最終章。主にNoSQLについて書かれている。

14.2 ビックデータとは何か

3Vがビックデータを規定する概念として広く受け入れられている

  • Volume
  • Velocity
  • Variety

ビックデータでは通常なら外れ値として排除されてしまうようなデータも含めて網羅的にデータを収集することに意味がある。

14.3 NoSQL

Not Only SQL、データベースはリレーショナルデータベースばかりではないんだよという意味。
NoSQLの分類は以下

  • キーバリューデータストア
  • 列ファミリデータストア
  • 文書データストア
  • グラフデータベース

14.4 CAP定理とBASE特性

この章で一番大事な部分。NoSQLのアーキテクチャは「蘇結合クラスタ」構成をとる。

14.4.2 CAP定理

[定理14.1] (CAP定理)共有データシステムにおいては、整合性、可用性、分断耐性という3つの性質のうち、高々2つしか両立させるができない。

共有データシステムでは以下のうち何れかの選択を迫られる

  1. 分断耐性を放棄する
  2. 可用性を放棄する
  3. 整合性を放棄する

1の選択肢をとったのが従来のデータベースシステム、2の選択肢をとったのがGoogleのBigtable、3の選択肢をとったのがAmazonのDynamoである。NoSQLは2か3のどちらかの選択肢をとることになる(分断耐性を放棄することはない)。Dynamoに限らずキーバリューストア系の製品は大体3の選択肢をとっている。

14.4.3 BASE特性

3つの特性のうち可用性をとる(整合性を放棄する)と、ネットワークの分断がおきた場合クライアントはとにかく接続できるサーバにアクセスして所望の複製されたデータを読み書きすることになる。整合性を放棄するとACID特性を満たせなくなる。この問題を解決するためにNoSQLはACID特性が謳うデータベースの一貫性を捨てて結果整合性という考え方を導入して対処している。
BASEは以下の略

  • Basically Available(基本的に可用)
  • Soft-state(ソフト状態)
  • Eventual consistency(結果整合性)

結果整合性とは現時点では整合性のないデータでも新たな更新要求がなくシステムに障害も発生してなければ全ての複製はいつかは整合するということ。

結果整合性

クライアント側からみたデータの整合性

  • 強い整合性
  • 弱い整合性

強い整合性とはデータの更新が完了したとした時点でその後のどの複製にアクセスしても更新された結果を返してくること。そうでない場合を弱い整合性という。結果整合性は弱い整合性の特殊な場合である。

14.5 ビックデータの管理・運用技術

MapReduceやBigtable、BigQueryについての説明。