chapter4關(guān)系數(shù)據(jù)庫設(shè)計(jì)理論

2023/5/12經(jīng)濟(jì)與管理學(xué)院14.1數(shù)據(jù)依賴4.2范式4.3關(guān)系模式的規(guī)范化4.4關(guān)系模式的分解算法4.5判斷分解服從規(guī)范地方法第四章關(guān)系數(shù)據(jù)庫設(shè)計(jì)理論目錄2023/5/12經(jīng)濟(jì)與管理學(xué)院2第四章關(guān)系數(shù)據(jù)庫設(shè)計(jì)理論

4.1數(shù)據(jù)依賴4.1.1關(guān)系模式中的數(shù)據(jù)依賴關(guān)系是一張二維表，它是所涉及屬性的笛卡爾積的一個(gè)子集。從笛卡爾積中選取哪些元組構(gòu)成該關(guān)系，通常是由現(xiàn)實(shí)世界賦予該關(guān)系的元組詞義來確定的。元組詞義實(shí)質(zhì)上是一個(gè)n目謂詞（n是屬性集中屬性的個(gè)數(shù)）。使該n目謂詞為真的笛卡爾積中的元素（或者說凡符合元組語義的元素）的全體就構(gòu)成了該關(guān)系。2023/5/12經(jīng)濟(jì)與管理學(xué)院3

關(guān)系模式：關(guān)系模式是對(duì)關(guān)系的描述，為了能夠清楚地刻劃一個(gè)關(guān)系，它需要由五個(gè)部分組成，即應(yīng)該是一個(gè)五元組：R(U,D,DOM,F)。其中R為關(guān)系名，U為組成該關(guān)系的屬性名集合，D為屬性組U中屬性所來自的域，DOM為屬性向域的映象集合，F(xiàn)為屬性間數(shù)據(jù)的依賴關(guān)系集合。2023/5/12經(jīng)濟(jì)與管理學(xué)院4

關(guān)系模式R(U,D,DOM,F)簡化為R(U,F)。當(dāng)且僅當(dāng)U上的一個(gè)關(guān)系r滿足F時(shí)，r稱為關(guān)系模式R(U,F)的一個(gè)關(guān)系。其中F為屬性間數(shù)據(jù)的依賴關(guān)系集合（實(shí)際上就是描述關(guān)系的元組語義，限定組成關(guān)系的各個(gè)元組必須滿足的完整性約束條件）。2023/5/12經(jīng)濟(jì)與管理學(xué)院54.1.2數(shù)據(jù)依賴對(duì)關(guān)系模式的影響數(shù)據(jù)依賴是通過一個(gè)關(guān)系中屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間的相互關(guān)系，是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象，是數(shù)據(jù)內(nèi)在的性質(zhì)，是語義的體現(xiàn)。最重要的數(shù)據(jù)依賴有函數(shù)依賴(functionaldependency)和多值依賴(multivalueddependency)。2023/5/12經(jīng)濟(jì)與管理學(xué)院6

函數(shù)關(guān)系普遍存在于現(xiàn)實(shí)生活中。如，描述一個(gè)學(xué)生關(guān)系，可以有學(xué)號(hào)（Sno）、姓名（Sname）、所在系（Sdept）等幾個(gè)屬性。由于一個(gè)學(xué)號(hào)只對(duì)應(yīng)一個(gè)學(xué)生，一個(gè)學(xué)生只在一個(gè)系。因而當(dāng)“學(xué)號(hào)“值確定后，姓名及所在系的值也就唯一地確定了。屬性間的這種函數(shù)依賴類似于數(shù)學(xué)中的函數(shù)，因此說Sno函數(shù)決定Sname和Sdept，記作snosname，snosdept。2023/5/12經(jīng)濟(jì)與管理學(xué)院7

設(shè)有數(shù)據(jù)庫設(shè)計(jì)的對(duì)象包括學(xué)號(hào)（Sno）、姓名（sname）、年齡（age）、性別（sex）、系名（Sdept）、系主任姓名（Mname）、課程名（Cname）和成績（Grade）。假設(shè)該數(shù)據(jù)庫模式由一個(gè)單一的關(guān)系模式st構(gòu)成，則該關(guān)系模式的屬性集合為：U={Sno,sname,sex,age,Sdept,Mname,Cname,Grade}2023/5/12經(jīng)濟(jì)與管理學(xué)院8一個(gè)系有若干名學(xué)生，但一個(gè)學(xué)生只屬于一個(gè)系；一個(gè)系只有一名主任；一個(gè)學(xué)生可以選修多門課程，每門課程有若干名學(xué)生選課；每個(gè)學(xué)生所學(xué)的每門課程都只有一個(gè)成績。2023/5/12經(jīng)濟(jì)與管理學(xué)院9則得到屬性組U上的一組函數(shù)依賴F（如圖）F={Snosname,snosex,snoage,snosdept,sdeptmname,(sno,cname)grade}SnoSdeptCnameMnameGradesnamesexage2023/5/12經(jīng)濟(jì)與管理學(xué)院10SNOsnamesexagecnamegradesdeptmnameS1李華男20C190IS王民S1李華男20C290IS王民S1李華男20C385IS王民S1李華男20C487IS王民S2張平女21C190IS王民S3劉良男21C175IS王民S3劉良男21C270IS王民S3劉良男21C456IS王民S4陳兵男20C190SC趙敏

