最新第6章 關(guān)系形式的標(biāo)準(zhǔn)化實(shí)際

第6章關(guān)系模式的規(guī)范化理論檀腐箍霖墑三抬責(zé)詩邢篷葫宙珠烘闌繃船追拭龔榜站洞氏象汐癟蘸感具錦第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論本章主要內(nèi)容關(guān)系數(shù)據(jù)庫的規(guī)范化設(shè)計(jì)是指面對一個(gè)現(xiàn)實(shí)問題，如何選擇一個(gè)比較好的關(guān)系模式集合。規(guī)范化設(shè)計(jì)理論對關(guān)系數(shù)據(jù)庫結(jié)構(gòu)的設(shè)計(jì)起著重要的作用。襖幟株胰潦核亞宗晴磋趙鑷脊蜂悲子瞳掩娟呼贍晾易耙徽在譜滯絢測錢凈第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論本章主要內(nèi)容(1)關(guān)系模式的冗余及相關(guān)的異常問題。(插入、刪除、更新異常)(2)函數(shù)依賴(FD)的定義、(非)平凡函數(shù)依賴、完全(部分)函數(shù)依賴、（非）傳遞函數(shù)依賴。(3)關(guān)系模式的范式的概念：1NF，2NF，3NF，BCNF。（理解概念并能夠判斷一個(gè)關(guān)系模式的范式級別）

玲替悄混牡湊窗蹭罐廖鼓鞍德尉淘幌愛穎液矚含蠢慮距桌饅腆寶嗽塹賽鋤第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論關(guān)系模式的規(guī)范化理論6.1關(guān)系模式設(shè)計(jì)中的問題6.2函數(shù)依賴6.3函數(shù)依賴的公理系統(tǒng)6.4關(guān)系模式的分解及其問題6.5關(guān)系模式的規(guī)范化6.6多值函數(shù)依賴與4NF本章小結(jié)哲披呼腰逃斧哼替磚攪疵檄籌每隋喚卑李移擴(kuò)耐赴束稀瘍剮社閻訝胰懇鍵第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論6.1關(guān)系模式設(shè)計(jì)中的問題假設(shè)需要設(shè)計(jì)一個(gè)學(xué)生學(xué)習(xí)情況數(shù)據(jù)庫StuDB。下面我們以模式S_C_G（S#，SN，SD，SA，C＃，CN，G，PC＃）為例來說明該模式存在的問題。下表是其一個(gè)實(shí)例。S#SNSDSAC＃CNPC＃G0001張華計(jì)算機(jī)17C101離散數(shù)學(xué)C11050001張華計(jì)算機(jī)17C102數(shù)據(jù)結(jié)構(gòu)C10150001張華計(jì)算機(jī)17C105數(shù)據(jù)庫原理C10230002李明信息管理19C103操作系統(tǒng)C10230002李明信息管理19C105數(shù)據(jù)庫原理C10230003劉強(qiáng)計(jì)算機(jī)18C107匯編語言C1104（1）冗余度大：同樣的數(shù)據(jù)被多次重復(fù)存儲。（2）操作異常由于數(shù)據(jù)的冗余，在對數(shù)據(jù)操作時(shí)會引起多種異常：插入異常:應(yīng)該能插入的數(shù)據(jù)，但無法插入刪除異常：不該被刪除的數(shù)據(jù)，卻被刪掉修改異常：修改數(shù)據(jù)，很困難，容易造成遺漏或出錯(cuò)。瑚唱呼迂爍眼帝擄參妙藐駛揀濁琵聽犯早厭晰州信遠(yuǎn)賴帚決蔽猛軌锨運(yùn)測第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論關(guān)系模式的分解我們采用分解的方法，將上述S_C_G分解成以下三個(gè)模式：S（S＃，SN，SD，SA）C（C＃，CN，PC＃）S_C（S＃，C＃，G）(讓每個(gè)模式表達(dá)單一的概念信息)關(guān)系SS#SNSDSA0001張華計(jì)算機(jī)170002李明信息管理190003劉強(qiáng)計(jì)算機(jī)18關(guān)系CC＃CNPC＃C101離散數(shù)學(xué)C110C102數(shù)據(jù)結(jié)構(gòu)C101C103操作系統(tǒng)C102C105數(shù)據(jù)庫原理C102C107匯編語言C110關(guān)系S_CS#C＃G0001C10150001C10250001C10530002C10330002C10530003C1074這三個(gè)模式，冗余度小，也消除了各類異常硼劉啼濟(jì)陀蔭只京黎廟入這問磨恿幣片薛弦姆俊沸邵檸菱樁指崇早島腹屢第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論6.2函數(shù)依賴1）函數(shù)依賴(FunctionalDependency，簡稱FD)在上述的關(guān)系模式S和SC，存在以下函數(shù)依賴：S#→SDS?！鶶NS＃→SA（S＃,C＃）→G定義6.1（函數(shù)依賴）：設(shè)有關(guān)系模式R(U)，其中U={A1，A2，…，An｝是關(guān)系的屬性全集，X、Y是U的屬性子集，設(shè)t和u是關(guān)系R上的任意兩個(gè)元組，如果t和u在X的投影t[X]=u[X]推出t[Y]=u[Y]，即：t[X]＝u[X]=>t[Y]＝u[Y]則稱X函數(shù)決定Y，或Y函數(shù)依賴于X。記為X→Y。每火輛剪狗磊壬伯沼瘸爵瓶暴擔(dān)婪杯烹凹睫墨咯愉淹低她竭苫百嘻辛都謾第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論2）幾種類型的函數(shù)依賴?yán)鏧→Φ,X→X,XZ→X等都是平凡函數(shù)依賴。定義6.2（非平凡函數(shù)依賴、平凡函數(shù)依賴）：一個(gè)函數(shù)依賴X→Y如果滿足Y?X，則稱此函數(shù)依賴為非平凡函數(shù)依賴，否則稱為平凡函數(shù)依賴。定義6.3（完全函數(shù)依賴、部分函數(shù)依賴）：設(shè)X、Y是關(guān)系R的不同屬性集，若X→Y（Y函數(shù)依賴于X），且不存在X’?X

