高次正規形

2020-07-12 (Sun.)

RDB

\(\def\null{\mathrm{null}}\def\A{\mathcal{A}}\def\D{\mathcal{D}}\def\dom{\mathrm{dom}}\def\Bool{\mathrm{Bool}}\) \(\def\mvdarrow{\rightarrow\!\!\!\rightarrow}\def\fdarrow{\rightarrow}\) \(\def\ID{\mathrm{ID}}\)

Relatinal Database で第一正規形 (1NF) を定義したが実はこれだけでは実用的ではない. より高次の正規形を定義する.

INDEX

第二正規形 (2NF)

定義

  1. 第一正規形であって,
  2. 全ての非キー属性は任意の候補キーに完全関数従属していること

これを第二正規形という. ここで非キー属性とはいかなる候補キーにも属さない属性(一個からなる名前列)のこと.

1NF であって 2NF ではない ID1 ID2 val
1 1 x
1 2 y
1 3 y
2 1 x

これで候補キーは (ID1, ID2) のみ. val を含んだ候補キーはありえないので val は非キー属性 (non-prime attribute). ここで 2NF の要請は val が (ID1, ID2) に完全関数従属することだが, その真の部分列 (ID2) に完全関数従属しているので要請を満たさない.

この関係は \(R_1(\ID_1, \ID_2), R_2(\ID_2, val)\) に完全情報無損失分解できて, 2NF になる.

第三正規形 (3NF)

推移的関数従属

このときに

であることを推移的関数従属性という. \(Z\) は推移的に \(X\) に関数従属する, という.

定義

  1. 第二正規形であって,
  2. 任意の非キー属性は任意の候補キーに推移的に関数従属 しない.

2NF であって 3NF ではない ID x y
1 1 a
2 1 a
3 2 b
4 2 b

候補キーは (ID) のみ. (x) 及び (y) は (ID) に完全関数従属しているのでこれは確かに 2NF.

ところで (y) は (x) に関数従属していて,

なので (x) は候補キー (ID) に推移的に関数従属している. 従って 3NF ではない.

今の例は \(R_1(\ID, x)\)\(R_2(x, y)\) に(完全情報無損失)分解することで 3NF になる.

ボイス-コッド正規形 (Boyce-Codd Normal Form; BNF)

定義

関係 \(R\) について, 関数従属性 \(X \fdarrow Y\) を持つならば次の二つのいずれかが成り立つこと:

  1. \(Y \prec X\)(自明な関数従属性), または
  2. \(X\)\(R\) のスーパーキー

このときの \(R\) を BNF という.

3NF であって BNF ではない ID1 ID2 val
1 1 a
1 2 a
2 1 b
2 2 c

(ID1, ID2) は候補キーだが同時に (ID2, val) も候補キーである. というわけでこの関係に非キー属性はなく, 自動的に第二正規形でかつ第三正規形になる.

ところで関数従属性として \(val \fdarrow \ID_1\) がある. (val) だけでは候補キーにはなりえないので, これは BNF ではないことが確認できる.

第四正規形 (4NF)

ここまで関数従属性を使ってきたけど, BNF の多値従属性バージョンを第四正規形という.

定義

\(R\) の任意の多値従属性 \(X \mvdarrow Y\) が次のいずれか

  1. \(Y \subset X\) または
  2. \(X\) がスーパーキー

このとき \(R\) は 4NF だという.

第五正規形 (5NF)

前回 の一番最後では多値従属性をさらに拡張した結合従属性を紹介した. 4NF の多値従属性を結合従属性に置き換えるのが 5NF. これは射影-結合正規形 (Project-Join Normal Form; PJNF) などとも呼ばれる.

定義

\(R\) の任意の結合従属性 \(\ast(A_1, \ldots, A_n)\) について,

  1. 自明な結合従属性であること, すなわち \(\exists i, A_i = A\), または
  2. \(A_i\) がスーパーキー