S4陳兵男20C285SC趙敏

不規(guī)范關(guān)系的實(shí)例－ST關(guān)系2023/5/12經(jīng)濟(jì)與管理學(xué)院11

若只考慮函數(shù)依賴這一種數(shù)據(jù)依賴，就得到一個(gè)描述學(xué)生的關(guān)系模式st(U,F)。但這個(gè)關(guān)系模式存在四個(gè)問題：（1）數(shù)據(jù)冗余太大。如每一個(gè)系主任的姓名重復(fù)出現(xiàn)。這將浪費(fèi)大量的存儲(chǔ)空間。（2）更新異常(updateanomalies)。由于數(shù)據(jù)冗余，當(dāng)更新數(shù)據(jù)庫中數(shù)據(jù)時(shí)，系統(tǒng)要付出很大的代價(jià)來維護(hù)數(shù)據(jù)庫的完整性，否則會(huì)面臨數(shù)據(jù)不一致的危險(xiǎn)。2023/5/12經(jīng)濟(jì)與管理學(xué)院12（3）插入異常(insertionanomalies)。如果一個(gè)系剛成立，尚無學(xué)生，就無法把這個(gè)系及其系主任的信息存入數(shù)據(jù)庫。（4）刪除異常(deletionanomalies)。如果一個(gè)系的學(xué)生全畢業(yè)了，在刪除該系學(xué)生信息的同時(shí)，把這個(gè)系及其系主任的信息也丟掉了。2023/5/12經(jīng)濟(jì)與管理學(xué)院134.1.3相關(guān)概念1.函數(shù)依賴設(shè)R(U)是屬性集U上的關(guān)系模式，X、Y是U的子集。對(duì)于R(U)的任意一個(gè)可能的關(guān)系r，如果r中不存在兩個(gè)元組，它們?cè)赬上的屬性值相同，而在Y上的屬性值不同，則稱“X函數(shù)確定Y”或“Y函數(shù)依賴于X”，記作XY。2023/5/12經(jīng)濟(jì)與管理學(xué)院14如對(duì)于學(xué)生關(guān)系模式：

St(U,F)U={Sno,sname,sex,age,Sdept,Mname,Cname,Grade}F={Snosname,snosex,snoage,snosdept,sdeptmname,(sno,came)grade}2023/5/12經(jīng)濟(jì)與管理學(xué)院15對(duì)函數(shù)依賴，注意：函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些關(guān)系實(shí)例滿足約束條件，而是指R的所有關(guān)系實(shí)例均要滿足的約束條件。函數(shù)依賴和別的數(shù)據(jù)關(guān)系一樣，是語義范疇的概念，我們只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴。如：“姓名函數(shù)決定年齡函數(shù)”這個(gè)函數(shù)依賴只有在沒有同名的條件下成立。數(shù)據(jù)庫設(shè)計(jì)者可以對(duì)現(xiàn)實(shí)世界作強(qiáng)制性規(guī)定。如上例，可強(qiáng)行規(guī)定不允許同名出現(xiàn)。2023/5/12經(jīng)濟(jì)與管理學(xué)院16若XY，則X稱為這個(gè)函數(shù)依賴的決定屬性集（determinant）。若XY，并且YX，則記為XY。若Y不函數(shù)依賴于X，則記為X?Y。2023/5/12經(jīng)濟(jì)與管理學(xué)院17函數(shù)依賴與屬性間的聯(lián)系類型有關(guān)：當(dāng)X，Y之間是“1對(duì)1”聯(lián)系時(shí)，則存在函數(shù)依賴XY和YX。當(dāng)X，Y之間是“多對(duì)1”聯(lián)系時(shí)，則只存在函數(shù)依賴XY。當(dāng)X，Y之間是“n對(duì)n”聯(lián)系時(shí)，則X和Y之間不存在函數(shù)依賴。2023/5/12經(jīng)濟(jì)與管理學(xué)院182.平凡函數(shù)依賴和非平凡函數(shù)依賴在關(guān)系模式R(U)中，對(duì)于U的子集X和Y，如果XY，但YX，則XY是非平凡函數(shù)依賴。若YX，則XY稱為平凡函數(shù)依賴。對(duì)于任何一個(gè)關(guān)系模式，平凡函數(shù)依賴都是必須成立的，它不反應(yīng)新的語義，因此我們總討論非平凡函數(shù)依賴。2023/5/12經(jīng)濟(jì)與管理學(xué)院193.完全函數(shù)依賴與部分函數(shù)依賴在關(guān)系模式R（U）中，如果XY，并且對(duì)于X的任何一個(gè)真子集X’，都有X’

