Aritalab:Lecture/Database/FD
(Created page with "==関数従属性== 属性の集合 X, Y について、X の属性値が決まれば Y の値も一意に定まるとき、X → Y と書いて Y は X に従属するとい...") |
m |
||
| Line 1: | Line 1: | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
==正規形== | ==正規形== | ||
データの整合性を保ち、構造をシンプルに保つためのガイドラインとして正規形という概念があります。正規形は第1から第5まであり、制約は次第に厳しくなりますが、実用的には第3正規形またはほぼ等価なボイス―コッド正規形 (Boyce-Codd Normal Form; BCNF) までが使われます。 | データの整合性を保ち、構造をシンプルに保つためのガイドラインとして正規形という概念があります。正規形は第1から第5まであり、制約は次第に厳しくなりますが、実用的には第3正規形またはほぼ等価なボイス―コッド正規形 (Boyce-Codd Normal Form; BCNF) までが使われます。 | ||
| − | + | 正規形とFDは密接な関係にあります。 A → B というFDがある場合、Aの値が決まれば B は決定されるのでテーブルの中にある冗長性を見つけ出す手掛かりになるからです。 | |
| − | ;第1正規形 (first normal form) | + | ;第1正規形 (first normal form, 1NF) |
データが全て集合やリストでなく、単一の値であるだけで第1正規形 (1NF) と呼びます。 | データが全て集合やリストでなく、単一の値であるだけで第1正規形 (1NF) と呼びます。 | ||
| − | ;第2正規形 (second normal form) | + | ;第2正規形 (second normal form, 2NF) |
歴史的には定義されていますが、重要ではないのでスキップ。 | 歴史的には定義されていますが、重要ではないのでスキップ。 | ||
| − | ;BCNF | + | ;Boyce-Codd 正規形 (BCNF) |
全てのFD X → A において | 全てのFD X → A において | ||
* A ∈ X (トリビアルなFD) であるか | * A ∈ X (トリビアルなFD) であるか | ||
* X はスーパーキー | * X はスーパーキー | ||
| − | + | である場合、BCNFと呼びます。簡単に言うと、FDが存在する場合は決定する属性のほうが必ずキーではなくてはならない（値が重複する行があってはならない）ということです。 | |
| − | + | ||
| + | {| | ||
| + | |'''問題''': 右の例はBCNFかどうか | ||
| + | | | ||
{| class="wikitable" | {| class="wikitable" | ||
! A || B || C | ! A || B || C | ||
| Line 44: | Line 24: | ||
|- | |- | ||
| a || y2 || c | | a || y2 || c | ||
| + | |} | ||
|} | |} | ||
| − | ;第3正規形 (third normal form) | + | ;第3正規形 (third normal form, 3NF) |
3NFの定義は全てのFD X → A において | 3NFの定義は全てのFD X → A において | ||
* A ∈ X (トリビアルなFD) であるか | * A ∈ X (トリビアルなFD) であるか | ||
| Line 53: | Line 34: | ||
を満たすことです。BCNFは3NFよりも厳しく、BCNFなら3NFでもあります。このややこしい条件は、テーブルの中身を無駄なく分解するために技術的に設定されたものです。 | を満たすことです。BCNFは3NFよりも厳しく、BCNFなら3NFでもあります。このややこしい条件は、テーブルの中身を無駄なく分解するために技術的に設定されたものです。 | ||
| − | + | ==正規形への変換== | |
| + | あるテーブルがBCNFを満たさない場合、そのテーブルには冗長な部分が潜むと考えられます。次の例を見てください。 | ||
| + | |||
| + | {| class="wikitable" | ||
| + | ! id || Species || Phyla | ||
| + | |- | ||
| + | | A || E. coli || Bacteria | ||
| + | |- | ||
| + | | B || C. elegans || Nematoda | ||
| + | |- | ||
| + | | C || E. coli || Bacteria | ||
| + | |- | ||
| + | | D || E. coli || Bacteria | ||
| + | |- | ||
| + | | E || C. elegans || Nematoda | ||
| + | |- | ||
| + | | F || E. coli || Bacteria | ||
| + | |} | ||
| + | |||
| + | 種名 (E. coli か C. elegans) が決まれば分類されるグループ (Bacteria か Nematoda) が決まるため、それぞれ同じ単語が何度も出現しています。これを二つのテーブルに分けることで、単語の重複を避けることができます。 | ||
| + | |||
| + | {| | ||
| + | | | ||
| + | {| class="wikitable" | ||
| + | ! id || Species | ||
| + | |- | ||
| + | | A || E. coli | ||
| + | |- | ||
| + | | B || C. elegans | ||
| + | |- | ||
| + | | C || E. coli | ||
| + | |- | ||
| + | | D || E. coli | ||
| + | |- | ||
| + | | E || C. elegans | ||
| + | |- | ||
| + | | F || E. coli | ||
| + | |} | ||
| + | | | ||
| + | {| class="wikitable" | ||
| + | ! Species || Phyla | ||
| + | |- | ||
| + | | E. coli || Bacteria | ||
| + | |- | ||
| + | | C. elegans || Nematoda | ||
| + | |} | ||
| + | |} | ||
| + | |||
===BCNFへの分解=== | ===BCNFへの分解=== | ||
Revision as of 09:18, 16 September 2011
正規形
データの整合性を保ち、構造をシンプルに保つためのガイドラインとして正規形という概念があります。正規形は第1から第5まであり、制約は次第に厳しくなりますが、実用的には第3正規形またはほぼ等価なボイス―コッド正規形 (Boyce-Codd Normal Form; BCNF) までが使われます。
正規形とFDは密接な関係にあります。 A → B というFDがある場合、Aの値が決まれば B は決定されるのでテーブルの中にある冗長性を見つけ出す手掛かりになるからです。
- 第1正規形 (first normal form, 1NF)
データが全て集合やリストでなく、単一の値であるだけで第1正規形 (1NF) と呼びます。
- 第2正規形 (second normal form, 2NF)
歴史的には定義されていますが、重要ではないのでスキップ。
- Boyce-Codd 正規形 (BCNF)
全てのFD X → A において
- A ∈ X (トリビアルなFD) であるか
- X はスーパーキー
である場合、BCNFと呼びます。簡単に言うと、FDが存在する場合は決定する属性のほうが必ずキーではなくてはならない（値が重複する行があってはならない）ということです。
| 問題: 右の例はBCNFかどうか |
|
- 第3正規形 (third normal form, 3NF)
3NFの定義は全てのFD X → A において
- A ∈ X (トリビアルなFD) であるか
- X はスーパーキーか、
- A はキーに含まれる
を満たすことです。BCNFは3NFよりも厳しく、BCNFなら3NFでもあります。このややこしい条件は、テーブルの中身を無駄なく分解するために技術的に設定されたものです。
正規形への変換
あるテーブルがBCNFを満たさない場合、そのテーブルには冗長な部分が潜むと考えられます。次の例を見てください。
| id | Species | Phyla |
|---|---|---|
| A | E. coli | Bacteria |
| B | C. elegans | Nematoda |
| C | E. coli | Bacteria |
| D | E. coli | Bacteria |
| E | C. elegans | Nematoda |
| F | E. coli | Bacteria |
種名 (E. coli か C. elegans) が決まれば分類されるグループ (Bacteria か Nematoda) が決まるため、それぞれ同じ単語が何度も出現しています。これを二つのテーブルに分けることで、単語の重複を避けることができます。
|
|
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 が成り立ちません。（だから分解できない。）