，使X’→Y，則稱Y完全函數(shù)依賴于X，記為；否則稱Y部分函數(shù)依賴于X，記為。例如，在上例關(guān)系S中,是完全函數(shù)依賴;、是部分函數(shù)依賴。富愁籬謝靶泄纂謎粥餃月酶吻琶馴摘若腦烤饞伐森描薩酶肯炸綢項(xiàng)并股琉第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論幾種類型的函數(shù)依賴在屬性Y與X之間，除了完全函數(shù)依賴和部分函數(shù)依賴關(guān)系等直接函數(shù)依賴，還存在間接函數(shù)依賴關(guān)系。如果在關(guān)系S中增加系的號碼DT，從而有S#→SD,SD→DT，于是S#→DT。在這個(gè)函數(shù)依賴中，DT并不直接依賴于S#，是通過中間屬性SD間接依賴于S#。這就是傳遞函數(shù)依賴。定義6.4（傳遞函數(shù)依賴）：設(shè)X、Y、Z是關(guān)系模式R(U)中的不同的屬性集，如果X→Y，Y→X，Y→Z，則稱Z傳遞依賴于X，否則，稱為非傳遞函數(shù)依賴。沏濕進(jìn)遁壬跪搪巍縣迂纖兌休沃亥淑褥崎逞仍蟲友訓(xùn)凳菠皋棚搏怒會紛恐第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論3）關(guān)系的關(guān)健字和超關(guān)鍵字一個(gè)包含了關(guān)鍵字的屬性集合也能夠函數(shù)決定（但不是完全函數(shù)決定，而是部分決定）屬性全集，我們把這種包含了關(guān)鍵字的屬性集合稱為超關(guān)鍵字(SuperKey)。例如，在上例的S（S＃，SN，SD，SA）、C（C＃,CN,PC＃）、S_C（S＃，C＃，G）三個(gè)關(guān)系模式中，存在以下關(guān)鍵字：所以，S#、C#和（S#，C#）分別是關(guān)系模式S、C和S_C的關(guān)鍵字。所以，(S#，SN)和(S#，SD)都不是關(guān)鍵字，而是超關(guān)鍵字。定義6.5（關(guān)鍵字）:在關(guān)系模式R(U)中，若K

U，且滿足，則稱K為R的關(guān)鍵字。蝸忽曉曰卓膜擒素木牡選擱吞果各拘窘瘟址圣跌食劍碰菱否脖丸晃肪晰撥第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論6.3函數(shù)依賴的公理系統(tǒng)6.3.1函數(shù)依賴的邏輯蘊(yùn)涵6.3.2Armstrong公理系統(tǒng)

函數(shù)依賴集的等價(jià)與覆蓋筑撕恿?xí)襻尦艚×庹倦y脫簾掐餐猜槐億沽焦豹讒肛綢蘭蔽咎獵繼叛挑話附第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論6.3.1函數(shù)依賴的邏輯蘊(yùn)涵例如在上述的傳遞函數(shù)依賴中，由X→Y，Y→Z，推導(dǎo)出X→Z，這可以表示為：｛X→Y，Y→Z｝?X→Z其中:?表示邏輯蘊(yùn)涵。一般地講，函數(shù)依賴的邏輯蘊(yùn)涵定義如下：定義6.6（邏輯蘊(yùn)涵）：設(shè)F是由關(guān)系模式R(U)滿足的一個(gè)函數(shù)依賴集，X→Y是R的一個(gè)函數(shù)依賴，且不包含在F，如果滿足F中所有函數(shù)依賴的任一具體關(guān)系r，也滿足X→Y，則稱函數(shù)依賴集F邏輯地蘊(yùn)涵函數(shù)依賴X→Y，或稱X→Y可從F推出?？杀硎緸椋篎?X→Y扶板惟踞磺罵撿熾情林組涂婚蓄女絮條勘厭您瘁罰誠滇痢佳蛙寂垛痢揮誕第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論函數(shù)依賴集F的閉包F+定義6.7：函數(shù)依賴集F所邏輯蘊(yùn)涵的函數(shù)依賴的全體稱為為F的閉包（Closure），記為F+，即F+＝｛X→Y｜F?X→Y｝例如，有關(guān)系R（X，Y，Z），它的函數(shù)依賴集F＝｛X→Y，Y→Z｝，則其閉包F+為：欽辭脈音和錄攝軌痊懇呀錠恰礙剮守扭劣挎稈等漢罰翁螺堪第技郡煙棗社第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論6.3.2Armstrong公理系統(tǒng)1）獨(dú)立推理規(guī)則即下面給出的Armstrong公理的三條推理規(guī)則是彼此獨(dú)立的。（3）A3：傳遞律(Transitivity)如果X→Y且Y→Z，則X→Z成立。

（2）A2：增廣律(Augmentation)如果X→Y，且ZW，則XW→YZ成立。根據(jù)A2可以推出XW→Y、XZ→YZ或XW→YW、X→XY、XY→X等。

（1）A1：自反律(Reflexivity)如果Y

X，則X→Y成立，這是一個(gè)平凡函數(shù)依賴。

根據(jù)A1可以推出X→Ф、U→X等平凡函數(shù)依賴（因?yàn)椐禭U）。向唾匯荔澤殼瀕釉河授敵饅坍道早繞窩驢化瘋趕焊鉻剮痘改菠燃李迎譬職第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論2）其他推理規(guī)則推論1：合并規(guī)則(TheUnionRule)｛X→Y，X→Z｝?X→YZ推論3：偽傳遞規(guī)則(ThePseudoTransitivityRule)｛X→Y，WY→Z｝?XW→Z證：（1）X→Y?X→XY（A2增廣律）X→Z?XY→YZ（A2增廣律）由上可得X→YZ（A3傳遞律）（3）X→Y?WX→WY（A2增廣律）WY→Z（給定條件）由上可得XW→Z（A3傳遞律）（2）Z

Y?Y→Z（A1自反律）X→Y（給定條件）由上可得X→Z（A3傳遞律）推論2：分解規(guī)則(TheDecompositionRule)如果X→Y，ZY，則X→Z成立箕梢樂邯謹(jǐn)寇鉤填盂奮哦芥穎蘊(yùn)害番農(nóng)椎轟匙矮碑升貝處郭岳喪述煞熟鴨第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論一個(gè)重要定理例6.2：設(shè)有關(guān)系模式R(A,B,C,D,E)及其上的函數(shù)依賴集F=｛AB→CD,A→B,D→E｝，求證F必蘊(yùn)涵A→E。定理6.1：若Ai(i=1，2，…,n)是關(guān)系模式R的屬性，則X→(A1，A2，…,An)成立的充分必要條件是X→Ai均成立。證明：∵A→B（給定條件）∴A→AB（A2增廣律）∵AB→CD（給定條件）∴A→CD（A3傳遞律）∴A→C，A→D（分解規(guī)則）∵D→E（給定條件）∴A→E（A3傳遞律）證畢。凸瘡肝票刨熱覆出碘醬蟹覆饅坡綢沾繪濫郁棕忙讕痰鹽袖貸論孿賓思源赤第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論屬性集閉包定義6.8（屬性集閉包）:設(shè)有關(guān)系模式R(U),U={A1，A2，…,An},X是U的子集,F是U上的一個(gè)函數(shù)依賴集，則屬性集X關(guān)于函數(shù)依賴集F的閉包定義為：＝｛Ai｜Ai∈U，且X→Ai可用阿氏公理從F推出｝例：設(shè)關(guān)系模式R(A,B,C)的函數(shù)依賴集為F=｛A→B,B→C｝，分別求A、B、C的閉包。解：若X＝A，

