いまさら聞けないリレーショナルデータベースの正規化 その１

正規化とは

正規化とは、特定のデータを定められたルールに従って整形し、データを扱いやすくすることである。
非常に多くの分野で扱われる言葉で、分野によって大きく意味が異なる。
一般的にデータの正規化と言うと、「リレーショナルデータベース(RDB)の正規化」のことを指すことが多いが、
「浮動小数点の正規化」*1や、「XMLの正規化」*2もメジャーである。
リレーショナルデータベースの正規化では、データの冗長性を少なくし、関連性の強いデータ項目（属性）郡をまとめて
一事実一箇所（1 fact in 1 place）になるようにすることを意味する。

リレーショナルデータベースを構築する場合、
データを効率的に扱いデータベースのメンテナンス性を高める目的から、
主キーから直接連想されるデータのみで構成されるよう設計するのが理想とされている。
それが正規化である。正規化の程度によって第１正規化から第５正規化までに分類される。
また、その他にボイスコッド正規化などがある。

正規化を理解するためには、まず「キー」と「関数従属」について知る必要がある。

キーについて

リレーショナルデータベースは、一般的にキーとそれ以外の項目から成り立つ。
キーというのは、それがわかれば他の値が決定するという、関数従属(後述)させる側の項目のことである。
キーにはいくつかの種類があって、テーブルの中から、レコードを特定できるキー項目のことを候補キーといい、
中でも中心的なキー項目のことを主キーと呼ぶ。
キー項目は、１つの項目からなることもあれば、複数の項目を合せてキーする場合もある。

例えば銀行口座テーブルについて考えてみる

口座番号は一意であり、顧客を特定することができる。
店番号と顧客番号の２つで一意となり、顧客を特定することができる。

この場合、候補キーは「口座番号」と「店番号と顧客番号を合せたもの」といえる。
主キーになるものはこのうちのどちらかで、
テーブルが例えば口座の情報であれば、「口座番号」が主キーになり、
顧客のテーブルであれば、「店番号と顧客番号をあわせたもの」が主キーとなる。

関数従属(functional dependency)という考え方

上記テーブルでは、主キーは商品コード、
それ以外の項目は商品名、発売元、販売元、価格となっている。
主キーとそれ以外の項目との関係を「関数従属」という。

補足すると、y=xで（中学の数学に出てくる関数的な意味で）xが例えば1だとyは1となる。
y=2xならxが1でyは2。まぁこれは当たり前なのですが、xが決まればyが決まるという、
このような状態のをyはxに関数従属しているという。
yがxに関数従属であるとき（ＸがきまればＹがきまるとき）、「Ｘ→Ｙ」と表記する。

同じように商品コードが決まれば、商品名、発売元、販売元、価格が決まります。
つまり、商品名、発売元、販売元、価格は商品コードに関数従属していえる。
従って、「商品名→商品コード」なんて風に表記することができる。

完全関数従属 (full functional dependency)

Ｘ→Ｙで且つ、ＹがＸのいかなる射影(projection)*3についても 関数従属が成り立たないこと。

たとえば、属性Ｘ＝(x1,x2,x3,x4) と、４つの要素からなる場合、
この「要素の真部分集合」たとえば(x1,x2,x3)や(x2,x4)から Ｙを一意に定めることが出来てしまったら、
Ｘ→Ｙは完全関数従属とは言えない （部分関数従属であるという)。
(x1,x2,x3)だけからＹが決まるなら、x4はＹを決めるには あっても無くても良い要素である。
主キーの中からレコードを一意に決めるのに 「あっても無くても無い要素」を除いた形式を 第二正規形という。

具体例で示す。例えば [受験番号・試験科目コード]という連結属性Ｘに対して、
[科目得点]Ｙ1は、[受験番号]だけ、もしくは[試験科目コード]だけが決まっても、 一意には値が定まらない。
つまり、 Ｙ1は、Ｘのどんな射影(要素の真部分集合)に対しても 関数従属が成りたたない、
逆に言えば、Ｙ1の値を定めるには、Ｘの全ての要素の値が 決まっている必要がある。
従って、[科目得点]Ｙ1は、[受験番号・試験科目コード]Ｘに対して、 完全関数従属である。

