情報無損失分解と関数従属性
本日のリレーション
今回は下記の【履修リスト】を対象に解説します． 【履修リスト】は，学籍番号，科目名，成績，教室で構成されています． また，下線は主キーを表しています．
| 学籍番号 | 科目名 | 成績 | 教室 |
|---|---|---|---|
| A001 | 情報処理演習 | A | 001 |
| A001 | プログラミング | A | 003 |
| A002 | 情報処理演習 | A | 001 |
| A002 | プログラミング | B | 003 |
| B003 | データベース | A | 002 |
| B003 | プログラミング | C | 003 |
【履修リスト】
更新時異常
リレーションの設計に問題があると， タプルの挿入・削除・更新を行う際に， 更新時異常（Update Anomaly）が発生することがあります． 【履修リスト】を例に，どのような問題が発生するか考えてみましょう．
タプル挿入時異常
カリキュラムが変更され 新規の科目「画像処理論」に関する情報を【履修リスト】に追加することを考えてみます． まだ履修する学生や成績は確定していないため，下記のタプルを追加することになります． このタプルは，主キーである学籍番号が空値であり，主キー制約に牴触してしまうため，追加することができません． これが，タプル挿入時異常 です．
| 学籍番号 | 科目名 | 成績 | 教室 |
|---|---|---|---|
| 画像処理論 | 001 |
タプル削除時異常
学籍番号B003の学生が退学した場合を考えてみます． この場合，下記の2つのタプルをリレーションから削除することになります． 削除は問題なく実行可能ですが，これを削除してしまうと， データベースの履修者が【履修リスト】に存在しなくなってしまい， $(データベース,002)$という情報も失われてしまいます． これが，タプル削除時異常 です．
| 学籍番号 | 科目名 | 成績 | 教室 |
|---|---|---|---|
| B003 | データベース | A | 002 |
| B003 | プログラミング | C | 003 |
タプル修正時異常
情報処理演習の教室が，001から004に変更になったことを考えてみます． この場合，一つの事象の変更であるにも関わらず， 情報処理演習を履修している学生が二人いるため， 2つのタプルを修正しなくてはなりません． これが，タプル修正時異常 です．
| 学籍番号 | 科目名 | 成績 | 教室 |
|---|---|---|---|
| A001 | 情報処理演習 | A | 004 |
| A002 | 情報処理演習 | A | 004 |
リレーションの分解
リレーションを分解することで，更新時異常を解消することが出来る場合があります． そこで，リレーション $R(A, B, C)$を下記の2つの射影に分解することを考えます． ここで，$A$，$B$，$C$は，リレーション$R$の属性の部分集合を表しており，属性の重複はないことを前提とします．
$$ R(A, B) $$
$$ R(A, C) $$
例えば，【履修リスト】を，【成績リスト】(学籍番号,科目名,成績)と 【科目リスト】(科目名,教室)に分解してみます． この場合，$A=\{科目名\}$，$B=\{学籍番号，成績\}$，$C=\{教室\}$に該当しています．
| 学籍番号 | 科目名 | 成績 |
|---|---|---|
| A001 | 情報処理演習 | A |
| A001 | プログラミング | A |
| A002 | 情報処理演習 | A |
| A002 | プログラミング | B |
| B003 | データベース | A |
| B003 | プログラミング | C |
【成績リスト】
| 科目名 | 教室 |
|---|---|
| 情報処理演習 | 001 |
| プログラミング | 003 |
| データベース | 002 |
【科目リスト】
このように分解することで，上述したタプル挿入時異常，タプル削除時異常， タプル修正時異常を回避することができます．
例題1
リレーションを分解したことで， タプル挿入時異常，タプル削除時異常，タプル修正時異常が解消されていることを示せ．
情報無損失分解
先ほどの例では，うまくリレーションを分解できましたが，どんな分解でも良いというわけではありません． 例えば，$R(A, B, C)$を下記のように分解することを考えます．
$$ R(A, B) $$
$$ R( C ) $$
先ほどと同じように，$A=\{科目名\}$，$B=\{学籍番号，成績\}$，$C=\{教室\}$とすると， 属性が教室だけのリレーションとなってしまい，「どの科目がどの教室なのか」という情報が失われてしまいます．
| 教室 |
|---|
| 001 |
| 003 |
| 002 |
【教室リスト】
上記のような情報損失が発生しないような分解を 情報無損失分解(Information Lossless Decomposition) と呼びます． 情報無損失分解であるためには，下記の条件を満たす必要があります．
情報無損失分解
リレーション$R$を，$R_1$と$R_2$に分解したとする． このとき，$R_1$と$R_2$の自然結合が，元のリレーション$R$に一致すれば情報無損失分解である． $$ R = R_1 * R_2 $$
例題2
【成績リスト】(学籍番号,科目名,成績)と 【科目リスト】(科目名,教室)への分解が情報無損失分解であることを示せ．
関数従属性
情報無損失分解が可能かどうかを調べる方法があります． これが 関数従属性 という考え方であり， 情報無損失分解の十分条件となっています（必ずしも満たす必要はないが，満たしていれば情報無損失分解が可能）． 関数従属性は次回に解説する「第2正規形」「第3正規形」の条件にもなっている重要な概念です．
関数従属性
リレーション$R(A, B, C)$が下記の条件を満たすとき，関数従属性$A \rightarrow B$ が成立する． $$ (\forall t_1,t_2 \in R )(t_1[A]=t_2[A] \rightarrow t_1[B]=t_2[B]) $$
関数従属性$A \rightarrow B$は，2つのタプルの属性$A$の値が同じであれば，属性$B$の値も同じであることを意味しています． この関係は関数$f(A)=B$のように記述することが可能であることから，関数従属性と呼ばれます（$A$に応じて$B$が一意に定まる）．
では，この関数従属性は，情報無損失分解とどのように関係するのでしょうか．
関数従属性と情報無損失分解
リレーション$R(A, B, C)$において，関数従属性$A \rightarrow B$ が成立するとき， 下記の分解は情報無損失分解である． $$ R(A, B) $$ $$ R(A, C) $$
つまり，リレーションに関数従属性が存在すれば，その組み合わせで情報無損失分解が可能ということです． 【履修リスト】に存在する関数従属性を探してみましょう． 例えば，$科目名 \rightarrow 教室$は成立するでしょうか． 情報処理演習は001，プログラミングは003，データベースは002に一意に決まっています． よって，$科目名 \rightarrow 教室$が成立することがわかります． すなわち，【成績リスト】(学籍番号,科目名,成績)と 【科目リスト】(科目名,教室)への分解は 情報無損失分解 であると言えます．
例題3
【履修リスト】の 成績 を被決定子（矢印の右側）とする関数従属性を示せ．
アームストロングの公理
関数従属性は「アームストロングの公理」で示される特性を持ちます． アームストロングの公理は 反射律，増加律，推移律があります． ここで，次の【科目リスト（定員を追加）】を例に考えてみます． このリレーションにおいて，$科目名 \rightarrow 教室$，$教室 \rightarrow 定員$が成立していることがわかります．
| 科目名 | 教室 | 定員 |
|---|---|---|
| 情報処理演習 | 001 | 30 |
| プログラミング | 002 | 40 |
| データベース | 001 | 30 |
【科目リスト（定員を追加）】
増加律
リレーション$R(A, B, C)$において，$A \rightarrow B$であるならば， $$ (A, C) \rightarrow (B, C) $$
増加律により，次の関数従属が成立します． $科目名 \rightarrow 教室$が成立しているので， 決定子と被決定子の両方に 定員 を加えても関数従属は成立しています．
$$ (科目名,定員) \rightarrow (教室,定員) $$
推移律
リレーション$R(A, B, C)$において，$A \rightarrow B$，かつ，$B \rightarrow C$であるならば， $$ A \rightarrow C $$
推移律により，次の関数従属が成立します． $科目名 \rightarrow 教室$，かつ，$教室 \rightarrow 定員$が成立しているため， 推移的な関数従属が成立することになります．
$$ 科目名\rightarrow 定員 $$
反射律
リレーション$R(A, B)$において，$B$が$A$の部分集合であるならば， $$ A \rightarrow B $$
反射律により，次の関数従属が成立します． 被決定子の$教室$は，決定子である$(科目名，教室)$の部分集合であるため関数従属が成立します．
$$ (科目名,教室) \rightarrow 教室 $$
情報処理技術者試験・過去問
下記リンクは ITパスポート試験ドットコム， 基本情報技術者試験ドットコム， 応用情報技術者試験ドットコム， データベーススペシャリストドットコムに掲載されている問題です．