lasciva blog

開発して得た知見やwebビジネスのストック

「リレーショナルデータベース入門」を読んだ

全体の感想

DBの本格的な入門書としては、今まで読んだ中では一番良かったように感じた。ただ個人的には、出会うタイミングには恵まれなかった。
最初の方は集合論から始まり、データを効率よく操作したり、表現するにはどのようなものでなければならないかについて言及されていた。中盤からはRDBの種類に関係なく一般的なDBMSがどのような仕組みなのか、クエリーを投げてからデータの読み込み、書き込みが行われるまでにどのような処理が行われているのかについて説明されていた。クエリの処理に必要なコストの計算方法なども紹介されており、joinやindexが内部でどのように処理されるのかも説明されていた。
クエリーを投げてから、内部でどのように処理が行われているのか理解できていない人にはオススメ。

目次

概要

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

2.1 本章のはじめに

データモデルは次の3要素から成り立っている。

  • 構造記述
  • 意味記述
  • 操作記述

2.9 空

「Interim Report ANSI/X3/SPARC Study Group on Data Base Management Systems」によると14種類の意味がある。

  1. Not valid for this individual
  2. Valid, but does not yet exist for this individual
  3. Exists, but not permitted to be logically stored
  4. Exists, but not knowable for this individual
  5. Exists, but not yet logically stored for this individual
  6. Logically stored, but subsequently logically deleted
  7. Logically stored, but not yet available
  8. Available, but understanding change (may be no longer valid)
  9. Available, but of suspect validity (unreliable)
  10. Available, but invalid
  11. Secured for this class of conceptual data
  12. Secured for this individual object
  13. Secured at this time
  14. Derived from null conceptual data (any of the above)

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

3.3 リレーショナル代数

  • 集合演算
    • 和集合演算
    • 差集合演算
    • 共通集合演算
    • 直積演算
  • リレーショナル代数に特有の演算
    • 射影演算
      • 属性を選択できる
    • 選択演算
      • 比較可能な任意の2つの属性の条件から、行を選択できる
      • 定数との比較は、定数の属性を追加して、それと比較することで実現される
    • 結合演算
      • ざっくり言うと、joinのこと
    • 商演算
      • 例えば、供給元と部品のリレーションから、ある部品の集合を供給する供給元のリレーションを生成するなど

3.5 リレーショナル代数演算の拡張

選択演算を満たすために、比較可能である必要がある。そこで、nullを導入するためには3値論理を導入する必要がある。

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

リレーショナル代数とリレーショナル論理は等価であると知られている。

いずれかを満たす時、リレーショナル完備という。

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

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

  • 概念スキーマ: 記号で表現される
  • 内部スキーマ: DB内部の実装方法(ISAMファイル、B+木など)
  • 外部スキーマ: ビューなど、ユーザの様々な要求に応えるために、DB空間を個別に生成する機能

6.4 3層スキーマの意義

物理的データ独立性と論理的データ独立性を担保できる。

6.5 DBMSの3大機能

6.6 リレーショナルDBMSのメタデータ管理

メタデータ自身もテーブルのスキーマとして定義して管理されている。

dev.mysql.com

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

8.4 ファイル編成とアクセス法

8.4.1 ファイル編成
  • ヒープ編成
    • 2次記憶に書き込まれた時刻順にレコードを順番付ける
    • 大量の挿入を高速に行える
    • 線形探索なので、レコードが多いと時間がかかる。また、虫食いブロックが多発して使用効率が悪くなってしまうので、記憶管理が必要になる
  • 順次編成
    • キーの順番で連続するように保存する
    • 高速にアクセスできる
    • レコードの削除、更新などの度にソートし直さなければならない
  • 直接編成
    • hash編成ともいい、キーをハッシュ関数に施して位置を決定する
    • 高速にアクセスできる
    • rangeクエリーが非効率
8.4.2 アクセス法
  • 順次アクセス法
  • インデックス法
  • ハッシュ法

8.6 インデックス法

8.6.1 インデックスとは何か

順序フィールド上にインデックスを張る場合、以下の2種類が定義できる。

  • 密集インデックス: すべての順序フィールド値が出現する
  • 点在インデックス: 一部のみ。アクセスする際は、近い値にアクセスしてから走査してたどり着く。データ量は小さくてすむが、パフォーマンスは良くない。
8.6.2 ISAM

インデックス付順次アクセス法(Indexed Sequential Access Method)

8.7 B+木

多段インデックスで、葉ノードは次のキーのポインタも保持しているので、range queryにも対応できる。平衡を保とうとするので、挿入、削除のコストは低くない。

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

9.3 質問処理とそのコスト

9.3.1 コスト式

C = Ci/o + ω x Ccpu

  • C: 質問を処理するコスト
  • Ci/o: 質問を処理するためにフェッチしたページの総数。さらにインデックスとデータに分解できる。
  • Ccpu: 質問を処理するために費やしたCPU使用率
  • ω: CPU使用率をページ数に換算するための重み係数
9.3.3 結合質問処理とそのコスト式
  1. 入れ子型ループ結合法とコスト式
# R: アウタ表, S: インナ表
for each t in R
    for each t` in S
  such that t[B] t`[B]
  compute t * t`
end
  1. ソートマージ結合法とコスト式
    • 結合列で2つのテーブルのレコードをソートして、そこから順次に先頭から一致するものを結合させる。
    • 一般には、入れ子型ループ結合法よりも高速に処理が行える。
      • ソートした結果、インナ表Sが順次編成ファイルとなるので、高速に読み出せるから
  2. ハッシュ結合とコストの計算式
    • 小さい方のテーブルをハッシュに変換して、そのハッシュに大きい方のテーブルで順次に参照する

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

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

ある値を複数のバージョンを保持して、トランザクションに応じたtimestampのバージョンを返す

11.6 SQLの隔離性水準

  • READ UNCOMMITTED
  • READ COMMITTED
  • REPEATABLE READ
  • SERIALIZABLE

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

12.4 分散型質問処理

12.4.3 準結合演算

異なるサイトにあるテーブルを結合するとき、結合に必要な属性だけ先に渡し、最終的に必要な行の他の属性を再度取得する。こうすることで、データの転送量を減らすことができる。