初めに
この記事は「リレーショナルデータベース入門 第３版」の第２章の一部をまとめたものです。
リレーションの例などは徹底攻略 データベーススペシャリスト教科書 令和4年度で用いられている具体例を参考にしています。
リレーションやドメインなどといった言葉の定義はこちらの記事を参照ください。
射影、自然結合の定義はこちらの記事を参照ください。
なお、証明については、本の証明の行間を自分の言葉で埋めて記載しています。
間違いがあったらすみません。ご指摘いただけますと幸いです。。
第１正規化
正規化とは大雑把に言えば、一定のルールに従ってリレーションを分割していくことである。
正規化の目的は(のちに見ていくが)タプルの更新時異状を排除することである。
定義（第１正規系）
リレーションR(A_{1},...,A_{n})は、その各ドメインdom(A_{i})(i=1,..,n)が\\
シンプルであるときに第1正規系と呼ぶ
ここでシンプルなドメインとは、ドメインの元が全て単一値を取ることを言う。
具体的には、そのドメインが他のいくつかのドメインの直積であったり、ドメインの冪集合であったりすることはない、と言うことである。
まず第１正規系である例とそうでない例を挙げる。
具体例①（第１正規系）：リレーション「伝票」
| 伝票番号 | 顧客名 | 顧客番号 | 商品番号 | 商品名 | 数量 |
|---|---|---|---|---|---|
| 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 |
それぞれのドメインの元が単一の値をとっているので、この関係は第１正規形である。
具体例②（第１正規系でない）
| 伝票番号 | 顧客名 | 顧客番号 | 商品番号 | 商品名 | 数量 |
|---|---|---|---|---|---|
| 1001 | ねこ商事 | 11 | {2001,2002)} | チョコ | 5 |
このような関係は、ひとつの値に対して集合が対応している（1001 の伝票番号に対して商品番号の部分集合{2001,2002}が対応している）
そのため、ドメインの値が全て単一の値をとっているわけではないので非正規系である。
具体例③（第１正規系でない）
| 伝票番号 | 顧客名＆ 顧客番号 | 商品番号 | 商品名 | 数量 |
|---|---|---|---|---|
| 1001 | (ねこ商事,11) | 2001 | チョコ | 5 |
このような関係は、ひとつの属性の中に複数の値の組み合わせ（直積）が入ってしまっている。
そのため、ドメインの値が全て単一の値をとっているわけではないので非正規系である.
このようにリレーションをできるだけ複雑にしないために、直積や冪集合を排除する操作として第１正規化が必要となる。
更新時異状
リレーションを第一正規系にするだけでは、リレーションを更新（新しいタプルの追加、不要なタプルの更新、タプルの修正）をしたときに様々な更新時異状が起こってしまう。
第１正規系リレーションでの更新時異状
先ほどの例を取り上げる。
具体例①（第１正規系）：リレーション「伝票」
| 伝票番号 | 顧客名 | 顧客番号 | 商品番号 | 商品名 | 数量 |
|---|---|---|---|---|---|
| 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:1対応）
・商品番号に対する商品名の重複はない（商品番号と商品名は1:1対応）
・主キーを{伝票番号,商品番号}とする
さて、このリレーションで発生する更新時異状は次の3つに分類される
・タプル挿入時異状
・タプル削除時異状
・タプル修正時異状
タプル挿入時異状
伝票番号1005の伝票を、購入商品が決まる前に登録したいとする。
そのとき、(1005,麒麟株式会社,30, - , - , -)と言うタプルを登録する必要がある。
しかし、商品番号の属性は主キーの元であり、nullは主キー制約の定義により許されていないので、登録することができない。
タプル削除時異状
くま工業からキャンセルが入り、全ての商品を返品することになったとする。
そのとき、伝票番号1003と1004のタプルを削除する必要がある。
この削除自体は問題なく進む。しかし、商品「ちんすこう」はくま工業のみしか今までに注文していなかったとすると、商品「ちんすこう」の情報が抹消されたことになる。
では、商品「ちんすこう」の情報を保持するために、(-, - , - , 2005, ちんすこう, -)のタプルを挿入しようとする。
すると、伝票番号は主キーであるために、主キー制約により挿入ができなくなる。
タプル修正時異状
顧客「ねこ商事」の社名が変わって「Cat Trading」になったとする。
そのとき、リレーションの１番目にあるタプルを修正するだけではすまず、２番目のタプルも修正する必要がある。もし、漏れがあれば、情報が不明確になったリレーションになってしまう。
更新時異状の解消
前節での更新時異状の原因をラフに探ってみると、異なった事象に関わるデータが一つのリレーションに集約してしまっているからである。
つまり、「どの顧客に対しどの商品を何個取引したか」といったリレーションになっているが、「どのような顧客か」「どのような商品があるか」「どのような取引があるか」といったように事象を切り分ける必要がある。
しかしやたらめったら分解すればいいと言うわけではなく、情報無損失分解という条件を満たしつつ分解する必要がある。
情報無損失分解
リレーション( スキーマ)の情報無損失分解
リレーションR(P1,...,.Pn)が二つの射影R(X1),R(X2)に分解されたとする。
ただしX1とX2の共通部分は空でなく、和集合を取れば全属性集合になるとする。
そこで改めて以下のように定める
X_{1}\cap X_{2} = \{A_{1},...,A_{k}\}\\
X_{1}-(X_{1}\cap X_{2}) = \{B_{1},...,B_{l}\}\\
X_{2}-(X_{1}\cap X_{2}) = \{C_{1},...,C_{m}\}
つまり、
リレーションR(P1,...,.Pn)はR(A1,..,Ak,B1,..,Bl,C1,..,Cm)
リレーションR(X1)はR(A1,..,Ak,B1,..,Bl)
リレーションR(X2)はR(A1,..,Ak,C1,..,Cm)
と書けるわけである。
リレーションR(P1,...,.Pn)、R(X1)、R(X2)をそれぞれ簡単にR,R1,R2と書くことにする
情報無損失分解とは以下を満たす分解のことである。
R = R_{1}*R_{2}
\quad (*は自然結合)
なお、リレーションスキーマRが２つの射影に情報無損失分解されるとは、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 |
このリレーションR(伝票番号,顧客名,顧客番号,商品番号,商品名,数量)を
X1 = {伝票番号,顧客名,顧客番号}
X2 = {伝票番号,商品番号,商品名,数量}
（これらは共通部分が空でないし、和をとると元の全属性集合になる）
としてR[X1],R[X2]に分解したとすると、以下のようにリレーションとなる
具体例④：リレーションR[X1]「伝票」
| 伝票番号 | 顧客名 | 顧客番号 |
|---|---|---|
| 1001 | ねこ商事 | 11 |
| 1002 | うさぎ開発 | 13 |
| 1003 | くま工業 | 29 |
| 1004 | くま工業 | 29 |
具体例⑤：リレーションR[X2]「伝票明細」
| 伝票番号 | 商品番号 | 商品名 | 数量 |
|---|---|---|---|
| 1001 | 2001 | チョコ | 5 |
| 1001 | 2002 | キャラメル | 10 |
| 1002 | 2001 | チョコ | 7 |
| 1002 | 2003 | ドーナツ | 20 |
| 1002 | 2004 | アメ | 8 |
| 1003 | 2005 | ちんすこう | 30 |
| 1004 | 2005 | ちんすこう | 100 |
これらの共通部分は{伝票番号}となる（A1,...,Akの部分）
また、X1からその共通部分を引いたものが{顧客番号,顧客名}（B1,...Blの部分）
また、X2からその共通部分を引いたものが{商品番号,商品名,数量}（C1,...,Cmの部分）
である。
この分解の仕方は情報無損失結合の条件を満たす。
なぜなら、X1とX2の共通部分である{伝票番号}をキーとして＝で結合すれば元のリレーションRと一致するからである。
もっと具体的な議論は省くが、簡単にだけ述べる。後の命題によりRがR1＊R2の部分集合であることがいえ、またRに後に述べる多値従属性がある（今回の例で言うともっと強い関数従属性がある）ことから、R1＊R2がRの部分集合であることが言える。そのためR＝R1＊R2となる。
情報損失分解
では逆にどのような場合は情報損失分解であるかを見ていく（情報無損失分解の定義を満たさないこと）
例えば上の具体例①リレーションR「伝票」を以下のように分解したとする
具体例⑥：リレーションR[X1]「伝票」
| 伝票番号 | 顧客名 | 顧客番号 | 商品番号 |
|---|---|---|---|
| 1001 | ねこ商事 | 11 | 2001 |
| 1001 | ねこ商事 | 11 | 2002 |
| 1002 | うさぎ開発 | 13 | 2001 |
| 1002 | うさぎ開発 | 13 | 2003 |
| 1002 | うさぎ開発 | 13 | 2004 |
| 1003 | くま工業 | 29 | 2005 |
| 1004 | くま工業 | 29 | 2005 |
具体例⑦：リレーションR[X2]「伝票商品」
| 商品番号 | 商品名 | 数量 |
|---|---|---|
| 2001 | チョコ | 5 |
| 2002 | キャラメル | 10 |
| 2001 | チョコ | 7 |
| 2003 | ドーナツ | 20 |
| 2004 | アメ | 8 |
| 2005 | ちんすこう | 30 |
| 2005 | ちんすこう | 100 |
この場合、商品番号で自然結合すると、以下の具体例⑧のように余計な行が足されてしまい、元のリレーションR「伝票」と一致しなくなる。この現象を結合の罠という。
具体例⑧：リレーションR[X1]*R[X2]
| 伝票番号 | 顧客名 | 顧客番号 | 商品番号 | 商品名 | 数量 |
|---|---|---|---|---|---|
| 1001 | ねこ商事 | 11 | 2001 | チョコ | 5 |
| 1001 | ねこ商事 | 11 | 2001 | チョコ | 7 |
| 1001 | ねこ商事 | 11 | 2002 | キャラメル | 10 |
| 1002 | うさぎ開発 | 13 | 2001 | チョコ | 5 |
| 1002 | うさぎ開発 | 13 | 2001 | チョコ | 7 |
| 1002 | うさぎ開発 | 13 | 2003 | ドーナツ | 20 |
| 1002 | うさぎ開発 | 13 | 2004 | アメ | 8 |
| 1003 | くま工業 | 29 | 2005 | ちんすこう | 30 |
| 1003 | くま工業 | 29 | 2005 | ちんすこう | 100 |
| 1004 | くま工業 | 29 | 2005 | ちんすこう | 30 |
| 1004 | くま工業 | 29 | 2005 | ちんすこう | 100 |
情報無損失分解の必要十分条件（多値従属性）
さて、情報無損失分解になるための必要十分条件を見ていく。
まずリレーションRと射影R1とR2に対して次が常に成り立つ。
命題①
R\subset R_{1}*R_{2}
命題①の証明
\begin{align}
& タプルt=(a_{1},...,a_{k},b_{1},..,b_{l},..,c_{1},...,c_{m})をRの元とする.\\
& また、t_{1} = (a_{1},...,a_{k},b_{1},..,b_{l}), t_{2} = (c_{1},...,c_{m}))として\\
& タプルt=(t_{1},t_{2})がR_{1}*R_{2}の元であることを示す.\\
\\
& まず射影の定義により、t_{1}はRの射影R_{1}の元になっている.\\
& 次にt_{2}は各C_{i}(i=1,..,m)のドメインの値で構成されていてかつ\\
& 射影R_{2}の元としてu=(a_{1},...,a_{k},c_{1},...,c_{m})を取れば,\\
& ・u[A_{i}]=t_{1}[A_{i}] (i=1,...,k)\\
& ・u[C_{i}]=t_{2}[C_{j}] (j=1,...,m)\\
& を満たす.よって(t_{1},t_{2})はR_{1}*R_{2}の元となる.\quad□
\end{align}
よって情報無損失分解であるかどうかは、R1とR2の自然結合がRの部分集合になっているかを確認すれば良いことになる。そのための必要十分条件は以下である。
命題②
R\supset R_{1}*R_{2} であるための必要十分条件は,次の(*)を満たすことである.\\
(*)
条件t[A_{1},..,A_{k}]=t^{\prime}[A_{1},...,A_{k}]を満たすRの任意のタプルt,t^{\prime}に対し\\
次のw,w{\prime}がRのタプルであることである.\\
w=(t[A_{1},..,A_{k},B_{1},...,B_{l}],t^{\prime}[C_{1},...,C_{m}])\\
w^{\prime}=(t^{\prime}[A_{1},..,A_{k},B_{1},...,B_{l}],t[C_{1},...,C_{m}])
命題②の証明(=>)
\begin{align}
& 初めに,R\supset R_{1}*R_{2} \Rightarrow (*)を示す\\
\\
& Rのタプルt,t^{\prime}でt[A_{1},..,A_{k}]=t^{\prime}[A_{1},...,A_{k}]を満たすものを任意に取る.\\
& この時,(*)で表されるwがR_{1}*R_{2}の元であることを示せば良い.\\
& なぜなら,R_{1}*R_{2}の元であれば,仮定よりRの元であることが従うからであり,また\\
& もう一方のw^{\prime}についてもtとt^{\prime}を入れ替えれば同様の議論で示されるからである。\\
\\
& 任意にとったタプルt,t^{\prime}に対し,\\
& タプルvをv=t[A_{1},..,A_{k},B_{1},...,B_{l}],\\
& タプルv^{\prime}をv^{\prime}=t^{\prime}[C_{1},...,C_{m}]とする.\\
\\
& この時,射影の定義からタプルvは射影R_{1}の元である.(①)\\
& また,タプルv^{\prime}はタプルt^{\prime}の\{C_{1},...,C_{m}\}値であるから,\\
& 各i=1,...,mに対して,t[C_{i}]はドメインdom(C_{i})の元である.(②)\\
& 更に,R_{2}の元uで次を満たすものが存在する.(③)\\
& ・v[A_{i}]=u[A_{i}] (i=1,...,k)\\
& ・v^{\prime}[C_{i}]=u[C_{j}] (j=1,...,m)\\
& 実際,R_{2}の元としてu=t^{\prime}[A_{1},...,A_{k},C_{1},...,C_{m}]を取ると,\\
& 仮定t[A_{1},..,A_{k}]=t^{\prime}[A_{1},...,A_{k}]より、v[A_{i}]=t[A_{i}]=t^{\prime}[A_{i}]=u[A_{i}](i=1,...,k)が従う.\\
& 同時に,タプルv^{\prime}とタプルuはともにタプルt^{\prime}の値であり,かつ属性C_{i}の値を持つのでv^{\prime}[C_{i}]=u[C_{j}] (j=1,...,m)が従う.\\
\\
& 以上の①,②,③から,自然結合の定義により,w=(v,v^{\prime})が R_{1}*R_{2} のタプルであることがわかる.\\
& よって,R\supset R_{1}*R_{2} \Rightarrow (*)が成り立つ.\quad□
\end{align}
命題②の証明(<=)
\begin{align}
& 次に,R\supset R_{1}*R_{2} \Leftarrow (*)を示す\\
\\
& R_{1}*R_{2}の元(v_{1},v_{2})を任意に取る.\\
& この元がRのタプルであることを示す.\\
\\
& 自然結合の定義から,v_{1}は射影R_{1}の元であるので,\\
& Rのタプルvで次を満たすものが存在する.\\
& ・v[A_{i}]=v_{1}[A_{i}] (i=1,...,k)\\
& ・v[B_{j}]=v_{1}[B_{j}] (j=1,...,l)\\
& また,自然結合の定義から,v_{2}に対し次を満たすR_{2}の元uが存在する.\\
& ・v_{1}[A_{i}]=u[A_{i}] (i=1,...,k)\\
& ・v_{2}[C_{j}]=u[C_{j}] (j=1,...,m)\\
& ここで,uは射影R_{2}の元であるから,Rのタプルv^{\prime}で次を満たすものが存在することがわかる.\\
& ・v^{\prime}[A_{i}]=u[A_{i}] (i=1,...,k)\\
& ・v^{\prime}[C_{j}]=u[C_{j}] (j=1,...,m)\\
\\
& 以上から,次が従う.\\
& ・v[A_{1},...,A_{k}]=v_{1}[A_{1},...,A_{k}]=u[A_{1},...,A_{k}]=v^{\prime}[A_{1},...,A_{k}]\\
& ・v_{1}=v[A_{1},...,A_{k},B_{1},...,B_{l}]\\
& ・v_{2}=u[C_{1},...,C_{m}]=v^{\prime}[C_{1},...,C_{m}]\\
& よって,条件(*)より,(v_{1},v_{2})がRのタプルになることがわかる.\\
\\
& 従って,R\supset R_{1}*R_{2} \Leftarrow (*)が成り立つ.\quad□
\end{align}
この命題①と命題②により、情報無損失分解の必要十分条件が命題②の（＊）の条件であることがわかった。
この（＊）の条件をリレーションRの多値従属性といい、C1...CmがA1...Akに多値従属するなどという。A1..Ak→→C1...Cmなどと書く。
先ほどの具体例を用いて、多値従属性を理解していく。
具体例⑥：リレーションR[X1]「伝票」
| 伝票番号 | 顧客名 | 顧客番号 | 商品番号 |
|---|---|---|---|
| 1001 | ねこ商事 | 11 | 2001 |
| 1001 | ねこ商事 | 11 | 2002 |
| 1002 | うさぎ開発 | 13 | 2001 |
| 1002 | うさぎ開発 | 13 | 2003 |
| 1002 | うさぎ開発 | 13 | 2004 |
| 1003 | くま工業 | 29 | 2005 |
| 1004 | くま工業 | 29 | 2005 |
具体例⑦：リレーションR[X2]「伝票商品」
| 商品番号 | 商品名 | 数量 |
|---|---|---|
| 2001 | チョコ | 5 |
| 2002 | キャラメル | 10 |
| 2001 | チョコ | 7 |
| 2003 | ドーナツ | 20 |
| 2004 | アメ | 8 |
| 2005 | ちんすこう | 30 |
| 2005 | ちんすこう | 100 |
具体例⑧：リレーションR=R[X1]*R[X2]
| 伝票番号 | 顧客名 | 顧客番号 | 商品番号 | 商品名 | 数量 |
|---|---|---|---|---|---|
| 1001 | ねこ商事 | 11 | 2001 | チョコ | 5 |
| 1001 | ねこ商事 | 11 | 2001 | チョコ | 7 |
| 1001 | ねこ商事 | 11 | 2002 | キャラメル | 10 |
| 1002 | うさぎ開発 | 13 | 2001 | チョコ | 5 |
| 1002 | うさぎ開発 | 13 | 2001 | チョコ | 7 |
| 1002 | うさぎ開発 | 13 | 2003 | ドーナツ | 20 |
| 1002 | うさぎ開発 | 13 | 2004 | アメ | 8 |
| 1003 | くま工業 | 29 | 2005 | ちんすこう | 30 |
| 1003 | くま工業 | 29 | 2005 | ちんすこう | 100 |
| 1004 | くま工業 | 29 | 2005 | ちんすこう | 30 |
| 1004 | くま工業 | 29 | 2005 | ちんすこう | 100 |
これらはR=R[X1]＊R[X2]を満たすので、情報無損失分解である。
さて、多値従属性とはどういう状況かを見ていく。
ここで、A1=商品番号,B1=伝票番号,B2=顧客名,B3=顧客番号,C1商品名,C2=数量とする。
結論から言うと、多値従属性A1→→C1C2とは、(A1,B1,B2,B3)の値に対応する(C1,C2)の値の集合がA1だけに依存し、(B1,B2,B3)とは独立に存在している（つまりA1だけを決めれば、C1,C2の値の集合が一意に定まる）ことを指す。
例えば、具体例の(A1,B1,B2,B3)=(2001,1001,ねこ商事,11)を定めると、(C1,C2,C3)の値の集合は{(チョコ,5),(チョコ,7)}となる。この集合は実はB1,B2,B3の値には依存せず、A1の値だけで決まる。
なぜなら、他のA1=2001のタプルについても同様の(C1,C2,C3)の値の集合が定まるからである。
実際、(A1,B1,B2,B3)=(2001,1002,うさぎ開発,13)を定めた時も、同様に(C1,C2,C3)の値の集合は{(チョコ,5),(チョコ,7)}となる。
この状況をちゃんと書いたものが、命題②の（＊）の条件である。
実際、命題②の（＊）の条件は RのタプルでA1の値が同じになるものを2つ任意に取り、それらの(C1,C2,C3)の値を取り替えても、Rのタプルになると言うこと。つまり、A1の値によって(C1,C2,C3)の値の集合が定まっていると言うことである。
改めて書くと、
リレーションRがR[A,B,C]が射影R[A,B]と射影R[A,C]に情報無損失分解されるための必要十分条件は、Rに多値従属性A→→Cが存在することである（つまり命題②の（＊）の条件を満たすこと）。
これらを用いて、関数従属性や完全関数従属などの概念を用意し、第２正規化の話に移っていく。
参考
・リレーショナルデータベース入門 第３版
・徹底攻略 データベーススペシャリスト教科書 令和4年度
・データベース論（７）
・矢沢久雄の情報工学“再”入門