初めに

この記事は「リレーショナルデータベース入門第３版」の第２章の一部をまとめたものです。
リレーションの例などは徹底攻略データベーススペシャリスト教科書令和4年度で用いられている具体例を参考にしています。

リレーションやドメインなどといった言葉の定義はこちらの記事を参照ください。
射影、自然結合の定義はこちらの記事を参照ください。
多値従属性、情報無損失分解についてはこちらの記事を参照ください。

なお、証明については、本の証明の行間を自分の言葉で埋めて記載している部分があります。

関数従属性

関数従属性と完全関数従属性

関数従属性とは多値従属性の特別な場合である。
大雑把にいうと、多値従属性がある属性の値に対して別の属性の値の集合が定まる概念であったことに対し、関数従属性はある属性の値に対して別の属性の値が定まる概念である。

定義（関数従属性）

リレーションスキーマ\textit R(A_{1},...,A_{k},B_{1},...,B_{l},C_{1},..,C_{m})に\\
関数従属性A_{1}...A_{k}→B_{1}...B_{l}が存在するとは\\
\textit Rの任意のインスタンスRに対して次が成り立つことである.\\
\forall t,t^{\prime} \in R \quad t[A_{1},...,A_{k}]=t^{\prime}[A_{1},...,A_{k}]\\ \Rightarrow　t[B_{1},...,B_{l}]=t^{\prime}[B_{1},...,B_{l}] \\

つまり任意のタプルに対して、A1,..,Akの値が等しければ,B1,...,Blの値も等しくなる（一意に定まる）ということである。これを用いて完全関数従属性を定義する。

定義（完全関数従属性）

関数従属性X→Yで,Xの任意の真部分集合X^{\prime}に対して\\
X^{\prime}→Yが成立しない時,YはXに完全関数従属しているという.\\

関数従属性と情報無損失分解

