Microsoft PowerPoint - basic-4-fd.ppt [互換モード]

Transcription

1 データベース設計関数従属性, BCNF, 3NF 講師 : 福田剛志 fukudat@fukudat.com データベース設計 (4) 1

2 関数従属性 (functional dependency or FD) [ 定義 ] 関数従属性 X A がリレーション R で成り立つとは,R の 2 つのタプルで属性 X の値が等しければ, 必ず属性 A の値も等しいことをいう. リレーションに格納されるデータが満たしている性質 例えば, 酒呑み ( 名前, 住所, 好きな酒, 製造元, 一番好きな酒 ) ありそうな関数従属性 : 名前 住所 名前 一番好きな酒 好きな酒 製造元 重要 この概念が今後のすべての議論の出発点 データベース設計 (4) 2

3 関数従属の例 名前 住所だから 名前 一番好きな酒だから 名前 住所 好きな酒 製造元 一番好きな酒 太郎 新宿 2 丁目 梅ッシュ チョーヤ 久保田千寿 太郎 新宿 2 丁目 八海山 八海酒造 久保田千寿 花子 大久保 3 丁目 梅ッシュ チョーヤ チューハイ 好きな酒 製造元だから 呑み屋 酒 値段 つぼ八 一番絞り 480 魚民 キリン淡麗 320 魚民 一番絞り 440 { 呑み屋, 酒 } 値段 データベース設計 (4) 3

4 なぜ関数従属というか? X A 属性 ( 集合 )X の値が属性 A の値を決定するのだから, 何らかの関数 (function) が存在して X の値から A を決めている. あるいは もっとも, そのような関数を構成することができるかどうかは判らない. 学籍番号で学生の名前が決まる. しかし, 学籍番号から学生の名前を計算する関数を作ることはできるだろうか. データベース設計 (4) 4

5 関数従属性表記上の慣習 X, Y, Z,... は属性の集合を現す ( ことが多い ) A, B, C, は一つの属性を表す ( ことが多い ) {A, B, C} のような属性の集合を, 単に A B C と表記する ( 括弧とカンマを省く ) X A は X determines A または X が A を決定する と読む. A が X に関数従属する. データベース設計 (4) 5

6 複数の属性に関わる関数従属性 右辺が複数属性の場合は本質的ではない 例えば, 名前 住所一番好きな酒 ならば 名前 住所 かつ 名前 一番好きな酒 と分けられるから. 複数の関数従属性をまとめて表記したいときには役に立つ. 左辺が複数属性の場合は本質的. 例えば, 呑み屋, 酒 値段 酒の 値段 は 呑み屋 だけでも 酒 だけでも決まらない. データベース設計 (4) 6

7 リレーションのキー (key) [ 定義 ] K がリレーション R のキー (key) であるとは, (1) R のすべての属性が K に関数従属であり, (2) K のどの真部分集合も (1) を満たさない 条件 (2) を省いたものを超キー (superkey) と呼ぶ. 全てのキーは超キーである. 例えば, 酒呑み ( 名前, 住所, 好きな酒, 製造元, 一番好きな酒 ) { 名前, 好きな酒 } は superkey である. なぜなら, ほかの属性はすべてこれらの値で決まる (i.e., (1) を満たす ). 名前 住所, 名前 一番好きな酒, 好きな酒 製造元 { 名前, 好きな酒 } は key である. なぜなら, その真部分集合 { 名前 }, { 好きな酒 } どちらも superkey でない (i.e., (2) を満たす ) 名前 not 製造元, 好きな酒 not 住所など ほかも superkey がある. { 名前, 好きな酒, 住所 }, { 名前, 好きな酒, 製造元 }, など データベース設計 (4) 7

8 候補キーと主キー (candidate key & primary key) 後で例を示すが, 一つのリレーションが複数個のキーを持つ場合がある. それら ( 前ページの定義に当てはまるもの ) 全部を候補キー (candidate key) と呼び, そのうち主観的に最も相応しいものを主キー (primary key) と呼ぶ ( 流儀もある ). この後の議論では使わないが, 一般によく使われるようなので, 憶えておいたほうがよい. 候補キーと主キーの違いはあくまで 主観 で, 理論的には, 候補キーと主キーに違いはない. 当然, 候補キー, 主キーは超キーである. データベース設計 (4) 8