?Y，則稱Y完全函數(shù)依賴于X，記作：XY；若XY，但Y不完全函數(shù)依賴于X，則稱Y對(duì)X部分函數(shù)依賴，記作XY。fp2023/5/12經(jīng)濟(jì)與管理學(xué)院204.傳遞函數(shù)依賴在關(guān)系模式R（U）中，如果XY，YZ，且YX子集，Y?X，則稱Z傳遞函數(shù)依賴于X。5.用函數(shù)依賴的概念定義碼設(shè)K為關(guān)系模式R(U,F)中的屬性或?qū)傩越M合，若KU，則K稱給R的一個(gè)候選碼。若關(guān)系模式R有多個(gè)候選碼，則選定其中一個(gè)做為主碼。f2023/5/12經(jīng)濟(jì)與管理學(xué)院214.2范式關(guān)系模式應(yīng)滿足的基本要求：（1）元組的每個(gè)分量必須是不可再分的數(shù)據(jù)項(xiàng)。（2）數(shù)據(jù)庫中的數(shù)據(jù)冗余應(yīng)盡可能少。（3）關(guān)系數(shù)據(jù)庫不能因?yàn)閿?shù)據(jù)更新操作而引起數(shù)據(jù)的不一致問題。（4）當(dāng)執(zhí)行數(shù)據(jù)插入操作時(shí)，數(shù)據(jù)庫中的數(shù)據(jù)不能產(chǎn)生插入異?，F(xiàn)象。（5）數(shù)據(jù)庫中數(shù)據(jù)不能產(chǎn)生刪除操作異常問題。（6）數(shù)據(jù)庫設(shè)計(jì)應(yīng)考察查詢要求，數(shù)據(jù)組織應(yīng)合理。2023/5/12經(jīng)濟(jì)與管理學(xué)院22

規(guī)范化理論是研究如何將一個(gè)不好的關(guān)系模式轉(zhuǎn)換為好的關(guān)系模式的理論，它是圍繞范式而建立的。規(guī)范化理論認(rèn)為，一個(gè)關(guān)系數(shù)據(jù)庫中的所有關(guān)系，都應(yīng)滿足一定的要求，它把關(guān)系應(yīng)滿足的規(guī)范要求分成幾級(jí)，并為每一級(jí)定義了相應(yīng)的約束條件集（范式）。如果一個(gè)關(guān)系滿足某個(gè)指定的約束集，則稱它屬于某種特定范式。1NF2NF3NFBCNF4NF5NF2023/5/12經(jīng)濟(jì)與管理學(xué)院234.2.1第一范式（1NF）如果一個(gè)關(guān)系模式Ｒ的所有屬性都是不可再分的數(shù)據(jù)項(xiàng)，則稱該關(guān)系為第一范式，記作Ｒ∈１ＮＦ。如ST模式中所有屬性都是不可再分的數(shù)據(jù)項(xiàng)，所以ST滿足1NF。在任何一個(gè)關(guān)系數(shù)據(jù)庫系統(tǒng)，第一范式是對(duì)關(guān)系模式的一個(gè)最起碼的要求。不滿足第一范式的數(shù)據(jù)庫模式不能稱為關(guān)系數(shù)據(jù)庫。但滿足第一范式的關(guān)系模式不一定是一個(gè)好的關(guān)系模式。2023/5/12經(jīng)濟(jì)與管理學(xué)院24

關(guān)系模式SLC（Sno，Sdept，Sloc，Cno，Grade）其中，Sloc為學(xué)生住處，假設(shè)每一個(gè)系的學(xué)生住在同一地方。SLC的碼為（Sno,Cno)。函數(shù)依賴包括：Grade(Sno,Cno)fSdeptSnoSdept(Sno,Cno)pSlocSnoSloc(Sno,Cno)pSlocSdept（因?yàn)槊總€(gè)系只住一個(gè)地方）2023/5/12經(jīng)濟(jì)與管理學(xué)院25非主屬性對(duì)碼的依賴關(guān)系如下圖所示：候選碼GradeSnoSdeptSlocCno圖中的實(shí)線表示完全函數(shù)依賴，虛線表示部分函數(shù)依賴。2023/5/12經(jīng)濟(jì)與管理學(xué)院26SLC關(guān)系存在以下問題：插入異常：插入一個(gè)還沒選課的學(xué)生時(shí)沒法插入，因?yàn)闊oCno。刪除異常：刪除一個(gè)只選了一門課的同學(xué)的選課時(shí)。數(shù)據(jù)冗余度大：如一個(gè)學(xué)生選了20門課，則Sdept和Sloc值就重復(fù)20次。修改復(fù)雜：如轉(zhuǎn)系時(shí)2023/5/12經(jīng)濟(jì)與管理學(xué)院274.2.2第二范式（2NF）若關(guān)系Ｒ∈１ＮＦ，且它的每一非主屬性都完全依賴于主碼，并且當(dāng)主碼是組合的屬性組時(shí)，應(yīng)依賴于每一個(gè)組成屬性，則稱Ｒ屬于第二范式，記作R∈2NF?！巴耆蕾嚒焙汀拔ㄒ粯?biāo)識(shí)于”是同義的。2023/5/12經(jīng)濟(jì)與管理學(xué)院28

關(guān)系模式SLC出現(xiàn)上述問題的原因是Sdept，Sloc對(duì)碼的部分函數(shù)依賴。為了消除這些部分函數(shù)依賴，可以采用投影分解法，把SLC分解為兩個(gè)關(guān)系模式：

SC(Sno,Cno,Grade)SL(Sno,Sdept,Sloc)

