《關(guān)系數(shù)據(jù)理論》PPT課件.ppt

《《關(guān)系數(shù)據(jù)理論》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《關(guān)系數(shù)據(jù)理論》PPT課件.ppt（99頁珍藏版）》請在裝配圖網(wǎng)上搜索。

4.1關(guān)系模式的設(shè)計問題,4.2關(guān)系模式的規(guī)范化,4.3數(shù)據(jù)依賴的公理系統(tǒng)(自學(xué)),4.4關(guān)系模式的分解,第四章關(guān)系數(shù)據(jù)理論,本章小結(jié),4.1函數(shù)依賴,一、問題——如何構(gòu)造一個關(guān)系模式例：假設(shè)有學(xué)生關(guān)系模式,其中，S#—學(xué)號、SNAME—學(xué)生姓名、CLASS—班級、C#—課程號、TNAME—教師姓名、TAGE—教師年齡、ADDRESS—教師地址、GRADE—成績。,S(S#,SNAME,CLASS,C#,TNAME,TAGE,ADDRESS,GRADE),關(guān)系S存在以下問題：1．?dāng)?shù)據(jù)冗余度高。SNAME、CLASS、TNAME、TAGE、ADDRESS重復(fù)存儲多次。,4.1函數(shù)依賴,2．?dāng)?shù)據(jù)修改復(fù)雜。3．插入異常。插入異常是指應(yīng)該插入到數(shù)據(jù)庫中的數(shù)據(jù)不能執(zhí)行插入操作的情形。,關(guān)系S的主碼：,（S#，C#）,從在S#、C#、和(S#,c#)上出現(xiàn)NULL值去分析。注意：當(dāng)一個元組在主碼的屬性上部分或全部為空時，該元組不能插入到關(guān)系中。,4.1函數(shù)依賴,4．刪除異常。刪除異常是指不應(yīng)該刪去的數(shù)據(jù)被刪去的情形。例如：選修某門課的所有學(xué)生都退選時，刪除相關(guān)元組，會丟失該課程老師的信息。解決：關(guān)系模式分解（關(guān)系規(guī)范化）分解為ST(S#，SNAME，CLASS)CT(C#,TNAME)TA(TNAME,TAGE,ADDRESS)SC(S#,C#,GRADE),,4.1函數(shù)依賴,二、函數(shù)依賴functionaldependency,abbr.FD,設(shè)：R（A1，A2，…An)=R(U)X，Y，Z為U的不同子集,定義4.1：①函數(shù)依賴是完整性約束的一種，它推廣了關(guān)鍵詞的概念。Ift1.X=t2.X,thent1.Y=t2.Y②函數(shù)依賴：若R的任意關(guān)系有：對X中的每個屬性值，在Y中都有惟一的值與之對應(yīng)，則稱Y函數(shù)依賴于X，記作X?Y。,屬性全集,4.1函數(shù)依賴,例：指出下列關(guān)系R中的函數(shù)依賴。,FD:AB->C、A→C、C→A、AB→D？InsertintoRvalues(a1,b1,c2,d1)FD=keyconstraint?,4.1函數(shù)依賴,函數(shù)依賴與屬性間的關(guān)系有：若X，Y是1—1關(guān)系，則存在X?Y或Y?X。如學(xué)號與借書證號若X，Y是m—1關(guān)系，則存在X?Y但Y+>X。如學(xué)號與姓名若X，Y是m—n關(guān)系，則X，Y間不存在函數(shù)依賴關(guān)系。如姓名與課程CF:實體間的聯(lián)系NOTE:函數(shù)依賴的方向性,4.1函數(shù)依賴,例試指出學(xué)生關(guān)系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE)中存在的函數(shù)依賴關(guān)系。S#→SNAME（每個學(xué)號只能有一個學(xué)生姓名）S#→CLASS（每個學(xué)號只能有一個班級）C#→TNAME（設(shè)每門課程只有一個教師任教，而一個教師可教多門課程，見CT表）TNAME→TAGE（每個教師只能有一個年齡）TNAME→ADDRESS（每個教師只能有一個地址）(S#，C#)→GRADE（每個學(xué)生學(xué)習(xí)一門課只能有一個成績）(S#，C#)→SNAME、(S#，C#)→CLASS、(S#，C#)→C#、(S#，C#)→TNAME、(S#，C#)→TAGE、(S#，C#)→ADDRESS,4.1函數(shù)依賴,三、函數(shù)依賴的分類X?Y，但Y不包含于X則稱X是非平凡的函數(shù)依賴。X?Y，但Y?X則稱X是平凡的函數(shù)依賴。若X?Y，則X叫做決定因素。若X?Y，Y?X，則記作:XY。定義4.2：在R(U)中，X,Y,Z為U的不同子集。完全函數(shù)依賴:是指X?Y，且對任何X的真子集X’，都有X’+>Y，記作：XF>Y。部分函數(shù)依賴:是指X?Y，且存在X的真子集X’，有X’->Y，記作：XP>Y。,定義4.3：在R(U)中傳遞函數(shù)依賴：是指若X?Y(Y不包含于X)，Y+>X，而Y?Z。記作：XT>Z。,4.1函數(shù)依賴,左部為單屬性的函數(shù)依賴一定是完全函數(shù)依賴。左部為多屬性的函數(shù)依賴，如何判斷其是否為完全函數(shù)依賴？方法：取真子集，看其能否決定右部屬性。例：試指出學(xué)生關(guān)系S中存在的完全函數(shù)依賴和部分函數(shù)依賴。S#→SNAME，S#→CLASS，TNAME→TAGE，TNAME→ADDRESS，C#→TNAME都是完全函數(shù)依賴。(S#，C#)→GRADE是一個完全函數(shù)依賴，因為S#+>GRADE，C#+>GRADE。,4.1函數(shù)依賴,例：試指出學(xué)生關(guān)系S中存在的傳遞函數(shù)依賴。解：因為C#→TNAME，TNAME+>C#，TNAME→TAGE，所以C#→TAGE是一個傳遞函數(shù)依賴。類似地，C#→ADDRESS也是一個傳遞函數(shù)依賴。,(S#，C#)→SNAME，(S#，C#)→CLASS，(S#，C#)→TNAME，(S#，C#)→TAGE，(S#，C#)→ADDRESS都是部分函數(shù)依賴，因為S#→SNAME，S#→CLASS，C#→TNAME，C#→TAGE，C#→ADDRESS。,4.1函數(shù)依賴,四、候選碼用函數(shù)依賴的概念來定義碼。定義4.4:設(shè)X為R中的屬性或?qū)傩越M合，若XF>U則X為R的候選碼。說明：XF>UX->UX能決定整個元組X’+>UX中無多余的屬性,術(shù)語：主碼主屬性:侯選碼中的屬性非主屬性全碼：整個屬性組為碼例：R(顧客，商品，日期),4.1函數(shù)依賴,例：試指出下列關(guān)系R中的侯選碼、主屬性和非主屬性。,解：關(guān)系R的侯選碼為：A，(D,E)關(guān)系R的主屬性為：A，D，E關(guān)系R的非主屬性：無,函數(shù)依賴判斷：A->D?D->A?…AD->E?…候選碼判斷:A->ADE?…AD->ADE?…,4.1函數(shù)依賴,例1.R(A,B,C,D)，F(xiàn)={A->B,A->C,AB->D}解：由AB->A(自反律)和A->C(已知)得：AB->C(傳遞律)又因為AB->A(自反律)，AB->B(自反律)和AB->D(已知)得：AB->ABCD。AB是R的唯一候選碼，同時也是R的主碼。,4.1函數(shù)依賴,例2.R(A,B,C,D)，F(xiàn)={A->B,A->C,A->D,AB->D}解：由A->A(自反律)和A->B,A->C,A->D(已知)得：A->ABCD可知A是R的候選碼AB->ABCD，但由于存在A->ABCD，則AB對ABCD是部分函數(shù)依賴，因此AB不能成為候選碼。A是R的唯一候選碼，A是主碼。,4.2關(guān)系模式的規(guī)范化,一、關(guān)系與范式關(guān)系的規(guī)范化是將一個低級范式的關(guān)系模式，通過關(guān)系模式的分解轉(zhuǎn)換為若干個高級范式的過程。關(guān)系模式分解的目的：去冗余、滿足約束。關(guān)系模式的冗余性問題。例R(A,B,C)，無任何約束可導(dǎo)致冗余，若規(guī)定FD:A->B，則冗余可利用FD預(yù)測到。約束條件通過函數(shù)的多值依賴和連接依賴及范式完成。,4.2關(guān)系模式的規(guī)范化,二、第一范式：1NF定義4.5:若R的每個分量都是不可分的數(shù)據(jù)項，則R∈1NF。從型上看：不存在嵌套結(jié)構(gòu)從值上看，不存在重復(fù)組1NF是關(guān)系模式的最低要求。例：學(xué)生關(guān)系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE)是1NF關(guān)系，但它存在數(shù)據(jù)冗余，插入異常和刪除異常等問題。,4.2關(guān)系模式的規(guī)范化,三、第二范式：2NF定義4.6若R∈1NF，且R中的每一個非主屬性都完全函數(shù)依賴于R的任一候選碼，則R∈2NF。例：學(xué)生關(guān)系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE),判斷R是否為2NF?侯選碼為(S#，C#)，非主屬性有：SNAME，CLASS，TNAME，TAGE，ADDRESS，GRADE(S#，C#)－>SNAME，S#－>SNAME(S#，C#)P>SNAMES?2NF(每一個非主屬性!)。,4.2關(guān)系模式的規(guī)范化,分解為2NF的方法：破壞部分依賴的條件。將滿足部分函數(shù)依賴和滿足完全函數(shù)依賴的屬性分解到不同的關(guān)系中。對上例，考察非主屬性和侯選碼之間的函數(shù)依賴關(guān)系：(S#，C#)P>SNAME，(S#，C#)P>CLASS，(S#，C#)P>TNAME，(S#，C#)P>TAGE，(S#，C#)P>ADDRESS，(S#，C#)F>GRADE區(qū)分出完全依賴和部分依賴，若是部分依賴，標(biāo)記出其中的主屬性。,4.2關(guān)系模式的規(guī)范化,關(guān)系S分解為三個關(guān)系：ST(S#，SNAME，CLASS)（只依賴S#的屬性分解到一個子模式中）CTA(C#，TNAME，TAGE，ADDRESS)（只依賴C#的屬性分解到另一個子模式中）SC(S#，C#，GRADE)（完全函數(shù)依賴于候選碼的屬性分解到第三個子模式中）分解后，關(guān)系ST、CTA和SC都為2NF。結(jié)論1：若關(guān)系R的侯選碼是單屬性的，則R必定是2NF。,4.2關(guān)系模式的規(guī)范化,達(dá)到2NF的關(guān)系仍然可能存在問題。例如，在關(guān)系CTA中還存在以下問題：（1）數(shù)據(jù)冗余。一個教師承擔(dān)多門課程時，教師的姓名、年齡、地址要重復(fù)存儲。（2）修改復(fù)雜。一個教師更換地址時，必須修改相關(guān)的多個元組。（3）插入異常。一個新教師報到，需將其有關(guān)數(shù)據(jù)插入到CTA關(guān)系中，但該教師暫時還未承擔(dān)任何教學(xué)任務(wù)，則因缺碼C#值而不能進(jìn)行插入操作。（4）刪除異常。刪除某門課程時，會丟失該課程任課教師的姓名、年齡和地址信息。,4.2關(guān)系模式的規(guī)范化,四、第三范式：3NF定義4.7如果關(guān)系R的任意一個非主屬性都不傳遞函數(shù)依賴于它的任意一個候選碼，則R∈3NF。關(guān)系CTA(C#，TNAME，TAGE，ADDRESS)是2NF，但不是3NF。候選碼：C#，非主屬性：TNAME、TAGE、ADDRESS。由于C#→TNAME，TNAME+>C#，TNAME→TAGE，所以C#T>TAGE，同樣有C#T>ADDRESS，即存在非主屬性對候選碼的傳遞函數(shù)依賴。,關(guān)系模式R（A，B，C，D），碼為AB，給出它的一個函數(shù)依賴集，使得R屬于2NF而不屬于3NF,4.2關(guān)系模式的規(guī)范化,分解為3NF的方法：破壞傳遞依賴的條件。將涉及傳遞函數(shù)依賴中的兩個依賴中的屬性分解到不同的關(guān)系中。例：CTA中，兩個傳遞依賴C#T>TAGE，C#T>ADDRESSC#→TNAME，TNAME+>C#，TNAME→TAGE。C#→TNAME，TNAME+>C#，TNAME→ADDRESS。將CTA分解為：CT(C#，TNAME)TA(TNAME，TAGE，ADDRESS)則關(guān)系CT和TA都是3NF，關(guān)系CTA中存在的問題得到了解決。,4.2關(guān)系模式的規(guī)范化,定理4.1一個3NF的關(guān)系必定是2NF。（3NF傳遞函數(shù)依賴，2NF完全函數(shù)依賴。）證明：用反證法。設(shè)R∈3NF，但R?2NF，則R中必有非主屬性A、侯選碼X和X的真子集X‘存在，使得X’→A。X’是侯選碼X的真子集，有X-X‘≠ф；A是非主屬性，A-X≠ф，A-X‘≠ф，這樣A、X、X‘是U的不同子集。X’是侯選碼X的真子集，則有X→X’且X’+>X，聯(lián)合反證假設(shè)X’→A可知存在傳遞依賴（X→X’，X’+>X，X’→A）R不是3NF，與題設(shè)矛盾。,4.2關(guān)系模式的規(guī)范化,通過轉(zhuǎn)為2NF消除了部分依賴，通過轉(zhuǎn)為3NF消除了傳遞依賴，問題：達(dá)到3NF的關(guān)系是否仍然存在問題？例：每一教師只教一門課。每門課由若干教師教，某一學(xué)生選定某門課，就確定了一個固定的教師。某個學(xué)生選修某個教師的課就確定了所選課的名稱：,4.2關(guān)系模式的規(guī)范化,解：關(guān)系SCT的侯選碼：(S#，CNAME)和(S#，TNAME)非主屬性：無（SCT至少是一個3NF關(guān)系)結(jié)論2：若關(guān)系R的所有屬性都是主屬性，則R必定是3NF。,候選碼判斷:S#->S#CNAMETNAME..取左部的相同值，判斷右部。,4.2關(guān)系模式的規(guī)范化,在3NF關(guān)系SCT中存在：插入異常。例如，一個新課程和任課教師的數(shù)據(jù)，在沒有學(xué)生選課時不能插入數(shù)據(jù)庫。刪除異常。例如，刪除某門課的所有選課記錄，會丟失課程與教師的數(shù)據(jù)。達(dá)到3NF的關(guān)系仍然可能存在問題。,4.2關(guān)系模式的規(guī)范化（自學(xué)）,五、BCNF定義4.8關(guān)系模式R∈1NF。若函數(shù)依賴集合F中的所有函數(shù)依賴X→Y（Y不包含于X）的左部都包含R的任一侯選碼，則R∈BCNF。換言之，BCNF中的所有依賴的左部都必須包含候選碼。例：關(guān)系SCT是否BCNF?因為TNAME→CNAME，其左部未包含該關(guān)系的任一侯選碼，所以它不是BCNF。解決：BCNF分解。,4.2關(guān)系模式的規(guī)范化,分解為BCNF的方法：消除不包含關(guān)系。1.假設(shè)R(U)不是BCNF,X是R的屬性子集，A是R的單個屬性，X->A是導(dǎo)致違反BCNF的函數(shù)依賴，則將R分解為R-A以及XA。2.若R-A以及XA仍然不是BCNF，則在R-A以及XA遞歸地執(zhí)行上述分解。例SCT：(S#，CNAME，TNAME)，F(xiàn)D:TNAME→CNAME?？煞纸鉃镾C(S#，TNAME)和CT(CNAME，TNAME)，它們都是BCNF。,4.2關(guān)系模式的規(guī)范化,定理4.2：一個BCNF的關(guān)系必定是3NF。（3NF：任意的非主屬性都不傳遞依賴于任意一個候選碼。）證明：用反證法。設(shè)R是一個BCNF，但不是3NF，則必存在一個非主屬性A和候選碼X以及屬性集Y，使得A傳遞依賴于X，即X→Y(Y不包含于X)，Y+>X，Y→A。這就是說Y不包含R的候選碼，但Y→A卻成立。根據(jù)BCNF定義可知，R不是BCNF，與題設(shè)矛盾。結(jié)論3：任何的二元關(guān)系必定是BCNF。,4.2關(guān)系模式的規(guī)范化,3NF下仍然存在插入異常和刪除異常，原因在于可能存在主屬性對候選碼的部分函數(shù)依賴和傳遞函數(shù)依賴。一個模式中的關(guān)系模式如果都屬于BCNF，則在函數(shù)依賴的范疇內(nèi)實現(xiàn)了徹底的分離，已消除了插入和刪除的異常。其它問題？,4.2關(guān)系模式的規(guī)范化（自學(xué)）,六、第四范式：4NF定義4.10若R∈1NF，D是R上的依賴集，如果對于任何一個多值依賴X??Y(Y-X≠ф,XY沒有包含R的全部屬性)，X都包含了R的一個候選關(guān)鍵詞，則R∈4NF。4NF必定是BCNF，但BCNF不一定是4NF。,,5種范式的關(guān)系：,4.2關(guān)系模式的規(guī)范化,1NF,非規(guī)范化的關(guān)系,2NF,3NF,4NF,BCNF,,范式的轉(zhuǎn)換關(guān)系：,,1NF,2NF,3NF,BCNF,4NF,,4.2關(guān)系模式的規(guī)范化,關(guān)系的規(guī)范化是將一個低級范式的關(guān)系模式，通過關(guān)系模式的分解轉(zhuǎn)換為若干個高級范式的過程。范式的轉(zhuǎn)換過程是通過分析和消除屬性間的數(shù)據(jù)依賴關(guān)系來實現(xiàn)的。屬性可分為碼和非主屬性。2NF,3NF考察非主屬性和碼的關(guān)系，BCNF考察主屬性和碼的關(guān)系。屬性間的依賴關(guān)系包括函數(shù)依賴和多值依賴。1NF,2NF,3NF,BCNF考察了函數(shù)依賴關(guān)系；4NF考察了多值依賴。,4.3數(shù)據(jù)依賴的公理系統(tǒng)（自學(xué)）,1.阿氏公理定義4.13設(shè)F是關(guān)系模式R的函數(shù)依賴集，X、Y是R的屬性子集，如果從F的函數(shù)依賴中能夠推出X?Y，則稱F邏輯蘊涵X?Y。在R中為F所邏輯蘊含的函數(shù)依賴全體叫F的閉包，記為：F+。F+={①F；②F中推出的非平凡的函數(shù)依賴；③平凡的函數(shù)依賴：A->φ、A->A、AB->A…..}例：有關(guān)系模式R(A，B，C)，它的函依賴集F={A→B，B→C}，計算F的閉包。,4.3數(shù)據(jù)依賴的公理系統(tǒng),Armstrong公理(阿氏公理)：對R有：A1自反律：若Y?X，則X?Y。A2增廣律：若X?Y，則XZ?YZ。A3傳遞律：若X?Y、Y?Z，則X?Z。Note：XY與YX的次序無關(guān)。,4.3數(shù)據(jù)依賴的公理系統(tǒng),證：設(shè)s，t是r的任意兩個元組，r是R的任意一個關(guān)系。A1自反律：若Y?X，則X?Y。若s[x]=t[x]，則在s和t中的x的任何子集也必相等?！遈?X，∴s[y]=t[y]∴X?Y。A2增廣律：若X?Y，則XZ?YZ。若s[xz]=t[xz]，即s[x]s[z]=t[x]t[z]則s[x]=t[x]且s[z]=t[z]∵X?Y，∴s[y]=t[y]∴s[yz]=s[y]s[z]=t[y]t[z]=t[yz]∴XZ?YZ,4.3數(shù)據(jù)依賴的公理系統(tǒng),A3傳遞律：若X?Y、Y?Z，則X?Z。若s[x]=t[x]∵X?Y∴s[y]=t[y]又∵Y?Z∴s[z]=t[z]∴X?Z。,4.3數(shù)據(jù)依賴的公理系統(tǒng),公理的推論：合并規(guī)則：若X?Y、X?Z，則X?YZ。分解規(guī)則：若X?YZ，則X?Y,X?Z。偽傳遞規(guī)則：若X?Y、WY?Z，則WX?Z。證明：合并規(guī)則：∵X?Y∴X?XY(A2)又∵X?Z∴XY?YZ(A2)∴X?YZ(A3),4.3數(shù)據(jù)依賴的公理系統(tǒng),分解規(guī)則：∵Y?YZ∴YZ?Y(A1)又∵X?YZ(已知）∴X?Y(A3)同理可證X?Z。偽傳遞規(guī)則：∵X?Y∴WX?WY(A2)又∵WY?Z(已知)∴WX?Z(A3)定理4.5:X?A1A2…AK成立的充分必要條件是X?Ai成立。,由合并律?由分解律?,4.3數(shù)據(jù)依賴的公理系統(tǒng),定義4.14:XF+={A|X?A能由F用阿氏公理導(dǎo)出}XF+稱為屬性集X關(guān)于F的閉包。定理4.6：X?Y能從F中用阿氏公理導(dǎo)出的充要條件是：Y?XF+,4.3數(shù)據(jù)依賴的公理系統(tǒng),定理4.6的證明證明：充分性（Y?XF+->X?Y）假設(shè)Y?XF+(其中Y=A1A2…An)由屬性閉包定義可知，X?A1，X?A2…，X?An能由阿氏公理導(dǎo)出，再由合并規(guī)則得X?A1A2…An，即X?Y。,4.3數(shù)據(jù)依賴的公理系統(tǒng),必要性：（X?Y->Y?XF+）假設(shè)X?Y能由阿氏公理導(dǎo)出(Y=A1A2…An)則有X?A1A2…An由分解規(guī)則得：X?A1，X?A2…，X?An由XF+的定義可知，Ai?XF+(i=1,2,…,n)即Y?XF+。,Armstrong公理系統(tǒng),Armstrong公理完備性的證明證明：（構(gòu)造性證明）用反證法假定存在函數(shù)依賴X?Y被F邏輯蘊涵，但X?Y不能用Armstrong公理從F中導(dǎo)出由引理二，構(gòu)造R(U)上的關(guān)系r如下：下面證明（1）r滿足F，（2）r不滿足X?Y,Y?，?Y?≠?，U?≠?,4.3數(shù)據(jù)依賴的公理系統(tǒng),2.屬性閉包的計算算法4.1:求屬性集X關(guān)于F的閉包XF+(X+)。算法：設(shè)R，A為U中屬性(集)。(1)X(0)=X(2)X(i+1)=X(i)∪A其中：對F中任一個Y->A，且Y?X(i)；求得X(i+1)后，對Y->A做刪除標(biāo)記。(3)若X(i+1)=X(i)或X(i+1)=U則結(jié)束，否則轉(zhuǎn)(2)。,最多|U-X|步,閉包的計算,示例1R,U=(A,B,C,G,H,I),F={A?B,A?C,CG?H,CG?I,B?H},計算所用依賴A?BAGBA?CAGBCCG?HAGBCHCG?IAGBCHI=AGBCHI,,閉包的計算,示例2R,U=(A,B,C,D,E),F={AB?C,B?D,C?E,CE?B,AC?B},計算所用依賴AB?CABCB?DABCDC?EABCDE=ABCDE,,閉包的計算,示例3R,U=(A,B,C,D,E,G),F={A?E,BE?AG,CE?A,G?D},計算所用依賴A?EABEBE?AGABEGG?DABEGD=ABEGD,,4.3數(shù)據(jù)依賴的公理系統(tǒng),3.函數(shù)依賴集的等價和覆蓋定義4.15:如果F+=G+，就說函數(shù)依賴集F覆蓋G或F與G等價。定理4.9:F+=G+的充分必要條件是F?G+，和G?F+。（1）必要性∵F和G等價，∴F+=G+，又∵F?F+，∴F?G+同理，∵G?G+，∴G?F+。（2）充分性任取X→Y∈F+，則有Y?XF+(定理4.6)又∵F?G+（已知），∴Y?XG++∴X→Y∈(G+)+=G+，∴F+?G+。同理可證G+?F+，∴F+=G+，即F和G等價。,4.3數(shù)據(jù)依賴的公理系統(tǒng),如何判斷函數(shù)依賴集F和G是否等價？根據(jù)定理4.9:只需F?G+和G?F+，即證集合的包含關(guān)系。對每個T∈F,有T∈G+；對每個S∈G，有S∈F+，T和S是形如X->Y的屬性依賴。證X->Y∈G+,根據(jù)定理4.6：只需Y?XG+轉(zhuǎn)為計算XG+,4.3數(shù)據(jù)依賴的公理系統(tǒng),例：F={A→B，B→C}，G={A→BC，B→C}，判斷F和G是否等價。解：（1）先檢查F中的每一個函數(shù)依賴是否屬于G+?！逜G+=ABC，∴B?AG+，∴A→B∈G+(定理4.6)又∵BG+=BC，∴C?BG+，∴B→C∈G+∴F?G+（2）然后檢查G中的每一個函數(shù)依賴是否屬于F+?！逜F+=ABC，∴BC?AF+，∴A→BC∈F+又∵BF+=BC，∴C?BF+，∴B→C∈F+∴G?F+由（1）和（2）可得F和G等價。,4.3數(shù)據(jù)依賴的公理系統(tǒng),4.最小函數(shù)依賴集定義4.16:若F滿足下列條件，則稱其為一個最小函數(shù)依賴集Fm。(1)F中每個函數(shù)依賴的右部都是單屬性；(2)對于F的任一函數(shù)依賴X→A，F(xiàn)-{X→A}與F都不等價；(3)對于F中的任一函數(shù)依賴X→A和X的真子集Z，(F-(X→A))U{Z→A}與F都不等價。,最?。海?）F中每個函數(shù)依賴的右部沒有多余的屬性；（2）F中不存在多余的函數(shù)依賴；（3）F中每個函數(shù)依賴的左部沒有多余的屬性。,4.3數(shù)據(jù)依賴的公理系統(tǒng),定理4.10:每個F與Fm等價。如何求最小函數(shù)依賴集Fm？(1)分解：使F中任一函數(shù)依賴的右部僅含有單屬性。(2)刪除冗余的函數(shù)依賴：方法：對F中任一X?A，在F-{X?A}中求X+，若A?X+，則X?A為多余的。(3)最小化左邊的多余屬性：方法：對F中任一XY?A，在F中求X+，若A?X+，則Y為多余的。[(4)檢查：用公理或(2)],4.3數(shù)據(jù)依賴的公理系統(tǒng),例：設(shè)有F={B→C，C→AB，BC→A}，求與F等價的最小函數(shù)依賴集。分解C→AB，F(xiàn)={B→C，C→A，C→B，BC→A}判斷B→C是否冗余，F(xiàn)’={C→A，C→B，BC→A}B+=B,B→C非冗余。F={B→C，C→A，C→B，BC→A}判斷C→A是否冗余，F(xiàn)’={B→C,C→B，BC→A}C+=ABC,C→A冗余。F={B→C，C→B，BC→A}判斷C→B是否冗余，F(xiàn)’={B→C,BC→A}C+=C,C→B非冗余。F={B→C，C→B，BC→A}判斷BC→A是否冗余，F(xiàn)’={B→C，C→B}BC+=BC,BC→A非冗余。F={B→C，C→B，BC→A}判斷BC→A。B+=ABC,A?B+，則C在BC→A中是多余的。Fmin={B→C，C→B，B→A},注意：對當(dāng)前F求閉包,4.3數(shù)據(jù)依賴的公理系統(tǒng),例：設(shè)有函數(shù)依賴集F={A→B,ABCD→E,EF→G,EF→H,ACDF→EG}求與F等價的最小函數(shù)依賴集。注意：一個函數(shù)依賴集的最小集不是惟一的。例如，F(xiàn)={A→B，B→A，B→C，A→C，C→A}Fm1={A→B，B→C，C→A}，F(xiàn)m2={A→B，B→A，A→C，C→A}。方法1：無多余屬性；依次判斷B->A,A->C是否冗余；方法2：無多余屬性；依次判斷B->C是否冗余。,Fmin={A→B,ACD→E,EF→G,EF→H},4.4關(guān)系模式的分解,對于存在數(shù)據(jù)冗余、插入異常、刪除異常的關(guān)系模式，可以通過對關(guān)系模式的分解來解決問題。關(guān)系模式分解后會帶來兩個問題：（1）查詢時的連接操作是否會丟失某些信息或多出某些信息。這引出了無損連接的概念。（2）分解后的關(guān)系模式是否保持了原來的函數(shù)依賴。這是保持函數(shù)依賴性的問題。,4.4關(guān)系模式的分解,1.等價模式分解的定義一個關(guān)系可以有多種分解方法，如何判斷分解的好與壞呢？例：關(guān)系模式R(S#，SD，MN),F={S#→SD，SDMN}分解一：ρ1={R1(S#)，R2(SD)，R3(MN)}不好！無法恢復(fù)r.分解二：ρ2={R1(S#，SD)，R2(S#，MN)}不好！丟失SDMN分解三：ρ3={R1(S#，SD)，R2(SD，MN)}好！,,R(A,B,C),∏AB(R),∏BC(R),∏AB(R),∏BC(R),,R(A,B,C),∏AB(R),∏BC(R),∏AB(R),∏BC(R),,有損分解,,無損分解,,4.4關(guān)系模式的分解,2.無損連接性與依賴保持性對于R中任何一個關(guān)系r，R分解ρ={R1,R2….RK}無損連接性：r=ΠR1(r)?ΠR2(r)?…?ΠRK(r)保持函數(shù)依賴：F≡ΠR1(F)∪ΠR2(F)∪…ΠRK(F)ΠRi(F)={X->Y|X->Y∈F+∧XY?Ri},,,Ri所蘊含的F+中的函數(shù)依賴,4.4關(guān)系模式的分解,例：R(A，B，C)，F(xiàn)={A->B，A->C}，分解ρ={AB，AC}判斷1：r=ΠAB(r)|X|ΠAC(r)是無損連接分解。判斷2:F≡ΠAB(F)∪ΠAC(F)={A->B，A->C}具有函數(shù)依賴保持性。,r,?ρ={AB，BC},4.4關(guān)系模式的分解（自學(xué)）,算法4.3無損連接性檢驗。輸入：關(guān)系模式R(A1，A2，…，An)，它的函數(shù)依賴集F，以及分解ρ={R1，R2，…，Rk}。輸出：確定ρ是否具有無損連接性。方法：(1)構(gòu)造一個k行n列的表，第i行對應(yīng)于關(guān)系模式Ri，第j列對應(yīng)于屬性Aj。如果Aj∈Ri，則在第i行第j列上放符號aj，否則放符號bij。（屬于用a代表，且位置信息用j表示；不屬于用b代表,且位置信息用ij表示。）(2)重復(fù)考察F中的每一個函數(shù)依賴，并修改表中的元素。其方法如下：取F中一個函數(shù)依賴X→Y，在X的分量中尋找相同的行，然后將這些行中Y的分量改為相同的符號，如果其中有aj，則將bij改為aj；若其中無aj，則全部改為bij（i是這些行的行號最小值）。,4.4關(guān)系模式的分解,(3)如果發(fā)現(xiàn)表中某一行變成了al，a2，…，an，則分解ρ具有無損連接性；如果F中所有函數(shù)依賴都不能再修改表中的內(nèi)容，且沒有發(fā)現(xiàn)這樣的行，則分解ρ不具有無損連接性。,無損連接分解,示例一：U={A,B,C,D,E},F={AB?C,C?D,D?E}?={(A,B,C),(C,D),(D,E)},AB?C,C?D,D?E,,,4.4關(guān)系模式的分解,示例二：U={A,B,C,D,E},F={A?C,B?C,C?D,DE?C,CE?A}?={(A,D),(A,B),(B,E),(C,D,E),(A,E)},A?C,,,4.4關(guān)系模式的分解,B?C,,C?D,,,,4.4關(guān)系模式的分解,DE?C,,,CE?A,,,4.4關(guān)系模式的分解,定理4.12設(shè)ρ=(R1，R2)是R的一個分解，F(xiàn)是R上的函數(shù)依賴集，分解ρ具有無損連接性的充分必要條件是：R1∩R2→(R1-R2)∈F+或R1∩R2→(R2-R1)∈F+證明：（1）充分性：設(shè)R1∩R2→(R1-R2)，按算法5.2可構(gòu)造出下表。表中省略了a和b的下標(biāo)，這無關(guān)緊要。,只能用于判斷分解為2個子模式的情況。,4.4關(guān)系模式的分解,如果R1∩R2→(R1-R2)在F中，則可將表中第2行位于(R1-R2)列中的所有符號都改為a，這樣該表中第2行就全是a了，則ρ具有無損連接性。同理可證R1∩R2→(R2-R1)的情況。如果R1∩R2→(R1-R2)不在F中，但在F+中，即它可以用公理從F中推出來，從而也能推出R1∩R2→Ax,其中Ax?R1-R2，所以可以將Ax列的第2行改為全a，同樣可以將R1-R2中的其他屬性的第2行也改為a，這樣第2行就變成全a行。所以分解ρ={R1，R2}具有無損連接性。同樣可以證明R1∩R2→(R2-R1)的情況。（2）必要性：設(shè)構(gòu)造的表中有一行全為a，例如第1行全為a，則由函數(shù)依賴定義可知R1∩R2→(R2-R1)；如果是第2行全為a，則R1∩R2→(R1-R2)。定理證畢。,4.4關(guān)系模式的分解,例:下列分解是否具有無損連接性和函數(shù)依賴保持性。已知：R(A,B,C)F={A→B，C→B}(1）ρ1={AB，BC}（2）ρ2={AC，BC},4.4關(guān)系模式的分解,（1）對ρ1和F構(gòu)造表：,（2）檢查F={A→B，C→B}對A→B，A列中無相同的行；對C→B,C列中無相同的行。ρ1不具有無損連接性。,ρ1={AB，BC}F={A→B，C→B},4.4關(guān)系模式的分解,ρ1={AB，BC}F={A→B，C→B}利用定理4.12解。R1∩R2=B(R1-R2)=AR1∩R2+>(R1-R2)ρ1不是無損連接分解。,4.4關(guān)系模式的分解,ρ2={AC，BC}F={A→B，C→B},對ρ2和F構(gòu)造表：,檢查F={A→B，C→B}對C→B,C列有相同的行，改寫B(tài)列的相異符號為a，下標(biāo)為列號2。第一行變?yōu)閍1a2a3,ρ2具有無損連接性。,4.4關(guān)系模式的分解,ρ2={AC，BC}F={A→B，C→B}利用定理4.12解。R1∩R2=C(R1-R2)=A；(R2-R1)=B；R1∩R2+>(R2-R1)ρ2是無損連接分解。,4.4關(guān)系模式的分解,3.模式分解的方法3NF的保持無損連接及函數(shù)依賴的分解：設(shè)：R1)對Fm中任一X->A，若XA=U則不分解，結(jié)束。2)若R中Z屬性在Fm中未出現(xiàn)，則所有Z為一個子模式，令U=U-Z。3)對Fm中X->A1，….X->An，用合成規(guī)則合成一個，再對Fm中每個X->A，令Ri=XA。4)R的分解為{R1，R2，….RK，碼},依賴保持不需要；原包含有不需要。,4.4關(guān)系模式的分解,BCNF的保持無損連接的分解：（1）令ρ={R}；（2）如果ρ中所有關(guān)系模式都是BCNF，則轉(zhuǎn)（4）；（3）如果ρ中有一個關(guān)系模式Ri不是BCNF，則Ri中必有X→A∈Fi+(A?X)，且X不是Ri的碼。設(shè)S1=XA，S2=Ui-A，用分解{S1，S2}代替Ri，轉(zhuǎn)（2）；（4）分解結(jié)束，輸出ρ。例：設(shè)R={A,B,C,D},F={A→C，C→A，B→AC，D→AC，BD→A}（1）將R分解為3NF且具有無損連接性和依賴保持性。（2）將R分解為BCNF且具有無損連接性。,關(guān)系模式的分解算法,示例：U={S#，SD，MN，C#，G}F={S#?SD，S#?MN，SD?MN，(S#,C#)?G}⒈U1={S#，SD},F1={S#?SD}U2={S#,MN,C#,G},F2={S#?MN,(S#,C#)?G}⒉U1={S#,SD},F1={S#?SD}U2={S#,MN},F2={S#?MN}U3={S#,C#,G},F3={(S#,C#)?G},4.4關(guān)系模式的分解,關(guān)系模式CTHRSG，其中C表示課程，T表示教師，H表示時間，R表示教室，S表示學(xué)生，G表示成績。函數(shù)依賴集F及其所反映的語義分別為：C?T每門課程僅有一位教師擔(dān)任。HT?R在任一時間，一個教師只能在一個教室上課。HR?C在任一時間，每個教室只能上一門課。HS?R在任一時間，每個學(xué)生只能在一個教室聽課。CS?G每個學(xué)生學(xué)習(xí)一門課程只有一個成績。,4.4關(guān)系模式的分解,解：HS?CTHRSG，HS是關(guān)系模式的關(guān)鍵字。,⑴面向3NF且保持函數(shù)依賴的分解。最小函數(shù)依賴集為F={C?T,CS?G,HR?C,HS?R,TH?R}分解為：?＝{CT，CSG，HRC，HSR，THR},⑵面向3NF既有無損連接性又保持函數(shù)依賴的分解?！逪S是關(guān)鍵字，?＝?∪{HS}，HS是HSR的一個子集∴分解仍為：?＝{CT，CSG，HRC，HSR，THR},4.4關(guān)系模式的分解,⑶面向BCNF且具有無損連接性的分解。,CTHRSGKey=HS,CSGKey=CSCS?G,CTHRSKey=HSC?T，TH?RHR?C，HS?R,CTKey=CC?T,CHRSKey=HSCH?R，HR?CHS?R,CHRKey=CH，HRCH?R，HR?C,CHSKey=HSHS?C,,,,,,,4.5.多值依賴與第四范式4NF）,例:學(xué)校中某一門課程由多個教師講授，他們使用相同的一套參考書。關(guān)系模式Teaching(C,T,B)課程C、教師T和參考書B,,例:學(xué)校中某一門課程由多個教師講授，他們使用相同的一套參考書。關(guān)系模式Teaching(C,T,B)課程C、教師T和參考書B,4.5.多值依賴與第四范式4NF）,4.5.多值依賴與第四范式4NF）,Teaching∈BCNF:Teach具有唯一候選碼(C，T，B)，即全碼Teaching模式中存在的問題(1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲多少次(2)插入操作復(fù)雜：當(dāng)某一課程增加一名任課教師時，該課程有多少本參照書，就必須插入多少個元組例如物理課增加一名教師劉關(guān)，需要插入兩個元組：（物理，劉關(guān)，普通物理學(xué)）（物理，劉關(guān)，光學(xué)原理）,4.5.多值依賴與第四范式4NF）,(3)刪除操作復(fù)雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個元組(4)修改操作復(fù)雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個元組產(chǎn)生原因存在多值依賴,4.5.多值依賴與第四范式4NF,第四范式：4NF定義4.10若R∈1NF，D是R上的依賴集，如果對于任何一個多值依賴X??Y(Y-X≠ф,XY沒有包含R的全部屬性)，X都包含了R的一個候選關(guān)鍵詞，則R∈4NF。4NF必定是BCNF，但BCNF不一定是4NF。,4.5.多值依賴與第四范式4NF,在R（U）的任一關(guān)系r中，如果存在元組t，s使得t[X]=s[X]，那么就必然存在元組w，v?r，（w，v可以與s，t相同），使得w[X]=v[X]=t[X]，而w[Y]=t[Y]，w[Z]=s[Z]，v[Y]=s[Y]，v[Z]=t[Z]（即交換s，t元組的Y值所得的兩個新元組必在r中），則Y多值依賴于X，記為X→→Y。這里，X，Y是U的子集，Z=U-X-Y。txy1z2sxy2z1wxy1z1vxy2z2,4.5.多值依賴與第四范式4NF,平凡多值依賴和非平凡的多值依賴若X→→Y，而Z＝φ，則稱X→→Y為平凡的多值依賴否則稱X→→Y為非平凡的多值依賴,4.5.多值依賴與第四范式4NF多值依賴的性質(zhì),（1）多值依賴具有對稱性若X→→Y，則X→→Z，其中Z＝U－X－Y多值依賴的對稱性可以用完全二分圖直觀地表示出來。（2）多值依賴具有傳遞性若X→→Y，Y→→Z，則X→→Z-Y,,,,（3）函數(shù)依賴是多值依賴的特殊情況。若X→Y，則X→→Y。（4）若X→→Y，X→→Z，則X→→Y?Z。（5）若X→→Y，X→→Z，則X→→Y∩Z。（6）若X→→Y，X→→Z，則X→→Y-Z，X→→Z-Y。,4.5.多值依賴與第四范式4NF多值依賴與函數(shù)依賴的區(qū)別,(1)有效性多值依賴的有效性與屬性集的范圍有關(guān)若X→→Y在U上成立，則在W（XY?W?U）上一定成立；反之則不然，即X→→Y在W（W?U）上成立，在U上并不一定成立多值依賴的定義中不僅涉及屬性組X和Y，而且涉及U中其余屬性Z。一般地，在R（U）上若有X→→Y在W（W?U）上成立，則稱X→→Y為R（U）的嵌入型多值依賴,,只要在R（U）的任何一個關(guān)系r中，元組在X和Y上的值滿足定義5.l（函數(shù)依賴），則函數(shù)依賴X→Y在任何屬性集W（XY?W?U）上成立。(2)若函數(shù)依賴X→Y在R（U）上成立，則對于任何Y?Y均有X→Y成立多值依賴X→→Y若在R(U)上成立，不能斷言對于任何Y?Y有X→→Y成立,4.5.多值依賴與第四范式4NF,例：Teach(C,T,B)∈4NF存在非平凡的多值依賴C→→T，且C不是候選碼用投影分解法把Teach分解為如下兩個關(guān)系模式：CT(C,T)∈4NFCB(C,B)∈4NFC→→T，C→→B是平凡多值依賴,,4.5.多值依賴與第四范式4NF,定理4.3如果關(guān)系模式R∈4NF，則R必為BCNF。證明：用反證法。設(shè)R∈4NF，但R?BCNF，則R中必有某個函數(shù)依賴X?Y(Y不包含于X)，且X不包含R的侯選碼。由多值依賴公理可知，若X?Y，則X??Y，而此時X不包含R的侯選碼，R不是4NF，與假設(shè)矛盾，從而定理得證。,4.5.多值依賴與第四范式4NF,分解為4NF的方法：（類似于BCNF，消除不包含關(guān)系。）1.假設(shè)R(U)不是4NF,X->->A是導(dǎo)致違反4NF的多值依賴，則將R分解為R-A以及XA。2.若R-A以及XA仍然不是4NF，則在R-A以及XA遞歸地執(zhí)行上述分解。,4.5.多值依賴與第四范式4NF）,⑷面向4NF且具有無損連接性的分解。,關(guān)系模式R中存在多值依賴C??HR，T??HR，顯然由于C或T都不含該關(guān)系模式的碼HS，∴R?4NF。選擇C??HR將它分解為CHR和CTSG;再將CTSG分解為CT和CSG。關(guān)系模式CTHRSG最后無損地分解為CHR、CT和CSG，其中每一個關(guān)系模式都屬于4NF。,4.6規(guī)范化的問題,1.規(guī)范化的優(yōu)缺點關(guān)系模式的分解會降低查詢的效率。所討論的關(guān)系規(guī)范化是基于泛關(guān)系假設(shè)的，即只基于一個關(guān)系模式的規(guī)范化。但現(xiàn)實并不一定滿足。2.反規(guī)范化的設(shè)計對一些特定的應(yīng)用不規(guī)范化，而是通過使用冗余來改進(jìn)性能。例：account(帳號，支行名，余額)depositor(客戶名，帳號)每次訪問帳戶時，帳戶持有者的名字都與帳戶密碼和余額一起顯示。,4.6規(guī)范化的問題,并不是規(guī)范化程度越高越好。例：earnings(公司號，年份，數(shù)量)若設(shè)計成：（1）使用多個關(guān)系，每年建一個表。不好?。ㄊ荁CNF）（2）使用一個關(guān)系：company_year(公司號，收入_2000，收入_2001，收入_2002)不好?。ㄊ荁CNF）,第四章關(guān)系數(shù)據(jù)理論小結(jié),1.函數(shù)依賴關(guān)系2.關(guān)系模式的規(guī)范化5種范式及轉(zhuǎn)換3.阿氏公理及其推理規(guī)則4.XF+的定義及求XF+5.用函數(shù)依賴或XF+求碼6.求最小函數(shù)依賴集Fm7.模式分解的概念、方法,