9 ER のキーとリレーショナルのキーの比較 ER モデルのキーは実体 (entity) の所有物 リレーションのキーはタプル (tuple) の所有物 通常, 一つのタプルは一つの実体を表すので, どちらも同じ. しかし, 下手に ER からリレーションへ変換すると, 一つの実体が複数のタプルで表現されてしまうことがある. このような場合は,ER とリレーションでキーの意味が変わってしまう. データベース設計 (4) 9

10 ER とリレーションのキーの比較例 名前 住所 酒呑み 好き 酒 名前 製造元 名前 住所 好きな酒 製造元 一番好きな酒 太郎 新宿 2 丁目 梅ッシュ チョーヤ 久保田千寿 太郎 新宿 2 丁目 八海山 八海酒造 久保田千寿 花子 大久保 3 丁目 梅ッシュ チョーヤ チューハイ リレーションのキー = 名前, 好きな酒 しかし,ER モデルでは 名前 は実体集合 酒呑み のキー 好きな酒 は実体集合 酒 のキー このため, 酒呑み の実体 太郎 が2つのタプル 酒 の実体 梅ッシュ が2つのタプルで表されている. データベース設計 (4) 10

11 キーはどうやって決めればよいのか? 明らかなキー属性 K がある場合 例えば, 住民基本台帳番号, 学籍番号, パスポート番号 すべての属性 A について関数従属性 K A が成り立つので,K 以外にキーはない. ER モデルを調べることにより決まる場合 ER の実体集合のキーと多対 1 の関連をたどることでキーが決定できる 物理的制約で決まる場合 例えば, 2 つの授業は同じ時間, 同じ部屋で実施することはできない ならば, 時間部屋 授業となり,{ 時間, 部屋 } が授業のキーとなりうる データベース設計 (4) 11

12 自明 (trivial) な関数従属性 [ 定義 ] A X のとき, 関数従属性 X A は必ず成立するので, 自明 (trivial) であると言う. A A A が A を決定するのは当たり前. ABC A もう決まっているのに, 他の属性 BC を加えても, 同じ事. AB BC これは全く自明とはいえないが, 以下と同義 AB B 自明 AB C 自明でない データベース設計 (4) 12

13 異常 (anomalies) リレーショナルスキーマ設計の目的は, 異常 (anomaly) と冗長性 (redundancy) を排除すること 冗長性 (redundancy): 同じ情報が不必要に繰り返されていること 更新異常 (update anomaly): 一つ事実のある例は変更されるが, 残りが変更されないこと 削除異常 (deletion anomaly): あるタプルが削除された時に, 有効な事実まで失われてしまうこと 不適切な関数従属性は異常を引き起こす. データベース設計 (4) 13

14 悪い設計の例 酒呑み ( 名前, 住所, 好きな酒, 製造元, 一番好きな酒 ) 名前 住所 好きな酒 製造元 一番好きな酒 太郎 大久保 バド Anheuser-Busch 一番絞り 太郎??? 一番絞り キリン??? 花子 新宿 バド Anheuser-Busch バド データは冗長である : 関数従属性によって,??? の値が決定できる. 名前から住所 ( 名前 住所 ) 好きな酒から製造元 ( 好きな酒 製造元 ) データベース設計 (4) 14

15 悪い設計は, 異常を引き起こす 名前 住所 好きな酒 製造元 一番好きな酒 太郎 大久保 バド Anheuser-Busch 一番絞り 太郎 大久保 一番絞り キリン 一番絞り 花子 新宿 バド Anheuser-Busch バド 更新異常 : もし太郎が大久保から引っ越したら, 太郎に関する全てのタプル ( 行 ) を更新する必要がある. 削除異常 : もし誰もバドを好きでなくなったら, バドの製造元が Anheuser- Busch である事実がデータから消えてしまう. データが冗長である (= 望ましくない関数従属性が存在している ) ことが原因. 異常が起きない設計をするために, 答えなければならない疑問 : どういう関数従属性が成り立っているか? どういう関数従属性が 望ましくない のか? データベース設計 (4) 15

16 関数従属性の推論 異常が起きないリレーションスキーマを設計するためには, リレーションにどんな関数従属性があるかわからなければならない FD が与えられたとき, 任意の X A が成り立っているか否か判定したい. 例えば, A B かつ B C なら, 必ず A C が成り立つ. これを, 論理的に含意 (logically implied) される関数従属性という データベース設計 (4) 16