其中SC的碼為(Sno,Cno)，SL的碼為Sno。這兩個(gè)關(guān)系模式的函數(shù)依賴如圖所示。2023/5/12經(jīng)濟(jì)與管理學(xué)院29

分解后的關(guān)系模式中，非主屬性都完全函數(shù)依賴于碼了，從而使上述4個(gè)問題在一定程度上得到了一定的解決。GradeSnoCno候選碼SCSnoSdeptSloc候選碼SL2023/5/12經(jīng)濟(jì)與管理學(xué)院30

屬于2NF的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式。如：

SL(Sno,Sdept,Sloc)中有下列函數(shù)依賴：即Sloc傳遞函數(shù)依賴于Sno。SnoSdeptSnoSlocSdeptSloc2023/5/12經(jīng)濟(jì)與管理學(xué)院31SL關(guān)系中仍然存在插入異常、刪除異常、數(shù)據(jù)冗余度大和修改復(fù)雜的問題。插入異常：如某個(gè)系剛成立，目前還沒有在校學(xué)生，就無法把這個(gè)系的信息存入數(shù)據(jù)庫。刪除異常：如某系學(xué)生全部畢業(yè)后在刪除學(xué)生信息的同時(shí)系的信息也被刪除。數(shù)據(jù)冗余度大：如關(guān)于系的住處的信息重復(fù)出現(xiàn)多次。修改復(fù)雜：如調(diào)整學(xué)生住處時(shí)。2023/5/12經(jīng)濟(jì)與管理學(xué)院324.2.3第三范式（3NF）如果關(guān)系模式R<U,F>中不存在碼X、屬性組Y以及非主屬性Z（Z?Y），使得XY，YZ和Y?X

成立，則R3NF。即：若R∈3NF，則每一個(gè)非主屬性既不部分函數(shù)依賴于碼，也不傳遞函數(shù)依賴于碼。

2023/5/12經(jīng)濟(jì)與管理學(xué)院33關(guān)系模式SL出現(xiàn)上述問題的原因是Sloc傳遞函數(shù)依賴于Sno。為消除該傳遞函數(shù)依賴，可以采用投影分解法，把SL分解為兩個(gè)關(guān)系模式：

SD(Sno,Sdept)DL(Sdept,Sloc)其中SD的碼為Sno，DL的碼為Sdept。2023/5/12經(jīng)濟(jì)與管理學(xué)院344.2.4BC范式（BCNF）設(shè)關(guān)系模式R<U，F(xiàn)>∈1NF，如果對(duì)于R的每一個(gè)函數(shù)依賴XY，若Y?X，則X必含有候選碼，那么R∈BCNF。由BCNF的定義可得到結(jié)論：一個(gè)滿足BCNF的關(guān)系模式有：所有非主屬性對(duì)每一個(gè)碼都是完全函數(shù)依賴；所有主屬性對(duì)每一個(gè)不包含它的碼，也是完全函數(shù)依賴；沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。2023/5/12經(jīng)濟(jì)與管理學(xué)院35BCNF范式和3NF的區(qū)別：BCNF不僅強(qiáng)調(diào)其他屬性對(duì)碼的完全的直接的依賴，而且強(qiáng)調(diào)主屬性對(duì)碼的完全的直接的依賴，它包括3NF，即R∈BCNF，則R一定屬于3NF。3NF只強(qiáng)調(diào)非主屬性對(duì)碼的完全直接依賴，這樣就可能出現(xiàn)主屬性對(duì)碼的部分依賴和傳遞依賴。有些關(guān)系模式屬于3NF，但不一定屬于BCNF，如：2023/5/12經(jīng)濟(jì)與管理學(xué)院36例.在關(guān)系模式STJ（S，T，J）中，S表示學(xué)生，T表示教師，J表示課程。假設(shè)每一教師只教一門課，每門課由若干教師教；某一個(gè)學(xué)生選定某門課就確定了一個(gè)固定教師。則存在的函數(shù)依賴為：F={(S,J)→T,(S,T)→J,T→J}關(guān)系的碼為：(S,J)和

(S,T)。關(guān)系的主屬性集為：{S,T,J}，非主屬性為空集，則該關(guān)系屬于3NF。但不屬于BCNF。2023/5/12經(jīng)濟(jì)與管理學(xué)院374.2.5第四范式（4NF）給定一個(gè)關(guān)系模式JPW(產(chǎn)品,零件,工序)，其中每種產(chǎn)品由多種零件構(gòu)成，每個(gè)零件在裝配時(shí)需要多道工序。2023/5/12經(jīng)濟(jì)與管理學(xué)院38該表不存在函數(shù)依賴，并且是全碼，所以JPW屬于BCNF。JPW電視機(jī)顯像管焊接電視機(jī)顯像管調(diào)試電視機(jī)電源測(cè)試電視機(jī)電源裝配電視機(jī)電源調(diào)試電視機(jī)開關(guān)焊接電視機(jī)開關(guān)調(diào)試影碟機(jī)電源測(cè)試影碟機(jī)開關(guān)調(diào)試2023/5/12經(jīng)濟(jì)與管理學(xué)院39多值依賴（MVD）的定義：設(shè)有關(guān)系模式R（U，F(xiàn)）是屬性集，X、Y是U的子集。如果R的任一關(guān)系，對(duì)于X的一個(gè)確定值，都存在Y的一組值與之對(duì)應(yīng)，且Y的這組值又與Z=U-X-Y中的屬性值不相關(guān)，此時(shí)稱Y多值依賴于X，或X多值決定Y，記為X→→Y。根據(jù)定義可知：產(chǎn)品→→零件。2023/5/12經(jīng)濟(jì)與管理學(xué)院40非平凡的多值依賴的定義：在多值依賴中，若X→→Y且Z=U-X-Y≠φ，則稱X→→Y為非平凡的多值依賴，否則稱為平凡的多值依賴。4NF的定義：關(guān)系模式R(U,F)∈1NF，如果對(duì)于R的每一個(gè)非平凡多值依賴X→→Y（YX)，X必含有碼，則稱R(U,F)∈4NF。

