関係の正規化

関係の正規化（かんけいのせいきか）は、関係データベース (リレーショナル・データベース) において、関係（リレーション）を正規形と呼ばれる形式に準拠させることにより、データの一貫性の維持と効率的なデータアクセスを可能にする関係設計を導くための方法である。正規形には様々なものが存在するが、いずれにせよ、正規化を行うことにより、データの冗長性と不整合が起きる機会を減らすことができる。 多くの関係データベース管理システム (RDBMS) は、論理的なデータベース設計とデータを格納する物理的な実装方法とが十分に分離されていないので、完全に正規化されたデータベースへのクエリ（検索質問）はパフォーマンスが良くないことがある。このような場合、パフォーマンスを向上させるためにデータの一貫性の低下と引き換えにあえて非正規化されることもある。 ある正規形であるためには、ある時点でたまたま関係（表、テーブル）中にあるすべての組（タプル、行）の値がその定義に当てはまるだけでは十分でなく、過去及び将来において、その関係中の組に増減があっても、定義から外れることがないように属性（列、カラム）が定義されていることを要する。 注意すべきは、実際の関係データベース管理システムでは、属性の定義域（ドメイン）に合致する限りで関係の中にどんな値からなる組でも入れることができるが、ここでの議論は「関係にはそれぞれの属性に対応した現実の事象を表す組としてシステム要件上あり得るものだけが入る」という暗黙の制約が仮定されていることである。言い換えれば、正規形の定義では各属性の値が属性ごとに一定の意味を持っていることが仮定される。これは、正規化が、与えられたある特定の要件に対して、ある特定の妥当な設計を導くための方法であることに由来する。 例えば、気象観測システム内に {観測日, 観測地, 気温} という列からなる気温観測テーブルがあるとき、{'6/9', '東京', 20} といった気温の観測データと考えられるものだけが入ると考え、システム要件から見てあり得ないもの、例えば {'6/9', '東京', -1000} といったあり得ない気温を持つ行や、政治家の誕生日、氏名、身長を表す {'1/8', '小泉純一郎', 169} といった行が入ってくることはないと仮定される。そのような仮定をすればそれぞれの定義の課する条件を常に満たすといえるとき、それぞれの正規形であるというのである。 以上の理由により、ある関係の形式的な定義を見ただけでは、それが正規形であるかどうかを判断することはできず、それには各属性の意味ないしそれに関するシステム要件を知る必要がある。ただし、この種の議論を行うとき、属性などに付けられた名前が自己説明的であるときは、いちいちそれらの意味を明示的に定義しないのがふつうである。 これまでに様々な正規形が定義されてきているが、第1～第5正規形及びボイス・コッド正規形がとくに広く知られている。以下ではこれらの正規形の定義を列挙する。 以下で、後に示した正規形は、それより前に示した正規形の十分条件になっている。例えば、第3正規形は常に第2正規形である。なお、歴史的な順序としては、まずエドガー・F・コッドにより第3正規形までが定義され、次に第3正規形の「修正」としてボイス・コッド正規形が定義された後、ロナルド・フェイギンにより第4正規形及び第5正規形が定義された。 これらの定義に沿った正規化は実務的にもよく行われるが、その際は、第3正規形までに止めて、それで一応、十分に正規化されたと考えることが多い。 関係がスカラ値のみを持ちうるとき、その関係を第1正規形 (first normal form; 1NF) であるという。スカラ値とはそれ以上分割できない値のことをいい、単一の数値や単語は一般にスカラ値だが、表や配列、カンマで区切った文字列などはふつうスカラ値ではない。第1正規形を満たさない関係は、その中の値を必ずしもリレーショナル演算（関係代数ないし関係論理による演算）の対象とすることができないという問題を持つ。 第1正規形の定義が意味することは、リレーショナル演算は単一の値として定義された以上に分割してデータを取り扱うことができないから、その必要があるデータは初めから単一の値に分解した形で関係に格納できるように設計すべきだということである。つまり、ある値がスカラ値であるかどうかは、その値をそれ以上分解して操作する必要があるかどうかによって初めて定まる。 同一定義域に属するスカラ値を複数組み合わせたもの（これはスカラ値でない）を1つのデータとして関係に格納しようとするとき、そのデータを繰り返しグループや反復群などという。データベース設計を行う際、スカラ値でないものを導入する必要に迫られる場合には、このような形になっていることが多い。繰り返しグループを排除して第1正規形にするには、関係内の反復する内容をそうでないものと別々の関係に分割し、それらの関係を主キーと外部キーの関連で結びつければよい。 ある関係が、第1正規形で、かつ、すべての非キー属性が、すべての候補キーに対して完全従属するとき、第2正規形 (second normal form; 2NF) であるという。つまり、第2正規形では、候補キーの一部に関数従属する非キー属性があってはならない。 A及びBを属性または属性の集合としたとき、「AがBに関数従属する」とは、Bの値を決めると、常にAの値が一つに定まるような性質をAが有することをいい、これをB → Aと書く。矢印の左側、つまりここでのBのことを決定項、右側、つまりここでのAのことを従属項という。属性の集合は { } で括る。（なお、A → A、{A, B} → A のように、従属項と決定項が同じか、従属項が決定項に含まれる属性だけからなる場合を自明な関数従属といい、以下の説明では関数従属から自明な関数従属を除く。） {会員番号, 会員氏名} という関係の場合、会員番号が決まれば会員氏名も一つに定まるから、会員氏名は会員番号に関数従属する。この例でわかるように、関数従属しているためには、従属項の値が単に一つの値に対応することだけが必要であり、従属項の実際の値を導き出すのに、決定項の値だけでは情報が不足していても良い。つまり、関数従属とは、決定項が従属項のデータを取り出すための「アドレス」として使えることを意味する。 複数の属性からなる決定項のうち一部の属性にも関数従属することを部分（関数）従属（性） といい、複数の属性からなる決定項に関数従属するが部分従属はしないことを完全（関数）従属（性） という。つまり、決定項に「余分な属性」がない場合が完全従属である。 候補キーでなく、かつ、候補キーの一部でもないような属性を「非キー属性」という。候補キーに部分従属する非キー属性は、それらが表す事象の発生・消滅・変化の点において、その他の属性と直接の関連がないにもかかわらず、それらとともに一つの組にまとめられてしまっている。そのため、第2正規形でない関係は、そのような属性をその他の属性とは独立して挿入・削除・更新する必要が生じるにもかかわらず、それをすることができない（無理に行えば更新異常を起こす）。第2正規形では、この問題の一部が解決されるが、推移的関数従属性（後述）が残る。 例えば、{会社コード, 代表者氏名, 従業員番号, 従業員氏名} という従業員台帳関係で、{会社コード, 従業員番号} の集合が候補キーだとすると（従業員番号は会社内でのみ一意性が保証されているものとする）、会社コード → 代表者氏名 という部分従属があるから、この関係は第2正規形ではない。この関係では、会社コードと代表者氏名の対応が組によって異なるという事態が発生する危険があるし、従業員のデータが存在しない会社については会社コードと代表者氏名の対応を保存することができない。 第1正規形の関係は、常に無損失なように第2正規形に分解することができる。無損失とは、分解してできた関係を結合して元の関係に復元できることを指す。 ある関係が、第2正規形で、かつ、非キー属性があるならば、それら全てが候補キーに非推移的に関数従属するとき、第3正規形 (third normal form; 3NF) であるという。 候補キーA及び非キー属性B, Cを含む関係があり、A → BかつB → Cのとき、Cは候補キーAに推移的に関数従属するという。推移的に従属する属性に従属する非キー属性も同様である。非推移的に従属するとは、関数従属するが推移的に関数従属していないことをいう。 第3正規形の目的と利点は、第2正規形とほぼ同様で、差異は、第2正規形が候補キーの一部に対する従属を問題とするのに対し、第3正規形は他の非キー属性に対する従属を問題とする、という点である。 例えば、{会員番号（候補キー）, 氏名, 所属店コード, 所属店名} という属性からなる店舗の顧客会員台帳関係では（会員は常に1つの店舗にだけ所属するものとする）、会員番号 → 所属店コードであるが、所属店コード → 所属店名でもあるから、所属店名は会員番号に推移的に従属する。したがって、この関係は第3正規形でない。所属店コードが同一なのに組によって所属店名が異なるという危険が生じうる点、会員がいない店舗に対するコードと名称の対応を保存できない点など、不利な点は第2正規形と同様である。 第2正規形の関係は、常に無損失なように第3正規形に変形することができるが、その方法には妥当でないものがありうる。例えば、先程の例で挙げた関係を第3正規形に変形する方法としては、{会員番号, 氏名, 所属店コード}{所属店コード,所属店名} の2つの関係に分解する方法と、{会員番号, 氏名, 所属店コード}{会員番号, 所属店名} の2つの関係に分解する方法が考えられるが、後者の方法は妥当でない。なぜなら、この方法では、先に挙げた不利な点が解決されず、更新異常を防ぐためには、両関係のデータ間の関連が監視されなければならないからである。 このようなことが起こるのは、元の関係にあった所属店コード → 所属店名の関連を、分解後の各関係における関数従属性から導くことができない形になっているからである。一般に、関係Rをその射影である関係R1と関係R2に分解して正規化する場合、「R1とR2の上の関数従属性からRの関数従属性をすべて導くことができ、かつ、R1とR2に共通の属性が、そのいずれかにおいて候補キーを構成する」という条件を満たすように分解するのが妥当である。なお、このような条件を満たす分解を従属性保存といい、その場合のR1とR2は、両関係中のデータ間の関連を監視することなく更新できるという意味で、独立であるという。第2正規形の関係は、常に無損失かつ独立なように第3正規形に分解することができる。 妥当な第3正規形では、関数従属に関する更新異常の問題がほぼ解決されるが、複数の属性からなる候補キーがある場合にまだ例外が残る。 ある関係上に存在する自明でない全ての関数従属性の決定項が候補キーであるとき、かつそのときに限り、その関係はボイス・コッド正規形 (Boyce/Codd normal form; BCNF) であるという。すなわち、ボイス・コッド正規形では、すべての属性が候補キーに完全従属する。この定義には第3正規形への言及がないが、ボイス・コッド正規形の関係はすべて第3正規形でもある。 ボイス・コッド正規形は、ほとんどの場合第3正規形と等価であり、複数の属性からなる候補キーが複数存在する場合にのみ差異が生じうる。第3正規形は非キー属性を従属項とする関数従属性だけを問題とするので、候補キーを構成する属性の間に候補キーを決定項としない関数従属性が存在することを許す。ボイス・コッド正規形では、この問題が存在することを許さない。ボイス・コッド正規形は、いわば第3正規形をより完全にしたものである。 第3正規形の関係は、常に無損失なようにボイス・コッド正規形に分解することができる。 第4正規形 (fourth normal form; 4NF) では候補キーではない属性への多値従属性をもった属性があってはならない。 多値従属性の定義を述べる。 R を関係とし、A, B, C を、R の属性集合の任意の部分集合とする。 R のある (A値, C値) 対に対応するB値の集合がA値だけに依存し、C値には独立かつそのときに限り、B は A に多値従属しているといい、次のように表す。 A B 例を示して説明する。 この例は、講義コースの関係データベースである。 各コースで推奨されている参考図書がある。 各コースには講義する予定となっている講師がいる。 講師はコースに属している。 参考図書はコースに属している。 講師と参考図書は互いに独立している。 こうしたことから、このデータベース設計には多値従属性が存在すると、述べることができる。 この例の関係は {コース, 参考図書, 講師} を候補キーとするボイス＝コッド正規形 (BCNF) であるが、第4正規形 (4NF) ではない。 仮に AHA コースに新しい参考図書を追加しようとする場合、そのコースの各講師のデータに対して参考図書を追加しなければならない。 逆に AHA コースに新しい講師を追加しようとする場合も同様である。 形式的にはこの例の関係には次の2つの多値従属性がある。 {コース} {参考図書} {コース} {講師} この例の関係のように、決定項（多値従属性の左側）が候補キーではない多値従属性のある関係では、冗長性がある。 正規化においては、自明でない多値従属性の存在する関係においては決定項が候補キーである場合に限り、第4正規形 (4NF) である。 このとき多値従属性は事実上は関数従属性である。 多値従属性は関数従属性を一般化した概念と位置づけることができる。 前述の例の関係は、次のように2つの第4正規形 (4NF) の関係に分解して正規化することができる。 第5正規形 (fifth normal form; 5NF) を満たす関係は、その関係が第4正規形であり、さらにその関係に含まれる結合従属性の決定項が候補キーのみである場合、かつその場合だけである。 第5正規形は、射影-結合正規形 (project-join normal form; PJ/NF) とも呼ばれる。 結合従属性の定義を述べる。 R を関係とし、A, B, ... , Z を、R の属性集合の任意の部分集合とする。 このとき、R が A, B, ... , Z 上の射影の結合と等しいときかつそのときに限り、R は結合従属性 * ( A, B, ... , Z ) を満たすという。 例を示して説明する。 この例は、医療情報の関係データベースである。 このデータベースには精神科医-保険会社-病気関係が一つ存在する。 精神科医-保険会社-病気関係の候補キーは、{精神科医, 保険会社, 病気} である。 この候補キーは3つの属性から構成される複合キーである。 各精神科医は、それぞれがいくつかの保険会社から払い戻しを受けて治療を行う。 各精神科医は、それぞれがいくつかの病気を治療することができる。 各保険会社は、それぞれがいくつかの病気を保険の対象とする。 精神科医は患者に対して、払い戻しができる範囲での治療法を行うことができる。 患者は病気にかかっており、契約した保険会社の保険に入っている。 精神科医と保険会社と病気の正当な組み合わせだけが、この関係に含まれるような制約が、全くなかった場合には、この3つの属性をもつ精神科医-保険会社-病気関係は、正しく現実世界の要件に適合するように、再設計をしなければならない。 しかしながら、ここで次の規則を適用すると前提する。 「ある精神科医が、保険会社 P の保険に入っている患者に対して、払い戻しができる範囲での治療法を行うことを承認されていて、その精神科医は病気 C の治療ができるのであれば、 – 保険会社 P が病気 C を保険の対象としている場合 – その精神科医は病気 C にかかっていて保険会社 P の保険に入っている患者に対して払い戻しができる範囲での治療を行うことができる、という命題は真にならなければならない。」 精神科医-保険会社-病気関係には、明らかに冗長性がある。 Dr. Lowenstein のデータを例にして考える。 Dr. Lowenstein がFriendlyCare社から払い戻しを受けているという事実が、2つの組に出現している。 Dr. Lowenstein がHealthco社から払い戻しを受けているという事実が、2つの組に出現している。 Dr. Lowenstein が不安状態の治療をすることができるという事実が、2つの組に出現している。 精神科医-保険会社-病気関係は、第4正規形であるが、第5正規形ではない。 なぜなら、精神科医-保険会社-病気関係においてある結合従属性を満たすが、これはこの関係のただ一つの候補キー {精神科医, 保険会社, 病気} によって意味されるものではないからである。 先述の前提のもとでは、精神科医-保険会社-病気関係は3つの関係に分解することができる。 精神科医-保険会社-病気関係の分解手順は次のとおりである。 精神科医-保険会社-病気関係を {精神科医, 病気} で射影して、精神科医-病気関係を得る。 精神科医-保険会社-病気関係を {精神科医, 保険会社} で射影して、精神科医-保険会社関係を得る。 精神科医-保険会社-病気関係を {保険会社, 病気} で射影して、保険会社-病気関係を得る。 この関係分解により冗長性がどのように除去されるのかに注意すること。 例えば、Dr. James が FriendlyCare 社から払い戻しを受けて治療するようになる場合を考える。 関係分解前の精神科医-保険会社-病気関係では、Dr. James は FriendlyCare 社が保険の対象としている不安状態とうつ病の治療ができるため、精神科医-保険会社-病気関係に2つの組を追加しなければならない。 関係分解後では、精神科医-保険会社関係に1つの組を追加するだけでよい。 第4正規形の関係が第5正規形の条件を満たさないケースは、稀でありほとんどない。 第4正規形の関係が第5正規形の条件を満たさない稀なケースとは、第4正規形の関係の属性値の組み合わせを正当にするための複雑な現実世界の制約が、その関係では強制できない場合である。 もしこのような関係が第5正規形に正規化されていないのであれば、その関係に含まれるデータの論理的一貫性を保つための負担の一部を、アプリケーションソフトウェアが担わなければならないのである。 アプリケーションソフトウェアは、その関係に対して追加・削除・更新を行う際に、その関係に含まれるデータの論理的一貫性を保つようにする責任を、担わなければならない。 そしてその関係に含まれるデータの論理的一貫性が損なわれるリスクは、日を追うごとに増えてゆく。 対照的に、関係が第5正規形として設計されていれば、データの論理的一貫性が損なわれるこのようなリスクは、除去される。 第5正規形の有用性についての警句: 先述の例での3つの関係のうち2つの関係だけを結合するだけでは、「誤った組」が現れる可能性がある。 正しい結果セットを求めるには、3つの関係すべてを (再) 結合しなければならない。 ドメイン・キー正規形ではすべての制約はドメインとキー制約の結果として生じるものでなければならない。