17 閉包 (closure) を求めるアルゴリズム 入力 : FD の集合 F, 属性集合 X 出力 : X の閉包 X + X + := X 繰り返し F の中から, 左辺 Y X + であるが, 右辺 A X + であるような Y A を探す. なければ終了. X + := X + + { A } はじめ X から出発して, 与えられた FD を使って広げていく. もう広げられなくなったら終了する. X + Y A 新しい X + データベース設計 (4) 17

18 閉包による関数従属性の推論 [ 定理 ] A X + ならば, そのときに限り,X A である. [ 証明 ] ( ) X + が余計なもの (X B であるような B) を含まない アウトライン : アルゴリズムのループ回数に関する帰納法を用いて, X + に含まれる属性が必ず X に関数従属することが示せる. ( ) X + は成立している FD を見逃さない アウトライン : X + に含まれない属性 C について, X C が成り立たないことが, 反例によって示せる ( 与えられた FD を全て満たし, かつ X C であるようなリレーションインスタンスが必ず構成できる ) データベース設計 (4) 18

19 閉包と超キー / キー 全ての属性が関数従属する属性集合は超キーであった. よって, 閉包 X + が全属性集合になるとき, そのときに限り,X は超キーである. 属性集合 X がキーかどうかの判定には, まず閉包 X + を求め, それが全属性集合になること. その上で, X から任意の属性を一つ除いた属性集合の閉包がどれも全属性集合にならない ( 超キーでない ). ことを調べればよい. データベース設計 (4) 19

20 なぜ必要か? 論理的に含意される (logically implied) 関数従属性をすべて見つける方法 後で説明する 正規化 (normalization) というリレーションスキーマを分解する操作で用いるため. 例えば, スキーマ ABCD にたいして, 関数従属性 AB C, C D, D A が成り立っているとする. ABCD を ABC と AD に分解したとすると,ABC ではどのような関数従属性が成り立っているか? AB C だけでなく C A も成り立つ! データベース設計 (4) 20

21 基本的な考え方 射影 (projection) のされたリレーションでどんな関数従属性 (FD) が成立するか知るためには, 与えられた FD から出発して, すべての含意された FD を見つける ( 閉包を使う ). その後, 射影後のスキーマに含まれる属性だけに制限した FD を選べばよい. データベース設計 (4) 21

22 含意される FD を全て発見する素朴なアルゴリズム 全ての部分集合 X について 閉包 X + を求める. A X + X について,X A が含意される. 但し,XY A は取り除く. なぜなら,X A が成り立っていれば, 必ず XY A なので冗長だから. 最後に, 射影された属性だけに限定する.. ただし, 部分集合 X は 2 n 1 個ある (n は属性の総数 ). 従って, この方法は指数時間かかる. データベース設計 (4) 22

23 若干の工夫 全体集合の閉包と, 空集合の閉包は求める必要がない. もし X + が全体集合であれば,X を含む集合の閉包は ( やはり全体集合となり, 新たな関数従属性を導かないので ) 求める必要がない. データベース設計 (4) 23

24 例題 スキーマ ABC に対して, 関数従属性 A B, B C が成り立っている.ABC を AC に射影した場合, どんな関数従属性が含意されるか? 解答 ) A + = ABC 従って A B, A C. ABC は全属性集合なので,AB +, AC + を求める必要はない. B + = BC 従って B C. C + = C からは何も得られない. BC + = BC からも何も得られない. 結果として得られる FD = A B, A C, B C. AC に射影すると, 残るのは A C だけ {A,C} に含まれる属性からなる FD だけを残す. データベース設計 (4) 24

25 幾何学的に見た関数従属性 あるリレーションのインスタンスをすべて想像する. 各インスタンスは, リレーションスキーマに合致しているタプルの集合 各インスタンスを要素 ( 点 =point) とする空間 (space) を考える. ちなみに, 空間 (space) とは 集合 (set) のことだが, なにか構造が付随していることを含意することが多い. データベース設計 (4) 25

26 例 : R(A,B) {(1,2), (3,4)} {} {(5,1)} {(1,2), (3,4), (1,3)} データベース設計 (4) 26

27 関数従属性はこの部分空間 任意の関数従属性 X A について, それを満たすインスタンスの集合が存在する. 従って, 関数従属性はこの空間の部分集合として表現できる. 自明な例 : A A 全体空間で表される データベース設計 (4) 27

28 例 : A B {} {(1,2), (3,4)} A B {(5,1)} {(1,2), (3,4), (1,3)} データベース設計 (4) 28