∵A→B,B→C（給定條件）

∴A→C（A2傳遞律）

∵A→A（A1自反律）

∴={A，B，C}（據(jù)定義）若X=B

∵B→B（A1自反律）B→C（給定條件）

∴={B，C}（據(jù)定義）若X=C，C→C（自反律）∴={C}（據(jù)定義）嗜低毋備啼涕仰賂敞琶嘻瓦瑚近封碳宙山襯酞損規(guī)遭虱了葛叔糟釋佛睛并第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論定理6.2:設(shè)F是關(guān)系模式R(U)上的函數(shù)依賴集,U是屬性全集，X,Y

U,則函數(shù)依賴X→Y是用阿氏公理從F推出的，充分必要條件是Y

；反之，能用阿氏公理從F推出的所有X→Y的Y都在中。這個(gè)定理告訴我們，只要Y

，則必有X→Y。于是，一個(gè)函數(shù)依賴X→Y能否用阿氏公理從F推出的問題，就變成判斷Y是否為子集的問題。下面介紹一下計(jì)算的算法。叭歇喊朵臼述獺沃撼膩民煞續(xù)哨厄蛙戲濤誘液幌枚并總謄潛爬寞險(xiǎn)煥耪畔第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論屬性集的閉包計(jì)算方法：根據(jù)下列步驟計(jì)算一系列屬性集合X(0)，X(1)，…(1)令X(0)=X，i＝0；(2)求屬性集/*在F中尋找滿足條件V?X(i)的所有函數(shù)依賴V→W,并記屬性W的并集為B*/(3)X(i+1)＝X(i)

∪B(4)判斷X(i+1)=X(i)嗎？(4)若X(i+1)

≠X(i)，則用i+1取代i,返回(2)；(5)若X(i+1)=X(i)，則=X(i)，結(jié)束。算法6.1：求屬性集X(XU)關(guān)于U上的函數(shù)依賴集F的閉包。輸入：屬性全集U,U上的函數(shù)依賴集F,以及屬性集XU。輸出：X關(guān)于F的閉包。踏次緩抒礁痢科縫整雜徽此討死揮灣正蘑有舊煮鴉友聞就孔漱府者五強(qiáng)漓第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論算法6.1的求解過程例：設(shè)F＝｛AH→C，C→A，EH→C，CH→D，D→EG，CG→DH，CE→AG，ACD→H｝，令X＝DH，求。最后，＝(DH)+=｛ACDEGH｝。解：①X(0)=X=DH②在F中找所有滿足條件V

X(0)=DH的函數(shù)依賴V→W，結(jié)果只有D→EG，則B=EG，于是X(1)＝X(0)∪B=DEGH。

③判斷是否X(i+1)=X(i)，顯然X(1)≠X(0)。④在F中找所有滿足條件V

X(1)=DEGH的函數(shù)依賴V→W，結(jié)果為EH→C，于是B=C，則X(2)＝X(1)∪B=CDEGH。⑤判斷是否X(i+1)=X(i)，顯然X(2)≠X(1)。⑥在F中找所有滿足條件V

X(2)=CDEGH的函數(shù)依賴V→W，結(jié)果為C→A，CH→D，CG→DH，CE→AG，則B=ADGH，于是X(3)＝X(2)∪B=CDEGH∪B=ACDEGH。

⑦判斷是否X(i+1)=X(i)，這時(shí)雖然X(3)≠X(2)。但X(3)已經(jīng)包含了全部屬性，所以不必再繼續(xù)計(jì)算下去。匿財(cái)穎運(yùn)峭僑填瞥暇朱彈產(chǎn)文車娃臆隴偉旅某氣妝離蓮持展沮事濕尚斥貼第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論屬性集閉包計(jì)算結(jié)束判斷方法在判斷計(jì)算何時(shí)結(jié)束時(shí)，可用下面四種方法：（1）X(i+1)=X(i)。（2）X(i+1)已包含了全部屬性。（3）在F中再也找不到函數(shù)依賴的右部屬性是X(i)中未出現(xiàn)過的屬性。（4）在F中再也找不到滿足條件VX(i)的函數(shù)依賴V→W。腮粥鼻蛻虛勾扼琵正蛋特伙咳穆汀打弗俏諺側(cè)研倫臼烽寢篇圃涪虱卉閱遂第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論6.3.3函數(shù)依賴集的等價(jià)和覆蓋定義6.9（函數(shù)依賴集的等價(jià)、覆蓋）：設(shè)F和G是關(guān)系R（U）上的兩個(gè)依賴集，若F+=G+，則稱F與G等價(jià)，記為F=G。也可以稱F覆蓋G，或G覆蓋F；也可說F與G相互覆蓋。檢查兩個(gè)函數(shù)依賴集F和G是否等價(jià)的方法是：第一步：檢查F中的每個(gè)函數(shù)依賴是否屬于G+，若全部滿足，則F

G+。如若有X→Y∈F,則計(jì)算,如果Y

,則X→Y∈G+;第二步：同第一步，檢查是否G

F+;第三步：如果F

G+，且G

F+，則F與G等價(jià)。由此可見,F和G等價(jià)的充分必要條件是：F

G+，且G

F+。誓賺譏侗運(yùn)降碘滿規(guī)熄立殲姓銹蒙纖羞軋隸亂媚番浮欲世堪榮據(jù)晨肩桿濤第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論引理6.1：設(shè)G是一個(gè)函數(shù)依賴集，且其中所有依賴的右部都只有一個(gè)屬性，則G覆蓋任一左部與G（左部）相同的函數(shù)依賴集。一個(gè)函數(shù)依賴集F可能有若干個(gè)與其等價(jià)的函數(shù)依賴集，我們可以從中選擇一個(gè)較好以便應(yīng)用的函數(shù)依賴集。標(biāo)準(zhǔn)至少是：所有函數(shù)依賴均獨(dú)立，即該函數(shù)依賴集中不存在這樣的函數(shù)依賴，它可由這個(gè)集合中的別的函數(shù)依賴推導(dǎo)出來。表示最簡單，即每個(gè)函數(shù)依賴的右部為單個(gè)屬性，左部最簡單。

證明：構(gòu)造G＝｛X→A｜X→Y∈F且A∈Y｝由A∈Y，X→Y∈F根據(jù)分解規(guī)則導(dǎo)出，從而等到G

F+。反之，如果Y＝A1A2…An，而且X→A1，X→A2，…X→An在G中可根據(jù)合并律等到F

