リレーションの正規化

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2014年4月30日 (水) 08:53時点における翼のない堕天使 (トーク)による版 (著名な正規形: link)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

リレーションの正規化(リレーションのせいきか)は、関係データベース (リレーショナル・データベース) において、正規形と呼ばれる形式に関係 (リレーション) を準拠させることにより、データの一貫性の維持と効率的なデータアクセスを可能にするリレーション設計を導くための方法である。正規形には様々なものが存在するが、いずれにせよ、正規化を行うことにより、データの冗長性と不整合が起きる機会を減らすことができる。

多くの関係データベース管理システム (RDBMS) は、論理的なデータベース設計とデータを格納する物理的な実装方法とが十分に分離されていないので、完全に正規化されたデータベースへのクエリ(検索質問)はパフォーマンスが良くないことがある。このような場合、パフォーマンスを向上させるためにデータの一貫性の低下と引き換えにあえて非正規化されることもある。

正規形の定義の解釈

ある正規形であるためには、ある時点でたまたま関係 (リレーション) 中にあるすべての組 (タプル、行) の値がその定義に当てはまるだけでは十分でなく、過去及び将来において、そのリレーション中の組に増減があっても、定義から外れることがないように属性 (列、カラム) が定義されていることを要する。

注意すべきは、実際の関係データベース管理システム (RDBMS) では、属性(列)の定義域 (ドメイン) に合致する限りでリレーション(表、テーブル)の中にどんな値からなる組(行)でも入れることができるが、ここでの議論は「リレーションにはそれぞれの属性に対応した現実の事象を表す組としてシステム要件上あり得るものだけが入る」という暗黙の制約が仮定されていることである。言い換えれば、正規形の定義では各属性の値が属性ごとに一定の意味を持っていることが仮定される。これは、正規化が、与えられたある特定の要件に対して、ある特定の妥当な設計を導くための方法であることに由来する。

例えば、気象観測システム内に {観測日, 観測地, 気温} という列からなる気温観測テーブルがあるとき、{'6/9', '東京', 20} といった気温の観測データと考えられるものだけが入ると考え、システム要件から見てあり得ないもの、例えば {'6/9', '東京', -1000} といったあり得ない気温を持つ行や、政治家の誕生日、氏名、身長を表す {'1/8', '小泉純一郎', 169} といった行が入ってくることはないと仮定される。そのような仮定をすればそれぞれの定義の課する条件を常に満たすといえるとき、それぞれの正規形であるというのである。

以上の理由により、あるリレーションの形式的な定義を見ただけでは、それが正規形であるかどうかを判断することはできず、それには各属性の意味ないしそれに関するシステム要件を知る必要がある。ただし、この種の議論を行うとき、属性などに付けられた名前が自己説明的であるときは、いちいちそれらの意味を明示的に定義しないのがふつうである。

著名な正規形

これまでに様々な正規形が定義されてきているが、第1~第5正規形及びボイス・コッド正規形がとくに広く知られている。以下ではこれらの正規形の定義を列挙する。

以下で、後に示した正規形は、それより前に示した正規形の十分条件になっている。例えば、第3正規形は常に第2正規形である。なお、歴史的な順序としては、まずエドガー・F・コッドにより第3正規形までが定義され、次に第3正規形の「修正」としてボイス・コッド正規形が定義された後、ロナルド・フェイギンにより第4正規形及び第5正規形が定義された。

これらの定義に沿った正規化は実務的にもよく行われるが、その際は、第3正規形までに止めて、それで一応、十分に正規化されたと考えることが多い。

第1正規形

関係 (リレーション) がスカラ値のみを持ちうるとき、そのリレーションを第1正規形 (first normal form; 1NF) であるという。スカラ値とはそれ以上分割できない値のことをいい、単一の数値や単語は一般にスカラ値だが、表や配列、カンマで区切った文字列などはふつうスカラ値ではない。第1正規形を満たさないリレーションは、その中の値を必ずしもリレーショナル演算 (関係代数ないし関係論理による演算) の対象とすることができないという問題を持つ。

第1正規形の定義が意味することは、リレーショナル演算は単一の値として定義された以上に分割してデータを取り扱うことができないから、その必要があるデータは初めから単一の値に分解した形でリレーションに格納できるように設計すべきだということである。つまり、ある値がスカラ値であるかどうかは、その値をそれ以上分解して操作する必要があるかどうかによって初めて定まる。

同一定義域 (ドメイン) に属するスカラ値を複数組み合わせたもの(これはスカラ値でない)を一つのデータとしてリレーションに格納しようとするとき、そのデータを繰り返しグループとか反復群などという。データベース設計を行う際、スカラ値でないものを導入する必要に迫られる場合には、このような形になっていることが多い。繰り返しグループを排除して第1正規形にするには、リレーション内の反復する内容をそうでないものと別々のリレーションに分割し、それらのリレーションを主キー外部キーの関連で結びつければよい。