29 複数の関数従属性を表す空間 各関数従属性がある部分空間を表すのだから, 複数の関数従属性の集まりは, それらの部分空間の交わり (intersection) を表す. 交わりにあるインスタンスはすべての関数従属性を満たす A B, B C, CD A をすべて満たすインスタンスの集合 A B CD A B C データベース設計 (4) 29

30 含意される関数従属性 (implied FD) もし関数従属性 X 1 A 1,, X n A n が Y B を含意するならば, Y B の空間は X 1 A 1,, X n A n の空間の交わりを含む. つまり, X i A i (1 i n) を満たすリレーションのインスタンスは必ず Y B を満たす. ただし, 逆は成り立たない. Y B を満たすインスタンスが必ずしも X i A i (1 i n) をすべて満たすとは限らない. データベース設計 (4) 30

31 例 A C A B B C A B と B C の交わりを A C が包含している. 従って, (A B かつ B C) ならば A C. 逆に,A C であるようなインスタンスの中には, A B と B C を満たさないようなものも存在する. データベース設計 (4) 31

32 Boyce-Codd 正規形 (normal form) [ 定義 ] リレーション R 上の全ての自明でない FD X A について,X が R の超キーである時, その時に限り,R は Boyce-Code Normal Form (BCNF) であるという. 注意 : 自明でない とは,A が X の要素でないことを意味する. 超キー は, キーを含む任意の属性集合 ( キーでも良い ) リレーションが BCNF であれば, 関数従属性を原因とする異常は発生しない. データベース設計 (4) 32

33 例 酒呑み ( 名前, 住所, 好きな酒, 製造元, 一番好きな酒 ) FD: 名前 住所, 一番好きな酒 好きな酒 製造元 キーは { 名前, 好きな酒 } どちらの FD も左辺は超キーではない. よって, このリレーションは BCNF ではない. 異常が発生しうるので, 良くない設計である. データベース設計 (4) 33

34 別の例 酒 ( 名前, 製造元, 住所 ) FD: 名前 製造元 製造元 住所 キーは { 名前 }. 名前 製造元は BCNF に違反しないが, 製造元 住所は違反するので, このリレーションも BCNF ではない. 異常が発生しうるので, 良くない設計である. データベース設計 (4) 34

35 BCNF への分解 (decomposition) 非 BCNF のリレーションを複数の BCNF リレーションに変換 ( 分解 ) する方法を正規化 (normalization) という. BCNF への分解 入力 : リレーション R とその FD 集合 F. BCNF に違反する FD X A を F の中から探す. もし F に含意される FD が BCNF に違反するなら, 必ず F 内の FD 自身が BCNF に違反している. 含意される FD を調べる必要はない. X の閉包 X + を計算する 全ての属性にはならない. さもなければ,X は超キーのはず. データベース設計 (4) 35

36 X A を用いた R の分解 R を次のスキーマを持つリレーションに分解 : R 1 = X +. R 2 = (R X + ) X. 与えられた FD 集合 F を 2 つのリレーションに射影する F の閉包 = F に含意される全ての自明でない FD の集合 R 1, R 2 の属性だけを用いている FD をそのリレーションの FD とする. データベース設計 (4) 36

37 分解の概観 R 1 R-X + X X + -X R 2 R データベース設計 (4) 37

38 例 酒呑み ( 名前, 住所, 好きな酒, 製造元, 一番好きな酒 ) F = { 名前 住所, 名前 一番好きな酒, 好きな酒 製造元 } BCNF に違反する FD を選ぶ名前 住所 左辺の閉包 : { 名前 } + = { 名前, 住所, 一番好きな酒 }. リレーションを分解する : 酒呑み 1( 名前, 住所, 一番好きな酒 ) 酒呑み 2( 名前, 好きな酒, 製造元 ) データベース設計 (4) 38

39 まだ終わっていない. 例の続き 酒呑み 1, 酒呑み 2 が BCNF かどうか調べなければならない. FD の射影は一般には面倒だが, この例では簡単. 酒呑み 1( 名前, 住所, 一番好きな酒 ) に関係する FD は名前 住所, 名前 一番好きな酒. 名前がキーだから, 酒呑み 1 は BCNF. データベース設計 (4) 39

40 例のまだ続き 酒呑み 2( 名前, 好きな酒, 製造元 ) に関する FD は好きな酒 製造元で, キーは { 名前, 好きな酒 }. BCNF に違反している. 好きな酒 + = { 好きな酒, 製造元 } なので, 酒呑み 2 は次の 2 つのリレーションに分解される : 酒呑み 3( 好きな酒, 製造元 ) 酒呑み 4( 名前, 好きな酒 ) データベース設計 (4) 40

