勉強日記

チラ裏

理論から学ぶデータベース実践入門 ch3 正規化理論(その1)

RDB SQL 開発環境

gihyo.jp

まとめ

  • BCNFまでの知識だけでも威力高い
    • 自動的に5NFまで満たしていることが多い
      • どういう時そうなるのかは次章
    • BCNFでは自明でない関数従属性が存在しない
  • まだ先がある
    • 結合従属性の排除

なぜDB設計は重要なのか

  • データと操作はセット
    • OOP
      • 適切にオブジェクトが設計されていないとメソッドは複雑怪奇に
    • RDB
      • 適切に個々のテーブルが設計されていないとクエリは複雑怪奇に
  • 正規化理論 (Normalization Theory)
    • リレーショナルモデルにおける設計の王道

正規化

リレーショナルモデルを補完する理論

  • リレーショナルモデルそのものの一部ではない
    • 正規化されていなくてもリレーショナルモデル自体は扱える
    • 扱いやすくはない
  • 正規化理論はリレーショナルモデルの上に立脚する補完的な理論

異常を防ぐことができる

  • 異常(Anomalies)
    • 矛盾が生じている状態
  • 矛盾
    • データが論理的な不整合を起こしている状態
  • 矛盾が生じたDBに問い合わせて導き出されたデータは一切信用ならない(前章より)
    • Principle of explosion
  • 矛盾はなぜ生じるの
    • 重複
  • 正規化は重複を排除する

正規形

正規形の種類

  • 第1正規形
  • 第2正規形
  • 第3正規形
  • BCNF
  • 第4正規形
  • 第5正規形
  • 第6正規形

第1正規形(1NF)

  • リレーションであること
    • リレーショナルモデルの世界では当然満足される
    • リレーショナルモデルではなくSQLに対して課される条件
  • つまりどういうこと
    • 行/列が順序付けされていない
      • ダメ:
        • SELECT *して全カラムの値を取り出し、アプリケーションがカラムの位置によってデータにアクセスする
        • ORDER BY 1
    • 重複する行が存在しない
      • 一意性制約により保証できる
        • 必須ではない。実際に重複さえなければ
    • 列の値がアトミックであること
      • 「アトミックである」ってなに
    • すべての列の値は定義されたものだけであり、かつそれぞれの行において常に存在する
      • NULLはダメ
        • 「ない」ことをNULLで表現するくらいならテーブル分割しろ

コラム: 列の値はスカラであるべき？

  • いいえ
  • スカラであることとアトミックであることとは異なる概念
  • 列の値はベクトルでもなんでもいい。ドメイン次第
    • リレーショナルモデル的にはリレーションでもよい
      • RVA: Relation Valued Attribute
      • ただしSQLでは非対応

繰り返しグループ

  • よくあるダメなやつ
  • ドメインの要素を,区切りで1つの列の値に突っ込むなど
  • 列持ちもダメ
    • データ1、データ2といった命名になるため、順序を持ってしまう
    • 欠員がある場合NULLが生じる
  • リレーションは「事実」
    • 真の命題
  • 単に事実を複数述べればよいのである(行持ち)

候補キーとスーパーキー

  • 候補キー(RK)
    • そのリレーションに含まれるタプルの値を一意に決められる属性の集合
    • 1種類とは限らないため「候補」
    • リレーショナルモデルの世界では「主キー」はない
      • どれを選ぶかは主観にすぎないため
    • 【疑問点】なんのRなんだろう
      • 参照キー(Reference Key)ってとこか
  • スーパーキー(SK)
    • 余計な属性を含むものも含める
  • 1NFでは最低でも1つの候補キーが存在する
    • タプルが重複しないため、全属性指定すれば必ずスーパーキーとなり、タプルの値を一意に決められる

関数従属性(FD)