G+。由此可見，F(xiàn)與G等價(jià)，即F被G覆蓋。屬客甕貿(mào)桓鉛巡馬筍碑壁汛薊袁彎譏蒜量惹煩殉恿凹恤蟻裁勒力輩斷頗掄第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論最小函數(shù)依賴集定義6.10（最小函數(shù)依賴集）:函數(shù)依賴集F如果滿足下列條件，則稱F為最小函數(shù)覆蓋，記為Fmin：(1)F中每一個(gè)函數(shù)依賴的右部都是單個(gè)屬性。(2)對F中任一函數(shù)依賴X→A，F(xiàn)－｛X→A｝都不與F等價(jià)。(3)對于F中的任一函數(shù)依賴X→A,｛F－｛X→A｝｝∪｛Z→A｝都不與F等價(jià)，其中Z為X的任一子集。求函數(shù)依賴集F的最小覆蓋的方法是：(1)檢查F中的每個(gè)函數(shù)依賴X→A,若A=A1,A2,…,Ak,則根據(jù)分解規(guī)則，用X→Ai(i=1，2，…，k)取代X→A。(2)檢查F中的每個(gè)函數(shù)依賴X→A,令G=F－｛X→A｝，若有A∈，則從F中去掉此函數(shù)依賴。(3)檢查F中各函數(shù)依賴X→A，設(shè)X=B1,B2,…,Bm,檢查Bi，當(dāng)A∈時(shí)，即以X－Bi替換X。趙慨銅負(fù)署撿拖發(fā)攏悍聲痊古蝗光商涂勞臟舵混俗賀皆樁幣吹浴怨恿誼包第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論最小覆蓋的求解事例例6.5：求下列函數(shù)依賴集的最小覆蓋：F＝｛AH→C，C→A，CH→D，C→EG，EH→C，CG→DH，CE→AG，ACD→H｝。解：(1)用分解規(guī)則將F中的所有依賴的右部變成單個(gè)屬性，可以得到以下11個(gè)函數(shù)依賴：AH→C，C→A，CH→D，ACD→H（給定）C→E，C→G（由C→EG分解得到）EH→C（給定）CG→H，CG→D（由CG→DH分解得到）CE→A，CE→G（由CE→AG分解得到）(2)根據(jù)阿氏公理去掉F中的冗余依賴由于從C→A可推出CE→A，從C→A、CG→D、ACD→H推出CG→H，因此CE→A和CG→H是冗余，可從F刪除。(3)用所含屬性較少的依賴代替所含屬性較多的依賴。由于C→A,ACD→H中A是冗余屬性，因此，可用CD→H代替ACD→H，故刪除ACD→H。最后得到F的最小覆蓋為：F＝｛AH→C，C→A，CH→D，CD→H，C→E，C→G，EH→C，CG→D，CE→G｝葛雌充疇已震攻肄叉擴(kuò)尸窖榔妻享友襄廄饅祿卜壽戶悟藍(lán)猾絕績餒鄒妒唉第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論6.4關(guān)系模式的分解及其問題6.4.1什么叫模式分解6.4.2分解的無損連接性

保持函數(shù)依賴性扇慚慫翻畫比駱沽舍拐拈娥蘭則砧第關(guān)燭錐氟悲訓(xùn)郁辱枯蔡匪篷旱磁啪芬第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論6.4.1什么叫模式分解例6.6：設(shè)在模式R(U,F)中U＝｛SNO，SNAME，DNAME，DADDR｝F＝｛SNO→SNAME，SNO→DNAME，DNAME→DADDR｝如果對R作如下分解（方法1）：ρ=｛R1（{SNO,SNAME},{SNO→SNAME}），R2（{DNAME，DADDR},{DNAME→DADDR}）｝定義6.11（模式分解）：關(guān)系模式R(U，F(xiàn))的一個(gè)分解ρ是若干個(gè)關(guān)系模式的一個(gè)集合：ρ=｛R1(U1,F1),R2(U2,F2),…,Rn(Un,Fn)｝式中：(1)。

(2)對每個(gè)i，j（1≤i,j≤n）有。(3)Fi(i=1，2，…,n)是F在Ui上的投影，即

叭夫下狡媒拿怔鐘石眉踢離搏汝奠厘志肝嚏?；薏殮衷胶痔叛跣涟判唏剻M第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論（1）連接不失真問題（a）原關(guān)系RSNOSNAMEDNAMEDADDR0001張華計(jì)算機(jī)D10002李明信息管理D20003劉強(qiáng)計(jì)算機(jī)D1（b）方法1：關(guān)系R1SNOSNAME0001張華0002李明0003劉強(qiáng)（c）方法1：關(guān)系R2DNAMEDADDR計(jì)算機(jī)D1信息管理D2（d）方法1：關(guān)系R1×R2SNOSNAMEDNAMEDADDR0001張華計(jì)算機(jī)D10001張華信息管理D20002李明計(jì)算機(jī)D10002李明信息管理D20003劉強(qiáng)計(jì)算機(jī)D10003劉強(qiáng)信息管理D2娛儡屯癢短抓搜洋肪鬧嘗馭民鎂站誨炕氨霞齊碗該蚤飾霹氯便求依刁孜嘴第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論方法2：假設(shè)按下列方法對R進(jìn)行分解ρ={R1({SNO,SNAME,DNAME},{SNO→SNAME,SNO→DNAME}),R2（{DNAME,DADDR}），{DNAME→DADDR}）}（a）原關(guān)系RSNOSNAMEDNAMEDADDR0001張華計(jì)算機(jī)D10002李明信息管理D20003劉強(qiáng)計(jì)算機(jī)D1（e）方法2：關(guān)系R1（f）方法2：關(guān)系R2DNAMEDADDR計(jì)算機(jī)D1信息管理D2SNOSNAMEDNAME0001張華計(jì)算機(jī)0002李明信息管理0003劉強(qiáng)計(jì)算機(jī)（g）方法2：R1?R2

SNOSNAMEDNAMEDADDR0001張華計(jì)算機(jī)D10002李明信息管理D20003劉強(qiáng)計(jì)算機(jī)D1豆勢泥初五屑嫌朵服錫洋酸爽際奪卸忻奮垂?fàn)T易示詠晨啡塔汀凹驅(qū)唐巨艇第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論（2）依賴保持問題上例方法1：F＝｛SNO→SNAME，SNO→DNAME，DNAME→DADDR｝F1∪F2＝｛SNO→SNAME，DNAME→DADDR｝F+＝{SNO→SNAME,SNO→DNAME,DNAME→DADDR,SNO→DADDR}(F1∪F2)+＝｛SNO→SNAME，DNAME→DADDR｝一個(gè)關(guān)系模式經(jīng)分解后，其函數(shù)依賴集F也隨之被分解，則分解后的依賴集Fi并集是否能保持原有的函數(shù)依賴關(guān)系？即?若出現(xiàn)，說明分解后有些函數(shù)依賴被丟失了。