41 例の結論 リレーション酒呑みを分解した結果 : 酒呑み 1( 名前, 住所, 一番好きな酒 ) 酒呑み 3( 好きな酒, 製造元 ) 酒呑み 4( 名前, 好きな酒 ) 分解されたリレーションの意味 : 酒呑み 1 は酒呑みについて 酒呑み 3 は酒について 酒呑み 4 は酒呑みと酒の関係についてのデータである. リレーション名, カラム名を再考すべきだろう はじめから, このように設計しておけばよかった データベース設計 (4) 41

42 分解した結果から元のリレーションを復元 分解した結果を結合 (join) すれば, 元のリレーションが得られる. 酒呑み 名前 住所 好きな酒 製造元 一番好きな酒 太郎 大久保 バド Anheuser-Busch 一番絞り 太郎 大久保 一番絞り キリン 一番絞り 花子 新宿 バド Anheuser-Busch バド 分解 (decomposition) 酒呑み 1 酒呑み 3 酒呑み 4 名前 住所 一番好きな酒 好きな酒 製造元 名前 好きな酒 太郎 大久保 一番絞り バド Anheuser-Busch 太郎 バド 花子 新宿 バド 一番絞り キリン 太郎 一番絞り 花子 バド データベース設計 (4) 42

43 第 3 正規形 動機 分解する際に問題となってしまうような構造の FD が存在する. A B と BC A 例えば,A = 郵便番号, B = 市町村名, C = 町名番地 郵便番号が決まれば都市名が決まる.(A B) 都市名と町名番地が決まれば, 郵便番号が決まる.(BC A) キーが 2 種類できる : {A,C} and {B,C}. これは, キーが複数ある最初の例. A B が BCNF に違反する 左辺 A がキーではない. AB, AC に分解する. データベース設計 (4) 43

44 第 3 正規形 動機 ( つづき ) しかし, 分解してしまうと FD BC A が判らなくなってしまう! B, C が二つのリレーションに分かれてしまう. 分解されたリレーション AB, AC の FD を調べても,BC A が確認できない. 郵便番号 都市名 都市名, 町名番地 郵便番号 A 郵便番号 B 都市名 C 町番地 東京都新宿区早稲田 新潟県朝日村早稲田 A 郵便番号 B 都市名 東京都新宿区 新潟県朝日村 A 郵便番号 C 町番地 早稲田 早稲田 データベース設計 (4) 44

45 第 3 正規形 (3NF) はこの問題を回避する 第 3 正規形 (3rd Normal Form; 3NF) は BCNF の条件を変更して, この状況ではリレーションを分解しないようにする. [ 定義 ] リレーション R 上の全ての自明でない FD X A について, (1) X が超キーであるか, または, (2) A がキーの要素である時, またその時に限り, R は第 3 正規形 (3NF) であるという. ( 注意 ) 条件 (1) は BCNF の条件 条件 (2) はそれを緩和する例外 データベース設計 (4) 45

46 例 さっきの例 R( 郵便番号 A, 都市名 B, 町番地 C) では 郵便番号 A 都市名 B 都市名 B, 町番地 C 郵便番号 A だったので, { 郵便番号 A, 町番地 C} { 都市名 B, 郵便番号 C} がそれぞれキーであった. したがって, 郵便番号 A, 都市名 B, 町番地 C はどれもキーの要素. 郵便番号 都市名は BCNF に違反しているが, 右辺がキーの要素なので,3NF には違反していない. データベース設計 (4) 46

47 3NF と BCNF の性質 キーが 1 種類のとき,BCNF と 3NF は一致する. リレーションの分解の, 重要な望ましい性質 : (1) 復元性 : リレーションを分解した結果から, 元のリレーションが再構成できる. (2) 従属性の保存 : 分解されたリレーションを調べると, 与えられた関数従属性が元のリレーションで成り立っていたかどうかが判る. (1) は情報が失われないという意味で, 無損失 ともいう. (2) は分解したリレーションを独立に検査できるという意味で, 独立性 ともいう. データベース設計 (4) 47

48 3NF と BCNF の性質 ( つづき ) BCNF 分解では性質 (1) が必ず成り立つ. 3 つ以上のリレーションに分解される場合でも. 証明は, 関係代数を学んでから 3NF 分解では性質 (1), (2) が共に必ず成り立つ. しかし,BCNF 分解は必ずしも (1), (2) を満たすとは限らない. 郵便番号, 都市名, 町番地の例 データベース設計 (4) 48

