情報無損失分解と関数従属性

Image from Gyazo

本日のリレーション

今回は下記の【履修リスト】を対象に解説します. 【履修リスト】は,学籍番号,科目名,成績,教室で構成されています. また,下線は主キーを表しています.

学籍番号 科目名 成績 教室
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パスポート試験ドットコム基本情報技術者試験ドットコム応用情報技術者試験ドットコムデータベーススペシャリストドットコムに掲載されている問題です.

愛知県名古屋市にある椙山女学園大学 文化情報学部 向研究室の公式サイトです. 専門は情報科学であり,人工知能やデータベースなどの技術要素を指導しています. この公式サイトでは,授業で使用している教材を公開すると共に, ベールに包まれた女子大教員のミステリアスな日常を4コマ漫画でお伝えしていきます. サイトに関するご意見やご質問はFacebookまたはTwitterでお問い合わせください.