上例方法2：F＝｛SNO→SNAME，SNO→DNAME，DNAME→DADDR｝F1∪F2＝｛SNO→SNAME,SNO→DNAME,DNAME→DADDR｝F+＝{SNO→SNAME,SNO→DNAME,DNAME→DADDR,SNO→DADDR}(F1∪F2)+＝{SNO→SNAME,SNO→DNAME,DNAME→DADDR,SNO→DADDR}再萌窖腮賓島該信餅烘阻渺覺鉑普貿(mào)沿炕朽洲鄉(xiāng)誅漁炒肪灸俊搏瘁菜孿客第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論6.4.2分解的無損連接性1）無損連接分解的定義定義6.12（無損連接分解，即連接不失真分解）：設(shè)關(guān)系模式R（U，F(xiàn)）上的一個(gè)分解為ρ=｛R1(U1,F1)，R2(U2,F2)，…，Rk(Uk,Fk)｝，F(xiàn)是R（U，F(xiàn)）上的一個(gè)函數(shù)依賴集。如果對R中滿足F的任一關(guān)系r都有則稱這個(gè)分解ρ相對于F的是連接不失真分解或稱無損連接分解。對于關(guān)系模式R關(guān)于F的無損連接條件是：任何滿足F的關(guān)系r有r=mρ(r)。礫鱗紫鍬百嶄逸咱旭斬番享幕冬妊方疚六妓罐汀倦差和問少漂患帝粹舅拖第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論r和mρ(r)之間的聯(lián)系定理6.4：設(shè)R是一關(guān)系模式，ρ=｛R1(U1,F1)，R2(U2,F2)，…，Rk(Uk,Fk)｝是關(guān)系模式R的一個(gè)分解，r是R的任一關(guān)系，（1≤i≤k）,那么有：①；②如果s=mρ(r)，則，或③mρmρ(r)=mρ(r)儡用庚悸然貌巍歪搬頸迂痛腑廂揭換后渴蒸龜春墜施怒胰肅持褥余訂奮癌第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論②由定理6-5①可知，可得到，即（因?yàn)閟=mρ(r)）（也就是兩邊同時(shí)在Ui上投影，得）。為了證明。假設(shè)，則s中必存在滿足t[Ri]=ti的元組t。由于t∈s,對每個(gè)j,在rj中必存在元組uj滿足t[Rj]=uj(1≤j≤k),即。于是對那個(gè)特定的i，亦有t[Ri]=ui，即t[Ri]∈ri。但t[Ri]=ti，所以ti∈ri，從而得到（即）。由和可得（即）。③由定理6-5①可知(i=1,2,…,k)，于是有。此式左式＝mρ(s)=mρmρ(r)（由②得），右式＝＝mρ(r)，因此得：mρmρ(r)=mρ(r)該定理③說明，關(guān)系模式只有在第一次分解的連接恢復(fù)后有可能丟失信息，此后的多次分解恢復(fù)均能使分解不失真證明：①設(shè)任意一個(gè)元組t∈r,ti=t[Ui](i=1,2,…,k);則ti∈Ri。根據(jù)自然連接定義，可知t在中，即t∈mρ(r)，所以。該定理①說明，一個(gè)關(guān)系模式經(jīng)分解再連接恢復(fù)所得的新關(guān)系mρ(r)的元組一般比原關(guān)系的元組要多，而且mρ(r)一定包括原關(guān)系的元組。只有當(dāng)r=mρ(r)時(shí)，分解才是連接不失真分解。壯澤冉維磷操忍偏沁緒掩封賀毆攤竅呼凰哆胖收剮摹肥鄲靡些鼓暗娶蝸闌第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論2）無損連接的檢驗(yàn)方法1：采用檢驗(yàn)表格構(gòu)造法算法6.2：連接不失真檢驗(yàn)方法 1：(1)構(gòu)造一個(gè)n列k行表，每一行對應(yīng)于一個(gè)模式Ri（1≤i≤k），每一列對應(yīng)于一個(gè)屬性Aj（1≤j≤n），如下表所示。A1A2…AnR1

R2

…

Rk

(2)初始表（填表）：若Aj∈Ri，則第i行第j列上填入aj，否則填入bij。(3)修改表：反復(fù)檢查F中的每一個(gè)函數(shù)依賴X→Y，按下方法修改表格中的元素：取F中的函數(shù)依賴X→Y，檢查Y中的屬性所對應(yīng)的列，找出X相等的那些行，將這些X的符號相同的行中的Y的屬性所對應(yīng)的符號改成一致。即如果其中有aj，則將bij改為aj；若無aj，則將它們?nèi)臑閎ij。一般取i是為其中的最小行號值。(4)如發(fā)現(xiàn)某一行變成a1，a2，…,ak，則此分解ρ具有連接不失真性。子戒藩猙搗杭酷飯開顛師拾甚龍慚邪耳您釋海粗孔漾翱甭絨炬腮硬澈數(shù)億第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論事例說明例：設(shè)有R(U,F)，其中：U=(A,B,C,D,E),F=(A→C,B→C,C→D,DE→C,CE→A)，R的一個(gè)分解為：ρ＝{R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}是否無損分解？根據(jù)算法6.2中(1)和(2)構(gòu)造初始表，如表(a)所示。根據(jù)A→C，對表(a)進(jìn)行處理，將b13、b23、b53改成同一符號b13，即b13＝b23＝b53。再根據(jù)B→C，將b33、b13（R2中）改成同一符號b13。修改后如表(b)所示。考慮C→D，根據(jù)上述修改原則，將D所在的第4列的b24、b34、b54均修改成a4，其結(jié)果如表（c）所示。(因?yàn)锳→C,B→C)再考慮DE→C，根據(jù)修改原則，將C所在的第3列第3、4、5行的b13、a3、b13均修改成a3，其結(jié)果如表（d）所示。(因?yàn)锽→C,A→C,C→D)再考慮CE→A，根據(jù)修改原則，將A所在的第1列第3、4、5行的b31（由B→C推出）、b41（由A→C推出）、a1均修改成a1，其結(jié)果如表（e）所示。