49 第 1 正規形 (first normal form; 1NF) [ 定義 ] リレーション R の全ての属性値が, スカラ値であるとき,R を第 1 正規形 (first normal form; 1NF) という. スカラ値とはそれ以上分解できない値のこと. つまり, 表が 入れ子 になっていないということ. 呑み屋 魚民 酒一番絞りキリン淡麗ウーロンハイ 非第 1 正規形 呑み屋 酒 魚民 一番絞り 魚民 キリン淡麗 魚民 ウーロンハイ 第 1 正規形 データベース設計 (4) 49

50 第 2 正規形 (second normal form; 2NF) [ 定義 ] ( 第 1 正規形の ) リレーションで, すべての非キー属性が, キーに対して完全従属するとき, そのリレーションは第 2 正規形 (second normal form; 2NF) であるという 完全従属 (fully dependent) とは, 一部分ではなく全体に対して関数従属性があることをいう. 例えば,A C ならば AB C は成り立つが,C は AB に完全従属ではない ( 部分従属 ; partially dependent という ). 例 ) R(A, B, C, D) において,AB C, A D だったとする AB + = ABCD なので,AB は R のキー. D がキーの一部 A に従属 ( キーには部分従属 ) なので,R は第 2 正規形ではない. A D は 3NF 違反. 分解して 3NF にすると, 自動的に 2NF になる. データベース設計 (4) 50

51 ( 参考 ) 第 3 正規形の別定義 [ 定義 ] 第 2 正規形のリレーション R の全ての非キー属性が, キーに非推移的に従属するとき,R は第 3 正規形 (third normal form; 3NF) であるという 非キー属性とは キーの一部でない属性 (= prime でない属性 ) 非キー属性がキーに関数従属なのは当たり前 推移的 とは,A B かつ B C のとき A C どうやって遷移的かどうかを判断するか? 新しい概念 既約 (irreducible) を定義しないといけない. 他では使わないので省略する. データベース設計 (4) 51

52 ( 参考 ) 第 4, 第 5 正規形の定義 [ 定義 ] 第 3 正規形のリレーションで, キーではない属性集合からの多値従属性 (multivalued dependency) がないものを第 4 正規形 (fourth normal form; 4NF) という. [ 定義 ] 第 4 正規形のリレーションで, キー制約から導かれない結合従属性を持たないものを第 5 正規形 (fifth normal form; 5NF) という. データベース設計 (4) 52

53 関数従属性 このあとの予告 BCNF 3NF まとめ キー 超キー keys, super keys 第 3 正規形 3 rd normal form 関数従属性 functional dependency ボイス コッド正規形 Boyce-Codd normal form 多値従属性 multi-valued dependency 第 4 正規形 4 th normal form 冗長性 redundancy 異常 anomaly 結合従属性 join dependency 第 5 正規形 5 th normal form データベース設計 (4) 53

54 演習 リレーション R(A, B, C, D) で次の関数従属性が成り立っている.{ B C, B D } R のキーを全て求めよ. R は BCNF か判定せよ. 必要ならば R を BCNF に分解 ( 正規化 ) せよ. データベース設計 (4) 54

55 演習 ( 回答 ) リレーション R(A, B, C, D) で次の関数従属性が成り立っている.{ B C, B D } R のキーを全て求めよ. A + = { A }, B + = { B, C, D }, C + = { C }, D + = { D } AB + = { A, B, C, D } = R. よって,{ A, B } がキー 以下同様 他にはキーは無い. データベース設計 (4) 55

56 演習 ( 回答 ) リレーション R(A, B, C, D) で次の関数従属性が成り立っている.{ B C, B D } R のキーを全て求めよ. { A, B } R は BCNF か判定せよ. B C, B D どちらも, 左辺が超キーではないので,R は BCNF ではない. データベース設計 (4) 56

57 演習 ( 回答 ) リレーション R(A, B, C, D) で次の関数従属性が成り立っている.{ B C, B D } R のキーを全て求めよ. { A, B } R は BCNF か判定せよ. BCNF ではない. 必要ならば R を BCNF に分解 ( 正規化 ) せよ. B+ = { B, C, D } より, R(A, B, C, D) を R1(B, C, D) と R2(B, A) に分解する. R1, R2 が BCNF かどうか検査する. R1 のキーは B だから,B C, B D はともに BCNF に違反しない. 明らかに R2 は BCNF. データベース設計 (4) 57