勉強日記

毎日投稿

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

gihyo.jp


まとめ

  • 結合従属性
    • 「無損失分解できるような状況」
    • 関数従属性の一般化
  • 関数従属性以外の、自明でも暗黙的でもない結合従属性を取り除くと4NF, 5NFを得る
  • 6NFは無駄な結合が多く、実用的ではない

結合従属性(JD)

  • BCNFで関数従属性を完全に排除した
  • まだ終わりではない
  • 結合従属性 (JD: Join Dependency)
    • キー自身に冗長性が含まれる

A, B, ..., CをリレーションRの見出しの部分集合であるとする。
もしA, B, ..., Cの射影に対応するリレーションを結合した結果と、
Rが同じ場合かつその場合に限り、Rは次の結合従属性を満たすこととする

☆{A, B, ..., C}

  • 候補キーの内部に結合従属性が含まれることは大いにあり得る
    • cf. 関数従属性はない
      • あったら、それは既約な「候補キー」ではない
  • 自明な結合従属性
    • A, B, ..., CのどれかがRの見出し全体と同じ
    • リレーションRそのものとRの任意の射影との結合はR
      • 【補】述語の変数が落ちてるだけなので

結合従属性は無損失分解が可能

  • 循環定義
  • 「結合して元に戻る」ことが定義

関数従属性は結合従属性の一種である

  • 関数従属性である ⊃ 無損失分解
  • 無損失分解できる ≡ 結合従属性である
  • したがって、関数従属性である ⊃ 結合従属性である
  • 集合としてはS_関数従属性 ⊆ S_結合従属性

暗黙的な結合従属性

  • Implied by Superkeys (スーパーキーによって、暗黙に定義される)
  • リレーションRの見出しの部分集合A, B, ..., CがすべてRのスーパーキーである場合
  • A, B, ..., Cは共通してRの候補キーを含む

非キー属性と結合従属性

  • 下記条件のいずれかを満たすと、BCNFは自動的に5NFの要件を満たす
    • 非キー属性が存在する
      • {RK} → 非キー属性なる関数従属がある
      • RKをさらに分解すると関数従属が壊れるため、これ以上無損失分解できない
        • 分解してもなお非キー属性を特定できるとしたら、それは部分関数従属しており、2NFですらない
    • キーに含まれる属性は1つだけである
      • キー自身の冗長性がない(当然)
  • サロゲートキー??
    • いったん無視してDB設計を進めよ
    • 正規化はナチュラルキーを対象として考えるもの
      • SQLで言われる
        「複合キーを使わず単一キーを使え」
        というのは、リレーショナルモデルでは不可能

結合従属性による正規化(4NF〜6NF)

第4正規形(4NF)

  • 一般的に「多値従属性(MVD: MultiValued Dependency)による正規化」と解説されるやつ
  • MVDは結合従属性の特殊なパターン
    • 結合従属性を見つけやすくするための道具であるといえる

A, B, CをリレーションRの見出しの部分集合であるとする。
A, B, Cが次の結合従属性を満たす場合かつその場合に限り、
BおよびCはAに多値従属すると言う。

☆{AB, AC}

次のような記号を用いて表現する。

A →→ B
A →→ C

氏名(RK) 学科(RK) 授業(RK)
桂小五郎 コンピュータアーキテクチャ リレーショナルモデル
桂小五郎 コンピュータアーキテクチャ Javaプログラミング
勝海舟 コンパイラ リレーショナルモデル
勝海舟 コンパイラ RoR
勝海舟 コンパイラ コンピュータアーキテクチャ原理
坂本龍馬 データベース リレーショナルモデル
坂本龍馬 データベース コンピュータアーキテクチャ原理
坂本龍馬 コンパイラ リレーショナルモデル
坂本龍馬 コンパイラ コンピュータアーキテクチャ原理
  • 分解する
  • 学科所属
氏名(RK) 学科(RK)
桂小五郎 コンピュータアーキテクチャ
勝海舟 コンパイラ
坂本龍馬 データベース
坂本龍馬 コンパイラ
  • 授業所属
氏名(RK) 授業(RK)
桂小五郎 リレーショナルモデル
桂小五郎 Javaプログラミング
勝海舟 リレーショナルモデル
勝海舟 RoR
勝海舟 コンピュータアーキテクチャ原理
坂本龍馬 リレーショナルモデル
坂本龍馬 コンピュータアーキテクチャ原理
  • 結合して元に戻る
  • 【補】分解のしかたによっては無損失分解にならないので注意する:
氏名(RK) 学科(RK)
桂小五郎 コンピュータアーキテクチャ
勝海舟 コンパイラ
坂本龍馬 データベース
坂本龍馬 コンパイラ
学科(RK) 授業(RK)
コンピュータアーキテクチャ リレーショナルモデル
コンピュータアーキテクチャ Javaプログラミング
コンパイラ リレーショナルモデル
コンパイラ RoR
コンパイラ コンピュータアーキテクチャ原理
データベース リレーショナルモデル
データベース コンピュータアーキテクチャ原理
  • 結合するとタプルが増えちゃう
