昔やったことのおさらい。
参考文献として http://www.amazon.co.jp/dp/4785620463 この本を見つつ、ネットで検索しつつ。

記号の意味

• X → A：属性集合Xが決まれば属性集合Aが決まる(関数従属)
• X ⊆ RS: XはRSの部分集合
• X ⊂ RS: XはRSの真部分集合 (X ⊆ RS かつ X ≠ RS)

• A ∈ RS: AはRSの要素

• {}: 集合

• 属性 (強調文字): 主キー

単語の意味

• 属性: DBのカラム
• 超キー: 行を特定できる属性の集合。例えば {メールアドレス, 氏名} のペアもあり。氏名は冗長なので省いたものが候補キー(またはキー)。そこから扱いやすいものを主キーとして選ぶ。
• 素属性: 候補キーの構成要素となる属性

※ 本に合わせて日本語とカタカナ

第三正規形

• RDBの更新不整合を解消するための指針は、すべてのリレーションスキーマを第三正規形とすることである。
• リレーションスキーマRSが第三正規形であるとは、関数従属性 X → A (X ⊆ RS, A ∈ RS, A ∉ X) が成り立つ場合に以下の条件のいずれかが常に満たされる場合
  1. X が RS の超キー
  2. A が素属性

営業 {商品番号, 顧客番号, 社員番号, 販売価格} というリレーションスキーマRSがあったとき、「{顧客番号} → 社員番号」という関数従属性Fが存在すれば、RSは第三正規形ではない。
候補キーは {商品番号, 顧客番号} であり、Fは上記1, 2のどちらも満たさない。
({顧客番号}は超キーではない、社員番号は候補キーの構成要素ではない)

これは {商品番号, 顧客番号, 販売価格}, {顧客番号, 社員番号} に分解することで第三正規形となる。

蛇足：{メールアドレス, 氏名, 携帯番号} というスキーマは「携帯番号 → 氏名」という関数従属性も考えられるが、携帯番号も実は主キーになり得る(候補キー)ので第三正規形の条件を満たす。

ボイス・コッド正規形

• 第三正規形の条件2を省いたもの。

営業 {商品番号, 顧客企業番号, 顧客担当者番号, 販売価格} というスキーマRSがあり、「顧客担当者番号 → 顧客企業番号」の関数従属性があるとき、RSは第三正規形の条件を満たすがボイス・コッド正規形の条件は満たさない。

これを主キーを維持したまま分解すると {商品番号, 顧客企業番号, 販売価格}, {顧客担当者番号, 顧客企業番号} になるが、結合できない。

主キーを変更して {商品番号, 顧客担当者番号, 販売価格}, {顧客担当者番号, 顧客企業番号} にするとボイス・コッド正規形の条件を満たす。
ただし、「{商品番号, 顧客企業番号} → 販売価格」が「{商品番号, 顧客担当者番号} → 販売価格」に変更されているので、元々商品と企業が決まれば価格が決まっていたものが、同一企業でも担当者ごとに異なる価格が追加できるようになってしまった。(従属性保存分解ではない。)

蛇足：こういった制約をデータベースに持たせるのかアプリケーションで実装するのかは、ケースバーケース、らしい。

さらに正規化

Wikipediaや@ITが分かりやすい。

多値従属性

数式は非常に長いのでざっくり言うと、X が 決まれば Yの集合が決まるとき 多値従属性 X →→ Y が成り立つという。
関数従属性は多値従属性の特殊な場合。

第四正規形

• 多値従属性 X →→ Y (XY ⊂ RS, Y ⊄ X) が成り立つ場合は、常にXがRSの超キーである場合

プロジェクト {プロジェクト番号, 社員番号, ミーティング日} のスキーマRSがあるとき、RSはボイス・コッド正規形ではあるが第四正規形ではない。(「プロジェクト番号 →→ 社員番号」「プロジェクト番号 →→ ミーティング日」は成立するが {プロジェクト番号} は超キーではない。)

分解して {プロジェクト番号, 社員番号}, {プロジェクト番号, ミーティング日} にすると第四正規形を満たす。

結合従属性

ざっくり言うと、リレーションRSとその分解 {RS1, RS2, ..., RSn} があるとき、{RS1, RS2, ..., RSn} の自然結合(natural join) とRSが等しい場合に、RSは結合従属性　*(RS1, RS2, ..., RSn) が成り立つという。

第五正規形

• RSの分解{RS1, ..., RSn}において自明でない結合従属性 *(RS1, ..., RSn) が成り立つ場合には常にRSn(1 <= i <= n)がRSの超キーである場合

部品提供 {工場番号, 部品番号, 業者番号} のスキーマRSがあり

• 「工場 対 部品」「工場 対 業者」「部品 対 業者」はN対N
• 工場fが必要とする部品pはfと契約のある業者のうちでpを提供可能な業者すべてから供給を受ける

という条件がある。
この場合、RSに多値従属性は存在しないので第四正規形は満たす。しかし「工場fが必要な部品群を決めたが業者は未定」などの場合に挿入不整合を起こす。
結合従属性に基づき {工場番号, 部品番号}, {工場番号, 業者番号}, {部品番号, 業者番号} に分解すると第五正規形を満たし、不整合も解消される。

雑感

第四正規形以降に数式が多すぎてちょっと力尽きたので雑になっている。
本のまとめの章にはこう書いてある。

一般には従属性に基づく整合性制約を保存した分解が可能なのは第三正規形までであり、それ以上の分解を行った場合には更新不整合を排除できる度合いは高まるものの、従属性を担保することができない。

つまり、データ追加更新削除時の整合性を重視するのか、Aが決まればBが決まるというビジネスルールを重視するかで正規化の度合いが変わり、それは状況によって選ばなければならない。ということ。