第2正規形

あるリレーションが、第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正規形に分解することができる。無損失とは、分解してできたリレーションを結合して元のリレーションに復元できることを指す。

第3正規形

あるリレーションが、第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正規形

第4正規形 (fourth normal form; 4NF) では候補キーではない属性への多値従属性をもった属性があってはならない。

多値従属性の定義を述べる。 R を関係とし、A, B, C を、R の属性集合の任意の部分集合とする。 R のある (A値, C値) 対に対応するB値の集合がA値だけに依存し、C値には独立かつそのときに限り、B は A に多値従属しているといい、次のように表す。

A ファイル:Twoheadrightarrow.gif B

[1]

例を示して説明する。 この例は、講義コースのリレーショナルデータベースである。 各コースで推奨されている参考図書がある。 各コースには講義する予定となっている講師がいる。

講義コースデータベースのリレーション
コース 参考図書 講師
AHA Silberschatz John D
AHA Nederpelt John D
AHA Silberschatz William M
AHA Nederpelt William M
AHA Silberschatz Christian G
AHA Nederpelt Christian G
OSO Silberschatz John D
OSO Silberschatz William M

講師はコースに属している。 参考図書はコースに属している。 講師と参考図書は互いに独立している。 こうしたことから、このデータベース設計には多値従属性が存在すると、述べることができる。 この例のリレーション (関係表、テーブル) は {コース, 参考図書, 講師} を候補キーとするボイス=コッド正規形 (BCNF) であるが、第4正規形 (4NF) ではない。 仮に AHA コースに新しい参考図書を追加しようとする場合、そのコースの各講師のデータに対して参考図書を追加しなければならない。 逆に AHA コースに新しい講師を追加しようとする場合も同様である。 形式的にはこの例のリレーションには次の2つの多値従属性がある。

この例のリレーションのように、決定項 (多値従属性の左側) が候補キーではない多値従属性のあるリレーションでは、冗長性がある。 正規化においては、自明でない多値従属性の存在するリレーションにおいては決定項が候補キーである場合に限り、第4正規形 (4NF) である。 このとき多値従属性は事実上は関数従属性である。 多値従属性は関数従属性を一般化した概念と位置づけることができる。

前述の例のリレーションは、次のように2つの第4正規形 (4NF) のリレーションに分解して正規化することができる。

コース 参考図書
AHA Silberschatz
AHA Nederpelt
OSO Silberschatz
コース 講師
AHA John D
AHA William M
AHA Christian G
OSO John D
OSO William M

第5正規形

第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 )

を満たすという。[2]

例を示して説明する。 この例は、医療情報のリレーショナルデータベースである。 このデータベースには精神科医-保険会社-病気リレーションが一つ存在する。

精神科医-保険会社-病気リレーションの候補キーは、{精神科医, 保険会社, 病気} である。 この候補キーは3つの属性から構成される複合キーである。

各精神科医は、それぞれがいくつかの保険会社から払い戻しを受けて治療を行う。 各精神科医は、それぞれがいくつかの病気を治療することができる。 各保険会社は、それぞれがいくつかの病気を保険の対象とする。

精神科医-保険会社-病気
精神科医 保険会社 病気
Dr. James Healthco 不安状態
Dr. James Healthco うつ病
Dr. Kendrick FriendlyCare 強迫神経症
Dr. Kendrick FriendlyCare 不安状態
Dr. Kendrick FriendlyCare うつ病
Dr. Kendrick FriendlyCare 気分障害
Dr. Lowenstein FriendlyCare 不安状態
Dr. Lowenstein FriendlyCare 統合失調症
Dr. Lowenstein Healthco 不安状態
Dr. Lowenstein Healthco 認知症
Dr. Lowenstein Victorian Life 転換性障害

精神科医は患者に対して、払い戻しができる範囲での治療法を行うことができる。 患者は病気にかかっており、契約した保険会社の保険に入っている。 精神科医と保険会社と病気の正当な組み合わせだけが、このリレーションに含まれるような制約が、全くなかった場合には、この3つの属性をもつ精神科医-保険会社-病気リレーションは、正しく現実世界の要件に適合するように、再設計をしなければならない。

しかしながら、ここで次の規則を適用すると前提する。 「ある精神科医が、保険会社 P の保険に入っている患者に対して、払い戻しができる範囲での治療法を行うことを承認されていて、その精神科医は病気 C の治療ができるのであれば、 – 保険会社 P が病気 C を保険の対象としている場合 – その精神科医は病気 C にかかっていて保険会社 P の保険に入っている患者に対して払い戻しができる範囲での治療を行うことができる、という命題は真にならなければならない。」