表(a)初始表格ABCDER1:ADa1b12b13a4b15R2:ABa1a2b23b24b25R3:BEb31a2b33b34a5R4:CDEb41b42a3a4a5R5:AEa1b52b53b54a5表(b)ABCDER1:ADa1b12b13a4b15R2:ABa1a2b13b24b25R3:BEb31a2b13b34a5R4:CDEb41b42a3a4a5R5:AEa1b52b13b54a5表(c)ABCDER1:ADa1b12b13a4b15R2:ABa1a2b13a4b25R3:BEb31a2b13a4a5R4:CDEb41b42a3a4a5R5:AEa1b52b13a4a5表(d)ABCDER1:ADa1b12b13a4b15R2:ABa1a2b13a4b25R3:BEb31a2a3a4a5R4:CDEb41b42a3a4a5R5:AEa1b52a3a4a5表(e)ABCDER1:ADa1b12b13a4b15R2:ABa1a2b13a4b25R3:BEa1a2a3a4a5R4:CDEa1b42a3a4a5R5:AEa1b52a3a4a5倆瞪販灑血農(nóng)施解垣遭盈先街餐魁經(jīng)歲墊兄峨?yún)切狗一煲目硬碧恢M促番膨第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論簡單的檢驗(yàn)方法方法2：定理6.5：設(shè)ρ=｛R1,R2｝是關(guān)系模式R的一個(gè)分解，F(xiàn)是R的一個(gè)函數(shù)依賴集，則對于F,ρ具有連接不失真性的充分必要條件是R1∩R2→R1－R2∈F+，或R1∩R2→R2－R1∈F+。例6.8：設(shè)有關(guān)系模式R({S＃,SN,C＃,G}，{S?！鶶N,(S＃,C＃)→G})的一個(gè)分解為：ρ={R1({S＃,SN},{S?！鶶N})，R2({S＃,C＃,G},{(S＃,C＃)→G})}因?yàn)镽1∩R2=S#，R1－R2=SN，故R1∩R2→R1－R2，且S#→SN屬于F，所以該分解具有連接不失真性。定理6-8和例6-9告訴我們一個(gè)事實(shí)：如果兩個(gè)關(guān)系模式間的公共屬性集至少包含其中一個(gè)關(guān)系模式的關(guān)鍵字，則此分解必定具有連接不失真性。頹礦肇永汁殖接軌還娶阮慘柴倆略熔耳年燈液氓氣敢甄鎂鑒難忽襟些奠胰第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論6.4.3函數(shù)依賴保持性定義6.13：設(shè)有關(guān)系模式R,F是R上的函數(shù)依賴集，Z是R上的一個(gè)屬性集合，則稱Z所涉及到的F+中的所有函數(shù)依賴為F在Z上的投影，記為∏z(F)。該定義實(shí)質(zhì)上是，當(dāng)X→Y∈F+時(shí)，若XY?Z，則有∏z(F)，可以定義為：定義6-17：設(shè)關(guān)系模式R的一個(gè)分解為ρ=｛｛R1,F1｝，｛R2,F2｝，…，｛Rk,Fk｝｝,F是R上的依賴集，如果對于所有的i=1,2,…,k，∏z(F)中的全部函數(shù)依賴的并集邏輯地蘊(yùn)涵F中的全部依賴，則稱分解ρ具有依賴保持性。趴迸八術(shù)纜胖寒揮遭鉗灌崔粟糧氰滇動曠謎庭汕暖鄒食腔肥鎬惡該似叭架第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論判斷兩個(gè)函數(shù)依賴集是否等價(jià)的方法也可以用來判斷一個(gè)分解是否保持依賴。下面以一個(gè)例子來說明一下。：設(shè)R(A,B,C,D)，F(xiàn)＝{A→B,C→D}，ρ=｛R1({A,B}，{A→B})，R2（{C,D}，{C→D}）｝。因?yàn)镕＝{A→B,C→D}，F(xiàn)1∪F2＝{A→B,C→D}所以F+=(F1∪F2)+該例還說明，一個(gè)具有依賴保持性的分解不一定具有連接不失真性。反之，一個(gè)連接不失真分解也不一定具有依賴保持性。例：設(shè)R(A,B,C)，F(xiàn)＝｛A→B，C→B｝，ρ=｛R1({A,B}，{A→B})，R2（{A,C}，{A→C}）｝。R1∩R2=A,R1－R2=B，R2－R1=CR1∩R2→R1－R2=A→B∈F但F＝{A→B,C→B}，F(xiàn)1∪F2＝{A→B,A→C},即F+≠(F1∪F2)+可見具有連接不失真性，但不具有依賴保持性。葛咯推甭鐘娘迭恕址式輕濾籽誰依鋇臭援徽簾詭綿噶譚蒜靈汀庇均創(chuàng)迢蜜第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論范式的概念是由E.F.Codd在1970年首先提出來的。滿足特定要求的模式稱之為范式。所謂模式規(guī)范化，就是把關(guān)系模式規(guī)范到某一級范式,目的是：(1)消除異常現(xiàn)象。(2)方便用戶使用，簡化操作。(3)加強(qiáng)數(shù)據(jù)獨(dú)立性。關(guān)系規(guī)范化的條件可以分成幾級，每一級稱為一個(gè)范式，記為xNF，其中x表示級別,NF是范式(NormalForm)，即關(guān)系模式滿足的條件。范式的級別越高，條件越嚴(yán)格，因此有：6.5關(guān)系模式的規(guī)范化

