【読書メモ1】理論から学ぶデータベース実践入門
奥野幹也, 『理論から学ぶデータベース実践入門』, 技術評論社 を読む。
- 第1章 SQLとリレーショナルモデル
- 第2章 述語論理とリレーショナルモデル
- 第3章 正規形
- 第4章 正規化理論(その2) 結合従属性
- 第5章 リレーションの直交性
- 第6章 ドメインの設計戦略
- 第7章 NULLとの戦い
- 第8章 SELECTはSQLの心臓部
- 第9章 履歴データの問題点
- 第10章 グラフに立ち向かう
- 第11章 インデックスの設計戦略
- 第12章 Webアプリケーションのためのデータ構造
- 第13章 リファクタリングの最適解
- 第14章 トランザクションの本質
- 気づき
- 総括
第1章 SQLとリレーショナルモデル
- リレーショナルモデルにおけるリレーションとは、各属性に対応した値を持つタプルの集合である。
- リレーションから異なるリレーションを計算する集合演算が和、積、直積、結合etc...
- リレーショナルモデルにおける結合は内部結合しか存在しえない
- 外部結合ではNULLや重複が発生しえて集合演算として不適切
- リレーショナルモデルにおける結合は内部結合しか存在しえない
クエリ
SELECT
- SELECT (カラムのリスト) FROM (テーブルのリスト) WHERE (検索条件)
- カラムのリストが射影、テーブルのリストが直積、検索条件が制限に対応する演算
- 理論的には直積、制限、射影の順に行われる
INSERT
リレーションは値であるため、タプルを追加して更新、はできない。 テーブルにはRelvar(関係変数)としてあるリレーションの値が割り当てられている。 INSERTで行われているのは、Relvarに新しい値が加わったリレーションを再代入することに相当する。 この一見の混乱は、テーブルが値と変数双方の役割を持つことに由来する
DELETE
DELETEもINSERTと同じ、新しいリレーションの再代入
UPDATE
- 元のリレーションから、WHERE句の条件に適合するタプルを集めた部分リレーションAと残りの部分リレーションBに分ける
- Aに修正を加えたリレーションとBの和集合をRelvarに新しく代入しなおす
SQLとリレーショナルモデルの相違
- 要素の重複 SQLは要素が重複しても許容する
- 要素間の順序 SQLは要素間に行番号で順序を付ける
- トランザクション トランザクションはリレーショナルモデルと関係ない要素
- ストアドプロシージャ 上に同じ
- NULL 集合にはNULLという概念がない
第2章 述語論理とリレーショナルモデル
リレーショナルモデルのベースは一階述語論理
- 述語と集合への所属関係は等価
- リレーションには対応する述語が存在する
- 論理式における
(xが象ならばそれは草食動物である)と集合における包含関係
(象全体は草食動物全体の部分集合である)は等価
データベース内にないデータに関しては閉世界仮説を採用する。「あるタプルが述語を真にする⇔リレーションに含まれている」ことを前提とする
第3章 正規形
正規化理論はリレーショナルモデルを前提としたDB設計理論であり、矛盾・異常の発生を防ぎ、インデックスを効きやすくし(カラム数が絞られNULLが減る)、ストレージを節約する
第1正規形はデータベースがリレーショナルモデルに則っていることを保証する
それ以降のボイスコッド正規形までは、自明でない関数従属性を取り除く作業となる
候補キーとスーパーキー、関数従属性
- 候補キー：タプルを一意に決められる属性の集合のうち、極小であるもの（主キーの「候補」）
- 正規化理論には主キーという概念は存在しない(主観的に決めるもののため)
- スーパーキー：候補キーのスーパーセット。言い換えれば、スーパーキーの極小部分集合が候補キー
- 非キー属性：候補キーに含まれない属性
- 関数従属性：リレーションの見出しの2つの部分集合AとB(つまるところ属性集合)の間の関係であり、Aの値が決まればBの値が決まるとき「BはAに関数従属する」
- 当然発生する自明な関数従属性：
- 任意の属性はスーパーキーに関数従属する
- x, yという属性があったとき、{x}と{y}はそれぞれ{x,y}に関数従属する(部分集合は元の見出しに関数従属する)
- 当然発生する自明な関数従属性：
第1正規形(1NF)
テーブルがリレーションであることを要求する
- 行と列が順序付けられていない
- 実装では順序付けられてしまっているが、クエリで行番号や列番号を使用しないことで再現可能
- 重複する行が存在しない
- 主キーの一意性制約などにより保証する
- 各エントリは、ドメインに属する要素の値をちょうど一つだけ含んでいる(複数の値を持たない)
- SUBSTRINGによる文字列の分解など、データのアトミック性を崩すクエリはこの要件に反する
- 全ての列の値は定義されたものだけであり、かつそれぞれの行において常に存在する
- NULLが存在しないこと
第2正規形
「候補キーの真部分集合から非キー属性への関数従属性が存在しない」状態
第3正規形
「推移関数従属性が存在しない」状態
推移関数従属性：非キー属性から非キー属性への関数従属性。主キー→非キー→非キーと推移的に関数従属しているさまから。
ボイスコッド正規形(BCNF)
「自明でない関数従属性が全て取り除かれた」状態
第3正規形が持ちボイスコッド正規形が持たない関数従属性：非キー属性から候補キーの真部分集合への関数従属性
この場合、非キーの方が豊富な情報を持っているので、候補キーを見直す必要がある。 そうすると第2正規形の要件に反した状態になるので、再び正規化を加えていけばいい。
BCNFまで正規化すれば、以下のケースでは5NFになっている(4NF, 5NFを考える必要があるのは、非キー属性が存在せず候補キーが複数属性からなるパターンのみ)
- 非キー属性が存在する
- キーが単一の属性からなる
第4章 正規化理論(その2) 結合従属性
4NFから6NFまでは自明でない結合従属性を排除する作業になる
結合従属性
複数の見出しの部分集合の射影を取り、対応するリレーションを分割する。それらを再度結合して元のリレーションに戻る性質を結合従属性という。それすなわち情報の無損失分解が可能であること
(例) リレーションRの見出しの部分集合A, Bがあり、射影AとBに対応するリレーションを結合したものとRが一致したとき、結合従属性{A,B}を持つ。
複数の見出しの中にRの見出し全体が含まれた場合は自明に復元できるので、自明な結合従属性。
見出しが全てスーパーキーになっている場合もRを復元可能なので、暗黙的な結合従属性。
第4正規形
多値従属性(A,B,Cに対する結合従属性{AB,AC})が存在しない状態
第5正規形
暗黙的なもの以外のすべての結合従属性(もっともシンプルなのは直積)が存在しない状態
第6正規形
暗黙的なものを含めすべての結合従属性が存在しない状態(複数の非キー属性があればそれらを別リレーションに分解する→全リレーションで非キー属性が0個か1個になる) 分解が多すぎて実用には向かないのでここまではやらないのが基本
第5章 リレーションの直交性
リレーションの直交性とは、リレーション間で重複した値を含まないこと 直交判定には6NFまでの分解が役に立つ(従属性が存在せず各リレーションの値間の必要十分な比較ができるため)
直交化戦略
- 正規化：5NFまで分解しておけば6NFに分解して確認するのが楽
- カラム命名統一：同じ意味の属性が分かりやすい
- アプリケーションの整合性：重複しているとき、それを利用するアプリケーション側も複数個所でデータを参照している可能性があるのでリファクタリング重要
直交性のメリット
- 異常・矛盾の防止
- 複雑な制約が必要なくなる・アプリケーション側の処理も楽になる
- 性能が向上することが多い
- 複雑な制約が必要なくなる・アプリケーション側の処理も楽になる
- 必要なデータの場所が明確になる
第6章 ドメインの設計戦略
諸々
- データ型を選定するにあたり、表示上・利便性上の問題とは別に本質に基づいて選択する
- 数値IDに桁数固定文字列を使うなどは表示に縛られている
- 既にナチュラルキーが存在するときにサロゲートキー(自動発行の恣意的なID)を作成するのは、更新オーバヘッドと新たな関数従属性を生むことから良くない
- IDの一部に意味を持たせるのは1NFに反する
ドメインTIPS
第7章 NULLとの戦い
NULLは値ではない(値が不明であることを示すマーカー)であり、NOT NULLでないカラムを含めた演算はtrueとfalseにNULLを加えた3値論理(3VL, 3 Valued Logic)になる。
NULLのよくないところ
- NULLは閉世界仮説に反する
- NULLが多く存在すると、インデックスの前後に固められるためオプティマイザの効果が減る
NULL対策
- テーブルの正規化
- NOT NULLにしつつデフォルト値を設定してしまう設計には弊害あり
- COUNT以外の集約関数でマッチしなかった場合など、結果にNULLが来うる場合にはCOALESCEを使う
第8章 SELECTはSQLの心臓部
基本知っていたが、標語があったので
- リレーショナルモデルの範疇でできることは、けっしてリレーショナルではない操作で実装しない
- リレーショナルモデルの範疇でうまく記述できないならDB設計を見直す
- リレーショナルでない操作がどうしても必要な場合は、リレーショナルな操作に関するロジックを必ず先に行う
第9章 履歴データの問題点
そも履歴は時系列という順序を持つので、リレーショナルモデルの範疇外。 商品価格の履歴を例にとって考える。
開始時刻、終了時刻をカラムに持たせた場合の問題点
- 現在時刻によってクエリの実行結果が変わる
- 特定の行のみ意味が違う
対策
- 開始時刻のみを持たせた上で、最新の価格に対応するタプルのみ別のリレーションに分割する
- 最新価格の取得はシンプルになるが、外部キーによる整合性管理が利用できずトリガ等が必要
- 最新の価格に対応するタプルを両方のリレーションに重複させる
- サロゲートキー持ちの履歴マスタを作り、そのキーを外部制約として持つ最新価格テーブルと履歴テーブルを持つ
- この方法だとさらに未来価格テーブルも持てる(時間経過によるテーブル間移動はバッチ処理により定期実行するのが吉、ただし厳密なリアルタイム性は成立しえない)
履歴データのアンチパターン
- 最新価格にフラグを立てる
- フラグはカーディナリティが低い(真か偽かの2つしかない)ため検索効率が悪い
- フラグは開始時刻・終了時刻に関数従属しているため冗長で整合性の維持・更新にコストがかかる
- 手続き型として実装する
- リレーショナルモデルで対応しきれない場合の最終手段
第10章 グラフに立ち向かう
グラフはエッジリストで表現するのが典型的だが、SQLはそもそも宣言的でループ処理に向いていないため、複雑な探索はストアドプロシージャに頼る必要がある。 問題の中心がグラフでRDBである必要がないならグラフDBを使うのも良い。
木の表現
- エッジリスト(各nodeにparentを対応付ける 親だけparentがNULL)
- 経路列挙(/a /a/b /a/c /a/c/d みたいに根からのパスで表現)
- 祖先判定は高速だが更新が遅い
- 入れ子集合モデル(各ノードが区間を持ち、包含で祖先関係を表す)
- 更新が複雑で、リレーショナルモデルと全く関係ない数値による管理なのが問題
- クロージャテーブル(祖先関係の組を全列挙する)
- エッジリストから推移的なものも全て加えたもの
- 行数がでかいが祖先判定は速く、リレーショナルモデルと相性がいい
第11章 インデックスの設計戦略
インデックスの種類
- B+木：範囲検索・等価検索
- ハッシュインデックス：等価検索
- 転置インデックス：文字列に対する単語検索
- 関数インデックス：関数評価後の値に対するインデックスを構築可能
- ビットマップインデックス：参照が非常に速くビットマップの更新が遅いためオンライントランザクション処理には向かない
設計順はDBの論理設計→クエリを書く→必要なインデックスを決める
パーティショニング
テーブルを複数のパーティションに分割する方法。検索対象の刈りこみが効く場合に有効になりやすい。
最新データを多く追加するケースでは、レンジパーティショニングを行うことでアクセスの局所性を活かしてキャッシュを利かせやすくなる
一意性制約はインデックスにより保証されるため、パーティショニングを行うとテーブル全体の一意性が保証されなくなる。この際、テーブル全体を対象として追加でグローバルインデックスを構築すると一意性制約を保証できるが性能は落ちる
- 必要なカラムが全て含まれているインデックス(カヴァリングインデックス)を使ったクエリは高速なので、サイズがでかくなっても使う価値はある
- マルチカラムインデックスの効果はOR条件には効きにくい(インデックスマージという実行計画が使われる実装はある)
よくないインデックスの例
- 全カラムにインデックスがある
- マルチカラムインデックスがない
- 多くあるマルチカラムインデックスに同じカラムの組が登場し、しかもすべて同じ順番
- フラグのようなカーディナリティが低いカラムにインデックスがある
第12章 Webアプリケーションのためのデータ構造
キャッシュ
キャッシュを利用することで、複雑さの増大と引き換えにコストのかかる処理を速い処理に置き換えたい。ただし、あくまでデータの論理的な保証はDBで行い、キャッシュは仮置き場としてしか利用しない。
DBのキャッシュとして使えるための要件手続き
- キャッシュミス時の対処法
- キャッシュミス時にDBへ問い合わせる方法
- キャッシュミス時に新たにキャッシュへエントリを追加する方法
- データ更新時にキャッシュと同期する方法
- データ消失時に再構築する方法
- 整合性を確認する方法
キャッシュが可能なデータ
- 頻繁にアクセスされる
- アクセスに偏りがある
- 変更が少ない
- 表示されることが目的
キャッシュの実装方法
- NoSQLをキャッシュとして用いるのはあり。オーバヘッドが少なく、分散処理が得意であるKVSなどはRDBの苦手な部分を補完しえる。
- 集計結果などを別テーブルにキャッシュとして記録するのもあり。トリガやバッチ処理、マテリアライズドビューなどによって更新する。
- 1度の結合も許容できない巨大データには、あらかじめ結合したテーブルをキャッシュに
- 定数個のタグによる検索には、検索用のタグ組み合わせと商品データを合わせたキャッシュテーブルを
スケールアウト
レプリケーション
マスタ：スレーブのDBサーバを1：Nの関係で置き、更新はマスタを介してのみ行う
参照の負荷分散に強いが、更新はマスタに負担がかかる。スレーブとの同期は非同期レプリケーションであり、やや時間差がある。
シャーディング
行ごとに別のサーバに保存する分散方法。更新が高速。レプリケーションと組み合わせるのも典型的。サーバをまたいだクエリの実行が難しく、1つのパーティションキーでテーブルのデータを完全に分けられるケースでのみ利用可能。
第13章 リファクタリングの最適解
手順
- 作業前後のバックアップ
- スキーマの移行
- データの移行
- アプリケーション移行のためのトリガーの作成
- アプリケーションのデプロイ
- 移行のためのトリガーの削除
- 移行のためのカラムの削除
移行期間には、変更前後のテーブルを両方保持し、双方向のトリガにより整合性を維持する必要がある。
その他にも
などを考慮
第14章 トランザクションの本質
トランザクションが達成したいこと
- 同時アクセスを、並列に矛盾が起きないよう捌く→全トランザクションを直列に逐次実行した場合と同じ結果にする
- 更新処理途中のクラッシュに対処する
トランザクションに要求される4事項(ACID特性)
- Atomicity：トランザクションは成功か失敗かの2状態のみ
- Consistency：トランザクションの前後でデータの一貫性が損なわれない(一貫性を定義するのはアプリケーション側で、例えばリレーショナルモデルにのっとっているか)
- Isolation：同時に実行しているトランザクション同士が互いに影響を与えない
- Durability：一度コミットしたトランザクションは消失しない
分離レベル：トランザクションがどれだけ互いに独立しているかを示す概念。分離レベルが低い順に
- READ-UNCOMMITTED：ダーティリードまで許す(コミットされていないデータも読んじゃう)
- READ-COMMITTED：インコンシステントリードまで許す(トランザクションが読み取ったデータの整合性が取れない)
- REPEATABLE-READ：ロストアップデートとファントムリードだけ許す(更新したデータが他トランザクションの影響で消失する/範囲検索中に過去になかったデータアイテムが出現する)
- SERIALIZABLE：異常を一切許さない
SERIALIZABLEが最も安全で、手間とリスクを取ってでも性能が欲しい場合にREAD-COMMITTEDやREPEATABLE-READを用いる
この場合は更新用の明示的なロックにSELECT FOR UPDATEを用いるなどする
気づき
- ORM(O/Rマッパとも)の意味が分かった。Objectがアプリケーション側でのオブジェクト指向的意味でのオブジェクトを指し、Relationがデータベース側のリレーションを意味している。オブジェクトとリレーションを1対1に対応付けるってことね。リレーションの意味がいまいちよく分かっていなかったが、まさにリレーショナルモデルにおける事実の集合≒テーブルだと分かれば難しくない。
総括
前半の主題は、SQL/RDBの立脚するリレーショナルモデルが集合論と述語論理に根差して正当性を保証されていること、それを活かすために可能な限りリレーショナルモデルを意識した運用を心掛けようという主張。