情報無損失分解と多値従属性の存在が同値であった(こちらの記事参照）が、情報無損失分解と関数従属性との関係は以下のようになる。

命題

リレーションスキーマ\textit R(X,Y,Z)に対し,X→YならばX→→Yである.

命題の証明

\begin{align}
& リレーションスキーマ\textit RのインスタンスRを任意に取る.\\
& リレーションRの任意のタプルt,t^{\prime}に対して\\
& t[X]=t^{\prime}[X]の時,以下がRのタプルであることを示せば良い.\\
& \quad w=(t[X,Z],t^{\prime}[Y])\\
& \quad w^{\prime}=(t^{\prime}[X,Z],t[Y])\\
& 今,関数従属性X→Yが存在しているので,t[Y]=t^{\prime}[Y]である.\\
& よって,w=(t[X,Z],t^{\prime}[Y])=(t[X,Z],t[Y])=t(X,Y,Z)が成り立つ.\\
& 従ってwはタプルtと一致するので,wがRのタプルであることが従う.\\
& 同様にしてw^{\prime}がt^{\prime}と一致し,w^{\prime}もRのタプルであることが従う.\\
& 以上からX→→Yが従う.\quad□
\end{align}

証明をつらつら書いたが、Xの値を決めて,Yの値が一意に決まるという関数従属性が成り立っていれば、Xの値を決めてYの値の集合が一意に決まるという多値従属性が成り立つというのは自然といえば自然である。多値従属性は関数従属性の拡張と言える。
この命題より、関数従属性の存在は情報無損失分解の十分条件であることがわかった。

第２正規化

リレーションが第１正規系の状態だと更新時異状が発生することを知った（こちらの記事参照）
また一方でリレーションを情報無損失分解することについて関数従属性・多値従属性という概念で性質を観測した。
さて、更新時異状をどのように解消していくかを「リレーションの高次の正規化」の観点で見ていく。まずは第２正規形の定義をする。

定義(第２正規系)

リレーションRが第２正規系であるとは次を満たすことを言う\\
1.\quad Rは第１正規系である\\
2.\quad Rの全ての非キー属性はRの各候補キーに完全関数従属している\\
ここで非キー属性とはいかなる候補キーにも属していない属性のことを言う

リレーションを第２正規形に変換することを第２正規化といい、この変換により先の更新時異状が解消される。
ここで第１正規系であるが、第２正規系でない具体例をあげ、それが上記の定義を満たしていないことを確認する。

具体例①（第１正規系）：リレーション「伝票」

伝票番号	顧客名	顧客番号	商品番号	商品名	数量
1001	ねこ商事	11	2001	チョコ	5
1001	ねこ商事	11	2002	キャラメル	10
1002	うさぎ開発	13	2001	チョコ	7
1002	うさぎ開発	13	2003	ドーナツ	20
1002	うさぎ開発	13	2004	アメ	8
1003	くま工業	29	2005	ちんすこう	30
1004	くま工業	29	2005	ちんすこう	100

※候補キーは{伝票番号,商品番号},{伝票番号,商品名}の二つ。

まず1.は満たしている。これは冪集合と直積集合を含んでないことから分かる。
2.を満たしているかを確認する。つまり、非キー属性をひとつずつ選び、それが各候補キーに完全関数従属しているかを見る。
非キー属性として{顧客番号}を選び、これをYとする。
また、候補キーとして{伝票番号,商品番号}を選び、これをXとする。
候補キーの真部分集合として{伝票番号}を選び、これをX’とする。
X’の元である伝票番号を決定したとき、Yの元である顧客番号は一意に定まる。
なぜなら伝票がわかれば顧客名がわかり、かつ顧客名と顧客番号は1:1対応のためである。
よって関数従属性X’→Yが作れたので、関数従属性X→Yは完全関数従属ではない。
従って2.を満たしていないので、具体例①は第２正規形ではない。

※ちなみに上記の確認の中で、非キー属性としてY={数量}を選び、候補キーとしてX＝{伝票番号,商品番号}を選ぶと、任意の真部分集合X’に対してYが一意に決定されない。つまりこの場合は関数従属性X→Yは完全従属。
（伝票番号だけがわかってもどの商品の行か分かんないから数量もわかんないし、商品番号決まってもどの顧客のものか分かんないから数量わからない）

なお、第２正規形にならなかった原因であるX’→Yのような関数従属性を部分関数従属性と言う。つまり、部分関数住属性があると完全関数従属にならず第２正規形になり得ないと言うこと。
よって第２正規形にするにはこのような部分関数従属を排除していく必要がある。

以下が分解結果である。それぞれのリレーションにもはや部分関数従属性は存在せず、先に挙げた更新時異状は発生しない。

具体例②（第２正規系）：リレーション「伝票」と「伝票明細」

伝票

伝票番号	顧客名	顧客番号
1001	ねこ商事	11
1002	うさぎ開発	13
1003	くま工業	29
1004	くま工業	29

※候補キー(主キー)は{伝票番号}

伝票明細

伝票番号	商品番号	商品名	数量
1001	2001	チョコ	5
1001	2002	キャラメル	10
1002	2001	チョコ	7
1002	2003	ドーナツ	20
1002	2004	アメ	8
1003	2005	ちんすこう	30
1004	2005	ちんすこう	100

※候補キーは{伝票番号,商品番号},{伝票番号,商品名}の二つ。

第３正規系

第２正規系にしても、実は第１正規系であるが第２正規系ではないときに発生したのと同様に更新時異状がまた発生してしまうのである。それを前節の具体例②を用いて説明する。

タプル挿入時異状

新しい顧客の情報を伝票が作られる前に登録しようとすると、
伝票番号が主キーであることから登録できなくなる。
つまり( - ,アルパカデパート, 30)みたいなタプルを挿入できない。

タプル修正時異状

くま工業が社名変更して「Kuma Tech」になったとき、修正しようとすると伝票番号1003,1004のタプル２つ分を修正する必要がある。一つでも抜け漏れがあると、整合性が取れなくなる。

タプル削除時異状

伝票番号1001の行を削除すると、顧客ねこ商事の情報もまとめて消え去ってしまう。
つまり顧客ねこ商事の情報を保持できなくなってしまう

更新時異状の原因

具体例②がいずれも確かに第２正規系であるが、伝票リレーションには非キー属性同士の関数従属性である顧客番号→顧客名が存在している。
そして顧客名は主キーの伝票番号に完全関数従属はしているが、この完全関数従属性は伝票番号→顧客番号, 顧客番号→顧客名という関数従属性の推移律から成っている。
ここが起因しており、この顧客番号→顧客名という関数従属性は本来のリレーションとは分離するべきなのである（これが第３正規化）
ここで推移的関数従属性の定義をし、またそれを用いて第３正規系の定義をする

定義(推移的関数従属性)

X,Y,ZをリレーションスキーマRの属集合とし\\
X→Y,Y\nrightarrow X,Y→Z が成り立っているとする.\\
ただし,Y→Zは自明な関数従属でないとする.この時\\
X→Z,Z\nrightarrow Xが成り立っており,X→Zを推移的関数従属性という.

定義(第３正規系)

リレーションRが第３正規系であるとは次を満たすことをいう\\
1. Rは第２正規系である.\\
2. Rの全ての非キー属性はRのいかなる候補キーにも推移的に関数従属しない

2.の条件を説明する。Rの非キー属性をA,Rの候補キーをKとしたときに、Rの属性集合Yが存在して次が成り立つことはないということである。

K→Y,Y\nrightarrow K,Y→A

例えば具体例②のリレーション「伝票」は上記のような推移的関数従属性が存在するので、第３正規形ではない。実際、非キー属性{顧客名}と候補キー{伝票番号}に対し、属性集合{顧客番号}が存在し、伝票番号→顧客番号と顧客番号→顧客名が成り立つ。また逆に顧客番号から伝票番号が一意に定まることはない。

そこでこの推移的関数従属性を排除するために、顧客番号→顧客名で情報無損失分解をすると、以下のようになり第３正規形となる。

具体例③（第３正規系）：リレーション「伝票」と「顧客」

伝票

伝票番号	顧客番号
1001	11
1002	13
1003	29
1004	29

顧客

顧客名	顧客番号
ねこ商事	11
うさぎ開発	13
くま工業	29

第３正規化の補足

第３正規化であることは以下のように換言できる。

命題

リレーションRが第３正規系であることと以下は同値である.\\
(*)AをRの非キー属性とする。X→Aなる自明でない関数従属性が存在した時、XはRのスーパキーとなる.

命題の証明

\begin{align}
& 初めに,Rが第３正規系である　\Rightarrow　(*)を示す\\
\\
& リレーションRの非キー属性Aを任意に取り,関数従属性X→Aを満たす属性集合Xが存在したとする.\\
& この時,Xがスーパキーであることを示す.\\
& 候補キーをKとして,仮にXはスーパキーでないとする.\\
& Kは候補キーであるから,関数従属性K→Xが存在する.\\
& また,仮定から関数従属性X→Aが存在する.\\
& そして,X\nrightarrow Kが成り立つ.\\
& なぜなら仮にX→Kなら,Kが候補キーであることから\\
& Xによってタプルの一意性が定まり,Xがスーパキーでないことに反するためである.\\
& 以上から推移的関数従属性の存在が言えるので、第３正規形であることに矛盾する.\\
& 従って,Xはスーパキーである.

\end{align}

命題の証明

\begin{align}
& 次に,Rが第３正規系である　\Leftarrow　(*)を示す\\
\\
& リレーションRの非キー属性をAとし,候補キーをKとする.\\
& もし,仮に関数従属性K→X,X→Aが存在し,X\nrightarrow Kであるとする.\\
& この時,(*)からXがスーパキーとなる.\\
& しかし,X\nrightarrow Kであることに矛盾するので,候補キーと非キー属性の間の推移的関数従属性は存在しないことが言える.\\
& また,仮にK\subset　K^{\prime}なる属性集合K^{\prime}が存在し,　K^{\prime}→Aを満たすとする.\\
& この時,(*)からK^{\prime}がスーパキーとなる.\\
& しかし,これはKが候補キーであることに矛盾するので,候補キーと非キー属性の間の完全関数従属性が言える.\\
& 以上からリレーションRが第３正規形であることが言える.

\end{align}

これは非キー属性が候補キー以外の属性集合に完全関数従属していない形が第３正規形であるということを示している.
つまり,以下のような関数従属性があると第３正規形ではないといえる.
・非キー属性→別の非キー属性
・候補キーの一部→非キー属性
・候補キーの一部と非キー属性→別の非キー属性
・候補キーの一部と別の候補キーの一部→非キー属性

ここから更なる高次の正規化の話に移っていく。

参考

・リレーショナルデータベース入門第３版
・徹底攻略データベーススペシャリスト教科書令和4年度
・データベース工学
・矢沢久雄の情報工学“再”入門