情報無損失分解 - オボエガキ用

Information

version	date	memo
0.1	2013/04/13	first creation
1.0	2013/04/14	更新異常関連

TODO

正規化とか。。。

概要

情報無損失分解について、手元の本だと分りづらかったので、調べた結果をまとめる。
良い資料があったので、それ準拠で正規化関連もまとめる

正規化

そもそも
RS（リレーションスキーマの）設計が良くないと、DBの更新時に異常が起きる。
じゃあ、異常が起きないようにRS分割しましょうね＾＾
という事らしい。

重複 != 冗長

RSにおいて、重複と冗長は違うよ！

名前

性	名
入速出	やる夫
入速出	やる実
美筆	やらない夫
美筆	やらない夫

名前テーブルにおいて、性の「入速出」が重複しているが、冗長ではない。
なぜなら、重複しているからと言って、２行目を消すと名の「やる実」の情報が欠落する事になる。
また、性と名について、「美筆やらない夫」は冗長である。４行目を消しても、情報が欠落するということにはならない。

（*) 但し、「性」属性について（「性」属性の射影として）見ると、「入速出」は冗長である。

更新異常

更新異常には、次の３つがあるよ。

タプル挿入
タプル削除
タプル修正

アイテムリスト

顧客名	商品名	数量	単価	金額
虫取り少年	モンスターボール	5	200	1,000
ジョーイ	モンスターボール	5	200	1,000
レッド	すごいキズぐすり	10	1,200	12,000
ロケット団のしたっぱ	キズぐすり	5	300	1,500

タプル挿入異常

「スーパーボール」を600で売ることにした。。。
しかし、テーブルの制約上、顧客を決めないとDBに登録できない。。。
よって、挿入できない。

タプル削除異常

「レッド」から「すごいキズぐすり」の注文が取り消された。
すると、「すごいキズぐすり」を扱っている事実と単価データが消失。。。
復元できなくなるので、削除できない。

タプル修正

１行目の「モンスターボール」の単価を100に下げる。
２行目の「モンスターボール」との単価と一致しなくなる。。。
よって修正できません。。。

分解

更新時の異常が起きないように適切に分解する。
「適切に分解される」 = 「自然結合により元に戻る」
この事を情報無損失分解という。

さっきのアイテムリストテーブルを情報無損失分解すると、次のようになる。
伝票

顧客名	商品名	数量	金額
虫取り少年	モンスターボール	5	1,000
ジョーイ	モンスターボール	5	1,000
レッド	すごいキズぐすり	10	12,000
ロケット団のしたっぱ	キズぐすり	5	1,500

アイテム

商品名	単価
モンスターボール	200
すごいキズぐすり	1,200
キズぐすり	300

分解の定義

リレーションスキーマ $RS = \{A_1,\dots,A_n\}$ に対して、 $RS_i \subseteq RS (1\le i \le m)$ なるリレーションスキーマの集合 $\rho=\{RS_1,\dots,RS_m\}$ の内
$RS_1\cup\dots\cup RS_m=RS$
となるものをRSの分解と呼ぶ。

情報無損失分解の定義

RSに関する関数従属性集合FとRSの分解 $\rho=\{RS_1,\dots,RS_m\}$ が与えられたとき、Fを満足するRSのすべてのインスタンスRについて
$R=\pi_{RS_1}(R) \triangleright\triangleleft \dots \triangleright\triangleleft \pi_{RS_m}(R)$
が成立するとき、分解 $\rho$ はRSの情報無損失分解であるという。

(注意)
結合記号は「 $\triangleright\triangleleft$ 」*1を用いることにする。
また、 $\pi_{RS_n}$ は $RS_n$ の射影

上の例で言うと、
$RS_1 =$ {顧客名, 商品名, 数量, 金額}
$\pi_{RS_1} =$

顧客名	商品名	数量	金額
虫取り少年	モンスターボール	5	1,000
ジョーイ	モンスターボール	5	1,000
レッド	すごいキズぐすり	10	12,000
ロケット団のしたっぱ	キズぐすり	5	1,500