正規化理論

正規化理論#

正規形

Abbreviation

定義

第一正規形

1NF

ドメインがシンプルであること

第二正規形

2NF

1NFを満たし、全ての非キー属性が各候補キーに完全関数従属していること

第三正規形

3NF

2NFを満たし、全ての非キー属性が各候補キーに推移的関数従属しないこと

第一正規形#

リレーショナルデータベースを設計するには、一般的に実体関連モデルを用いてER図を作成し、そこからリレーションスキーマを導出する。得られたリレーションスキーマは、全て第一正規形を満たさなければならない。

Definition

リレーションスキーマ\(\boldsymbol{R}(A_1, A_2, \ldots, A_n)\)が第1正規形（1NF, first normal form）であるとは，任意のドメインがシンプルであることをいう．

シンプルはドメインの元が原子的（atomic），即ち分解不可能（nondecomposable）な値であることを指す．

第二正規形#

更新時異状#

しかし、リレーションスキーマが第1正規形を満たしていても、様々な更新時異状（update anomaly）が発生する可能性がある。

例えば、以下のようなリレーションを考える。「学籍番号」と「科目番号」を主キーとする。

学籍番号

科目番号

科目名

成績

2501

CS101

計算機科学

92

2501

CS102

プログラミング

85

2502

CS101

計算機科学

88

2502

CS103

データベース

90

  • 挿入時異状: 新しい科目「CS104 人工知能概論」を追加したいが、まだ受講者がいないため、挿入できない。

  • 削除時異状: (2502, CS103, データベース, 90)を削除すると、科目「データベース」の情報が失われる。

  • 修正時異状: 科目名「計算機科学」を「コンピュータサイエンス」に変更したいが、複数の行を修正する必要がある。

関数従属性#

Definition

リレーションスキーマ\(\boldsymbol{R}(X, Y, Z)\)において、関数従属性（functional dependency）\(X \to Y\)が存在するとは、\(\boldsymbol{R}\)の任意のインスタンス\(R\)に対して、次の条件が成り立つことをいう。

\[ \forall r_1, r_2 \in R, \quad (r_1[X] = r_2[X] \implies r_1[Y] = r_2[Y]) \]

つまり、\(X \to Y\)が存在する場合、任意のインスタンス\(r_1\)と\(r_2\)において、\(X\)の値が同じならば、\(Y\)の値も同じであることを意味する。

Definition

関数従属性\(X \to Y\)において、\(X\)の任意の真部分集合\(X'\)に対して、\(X' \not\to Y\)が成り立つとき、\(Y\)は\(X\)に完全関数従属しているという。

Example

成績(学籍番号, 科目番号, 科目名, 成績)において、学籍番号と科目番号の組み合わせが主キーであるとする。次のような完全関数従属性が存在する。

  1. \(\{学籍番号, 科目番号\} \to \{成績\}\)

  2. \(\{科目番号\} \to \{科目名\}\)

Example

下記のリレーションスキーマでは、完全関数従属性を定義してみよう。

  1. 注文(顧客ID, 商品番号, 商品名, 単価, 数量, 金額)

  2. 成績(学籍番号, 科目番号, 科目名, 成績, 単位数, 担当教員, 判定)

  3. 供給(供給者ID, 商品番号, 在庫数, 所在地, 供給者名, 電話番号)

正規化#

Definition

リレーションスキーマ\(\boldsymbol{R}\)が第2正規形（2NF, second normal form）であるとは，次の条件を満たすことをいう．

  1. \(\boldsymbol{R}\)は第1正規形である．

  2. \(\boldsymbol{R}\)の全ての非キー属性が，\(\boldsymbol{R}\)の全ての候補キーに完全関数従属している．

Example

成績(学籍番号, 科目番号, 科目名, 成績)

科目名は主キーの真部分集合である{科目番号}に完全従属しているので、リレーション成績は第二正規形ではない。