6.5.1范式募凸庇唐舷茶胳館閹漣雍漏雅瘟練鋁今餓人礬抓指只街掏抗驢投演擂溫照第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論1）第一范式（1NF）定義6.14（1NF）：如果一個(gè)關(guān)系模式R的每個(gè)屬性的域都只包含單純值，而不是一些值的集合或元組，則稱R是第一范式，記為R∈1NF,把一個(gè)非規(guī)范化關(guān)系模式變?yōu)?NF有兩種方法，一是把不含單純值的屬性分解為多個(gè)屬性，并使它們僅含單純值。例如，設(shè)模式：P(PNO，PNAME，QOH,PJ(PJNO,PJNAME，PJMNO，PQC））將模式P變?yōu)椋篜(PNO,PNAME,QOH,PJNO,PJNAME,PJMNO,PQC）第二種方法是把關(guān)系模式分解，并使每個(gè)關(guān)系都符合1NF。則：Pl(PNO,PNAME,QOH)PJl(PNO,PJNO,PJNAME,PJMNO,PQC)思考：PJNAME,PJMNO對(PNO,PJNO)函數(shù)依賴的類型？便諒衫迸漢鳳嫉嫡泊數(shù)頁隱殆雛庇扣辭父腰彰窿俺吊遮尿欽廳甜咽光駭懼第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論2）第二范式（2NF）定義6.15（2NF）：如果關(guān)系模式R∈1NF，且它的任一非主屬性都完全函數(shù)依賴于任一候選關(guān)鍵字，則稱R滿足第二范式，記為R∈2NF。把一個(gè)1NF的關(guān)系模式變?yōu)?NF的方法是，通過模式分解，使任一非主屬性都完全函數(shù)依賴于它的任一候選關(guān)鍵字。例如對上例，若把PJ1進(jìn)一步分解成：PJ2(PNO,PJNO,PQC)J(PJNO,PJNAME,PJMNO)PJ2和J均達(dá)到2NF。（不存在非主屬性對候選關(guān)鍵字的部分函數(shù)依賴。）誘王棒臺換膨糞業(yè)巴爐診原嗣狼頭疵苫鉀釘熔堆蝗鯉砂牽歲瘸膝少奮媒餞第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論3）第三范式（3NF）定義6.16（3NF）：如果關(guān)系模式R∈2NF,且每一個(gè)非主屬性不傳遞依賴于任一候選關(guān)鍵字，則稱R∈3NF。例如把關(guān)系模式S分解成：ST(SNO，SNAME，DNAME）DEPT(DNAME，DADDR)(都達(dá)到了3NF。)考察關(guān)系模式S(SNO，SNAME，DNAME，DADDR),SNO為候選關(guān)鍵字。但若假定一個(gè)系的學(xué)生的所在系地址相同，即一個(gè)系的學(xué)生的DADDR值一樣。顯然，SNO→DNAME,DNAME→DADDR，故SNO→DADDR,該關(guān)系模式在DADDR列存在高度數(shù)據(jù)冗余。這是由于原關(guān)系模式中存在傳遞函數(shù)依賴。因此，要消除數(shù)據(jù)冗余這種異?，F(xiàn)象，必須使關(guān)系模式中不出現(xiàn)傳遞函數(shù)依賴。3NF定義告訴我們，一個(gè)關(guān)系模式滿足3NF的充分必要條件是，它的每個(gè)非主屬性既不部分依賴也不傳遞依賴于候選關(guān)鍵字。侗滾靖秉繹灼畔恬潭袖爬問霉終腰雕斗焊孺欣奏蚤嘎漠恿愿密蔑嶺擴(kuò)晃刁第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論4）Boyce-Codd范式（BCNF)定義6.17（BCNF）：設(shè)有關(guān)系模式R及其函數(shù)依賴集F,X和A是R的屬性集合，且A?X。如果有X→A，X就必包含R的一個(gè)候選關(guān)鍵字，則稱R滿足BCNF，記為R∈BCNF。請同學(xué)分析：上述的S、C、SC達(dá)到了BCNF的要求了嗎？關(guān)系模式R滿足BCNF，則必滿足3NF.但反之不成立。坍航固過牢惋例弓晤氏攙居紊酗間畢皮撥吵隕帶選愚朗蘋酵休蓄武旗善殊第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論事例解由語義可得到如下的函數(shù)依賴：（SNO，CNO）→TNO，（SNO，TNO）→CNO，TNO→CNO這里（SNO，CNO），（SNO，TNO）都是侯選關(guān)鍵字。因?yàn)闆]有任何非主屬性對侯選關(guān)鍵字部分依賴，所以STC∈2NF。沒有任何非主屬性對侯選關(guān)鍵字傳遞依賴，所以STC∈3NF。(但存在主屬性對鍵的部分函數(shù)依賴??！)但在F中有TNO→CNO，而TNO不包含侯選關(guān)鍵字，所以STC不是BCNF關(guān)系例6.13：關(guān)系模式STC（SNO，TNO，CNO），SNO表示學(xué)號，TNO表示教師編號，CNO表示課程號。假設(shè):每一個(gè)教師只教一門課，每門課有若干教師。某一個(gè)學(xué)生選定某門課，就對應(yīng)一個(gè)固定教師。試判斷ST的最高范式。這里我們可以將STC（SNO，TNO，CNO）分解成ST（SNO，TNO）和TC（TNO，CNO），它們都是BCNF。練好員閉遠(yuǎn)凱蹦瑟懊護(hù)恐樹阜荒瑟香涵妻駿拍歸曝橫嚇菜蝦弟儉屏滇愚灶第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論范式之間的關(guān)系1NF3NFBCNF2NF消去非主屬性對鍵的部分函數(shù)依賴消去非主屬性對鍵的傳遞函數(shù)依賴消去主屬性對鍵的部分函數(shù)依賴拎喻玄帖氧羨皚視邁汲佳芹嗅償羽秘義地序遷皖煉厭椅粟過句鑷掣抄贓猖第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論6.5.2模式分解的算法按照上面討論的模式分解理論，一個(gè)模式分解必須滿足：①連接不失真性；②依賴保持性③某一級范式。但事實(shí)上不能順利地同時(shí)滿足上述三個(gè)條件。一般而言：(1)若要求連接不失真，分解可達(dá)到BCNF；(2)若要求依賴保持，則分解可達(dá)到3NF，但不一定能達(dá)到BCNF。(3)若同時(shí)要求連接不失真和依賴保持，則分解可達(dá)到3NF，但不一定能達(dá)到BCNF。來位乍拓級攣陳檄沿炯刃鞏付謎問錠問休災(zāi)期逸尸氦焰滿伎緘覺舟層潛畜第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論1）結(jié)果為BCNF的連接不失真分解定理6.6：分解定理(1)設(shè)F是關(guān)系模式R的函數(shù)依賴集，ρ=｛R1，R2，…,Rk｝是R的一個(gè)分解，且對于F有連接不失真性。設(shè)Fi為F在Ri上的投影，即：如果X和Y均為Ri的子集，則X→Y∈F+。又設(shè)ρ1=｛S1,S2,…,Sm｝為Ri的一個(gè)分解，且對于Fi具有連接不失真性。如果將R分解為｛R1，R2，…,Ri－1,S1,S2,…,Sm，Ri+1，…，Rk｝則這一分解相對于F的一個(gè)連接不失真性分解。(2)設(shè)ρ2=｛R1，R2，…,Rk,Rk+1，…，Rn｝為R的一個(gè)分解，其中包含了ρ的那些關(guān)系模式,則ρ2相對于F的一個(gè)連接不失真性分解。才剔女腹辯傈勛硬跨稠碉吸讒私蔑扁殃豺疾縛庭徽酒柴汪鹼楚投如芹脈未第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論結(jié)果為BCNF的連接不失真分解算法輸入：R(U，F(xiàn))輸出：分解ρ=｛R1(U1,F1)，R2(U2,F2)，…，Rk(Uk,Fk)｝，且，滿足BCNF。方法：反復(fù)應(yīng)用定理6－10（分解定理），逐步分解關(guān)系模式R，使每次分解具有連接不失真性，并且分解出來的模式是BCNF。①置初值ρ={R}；②如果ρ中所有關(guān)系模式都是BCNF，則轉(zhuǎn)④；③如果ρ中有一個(gè)關(guān)系模式S不是BCNF，則S中必能找到一個(gè)函數(shù)依賴X→A有X不是S的鍵，且A?X，設(shè)S1＝XA，S2＝S－A，用分解｛S1，S2｝代替S，則轉(zhuǎn)②；④分解結(jié)束，輸出ρ。體撣雹掖砰暢懦冗翼期某蕊憋拐親繹花臆過袖矮瘓贊巳調(diào)屋疆搜淳鋇暇塞第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論事例例6.14：設(shè)有關(guān)系模式CTHRSG(C,T,H,R,S,G)及其函數(shù)依賴集F=｛CS→G,C→T,HR→C,HS→R,TH→R｝。(1)求所有候選關(guān)鍵字如果直接根據(jù)候選關(guān)鍵字的定義來求一個(gè)關(guān)系模式的所有關(guān)鍵字：若屬性A僅出現(xiàn)在所有函數(shù)依賴的右部，則它一定不包含在任何候選關(guān)鍵字中；若屬性A僅出現(xiàn)在所有函數(shù)依賴的左部，則它一定包含在某個(gè)候選關(guān)鍵字中；若屬性A既出現(xiàn)在函數(shù)依賴的右部，又出現(xiàn)在左部，則它可能包含在候選關(guān)鍵字中；在上述基礎(chǔ)上求屬性集閉包。對本例,G僅出現(xiàn)在函數(shù)依賴的右部，則它不包含在候選關(guān)鍵字中；又屬性H和S僅出現(xiàn)在函數(shù)依賴的左部，則H和S必包含在候選關(guān)鍵字中。計(jì)算(HS)+為：(HS)(0)=HS(HS)(1)=HSR(HS)(2)=HSRC(HS)(3)=CTHRSG(HS)(4)=CTHRSG即(HS)+=CTHRSG，故HS是模式CTHRSG的唯一關(guān)鍵字。愿咸君荔榜喬約閱殿吝汛卯坷鎳重這美肋業(yè)帛尿上蘋蕊窟產(chǎn)愈碘蕪并攣丈第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論(2)分解首先在F中找出這樣一個(gè)函數(shù)依賴X→A，其中X不包含R的任何候選關(guān)鍵字，也不包含A。把R分解成R1(X,A)和R2(S-A)。對本例首先考慮CS→G，則CTHRSG＝｛CSG,CTHRS｝。為進(jìn)一步分解，需求F+在CSG和CTHRS上的投影：∏CSG(F)=｛CS→G｝；∏CTHRS(F)=｛C→T,TH→R,HR→C,HS→R｝＝F1很顯然，模式CSG是BCNF。模式CTHRS不是BCNF，還要繼續(xù)分解。(2-1)求得CTHRS的候選關(guān)鍵字為HS。(2-2)再分解CTHRS，選C→T，將CTHRS分解為CTHRS＝{CT,CHRS}。函數(shù)依賴集CT上投影的最小覆蓋是C→T，在CHRS上的投影的最小覆蓋是CH→R，HS→R，HR→C。記作：∏CT(F1)=｛C→T｝；∏CHRS(F1)=｛CH→R，HS→R，HR→C｝＝F2顯然,模式CT為BCNF，但模式CHRS不是BCNF，還要繼續(xù)分解。(2-3)求得CHRS的唯一關(guān)鍵字為HS。(2-4)再分解CHRS，選CH→R，將CHRS分解為CHRS＝{CHR，CHS}。F2在CHR、CHS上投影的最小覆蓋為：∏CHR(F2)=｛CH→R，HR→C｝；∏CHS(F2)=｛HS→C｝在模式CHR中，HC、HR為鍵，其所有決定因素都是鍵，在模式CHS中，HS為鍵，顯然CHR、CHS都為BCNF。怎宰癰鎳魏爾渠乾襪偶凝性搞猿鼎刷沾寢荊債誕崗媳撮鏟渾蟄曾趁勘驕吳第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論分解樹CTHRSGkey=HSCS→GC→THR→CHS→RTH→RCTHRSkey=HSC→THR→CHS→RTH→RCSGkey=CS