4NF限制關(guān)系模式的屬性間不許有非平凡且非函數(shù)依賴的多值依賴。2023/5/12經(jīng)濟(jì)與管理學(xué)院41

在JWP模式中，由于它為全碼且存在產(chǎn)品→→零件、零件→→工序，而產(chǎn)品和零件都不包含碼，故JPW不屬于4NF?？煞纸鉃椋篔P(產(chǎn)品，零件)和PW(零件，工序)。2023/5/12經(jīng)濟(jì)與管理學(xué)院42

函數(shù)依賴和多值依賴是兩種最重要的數(shù)據(jù)依賴。如果只考慮函數(shù)依賴，則BCNF是最高的關(guān)系模式范式；如果考慮了多值依賴，則4NF是最高的關(guān)系范式。4.2.6連接依賴與5NF連接依賴是與關(guān)系分解和連接運(yùn)算有關(guān)的數(shù)據(jù)依賴，是研究第5NF的基礎(chǔ)。2023/5/12經(jīng)濟(jì)與管理學(xué)院434.3關(guān)系模式的規(guī)范化

關(guān)系模式的規(guī)范化：一個(gè)低一級(jí)范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換成若干個(gè)高一級(jí)范式的關(guān)系模式集合，這種過程就叫關(guān)系模式的規(guī)范化。規(guī)范化程度可以有6個(gè)不同的級(jí)別，即6個(gè)范式。4.3.1關(guān)系模式規(guī)范化的步驟

1.問題提出規(guī)范化程度過低的關(guān)系不一定能夠很好的描述現(xiàn)實(shí)世界，可能會(huì)存在插入異常、刪除異常、修改復(fù)雜和數(shù)據(jù)冗余等問題。2023/5/12經(jīng)濟(jì)與管理學(xué)院442.解決辦法對(duì)其進(jìn)行規(guī)范化，轉(zhuǎn)換成高一級(jí)范式。3.基本思想逐步消除數(shù)據(jù)依賴中的不合適的部分，使模式中的各關(guān)系模式達(dá)到某種程度的“分離”，即采用“一事一地”的模式設(shè)計(jì)原則，讓一個(gè)關(guān)系描述一個(gè)概念、一個(gè)實(shí)體或者實(shí)體間的一種聯(lián)系。若多于一個(gè)概念就把它“分離”出去。因此所謂規(guī)范化實(shí)質(zhì)上就是概念的單一化。2023/5/12經(jīng)濟(jì)與管理學(xué)院452NF1NF3NFBCNF4NF5NF消除非主屬性對(duì)碼的部分函數(shù)依賴消除非主屬性對(duì)碼的傳遞函數(shù)依賴消除主屬性對(duì)碼的部分和傳遞函數(shù)依賴（使決定屬性都稱為投影的候選碼）消除非平凡且非函數(shù)依賴的多值依賴消除不是由候選碼所蘊(yùn)含的連接依賴消除決定屬性集非碼的非平凡函數(shù)依賴2023/5/12經(jīng)濟(jì)與管理學(xué)院464.3.2關(guān)系模式的分解

1.分解原則

只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)的方法才有意義，即分解后的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系，那么這種分解就沒有丟失信息。例對(duì)于關(guān)系模式SL(SNO,SDEPT,SLOC)的分解。（見書本）2023/5/12經(jīng)濟(jì)與管理學(xué)院472.相關(guān)概念定義1：設(shè)關(guān)系模式R(U,F)被分解為若干個(gè)關(guān)系模式R1(U1,F1)，R2(U2,F2)，…Rn(Un,Fn)（其中U=U1∪U2∪…∪Un，且不存在UiUj，F(xiàn)i為F在Ui上的投影），若R與R1，R2，…Rn自然連接的結(jié)果相等，則稱關(guān)系模式R的這個(gè)分解具有無損連接性（losslessjoin）。只有具有無損連接性的分解才能夠保證不丟失信息。2023/5/12經(jīng)濟(jì)與管理學(xué)院48