そこで、科目番号\(\to\)科目名という関数従属を用いて、成績を成績(学籍番号, 科目番号, 成績)と科目(科目番号, 科目名)に分解すると、どちらも第二正規形になる。

Example

下記のリレーションスキーマを第二正規形に正規化してみよう。

  1. 注文(顧客ID, 商品番号, 商品名, 単価, 数量, 金額)

  2. 成績(学籍番号, 科目番号, 科目名, 成績, 単位数, 担当教員, 判定)

  3. 供給(供給者ID, 商品番号, 在庫数, 所在地, 供給者名, 電話番号)

第三正規形#

更新時異状#

第二正規形を満たしていても、更新時異状が発生する可能性がある。

例えば、以下のようなリレーションを考える。「学籍番号」を主キーとする。

学籍番号

氏名

学部

キャンパス

2501

山田太郎

理工学部

小金井

2502

佐藤花子

情報学部

小金井

2503

鈴木一郎

経済学部

多摩

2504

田中二郎

文学部

市ヶ谷

2505

高橋三郎

文学部

市ヶ谷

ここで、学籍番号\(\to\)氏名, 学籍番号\(\to\)学部, 学籍番号\(\to\)キャンパスとする。主キーは学籍番号であるため、このリレーションは第二正規形である。

  • 挿入時異状: 新しい学部「データサイエンス学部」ができ、キャンパスが小金井と決定したとする。学籍番号が決まっていないため、挿入できない。

  • 削除時異状: 学籍番号2501の学生が退学した場合、(理工学部, 小金井)の情報が失われる。

  • 修正時異状: 文学部を多摩キャンパスに移動したとする。複数の行を修正する必要がある。

推移的関数従属性#

Definition

リレーションスキーマ\(\boldsymbol{R}(X, Y, Z)\)において、\(X \to Y\)と\(Y \to Z\)が存在するとき、\(X \to Z\)が成立する。

Example 1

学生(学籍番号, 氏名, 学部, キャンパス)には

\[\begin{split} \text{学籍番号} \to \text{学部}\\ \text{学部} \to \text{キャンパス} \end{split}\]

があるため、推移的関数従属性

\[ \text{学籍番号} \to \text{キャンパス} \]

が存在する。

正規化#

Definition

リレーションスキーマ\(\boldsymbol{R}\)が第3正規形（3NF, third normal form）であるとは，次の条件を満たすことをいう．

  1. \(\boldsymbol{R}\)は第2正規形である．

  2. \(\boldsymbol{R}\)の全ての非キー属性が，\(\boldsymbol{R}\)の全ての候補キーに推移的関数従属していない．

Example 2

学生(学籍番号, 氏名, 学部, キャンパス)には、キャンパスが学籍番号に推移的に従属するので、第3正規形ではない。

\(\text{学部} \to \text{キャンパス}\)という関数従属を用いて、学生(学籍番号, 氏名, 学部)と学部(学部, キャンパス)に分解すると、どちらも第3正規形になる。

Example 3

下記のリレーションスキーマを第3正規形に正規化してみよう。

  1. 社員(社員番号, 氏名, 部署, 勤務地)

  2. 社員(社員番号, 氏名, 職位, 給与)

練習#

下記のリレーションスキーマは第一正規形を満たしているが、第二正規形や第三正規形を満たしていない。問題1から3を解いて、第三正規形に正規化してみよう。同じ職位の場合は、同じ給与であるとする。プロジェクトにおいての社員の仕事時間は、プロジェクト番号と社員番号の組み合わせで一意に決まるとする。

  • プロジェクト(プロジェクト番号, プロジェクト名, 社員番号, 社員名, 職位, 給与, 仕事時間)

  1. リレーションスキーマを完全関数従属性を定義してみよう。

  2. 定義した完全関数従属性を用いて、リレーションスキーマを第2正規形に正規化してみよう。

  3. 第2正規形に正規化したリレーションスキーマを用いて、第3正規形に正規化してみよう。

Contents