あるリレーションRの見出しの2つの部分集合をA, Bとする。
Rの要素のすべてのタプルにおいて、Aの値が同じならばBの値も同じである場合
かつその場合だけに限り、BはAに関数従属すると言う。 このような関係をA→Bと記述する。

  • 自明な関数従属性
    • リレーションの任意の属性はスーパーキーに関数従属する
    • リレーションから取り除くことはできない
  • 自明ではない関数従属性
    • 候補キーの真部分集合から非キー属性(Non-Prime Attribute)へのFD (部分関数従属)
    • 非キー属性から非キー属性へのFD (推移的関数従属)
    • 非キー属性から候補キーの真部分集合へのFD (名前ない？)
  • 正規化とは、自明ではない関数従属性を排除する作業
    • 隠れたキーを探し出す

コラム: 候補キー内部に自明ではない関数従属性は存在しないのか

  • ないよ
  • 背理法
    • (前提) 候補キー内部の自明ではない関数従属性があるとする
    • 候補キーの真部分集合をA, Bとする
    • A→B なるFDがある
    • Aだけでキーとしての機能を有することになる
    • 候補キー=キーとして余計な属性を持たないことに矛盾する
    • 前提が誤っている

第2正規形(2NF)

  • 部分関数従属(Partial Functional Dependency)を取り除く
  • 分解: 射影演算
  • 無損失分解(Non-loss Decomposition)
    • 結合で元に戻る
  • 無損失分解ができるかどうかの基準が「従属性」

第3正規形(3NF)

  • 推移的関数従属(Transitive Dependency)を取り除く
  • 無損失分解

ボイスコッド正規形(BCNF)

  • 非キー属性から候補キーの真部分集合へのFDを取り除く
  • 3NFであるがBCNFでない例
氏名(RK) 学科(RK) 研究室
桂小五郎 コンピュータアーキテクチャ デバイスドライバ
勝海舟 コンパイラ 最適化
坂本龍馬 データベース リレーショナルデータベース
坂本龍馬 コンパイラ 最適化
西郷隆盛 データベース 分散データベース
高杉晋作 コンパイラ 並列化コンパイラ
高杉晋作 コンピュータアーキテクチャ 割り込み処理
  • このリレーションでは、研究室がわかれば学科がわかる
{研究室} → {学科}
  • 3NFであるがBCNFでないリレーションは、候補キーが複数存在する
    • {氏名, 学科}
    • {氏名, 研究室}
  • 後者に注目すると…
氏名(RK) 学科 研究室(RK)
桂小五郎 コンピュータアーキテクチャ デバイスドライバ
勝海舟 コンパイラ 最適化
坂本龍馬 データベース リレーショナルデータベース
坂本龍馬 コンパイラ 最適化
西郷隆盛 データベース 分散データベース
高杉晋作 コンパイラ 並列化コンパイラ
高杉晋作 コンピュータアーキテクチャ 割り込み処理
  • 部分関数従属があるため2NFですらなかった
  • 第2正規化する
  • 研究室配属リレーション
氏名(RK) 研究室(RK)
桂小五郎 デバイスドライバ
勝海舟 最適化
坂本龍馬 リレーショナルデータベース
坂本龍馬 最適化
西郷隆盛 分散データベース
高杉晋作 並列化コンパイラ
高杉晋作 割り込み処理
  • 正規形の次数
    • 非キー属性がないので低くともBCNF
  • 研究室学科リレーション
研究室(RK) 学科
デバイスドライバ コンピュータアーキテクチャ
最適化 コンパイラ
リレーショナルデータベース データベース
分散データベース データベース
並列化コンパイラ コンパイラ
割り込み処理 コンピュータアーキテクチャ
  • 正規形の次数
    • 候補キーが1属性しかなく、部分関数従属がないため2NF
    • 非キー属性が1つしかなく、推移的関数従属がないため3NF
    • {学科}から{研究室}への関数従属がないためBCNF
  • 3NFではあるがBCNFではない、という場合は、候補キーが他にないかということから検討するとよい