データベース設計
関数従属性, BCNF, 3NF
講師： 福田 剛志
fukudat@fukudat.com http://www.fukudat.com/
関数従属性 (functional dependency or FD) [定義] 関数従属性 “X A” がリレーション R で成り立つ とは，R の2つのタプルで属性 X の値が等しければ， 必ず属性 A の値も等しいことをいう． • リレーションに格納されるデータが満たしている性質 • 例えば， – 酒呑み(名前，住所，好きな酒，製造元，一番好きな酒) – ありそうな関数従属性： • 名前 住所 • 名前 一番好きな酒 • 好きな酒 製造元 【重要】 この概念が今後の
関数従属の例 名前 住所 好きな酒 製造元 一番好きな酒 太郎 新宿2丁目 梅ッシュ チョーヤ 久保田千寿 太郎 新宿2丁目 八海山 八海酒造 久保田千寿 花子 大久保3丁目 梅ッシュ チョーヤ チューハイ 名前 住所 だから 好きな酒 製造元 だから 名前 一番好きな酒 だから 呑み屋 酒 値段 つぼ八 一番絞り 480 魚民 キリン淡麗 320 魚民 一番絞り 440
なぜ関数従属というか? • X A … 属性(集合)Xの値が属性Aの値を決定する のだから，何らかの関数 (function) が存在して X の値 から A を決めている． • もっとも，そのような関数を構成することができるかどう かは判らない． – 学籍番号で学生の名前が決まる．しかし，学籍番号から学生 の名前を計算する関数を作ることはできるだろうか． あるいは
関数従属性表記上の慣習 • X, Y, Z, ... は属性の集合を現す(ことが多い) • A, B, C,… は一つの属性を表す(ことが多い) • {A, B, C} のような属性の集合を，単に A B C と 表記する (括弧とカンマを省く) • X A は “X determines A” または「X が A を 決定する」と読む． – A が X に関数従属する．
複数の属性に関わる関数従属性 • 右辺が複数属性の場合は本質的ではない – 例えば， • 「名前 住所 一番好きな酒」 ならば • 「名前 住所」 かつ 「名前 一番好きな酒」 と分けられるから． – 複数の関数従属性をまとめて表記したいときには役 に立つ． • 左辺が複数属性の場合は本質的． – 例えば， • 「呑み屋, 酒 値段」
リレーションのキー (key) [定義] K がリレーション R のキー(key) であるとは， (1) R のすべての属性が K に関数従属であり， (2) K のどの真部分集合も (1) を満たさない • 条件(2)を省いたものを超キー(superkey)と呼ぶ． – 全てのキーは超キーである． • 例えば， – 酒呑み(名前，住所，好きな酒，製造元，一番好きな酒) – {名前, 好きな酒} は superkey である．なぜなら，ほかの属性はすべてこ れらの値で決まる (i.e., (1)を満たす)． • 「名前 住所」, 「名前 一番好きな酒」, 「好きな酒 製造元」 – {名前, 好きな酒} は key である．なぜなら，その真部分集合 {名前}, {好 きな酒} どちらも superkey でない (i.e., (2)を満たす) • 名前 not 製造元, 好きな酒 not 住所 など – ほかも superkey がある． • {名前, 好きな酒, 住所}, {名前, 好きな酒, 製造元}, … など
候補キーと主キー (candidate key & primary key) • 後で例を示すが，一つのリレーションが複数個 のキーを持つ場合がある． • それら（前ページの定義に当てはまるもの）全部 を候補キー (candidate key) と呼び，そのうち主 観的に最も相応しいものを主キー(primary key) と呼ぶ（流儀もある）． – この後の議論では使わないが，一般によく使われる ようなので，憶えておいたほうがよい． – 候補キーと主キーの違いはあくまで「主観」で，理論 的には，候補キーと主キーに違いはない． – 当然，候補キー，主キーは超キーである．
ERのキーとリレーショナルのキーの比較 • ERモデルのキーは実体 (entity) の所有物 • リレーションのキーはタプル (tuple) の所有物 • 通常，一つのタプルは一つの実体を表すので， どちらも同じ． • しかし，下手にERからリレーションへ変換すると， 一つの実体が複数のタプルで表現されてしまう ことがある． – このような場合は，ERとリレーションでキーの意味が 変わってしまう．
ERとリレーションのキーの比較例 • リレーションのキー = 名前, 好きな酒 • しかし，ERモデルでは • 「名前」は実体集合「酒呑み」のキー • 「好きな酒」 は実体集合「酒」のキー 名前 住所 好きな酒 製造元 一番好きな酒 太郎 新宿2丁目 梅ッシュ チョーヤ 久保田千寿 太郎 新宿2丁目 八海山 八海酒造 久保田千寿 花子 大久保3丁目 梅ッシュ チョーヤ チューハイ 住所 名前 酒呑み 名前 製造元 酒 好き • このため，
キーはどうやって決めればよいのか? • 明らかなキー属性 K がある場合 – 例えば，住民基本台帳番号，学籍番号，パスポート番号 – すべての属性 A について関数従属性 K A が成り立つの で，K 以外にキーはない． • ERモデルを調べることにより決まる場合 – ERの実体集合のキーと多対1の関連をたどることでキーが決 定できる • 物理的制約で決まる場合 – 例えば，「2つの授業は同じ時間，同じ部屋で実施することは できない」ならば，時間 部屋 授業 となり，{時間, 部屋} が 授業のキーとなりうる
自明 (trivial) な関数従属性 [定義] A ∈ X のとき，関数従属性 X A は必ず成立す るので，自明 (trivial) であると言う． • A A – A が A を決定するのは当たり前． • ABC A – もう決まっているのに，他の属性 BC を加えても，同じ事． • AB BC – これは全く自明とはいえないが，以下と同義 • AB B … 自明
異常 (anomalies) • リレーショナルスキーマ設計の目的は，異常 (anomaly) と冗長性 (redundancy) を排除する こと – 冗長性 (redundancy): 同じ情報が不必要に繰り返さ れていること – 更新異常 (update anomaly)： 一つ事実のある例は 変更されるが，残りが変更されないこと – 削除異常 (deletion anomaly): あるタプルが削除さ れた時に，有効な事実まで失われてしまうこと • 不適切な関数従属性は異常を引き起こす．
悪い設計の例 酒呑み(名前, 住所, 好きな酒, 製造元, 一番好きな酒) データは冗長である: 関数従属性によって，??? の値が決定できる． • 名前から住所 (名前 住所) • 好きな酒から製造元 (好きな酒 製造元) 名前 住所 好きな酒 製造元 一番好きな酒 太郎 大久保 バド Anheuser-Busch 一番絞り 太郎 ??? 一番絞り キリン ??? 花子 新宿 バド Anheuser-Busch バド
悪い設計は，異常を引き起こす 名前 住所 好きな酒 製造元 一番好きな酒 太郎 大久保 バド Anheuser-Busch 一番絞り 太郎 大久保 一番絞り キリン 一番絞り 花子 新宿 バド Anheuser-Busch バド • 更新異常: もし太郎が大久保から引っ越したら，太郎に関する全てのタプル （行）を更新する必要がある． • 削除異常： もし誰もバドを好きでなくなったら，バドの製造元が Anheuser-Busch である事実がデータから消えてしまう． • データが冗長である（＝望ましくない関数従属性が存在している）ことが原因． • 異常が起きない設計をするために，答えなければならない疑問： – どういう関数従属性が成り立っているか? – どういう関数従属性が「望ましくない」のか?
関数従属性の推論 • 異常が起きないリレーションスキーマを設計する ためには，リレーションにどんな関数従属性があ るかわからなければならない • FD が与えられたとき，任意の X A が成り 立っているか否か判定したい． – 例えば， • A B かつ B C なら，必ず A C が成り立つ． • これを，論理的に含意 (logically implied) される関数従属 性という
閉包 (closure) を求めるアルゴリズム 入力: FDの集合 F, 属性集合 X 出力: Xの閉包 X+ • X+ := X • 繰り返し – F の中から，左辺 Y ∈ X+ であるが，右辺 A ∈ X+ であるよ うなY A を探す．なければ終了. – X+ := X+ + { A } 新しい X+ Y A X+ • はじめ X から出発して，与えられた FD を使って広げていく． • もう広げられなくなったら終了する ．
閉包による関数従属性の推論 [定理] A ∈ X+ ならば，そのときに限り，X A である． [証明] () X+ が余計なもの(XBであるようなB)を含まない – アウトライン： アルゴリズムのループ回数に関する帰納法を 用いて， X+ に含まれる属性が必ず X に関数従属すること が示せる． () X+ は成立しているFDを見逃さない – アウトライン: X+ に含まれない属性Cについて， XCが成 り立たないことが，反例によって示せる （与えられたFD を 全て満たし，かつXCであるようなリレーションインスタン スが必ず構成できる）
閉包と超キー/キー • 全ての属性が関数従属する属性集合は超キーであっ た． • よって，閉包 X+ が全属性集合になるとき，そのときに 限り，X は超キーである． • 属性集合 X がキーかどうかの判定には， – まず閉包X+を求め，それが全属性集合になること． – その上で， X から任意の属性を一つ除いた属性集合の閉包 がどれも全属性集合にならない(超キーでない)． ことを調べればよい．
論理的に含意される(logically implied) 関数従属性をすべて見つける方法 • なぜ必要か? – 後で説明する「正規化 (normalization)」 というリレー ションスキーマを分解する操作で用いるため． • 例えば， – スキーマ ABCD にたいして，関数従属性 ABC, CD, DA が成り立っているとする．
– ABCD を ABC と AD に分解したとすると，ABC で
はどのような関数従属性が成り立っているか?
基本的な考え方 • 射影 (projection) のされたリレーションでどんな 関数従属性 (FD) が成立するか知るためには， – 与えられたFDから出発して，すべての含意された FDを見つける(閉包を使う)． – その後，射影後のスキーマに含まれる属性だけに制 限した FD を選べばよい．
含意されるFDを全て発見する素朴なアルゴリズム • 全ての部分集合 X について – 閉包 X+ を求める． – ∀A ∈ X+−X について，XA が含意される． – 但し，XYA は取り除く． • なぜなら，XA が成り立っていれば，必ず XYAなので 冗長だから． • 最後に，射影された属性だけに限定する． ． ただし，部分集合 X は 2n – 1 個 ある (n は属性の総数)． 従って，この方法は指数時間かかる．
若干の工夫 • 全体集合の閉包と，空集合の閉包は求める必 要がない． • もし X+ が全体集合であれば，Xを含む集合の 閉包は(やはり全体集合となり，新たな関数従属 性を導かないので)求める必要がない．
例題 • スキーマ ABC に対して，関数従属性 AB, BCが 成り立っている．ABC を AC に射影した場合，どんな 関数従属性が含意されるか? 解答） – A+ = ABC 従って AB, AC. • ABC は全属性集合なので，AB+, AC+ を求める必要はない． – B+ = BC 従って BC. – C+ = C からは何も得られない． – BC+ = BC からも何も得られない． – 結果として得られるFD = AB, AC, BC. – AC に射影すると，残るのは AC だけ
幾何学的に見た関数従属性 • あるリレーションのインスタンスをすべて想像す る． – 各インスタンスは，リレーションスキーマに合致して いるタプルの集合 • 各インスタンスを要素（点=point）とする空間 (space) を考える． – ちなみに，「空間 (space)」 とは 「集合 (set)」 のこと だが，なにか構造が付随していることを含意すること が多い．
例: R(A,B)
{(1,2), (3,4)}
{}
{(1,2), (3,4), (1,3)}
関数従属性はこの部分空間 • 任意の関数従属性 XA について，それを満 たすインスタンスの集合が存在する． • 従って，関数従属性はこの空間の部分集合とし て表現できる． • 自明な例： AA – 全体空間で表される
例: AB {(1,2), (3,4)} {} {(1,2), (3,4), (1,3)} {(5,1)} A B
複数の関数従属性を表す空間 • 各関数従属性がある部分空間を表すのだから， 複数の関数従属性の集まりは，それらの部分空 間の交わり (intersection) を表す． – 交わりにあるインスタンスはすべての関数従属性を 満たす AB BC CDA AB, BC, CDA を すべて満たすインスタ ンスの集合
含意される関数従属性 (implied FD) • もし関数従属性 X1A1,…, Xn An が YB を 含意するならば， YB の空間はX1A1,…, Xn An の空間の交わりを含む． • つまり， XiAi (1 ≤ i ≤ n) を満たすリレーション のインスタンスは必ずYB を満たす． – ただし，逆は成り立たない． YB を満たすインスタンスが必ずしも XiAi (1 ≤ i ≤ n) をすべて満たすとは限らない．
例 A B B C AB と BC の交わりをAC が包含している． 従って， (AB かつ BC) ならば AC. 逆に，AC であるようなインスタンスの中には， A C
Boyce-Codd 正規形 (normal form)
[定義] リレーション R 上の全ての自明でない FD
X A について，X が R の超キーである時，そ
の時に限り，R は Boyce-Code Normal Form
(BCNF) であるという． – 注意： • 「自明でない」とは，A が X の要素でないことを意味する． • 「超キー」は，キーを含む任意の属性集合（キーでも良い） • リレーションがBCNFであれば，関数従属性を原 因とする異常は発生しない．
例 • 酒呑み(名前，住所，好きな酒，製造元， 一番好きな酒） • FD: – 名前 住所, 一番好きな酒 – 好きな酒 製造元 • キーは {名前, 好きな酒} • どちらのFDも左辺は超キーではない． • よって，このリレーションは BCNF ではない． – 異常が発生しうるので，良くない設計である．
別の例 • 酒(名前，製造元，住所) • FD: – 名前 製造元 – 製造元 住所 • キーは {名前}. • 名前 製造元は BCNF に違反しないが， 製造元 住所は違反するので， このリレーションも BCNF ではない． – 異常が発生しうるので，良くない設計である．
BCNF への分解 (decomposition) • 非BCNFのリレーションを複数のBCNFリレーションに 変換（分解）する方法を正規化 (normalization) という． 【BCNFへの分解】 • 入力： リレーション R とその FD 集合 F. • BCNFに違反する FD X A を F の中から探す． – もし F に含意される FD が BCNF に違反するなら，必ず F 内の FD 自身が BCNF に違反している． – 含意される FD を調べる必要はない． • Xの閉包 X+を計算する – 全ての属性にはならない．さもなければ，X は超キーのはず．
X A を用いた R の分解 • R を次のスキーマを持つリレーションに分解: – R1 = X+. – R2 = (R – X+) ∪ X. • 与えられた FD集合 F を2つのリレーションに射 影する – Fの閉包 = Fに含意される全ての自明でないFDの集 合 – R1, R2 の属性だけを用いている FD をそのリレー ションの FD とする．
分解の概観
R－X+ X X+－X
R2
R1
例 • 酒呑み(名前, 住所, 好きな酒, 製造元, 一番好き な酒) • F = { 名前住所, 名前一番好きな酒, 好きな 酒製造元 } • BCNFに違反するFDを選ぶ 名前住所 • 左辺の閉包: {名前}+ = {名前, 住所, 一番好きな 酒}. • リレーションを分解する: – 酒呑み1(名前, 住所, 一番好きな酒)
例の続き • まだ終わっていない． • 酒呑み1, 酒呑み2が BCNF かどうか調べなけ ればならない． • FD の射影は一般には面倒だが，この例では簡 単． • 酒呑み1(名前，住所，一番好きな酒) に関係す る FD は 名前住所, 名前一番好きな酒． – 名前がキーだから，酒呑み1は BCNF.
例のまだ続き • 酒呑み2(名前，好きな酒，製造元)に関する FD は 好きな酒製造元 で，キーは {名前, 好きな 酒}. – BCNF に違反している. • 好きな酒+ = {好きな酒, 製造元} なので，酒呑み 2 は次の2つのリレーションに分解される: – 酒呑み3(好きな酒, 製造元) – 酒呑み4(名前, 好きな酒)
例の結論 • リレーション酒呑みを分解した結果: – 酒呑み1(名前，住所，一番好きな酒) – 酒呑み3(好きな酒，製造元) – 酒呑み4(名前, 好きな酒) • 分解されたリレーションの意味： – 酒呑み1 は酒呑みについて – 酒呑み3 は酒について – 酒呑み4 は酒呑みと酒の関係について のデータである． – リレーション名，カラム名を再考すべきだろう – はじめから，このように設計しておけばよかった
分解した結果から元のリレーションを復元 • 分解した結果を結合 (join) すれば，元のリレー ションが得られる． 名前 住所 好きな酒 製造元 一番好きな酒 太郎 大久保 バド Anheuser-Busch 一番絞り 太郎 大久保 一番絞り キリン 一番絞り 花子 新宿 バド Anheuser-Busch バド 名前 住所 一番好きな酒 太郎 大久保 一番絞り 好きな酒 製造元 バド Anheuser-Busch 名前 好きな酒 太郎 バド 分解 (decomposition) 酒呑み 酒呑み1 酒呑み3 酒呑み4
第3正規形 – 動機 • 分解する際に問題となってしまうような構造の FD が存 在する． • AB と BCA 例えば，A = 郵便番号, B = 市町村名, C = 町名番地 – 郵便番号が決まれば都市名が決まる．(AB) – 都市名と町名番地が決まれば，郵便番号が決まる．(BCA) • キーが2種類できる: {A,C} and {B,C}. – これは，キーが複数ある最初の例． • AB がBCNF に違反する – 左辺 A がキーではない． – AB, AC に分解する．
第3正規形 – 動機 (つづき) • しかし，分解してしまうと FD BC A が判らなくなって しまう！ – B, C が二つのリレーションに分かれてしまう． – 分解されたリレーション AB, AC の FD を調べても，BCA が確認できない． A 郵便番号 B 都市名 162-0041 東京都新宿区 958-0213 新潟県朝日村 A郵便番号 C 町番地 A 郵便番号 B 都市名 C 町番地 162-0041 東京都新宿区 早稲田 958-0213 新潟県朝日村 早稲田 • 郵便番号都市名 • 都市名, 町名番地郵便番号
第３正規形 (3NF) はこの問題を回避する • 第3正規形 (3rd Normal Form; 3NF) はBCNF の条 件を変更して，この状況ではリレーションを分解しな いようにする． [定義] リレーション R 上の全ての自明でない FD XA について， (1) X が超キーであるか，または， (2) A がキーの要素である時，またその時に限り， R は 第3正規形 (3NF) であるという． （注意） • 条件(1) は BCNF の条件 • 条件(2) はそれを緩和する例外
例 • さっきの例 R(郵便番号A, 都市名B, 町番地C)では – 郵便番号A都市名B – 都市名B, 町番地C郵便番号A だったので， – {郵便番号A, 町番地C} – {都市名B, 郵便番号C} がそれぞれキーであった． • したがって，郵便番号A，都市名B, 町番地C はどれも キーの要素． • 郵便番号都市名 は BCNF に違反しているが，右辺
3NF と BCNF の性質 • キーが1種類のとき，BCNF と 3NF は一致する． • リレーションの分解の，重要な望ましい性質： (1) 復元性: リレーションを分解した結果から，元のリレーション が再構成できる． (2) 従属性の保存: 分解されたリレーションを調べると，与えら れた関数従属性が元のリレーションで成り立っていたかどう かが判る． – (1)は情報が失われないという意味で，「無損失」ともいう． – (2)は分解したリレーションを独立に検査できるという意味で， 「独立性」ともいう．
3NF と BCNF の性質 (つづき) • BCNF 分解では性質(1)が必ず成り立つ． – 3つ以上のリレーションに分解される場合でも． – 証明は，関係代数を学んでから • 3NF 分解では性質(1), (2) が共に必ず成り立つ． • しかし，BCNF 分解は必ずしも (1), (2) を満たす とは限らない． – 郵便番号，都市名，町番地の例
第1正規形 (first normal form; 1NF) [定義] リレーション R の全ての属性値が，スカラ 値であるとき，R を第1正規形 (first normal form; 1NF) という． – スカラ値とはそれ以上分解できない値のこと． – つまり，表が「入れ子」になっていないということ． 呑み屋 酒 魚民 一番絞り 魚民 キリン淡麗 魚民 ウーロンハイ 呑み屋 酒 魚民 一番絞り キリン淡麗 ウーロンハイ 非第1正規形 第1正規形
第2正規形 (second normal form; 2NF)
[定義] (第1正規形の)リレーションで，すべての非キー属性が，キー
に対して完全従属するとき，そのリレーションは第2正規形
(second normal form; 2NF) であるという
– 完全従属 (fully dependent) とは，一部分ではなく全体に対して関数従属 性があることをいう． • 例えば，AC ならば ABC は成り立つが，CはABに完全従属ではない (部 分従属; partially dependent という)． • 例) R(A, B, C, D) において，ABC, AD だったとする – AB+ = ABCD なので，AB は Rのキー． – D がキーの一部 A に従属（キーには部分従属）なので，R は第2正規形 ではない． – ADは3NF違反．分解して3NF にすると，自動的に 2NF になる．
(参考) 第3正規形の別定義
[定義] 第2正規形のリレーション R の全ての非キー属性
が，キーに非推移的に従属するとき，R は第3正規形
(third normal form; 3NF) であるという
– 非キー属性とは、キーの一部でない属性 (= primeでない属性) – 非キー属性がキーに関数従属なのは当たり前 – 「推移的」とは，AB かつ BC のとき AC • どうやって遷移的かどうかを判断するか? – 新しい概念「既約(irreducible)」を定義しないといけない． – 他では使わないので省略する．
(参考) 第4，第5正規形の定義 [定義] 第3正規形のリレーションで，キーではない 属性集合からの多値従属性(multivalued dependency)がないものを第4正規形(fourth normal form; 4NF) という． [定義] 第4正規形のリレーションで，キー制約から 導かれない結合従属性を持たないものを第5正 規形 (fifth normal form; 5NF)という．
このあとの予告 冗長性 redundancy 異常 anomaly 関数従属性 functional dependency 多値従属性 multi-valued dependency 結合従属性 ボイス・コッド正規形
Boyce-Codd normal form
第4正規形 4th normal form 第5正規形 第3正規形 3rd normal form 関数従属性・BCNF・3NF まとめ キー・超キー
演習 • リレーション R(A, B, C, D) で次の関数従属性 が成り立っている．{ BC, BD } – R のキーを全て求めよ． – R は BCNF か判定せよ． – 必要ならば R を BCNF に分解(正規化)せよ．
演習 (回答) • リレーション R(A, B, C, D) で次の関数従属性 が成り立っている．{ BC, BD } – R のキーを全て求めよ． A+ = { A }, B+ = { B, C, D }, C+ = { C }, D+ = { D } AB+ = { A, B, C, D } = R．よって，{ A, B } がキー 以下同様…他にはキーは無い．
演習 (回答) • リレーション R(A, B, C, D) で次の関数従属性 が成り立っている．{ BC, BD } – R のキーを全て求めよ． { A, B } – R は BCNF か判定せよ． • B C, B D どちらも，左辺が超キーではないので，R は BCNF ではない．
演習 (回答) • リレーション R(A, B, C, D) で次の関数従属性 が成り立っている．{ BC, BD } – 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 だから，BC, BD はともに BCNF に違反しない． – 明らかに R2 は BCNF．