氏名(RK) 学科(RK) 授業(RK)
桂小五郎 コンピュータアーキテクチャ リレーショナルモデル
桂小五郎 コンピュータアーキテクチャ Javaプログラミング
勝海舟 コンパイラ リレーショナルモデル
勝海舟 コンパイラ RoR
勝海舟 コンパイラ コンピュータアーキテクチャ原理
坂本龍馬 データベース リレーショナルモデル
坂本龍馬 データベース コンピュータアーキテクチャ原理
坂本龍馬 コンパイラ リレーショナルモデル
坂本龍馬 コンパイラ RoR
坂本龍馬 コンパイラ コンピュータアーキテクチャ原理

第5正規形(5NF)

  • 暗黙的ではないすべての結合従属性が取り除かれた状態
    • 3つ以上
      • ☆{AB, BC, CA}
氏名(RK) 学科(RK) 授業(RK)
勝海舟 コンパイラ C++
勝海舟 コンパイラ Java
坂本龍馬 コンパイラ C++
坂本龍馬 コンパイラ RoR
坂本龍馬 データベース RoR
坂本龍馬 データベース リレーショナルモデル
桂小五郎 コンパイラ Java
桂小五郎 コンピュータアーキテクチャ Java
桂小五郎 コンピュータアーキテクチャ OS
桂小五郎 コンピュータアーキテクチャ コンピュータアーキテクチャ原理
  • 分解
氏名(RK) 学科(RK)
勝海舟 コンパイラ
坂本龍馬 コンパイラ
坂本龍馬 データベース
桂小五郎 コンパイラ
桂小五郎 コンピュータアーキテクチャ
氏名(RK) 授業(RK)
勝海舟 C++
勝海舟 Java
坂本龍馬 C++
坂本龍馬 RoR
坂本龍馬 リレーショナルモデル
桂小五郎 Java
桂小五郎 OS
桂小五郎 コンピュータアーキテクチャ原理
学科(RK) 授業(RK)
コンパイラ C++
コンパイラ Java
コンパイラ RoR
データベース RoR
データベース リレーショナルモデル
コンピュータアーキテクチャ Java
コンピュータアーキテクチャ OS
コンピュータアーキテクチャ コンピュータアーキテクチャ原理
  • 学科により受講可能な授業が制限されている場合など
  • 【補】桂小五郎氏に関わるタプルのみ見てみる
  • 元の見出し
氏名(RK) 学科(RK) 授業(RK)
桂小五郎 コンパイラ Java
桂小五郎 コンピュータアーキテクチャ Java
桂小五郎 コンピュータアーキテクチャ OS
桂小五郎 コンピュータアーキテクチャ コンピュータアーキテクチャ原理
  • 分割
氏名(RK) 学科(RK)
桂小五郎 コンパイラ
桂小五郎 コンピュータアーキテクチャ
氏名(RK) 授業(RK)
桂小五郎 Java
桂小五郎 OS
桂小五郎 コンピュータアーキテクチャ原理
  • ここまでだけだと無損失分解にならない
    • 結合すると余計なタプルが現れる
氏名(RK) 学科(RK) 授業(RK)
桂小五郎 コンパイラ Java
桂小五郎 コンパイラ OS
桂小五郎 コンパイラ コンピュータアーキテクチャ原理
桂小五郎 コンピュータアーキテクチャ Java
桂小五郎 コンピュータアーキテクチャ OS
桂小五郎 コンピュータアーキテクチャ コンピュータアーキテクチャ原理
  • 学科による受講可能な授業の制限
学科(RK) 授業(RK)
コンパイラ C++
コンパイラ Java
コンパイラ RoR
コンピュータアーキテクチャ Java
コンピュータアーキテクチャ OS
コンピュータアーキテクチャ コンピュータアーキテクチャ原理
  • 下記赤タプルは、上記リレーションの述語に入れると偽になる
    • ので、結合後のリレーションには含まれない
氏名(RK) 学科(RK) 授業(RK)
桂小五郎 コンパイラ Java
桂小五郎 コンパイラ OS
桂小五郎 コンパイラ コンピュータアーキテクチャ原理
桂小五郎 コンピュータアーキテクチャ Java
桂小五郎 コンピュータアーキテクチャ OS
桂小五郎 コンピュータアーキテクチャ コンピュータアーキテクチャ原理

接続の罠(Connection Trap)

  • 分解後のリレーションが元のリレーションと同じ事実を表しているように見えない現象
  • 坂本龍馬はデータベース学科に所属しており、「ある授業」を受講する
  • 坂本龍馬は「ある学科」に所属しており、リレーショナルモデルの授業を受講する
  • 「ある生徒」はデータベース学科に所属しており、リレーショナルモデルの授業を受講する
  • 【補】「ある〜〜」は射影により落ちた変項
  • 罠っぽいだけで、実際には何の罠もない
    • 結合従属性により、元のリレーションに復元できることが保証されるから

結合従属性を発見するのは難しい?

  • まず非キー属性を持たず、属性が複数であることで絞りこめる
  • 実際に射影をとってみる
    • SQLSELECT DISTINCT
    • 結合して元のリレーションと同じになれば、結合従属性が存在している可能性がある

第6正規形(6NF)

  • 自明な結合従属性以外すべての結合従属性を排除
    • 暗黙的な結合従属性も排除
  • 5NFであり6NFでないケース: 非キー属性が複数
  • 非キー属性の個数が0個または1個になるまで分解
  • 無駄な結合が多く、実用的でない