CS→GCTkey=CC→TCHRkey=CH,HRCH→RHR→CCHRSkey=HS

CH→RHR→CHS→RCHSkey=HSHS→C鉗懊礫豌團(tuán)得銑韋錢蕩蕭布惠啤砷酗拘敗剁經(jīng)分艙迷掉攘淺氛遭充茶劇產(chǎn)第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論

2）結(jié)果為3NF的依賴保持分解算法6-4：結(jié)果為3NF的依賴保持分解算法輸入：關(guān)系模式R和函數(shù)依賴集F輸出：結(jié)果為3NF的一個(gè)依賴保持分解步驟：(1)如果R中有某些屬性與F的最小覆蓋F′中的每個(gè)依賴的左邊和右邊都無關(guān)，原則上可由這些屬性構(gòu)成一個(gè)關(guān)系模式，并從R中將它們消除；(2)如果F′中有一個(gè)依賴涉及到R的所有屬性，則輸出R;(3)否則，輸出一個(gè)分解ρ,它由模式XA組成，其中X→A∈F。但當(dāng)X→Al，X→A2，…，X→An均屬于F′時(shí)，則用模式XAlA2…An代替XAi(i=1,2，…,n)。例6-15：對于上例，F(xiàn)′={{C→T,CS→G,HT→R,HR→C,CH→R,HS→R｝,KEY＝HS}所以ρ={CT,CSG,HRT,CHR,HSR}薔墜番宇曉暗研戌綿拷焚身強(qiáng)派素嗡莫植企濤媽啦柒易鑰衡劇錫什筍撬黨第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論定理6-11：設(shè)δ是由結(jié)果為3NF的依賴保持分解算法得到的3NF分解，X為R的一個(gè)候選關(guān)鍵字，則τ＝δ∪｛X｝是R的一個(gè)分解，且τ中的所有關(guān)系模式均滿足3NF,同時(shí)，既具有連接不失真性，又具有依賴保持性。3）結(jié)果為3NF且具有依賴保持和連接不失真的分解例：已知R(C,T,H,R,S,G),F′=｛C→T,HR→C,CS→G,HS→R,HT→R｝，KEY=HS，則τ={CT,CSG,HRT,CHR,HSR,HS｝但HSHSR，故τ=｛CT，CSG，HRT，CHR，HSR｝拐體炮粉囑訝誹乎曼穆雞崇燼拿格寓榷筑篆苯遞褪月洗貞蕾針冶蔓澇搭闊第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論6.6多值函數(shù)依賴與4NF6.6.1BCNF關(guān)系模式存在的問題(CTB是關(guān)鍵字)CTB高等數(shù)學(xué)張華民高等數(shù)學(xué)高等數(shù)學(xué)張華民高等數(shù)學(xué)教程高等數(shù)學(xué)王天華高等數(shù)學(xué)高等數(shù)學(xué)王天華高等數(shù)學(xué)教程高等數(shù)學(xué)林靜高等數(shù)學(xué)高等數(shù)學(xué)林靜高等數(shù)學(xué)教程普通物理吳剛物理學(xué)普通物理吳剛普通物理普通物理吳剛普通物理基礎(chǔ)普通物理李曉芳物理學(xué)普通物理李曉芳普通物理普通物理李曉芳普通物理基礎(chǔ)幫消墓躍沾灌嫁腰方寥兩差鵑牛臀訃港哩騎踢藥舒撇翼瓷倦俊抒吸擎腕鞘第6章關(guān)系模式的規(guī)范化理論第6章關(guān)系模式的規(guī)范化理論6.6.2多值函數(shù)依賴為了形式地定義多值依賴，根據(jù)上例，構(gòu)造一個(gè)抽象關(guān)系R(U)（