Aritalab:Lecture/Database/FD

Revision as of 13:20, 13 September 2011

関数従属性

属性の集合 X, Y について、X の属性値が決まれば Y の値も一意に定まるとき、X → Y と書いて Y は X に従属するといいます。（逆に X は Y を決定します。）関数従属性 (functional dependency) をここではFDと書きます。

例. AB → C

アームストロングの公理

以下の規則によって、与えられた関数従属性から成立する全てのFDを導き出すことができます。

• 反射律: Y が X の部分集合なら、X → Y
• 増加律: X → Y なら、XZ → YZ
• 推移律: X → Y かつ Y → Z なら、X → Z

ここから導き出したFDの集合を F⁺と書きます。

正規形

データの整合性を保ち、構造をシンプルに保つためのガイドラインとして正規形という概念があります。正規形は第1から第5まであり、制約は次第に厳しくなりますが、実用的には第3正規形またはほぼ等価なボイス―コッド正規形 (Boyce-Codd Normal Form; BCNF) までが使われます。

正規形とFDは密接な関係にあります。A → B というFDがある場合、Aの値が決まれば B は決定されるので、

第1正規形 (first normal form)

データが全て集合やリストでなく、単一の値であるだけで第1正規形 (1NF) と呼びます。

第2正規形 (second normal form)

歴史的には定義されていますが、重要ではないのでスキップ。

BCNF

全てのFD X → A において

• A ∈ X (トリビアルなFD) であるか
• X はスーパーキー

である場合、BCNFと呼びます。簡単に言うと、FDが存在する場合は決定する属性は必ずキーではなくてはならない（値が重複する行があってはならない）ということです。

以下の例はBCNFかどうか

第3正規形 (third normal form)

3NFの定義は全てのFD X → A において

• A ∈ X (トリビアルなFD) であるか
• X はスーパーキーか、
• A はキーに含まれる

を満たすことです。BCNFは3NFよりも厳しく、BCNFなら3NFでもあります。このややこしい条件は、テーブルの中身を無駄なく分解するために技術的に設定されたものです。

正規形への変換

BCNFへの分解

関係 R がBCNFを満たさず、X → A がBCNFを満たさないFDと仮定します。このとき、R を R − A と、XA に分解します。分解後にどちらかがBCNFを満たさないときは、さらに分解していきます。

この分解にしたがえば、元の関係 R が R − A と、XA を join して再構成できるので情報を失いません。しかし、以下のような問題を考えることができます。

例

PGTという属性をもつ表があり、タンパク質 P はフェイズ T に遺伝子 G に結合するとします。各フェイズには特定の遺伝子にか結合できないので、PG → T です。また各フェイズにはタンパク質が 1 種しか反応しないとすると T → P が成立し、BCNFを満たしません。しかし、分解してしまうと PG → T が成り立ちません。（だから分解できない。）