定義2：設(shè)關(guān)系模式R(U,F)被分解為若干個(gè)關(guān)系模式R1(U1,F1)，R2(U2,F2)，…Rn(Un,Fn)（其中U=U1∪U2∪…∪Un，且不存在UiUj，F(xiàn)i為F在Ui上的投影），若F所邏輯蘊(yùn)含的函數(shù)依賴一定也由分解得到的某個(gè)關(guān)系模式中的函數(shù)依賴Fi所邏輯蘊(yùn)含，則稱關(guān)系模式R的這個(gè)分解是保持函數(shù)依賴的（preserverdependency）。2023/5/12經(jīng)濟(jì)與管理學(xué)院493.判斷原則判斷對(duì)關(guān)系模式的一個(gè)分解是否與原關(guān)系模式等價(jià)可以有三種不同的標(biāo)準(zhǔn)：分解具有無損連接性。（保證不丟失信息）分解要保持函數(shù)依賴。（可減輕或解決各種異常情況）分解既要保持函數(shù)依賴，又要具有無損連接性。2023/5/12經(jīng)濟(jì)與管理學(xué)院504.4關(guān)系模式的分解算法

對(duì)關(guān)系進(jìn)行模式分解是規(guī)范化的主要方法。本節(jié)討論關(guān)系模式分解的理論基礎(chǔ)、模式分解的算法和模式分解的規(guī)范問題。4.4.1關(guān)系模式分解的算法基礎(chǔ)

1974年W.W.Armstrong提出了一套有效而完備的公理系統(tǒng)－Armstrong公理，該公理后來成為關(guān)系模式分解的算法基礎(chǔ)。2023/5/12經(jīng)濟(jì)與管理學(xué)院511.函數(shù)依賴的邏輯蘊(yùn)含的定義設(shè)F是模式R(U)的函數(shù)依賴集，X和Y是屬性集U的子集。如果從F中的函數(shù)依賴能推出XY，則稱F邏輯蘊(yùn)涵XY，或稱XY是F的邏輯蘊(yùn)含。2.Armstrong公理系統(tǒng)（1）Armstrong公理系統(tǒng)設(shè)U為屬性集，F(xiàn)是U上的函數(shù)依賴集，于是有關(guān)系模式R(U,F)。對(duì)于R(U,F)來說，有以下的推理規(guī)則：2023/5/12經(jīng)濟(jì)與管理學(xué)院521）自反律(Reflexivity):若YXU，則XY為F所蘊(yùn)涵。2）增廣律(Augmentation)：若XY為F所蘊(yùn)涵，且ZU，則XZYZ為F所蘊(yùn)涵。3）傳遞律(Transitivity)：若XY及YZ為F所蘊(yùn)涵，則XZ為F所蘊(yùn)涵。（2）Armstrong公理的三個(gè)推理1）合并規(guī)則(UnionRule)：若XY，XZ有XYZ。2023/5/12經(jīng)濟(jì)與管理學(xué)院532）偽傳遞規(guī)則(PseudotransitivityRule)：若XY，WYZ，則XWZ。3）分解規(guī)則(positionRule)：若XY且ZY，則XZ。注：根據(jù)合并規(guī)則和分解規(guī)則，有：XA1A2…Ak成立的充分必要條件是XAi成立（i＝1，2，…，k）。2023/5/12經(jīng)濟(jì)與管理學(xué)院54（3）Armstrong公理是有效和完備的

Armstrong公理的有效性指在F中根據(jù)Armstrong公理推導(dǎo)出來的每一個(gè)函數(shù)依賴一定為F所邏輯蘊(yùn)含。Armstrong公理的完備性是指F所邏輯蘊(yùn)含的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來。2023/5/12經(jīng)濟(jì)與管理學(xué)院554.4.2函數(shù)依賴集閉包F+和屬性集閉包XF+1.函數(shù)依賴集閉包F+定義在關(guān)系模式R(U,F)中，為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫做F的閉包，記作F+

。一般情況下，F(xiàn)≤F+

。如果F=F+

，則稱F是函數(shù)依賴的完備集。2023/5/12經(jīng)濟(jì)與管理學(xué)院562.屬性集閉包XF+的定義設(shè)有關(guān)系模式R(U,F)，X是U的子集，稱所有用公理從F推出的函數(shù)依賴集XAi中Ai的屬性集為X的屬性閉包，記作XF+

。即：XF+={Ai|Ai∈U，XAi∈F+}由公理的自反性可知XX，因此XXF+

。2023/5/12經(jīng)濟(jì)與管理學(xué)院573.屬性集閉包XF+的求法算法：求屬性集X關(guān)于函數(shù)依賴F的屬性閉包XF+

。輸入：關(guān)系模式R的全部屬性集U，在U上的函數(shù)依賴F，U的子集X。輸出：關(guān)于F的屬性閉包XF+。方法：計(jì)算X(i)(i=0,1,…)2023/5/12經(jīng)濟(jì)與管理學(xué)院58（1）令X(0)=X，i=0；（2）X(i+1)=X(i)A；其中A是這樣的屬性：在F中尋找尚未用過的左邊是X(i)的子集的函數(shù)依賴：YjZj

（j＝1，…k），其中YjX(i)。即在Zj中尋找X(i)中未出現(xiàn)過的屬性集合A，若無這樣的A則轉(zhuǎn)(4)。（3）判斷是否有X(i+1)=X(i)，若是則轉(zhuǎn)(4)；否則轉(zhuǎn)(2)。（4）輸出X(i)，即為XF+。2023/5/12經(jīng)濟(jì)與管理學(xué)院59

