Aritalab:Lecture/Database/FD - Revision history

Adm: /* 正規形 */

2011-10-03T01:56:34Z

‎正規形

Adm at 00:18, 16 September 2011

2011-09-16T00:18:20Z

Adm: Created page with "==関数従属性== 属性の集合 X, Y について、X の属性値が決まれば Y の値も一意に定まるとき、X → Y と書いて Y は X に従属するとい..."

2011-09-13T04:20:59Z

Created page with "==関数従属性== 属性の集合 X, Y について、X の属性値が決まれば Y の値も一意に定まるとき、X → Y と書いて Y は X に従属するとい..."

New page

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

; 例. AB → C
{| class="wikitable"
! A || B || C || D
|-
| a1 || b1 || c1|| d1
|-
| a1 || b1 || c1 || d2
|-
| a1 || b2 || c2 || d1
|-
| a2 || b1 || c3 || d1
|}

===アームストロングの公理===
以下の規則によって、与えられた関数従属性から成立する全てのFDを導き出すことができます。
*反射律: Y が X の部分集合なら、X → Y
*増加律: X → Y なら、XZ → YZ
*推移律: X → Y かつ Y → Z なら、X → Z
ここから導き出したFDの集合を F<sup>+</sup>と書きます。

==正規形==
データの整合性を保ち、構造をシンプルに保つためのガイドラインとして正規形という概念があります。正規形は第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かどうか
{| class="wikitable"
! A || B || C
|-
| a || y1 || c
|-
| a || y2 || c
|}

;第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 が成り立ちません。（だから分解できない。）

@@ Line 7: / Line 7: @@
 データが全て集合やリストでなく、単一の値であるだけで第1正規形 (1NF) と呼びます。
 ;第2正規形 (second normal form, 2NF)
-歴史的には定義されていますが、重要ではないのでスキップ。
+歴史的には定義されていますが、現在は重要ではないと考えられるのでスキップします。
 ;Boyce-Codd 正規形 (BCNF)
 全てのFD X &rarr; A において
@@ Line 16: / Line 16: @@
 {|
-|'''問題''': 右の例はBCNFかどうか
+|'''問題''': 右の例はBCNFかどうか<br/>答え: FD A &rarr; C だが A はキーでないのでBCNFになっていない
+|
 {| class="wikitable"

@@ Line 1: / Line 1: @@
 ==正規形==
 データの整合性を保ち、構造をシンプルに保つためのガイドラインとして正規形という概念があります。正規形は第1から第5まであり、制約は次第に厳しくなりますが、実用的には第3正規形またはほぼ等価なボイス―コッド正規形 (Boyce-Codd Normal Form; BCNF) までが使われます。
-正規形とFDは密接な関係にあります。A &rarr; B というFDがある場合、Aの値が決まれば B は決定されるので、
+正規形とFDは密接な関係にあります。 A &rarr; B というFDがある場合、Aの値が決まれば B は決定されるのでテーブルの中にある冗長性を見つけ出す手掛かりになるからです。
-;第1正規形 (first normal form)
+;第1正規形 (first normal form, 1NF)
 データが全て集合やリストでなく、単一の値であるだけで第1正規形 (1NF) と呼びます。
-;第2正規形 (second normal form)
+;第2正規形 (second normal form, 2NF)
 歴史的には定義されていますが、重要ではないのでスキップ。
-;BCNF
+;Boyce-Codd 正規形 (BCNF)
 全てのFD X &rarr; A において
 * A &isin; X (トリビアルなFD) であるか
 * X はスーパーキー
-である場合、BCNFと呼びます。簡単に言うと、FDが存在する場合は決定する属性は必ずキーではなくてはならない（値が重複する行があってはならない）ということです。
+である場合、BCNFと呼びます。簡単に言うと、FDが存在する場合は決定する属性のほうが必ずキーではなくてはならない（値が重複する行があってはならない）ということです。
-;以下の例はBCNFかどうか
 {| class="wikitable"
 ! A || B || C
@@ Line 44: / Line 24: @@
 |-
 | a || y2 || c
 |}
-;第3正規形 (third normal form)
+;第3正規形 (third normal form, 3NF)
 NFの定義は全てのFD X &rarr; A において
 * A &isin; X (トリビアルなFD) であるか
@@ Line 53: / Line 34: @@
 を満たすことです。BCNFは3NFよりも厳しく、BCNFなら3NFでもあります。このややこしい条件は、テーブルの中身を無駄なく分解するために技術的に設定されたものです。
-===正規形への変換===
+==正規形への変換==
 ===BCNFへの分解===