一方、[受験者名]Ｙ2は、[受験番号・試験科目コード]Ｘの射影である が、
[受験番号]だけが決まれば、一意に値が定まってしまう。つまり、
Ｙ2は、Ｘの射影に対して関数従属が成り立つ。逆に言えば、Ｙ2の値を定めるには、
Ｘの一部の要素の値が決まっていれば他の要素は関係ない。
従って、[受験者名]Ｙ2は、[受験番号・試験科目コード]Ｘに対して、部分関数従属である。

部分関数従属 (partial functional dependency)

属性Ｘの一部の要素(射影)にＹが従属するとき、ＹはＸに部分関数従属であると言う。
つまり、{Ｘ1,Ｘ2}→ＹとＸ1→Ｙが同時に成立するとき、 Ｙは{Ｘ1,Ｘ2}に部分関数従属する。

推移的関数従属 (transitive functional dependency)

既存の関数従属から、 新たな関数従属を得られる時、推移的関数従属がある、という。
例えば、[取引コード]Ｘ→[取引先会社コード・取引先会社名]Ｙという関数従属関係がある時、
よく見ると、Ｙの中で、[取引先会社名]Ｙ2は、 やはりＹの中の[取引先会社コード]Ｙ1に関数従属である。
つまり、Ｘ→Ｙという関数従属は、詳しく見ると Ｙ1→Ｙ2という関数従属を含んでいる。
Ｘ→Ｙ1→Ｙ2、という関数従属関係の連鎖が見られる。これを推移的関数従属という。

従属性について

多値従属性 (multivalued dependency, MVD)

「関数従属性は、 多値従属性の一種である。 多値従属性は、結合従属性の一種である。 *4」

リレーション(表)Ｒについて、Ｒ(Ａ,Ｂ,Ｃ)というタプル(組)があるとき、
Ａが決まれば、Ｃとは無関係にＢの複数の値が一意に決まるとき、 これを、Ａ->>Ｂと表記する。
Ａ->>Ｂの関係が成り立ち、且つＡが決まれば、Ｂとは無関係にＣの複数の値が一意に決まるとき 、
つまり、「Ａ->>Ｂ」と「Ａ->>Ｃ」が同時に成り立つことを、 特に 「Ａ->>Ｂ|Ｃ」と表記し、これを多値従属性がある、という。
「Ａ->>Ｂ|Ｃ」である時、リレーションＲは、情報を保ったまま、 Ｒ1(Ａ,Ｂ) と Ｒ2(Ａ,Ｃ) に分解できる。

結合従属性 (join dependency)

分解後の表を結合すると元の表に戻る性質。 全ての正規化は、結合従属性を維持するように行われる。
つまり、分解によって情報が失われないように表を分解していくことが、基本的な正規化のルールである。
特定のリレーションにおいて、その分解成分の自然結合をとると復元できるもののことを、「情報無損失分解*5」という。

*1:浮動小数点数は、その性質上1つの値を複数の表現で表すことができる。しかし、表現形式の違う浮動小数点数が混在していると、比較などの処理を行う際に支障をきたすため、浮動小数点数を表現する際の規格がメーカーや業界団体によって決められている。この規格に沿って浮動小数点数の表現を(実際の値を変えないまま)調整するのが浮動小数点数の正規化である。正規化の基本的なポリシーはどの規格も同じで、数値の最上位の桁が小数点のすぐ上かすぐ下に来るように小数点の位置を調整し、有効数字の桁数を最大限確保するものになっている。

*2:XMLの正規化には2種類あり、ひとつはXML規格の一部として規定されている「ノーマライズ(normalize)」、もうひとつは独立した規格として規定されている「カノニカライズ(canonicalize)」である。知名度が高いのはカノニカライズの方で、「Canonical XML」という規格で定められている。Canonical XMLは、論理的に同等の文書をバイナリデータレベルで完全に一致させるための規格で、XML文書が改竄されていないことを証明するための電子署名を有効に機能させるためのものである。

*3:特定の列を取り出すこと。　※第１、第３列を取り出すような場合、Ｐ={(x,a,p),(y,b,q),(z,c,r)}→射影:Ｐ'={(x,p),(y,q),(z,r)}　と、記述できる

*4:Faginの定理

*5:information losseless decomposition