對(duì)于（3）的停止條件，以下四種方法是等價(jià)的：X(i+1)=X(i)A；當(dāng)發(fā)現(xiàn)X(i)包含了全部屬性時(shí)；在F中的函數(shù)依賴的右邊屬性中再也找不到X(i)中未出現(xiàn)過的屬性時(shí)；在F中未用過的函數(shù)依賴的左邊屬性已經(jīng)沒有X(i)的子集時(shí)。2023/5/12經(jīng)濟(jì)與管理學(xué)院60例設(shè)有關(guān)系模式R(U,F)，其中U={A,B,C,D,E,I}；F={AD,ABE,BIE,CDI,EC}，計(jì)算(AE)F+解：令X={AE}，X(0)=AE

2023/5/12經(jīng)濟(jì)與管理學(xué)院61

在F中找出左邊是AE子集的函數(shù)依賴，其結(jié)果是：AD，EC，則X(1)=X(0)DC=ACDE。顯然X(1)≠X(0)。在F中找出左邊是ACDE子集的函數(shù)依賴，其結(jié)果是：CDI，則X(2)=X(1)I＝ACDEI。雖然X(2)≠X(1)，但是F中未用過的函數(shù)依賴的左邊屬性已沒有X(2)的子集，所以不必再計(jì)算下去，即(AE)F+={ACDEI}。2023/5/12經(jīng)濟(jì)與管理學(xué)院624.4.3函數(shù)依賴的等價(jià)和覆蓋1.函數(shù)依賴集的等價(jià)的概念設(shè)F和G是兩個(gè)函數(shù)依賴集，如果F+=G+，則稱F和G等價(jià)。F與G等價(jià)說明F覆蓋G，同時(shí)G也覆蓋F。2.判斷兩函數(shù)依賴集等價(jià)的方法定理：F+=G+的充要條件是FG+且GF+。2023/5/12經(jīng)濟(jì)與管理學(xué)院633.函數(shù)依賴集的最小集（1）最小函數(shù)依賴集的定義如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集，亦稱為最小依賴集或最小覆蓋。F中任一函數(shù)依賴的右部僅含有一個(gè)屬性。F中不存在這樣的函數(shù)依賴XA，使得F與F-{XA}等價(jià)。F中不存在這樣的函數(shù)依賴XA，X有真子集Z使得F與F-{XA}∪{Z-A}與F等價(jià)。2023/5/12經(jīng)濟(jì)與管理學(xué)院64注：條件1）說明，在最小函數(shù)依賴集中的所有函數(shù)依賴都應(yīng)該是“右端沒有多余的屬性”的最簡單的形式；條件2）保證了最小函數(shù)依賴集中無多余的函數(shù)依賴；條件3）要求，最小函數(shù)依賴集中的每個(gè)函數(shù)依賴的左端沒有多余的屬性。2023/5/12經(jīng)濟(jì)與管理學(xué)院65（2）算法：計(jì)算最小依賴集輸入：一個(gè)函數(shù)依賴集F。輸出：F的一個(gè)等價(jià)最小依賴集G。方法：1）應(yīng)用分解規(guī)則，使F中每一個(gè)依賴的右部屬性單一化。2）去掉各依賴左部多余的屬性。具體做法是：一個(gè)一個(gè)地檢查F中左邊是非單一屬性地依賴，例如XYA，現(xiàn)在要判斷Y是否為多余地，則以XA代替XYA是否等價(jià)？只要在F中求X+，若X+包含A，則Y是多余的屬性；否則Y不是多余的屬性。依次判斷其他屬性即可消除各依賴左邊的多余屬性。2023/5/12經(jīng)濟(jì)與管理學(xué)院663）去掉多余的依賴。具體做法是：從第一個(gè)依賴開始，從F中去掉它（假設(shè)該依賴為XY），然后在余下的依賴中求X+，看X+是否包含Y，若是，則去掉XY；若不包含Y，則不能去掉XY。這樣依次做下去。2023/5/12經(jīng)濟(jì)與管理學(xué)院67例1.設(shè)有依賴集：F={ABC,DEG,CA,BEC,BCD,CGBD,ACDB,CEAG}計(jì)算其等價(jià)的最小函數(shù)依賴集Fm。2023/5/12經(jīng)濟(jì)與管理學(xué)院681）利用分解規(guī)則，將所有的函數(shù)依賴右邊屬性單一化，結(jié)果為：F1={ABC,DE,DG,CA,BEC,BCD,CGB,CGD,ACDB,CEA,CEG}2）在F1中去掉依賴左部多余的屬性。對(duì)于CEA，由于有CA，則E是多余的；對(duì)于ACDB，由于(CD)F1+=ABCDEG，則A是多余的。刪除依賴左部多余的依賴后：F2={ABC,DE,DG,CA,BEC,BCD,CGB,CGD,CDB,CEG}2023/5/12經(jīng)濟(jì)與管理學(xué)院693）在F2中去掉多余的依賴。①設(shè)ABC為冗余的函數(shù)依賴，則去掉ABC得F3={DE,DG,CA,BEC,BCD,CGB,CGD,CDB,CEG}，由于從F3中找不到左部為AB或其子集的函數(shù)依賴，則(AB)F3+=AB。由于C(AB)F3+，所以ABC非冗余函數(shù)依賴，不能去掉。2023/5/12經(jīng)濟(jì)與管理學(xué)院70②設(shè)CGB為冗余的函數(shù)依賴，則去掉CGB得F4={ABC,DE,DG,CA,BEC,BCD,CGD,CDB,CEG}，由于(CG)F4+=ABCDEG。由于B(CG)F4+，所以CGB為冗余函數(shù)依賴，從F4去掉。2023/5/12經(jīng)濟(jì)與管理學(xué)院71③設(shè)CGD為冗余的函數(shù)依賴，則去掉CGD得。