精神科医-保険会社-病気リレーションには、明らかに冗長性がある。 Dr. Lowenstein のデータを例にして考える。

  • Dr. Lowenstein がFriendlyCare社から払い戻しを受けているという事実が、2つの組 (タプル) に出現している。
  • Dr. Lowenstein がHealthco社から払い戻しを受けているという事実が、2つの組に出現している。
  • Dr. Lowenstein が不安状態の治療をすることができるという事実が、2つの組に出現している。

精神科医-保険会社-病気リレーションは、第4正規形であるが、第5正規形ではない。 なぜなら、精神科医-保険会社-病気リレーションにおいてある結合従属性を満たすが、これはこのリレーションのただ一つの候補キー {精神科医, 保険会社, 病気} によって意味されるものではないからである[3]

先述の前提のもとでは、精神科医-保険会社-病気リレーションは3つのリレーションに分解することができる。 精神科医-保険会社-病気リレーションの分解手順は次のとおりである。

  • 精神科医-保険会社-病気リレーションを {精神科医, 病気} で射影して、精神科医-病気リレーションを得る。
  • 精神科医-保険会社-病気リレーションを {精神科医, 保険会社} で射影して、精神科医-保険会社リレーションを得る。
  • 精神科医-保険会社-病気リレーションを {保険会社, 病気} で射影して、保険会社-病気リレーションを得る。
精神科医-病気
精神科医 病気
Dr. James 不安状態
Dr. James うつ病
Dr. Kendrick 強迫神経症
Dr. Kendrick 不安状態
Dr. Kendrick うつ病
Dr. Kendrick 気分障害
Dr. Lowenstein 統合失調症
Dr. Lowenstein 不安状態
Dr. Lowenstein 認知症
Dr. Lowenstein 転換性障害
精神科医-保険会社
精神科医 保険会社
Dr. James Healthco
Dr. Kendrick FriendlyCare
Dr. Lowenstein FriendlyCare
Dr. Lowenstein Healthco
Dr. Lowenstein Victorian Life
保険会社-病気
保険会社 病気
Healthco 不安状態
Healthco うつ病
Healthco 認知症
FriendlyCare 強迫神経症
FriendlyCare 不安状態
FriendlyCare うつ病
FriendlyCare 気分障害
FriendlyCare 統合失調症
Victorian Life 転換性障害

このリレーション分解により冗長性がどのように除去されるのかに注意すること。 例えば、Dr. James が FriendlyCare 社から払い戻しを受けて治療するようになる場合を考える。 リレーション分解前の精神科医-保険会社-病気リレーションでは、Dr. James は FriendlyCare 社が保険の対象としている不安状態とうつ病の治療ができるため、精神科医-保険会社-病気リレーションに2つの組 (行) を追加しなければならない。 リレーション分解後では、精神科医-保険会社リレーションに1つの組を追加するだけでよい。

第5正規形の有用性

第4正規形のリレーションが第5正規形の条件を満たさないケースは、稀でありほとんどない。 第4正規形のリレーションが第5正規形の条件を満たさない稀なケースとは、第4正規形のリレーションの属性値の組み合わせを正当にするための複雑な現実世界の制約が、そのリレーションでは強制できない場合である。

もしこのようなリレーションが第5正規形に正規化されていないのであれば、そのリレーションに含まれるデータの論理的一貫性を保つための負担の一部を、アプリケーションソフトウェアが担わなければならないのである。 アプリケーションソフトウェアは、そのリレーションに対して追加・削除・更新を行う際に、そのリレーションに含まれるデータの論理的一貫性を保つようにする責任を、担わなければならない。 そしてそのリレーションに含まれるデータの論理的一貫性が損なわれるリスクは、日を追うごとに増えてゆく。

対照的に、リレーションが第5正規形として設計されていれば、データの論理的一貫性が損なわれるこのようなリスクは、除去される。

第5正規形の有用性についての警句:

先述の例での3つのリレーションのうち2つのリレーションだけを結合するだけでは、「誤った組」が現れる可能性がある。

正しい結果セットを求めるには、3つのリレーションすべてを (再) 結合しなければならない。

ドメイン・キー正規形

ドメイン・キー正規形ではすべての制約はドメインとキー制約の結果として生じるものでなければならない。

脚注

テンプレート:脚注ヘルプ

  1. C. J. Date 、藤原譲ほか、1997年、p.358
  2. C. J. Date 、藤原譲ほか、1997年、p.362
  3. C. J. Date 、藤原譲ほか、1997年、p.363

関連項目

参考文献

テンプレート:Databaseテンプレート:Link GA