理論から学ぶデータベース実践入門 ch4 正規化理論(その2)
まとめ
- 結合従属性
- 「無損失分解できるような状況」
- 関数従属性の一般化
- 関数従属性以外の、自明でも暗黙的でもない結合従属性を取り除くと4NF, 5NFを得る
- 6NFは無駄な結合が多く、実用的ではない
結合従属性(JD)
- BCNFで関数従属性を完全に排除した
- まだ終わりではない
- 結合従属性 (JD: Join Dependency)
- キー自身に冗長性が含まれる
A, B, ..., CをリレーションRの見出しの部分集合であるとする。
もしA, B, ..., Cの射影に対応するリレーションを結合した結果と、
Rが同じ場合かつその場合に限り、Rは次の結合従属性を満たすこととする☆{A, B, ..., C}
- 候補キーの内部に結合従属性が含まれることは大いにあり得る
- cf. 関数従属性はない
- あったら、それは既約な「候補キー」ではない
- 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つだけである
- キー自身の冗長性がない(当然)
- 非キー属性が存在する
- サロゲートキー??
結合従属性による正規化(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 |
坂本龍馬 | コンパイラ | コンピュータアーキテクチャ原理 |
- リレーションが表現する事実
- 後ろ3つがダウト
第5正規形(5NF)
- 暗黙的ではないすべての結合従属性が取り除かれた状態
- 3つ以上
☆{AB, BC, CA}
- 3つ以上
氏名(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)
- 分解後のリレーションが元のリレーションと同じ事実を表しているように見えない現象
- 【補】「ある〜〜」は射影により落ちた変項
- 罠っぽいだけで、実際には何の罠もない
- 結合従属性により、元のリレーションに復元できることが保証されるから
結合従属性を発見するのは難しい?
- まず非キー属性を持たず、属性が複数であることで絞りこめる
- 実際に射影をとってみる
- SQLの
SELECT DISTINCT
- 結合して元のリレーションと同じになれば、結合従属性が存在している可能性がある
- SQLの
第6正規形(6NF)
- 自明な結合従属性以外すべての結合従属性を排除
- 暗黙的な結合従属性も排除
- 5NFであり6NFでないケース: 非キー属性が複数
- 非キー属性の個数が0個または1個になるまで分解
- 無駄な結合が多く、実用的でない