F4={ABC,DE,DG,CA,BEC,BCD,CDB,CEG}，由于(CG)F4+=ACG。由于D(CG)F4+，所以CGD為非冗余函數(shù)依賴，不能從F4去掉。2023/5/12經(jīng)濟(jì)與管理學(xué)院72④設(shè)CEG為冗余的函數(shù)依賴，則去掉CGD得。

F5={ABC,DE,DG,CA,BEC,BCD,CGD,CDB}，由于(CE)F5+=ACE，故G(CG)F5+，所以CEG為非冗余函數(shù)依賴，不能從F5去掉。故最小函數(shù)依賴集為：Fm={ABC,DE,DG,CA,BEC,BCD,CGD,CDB,CEG}2023/5/12經(jīng)濟(jì)與管理學(xué)院73例2.求F={ABC,AB,BA}的最小函數(shù)依賴集Fm。解：1）將F中的最小函數(shù)依賴都分解為右部為單屬性的函數(shù)依賴。很顯然，F(xiàn)滿足該條件。2）去掉F中冗余的函數(shù)依賴。①設(shè)ABC是冗余的，去掉得：F1={AB,BA}，由于(AB)F1+=AB，故C(AB)F1+，所以ABC不冗余。2023/5/12經(jīng)濟(jì)與管理學(xué)院74②設(shè)AB是冗余的，去掉得：F1={ABC,BA}，由于(A)F1+=A，故B(AB)F1+，所以AB不冗余。③設(shè)BA是冗余的，去掉得：F1={ABC,AB}，由于(B)F1+=B，故A(AB)F1+，所以BA不冗余。經(jīng)檢驗(yàn)后的函數(shù)依賴集仍為F。2023/5/12經(jīng)濟(jì)與管理學(xué)院753）去掉函數(shù)依賴左部多余的屬性。本題只需考慮ABC的情況。方法1：在決定因素中去掉B，若CAF+，則以AC代替ABC。求得AF+=ABC，由于CAF+，所以以AC代替ABC。故：Fm={AC,AB,BA}2023/5/12經(jīng)濟(jì)與管理學(xué)院76方法1：在決定因素中去掉A，若CAF+，則以BC代替ABC。求得AF+=ABC，由于CAF+，所以以BC代替ABC。故：Fm={BC,AB,BA}2023/5/12經(jīng)濟(jì)與管理學(xué)院774.5判斷分解服從規(guī)范地方法4.5.1判斷分解具有無損連接性的方法

定義：設(shè)ρ＝{R1，R2…，RK}是關(guān)系模式R(U,F)的一個(gè)分解，r是R(U,F)的一個(gè)關(guān)系。定義即mρ(r)是r在ρ中各關(guān)系模式上投影的連接。這里πRi(r)={t.Ui|tr}ki=1mρ(r)=πRi(r)2023/5/12經(jīng)濟(jì)與管理學(xué)院78

定義：設(shè)ρ＝{R1，R2…，RK}是關(guān)系模式R(U,F)的一個(gè)分解，如果對(duì)于R的任一滿足F的關(guān)系r都有：r=mρ(r)成立，則稱分解ρ具有無損連接性，簡稱ρ為無損連接。2023/5/12經(jīng)濟(jì)與管理學(xué)院79算法：檢驗(yàn)無損連接性。輸入：關(guān)系模式R=(A1，A2…，An)，它的函數(shù)依賴集F以及分解ρ＝{R1，R2…，RK}。輸出：確定ρ是否具有無損連接性。方法：（1）構(gòu)造一個(gè)k行n列的表，第i行對(duì)應(yīng)于關(guān)系模式Ri，第j列對(duì)應(yīng)于屬性Aj。如果AjRi，，則在第i行第j列上放符號(hào)aj，否則放符號(hào)bij。2023/5/12經(jīng)濟(jì)與管理學(xué)院80（2）逐個(gè)檢查F中的每一個(gè)函數(shù)依賴，并修改表中的元素。其方法如下：取得F中的一個(gè)函數(shù)依賴XY，在X的分量中尋找相同的行，然后將這些行中Y的分量改為相同的符號(hào)，如果其中有aj，則將bij改為aj；若其中無aj，則改為bij。（3）這樣反復(fù)進(jìn)行，如果發(fā)現(xiàn)某一行變成了a1，a2，…，ak，則分解ρ具有無損連接性；如果F中所有函數(shù)依賴都不能再修改表中的內(nèi)容，且沒有發(fā)現(xiàn)這樣的行，則分解ρ不具有無損連接。2023/5/12經(jīng)濟(jì)與管理學(xué)院81例.設(shè)有關(guān)系模式R(