《關(guān)系數(shù)據(jù)理論》PPT課件.ppt
《《關(guān)系數(shù)據(jù)理論》PPT課件.ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《《關(guān)系數(shù)據(jù)理論》PPT課件.ppt(99頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
4.1關(guān)系模式的設(shè)計(jì)問(wèn)題,4.2關(guān)系模式的規(guī)范化,4.3數(shù)據(jù)依賴的公理系統(tǒng)(自學(xué)),4.4關(guān)系模式的分解,第四章關(guān)系數(shù)據(jù)理論,本章小結(jié),4.1函數(shù)依賴,一、問(wèn)題如何構(gòu)造一個(gè)關(guān)系模式例:假設(shè)有學(xué)生關(guān)系模式,其中,S#學(xué)號(hào)、SNAME學(xué)生姓名、CLASS班級(jí)、C#課程號(hào)、TNAME教師姓名、TAGE教師年齡、ADDRESS教師地址、GRADE成績(jī)。,S(S#,SNAME,CLASS,C#,TNAME,TAGE,ADDRESS,GRADE),關(guān)系S存在以下問(wèn)題:1數(shù)據(jù)冗余度高。SNAME、CLASS、TNAME、TAGE、ADDRESS重復(fù)存儲(chǔ)多次。,4.1函數(shù)依賴,2數(shù)據(jù)修改復(fù)雜。3插入異常。插入異常是指應(yīng)該插入到數(shù)據(jù)庫(kù)中的數(shù)據(jù)不能執(zhí)行插入操作的情形。,關(guān)系S的主碼:,(S#,C#),從在S#、C#、和(S#,c#)上出現(xiàn)NULL值去分析。注意:當(dāng)一個(gè)元組在主碼的屬性上部分或全部為空時(shí),該元組不能插入到關(guān)系中。,4.1函數(shù)依賴,4刪除異常。刪除異常是指不應(yīng)該刪去的數(shù)據(jù)被刪去的情形。例如:選修某門課的所有學(xué)生都退選時(shí),刪除相關(guān)元組,會(huì)丟失該課程老師的信息。解決:關(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)系有:對(duì)X中的每個(gè)屬性值,在Y中都有惟一的值與之對(duì)應(yīng),則稱Y函數(shù)依賴于X,記作XY。,屬性全集,4.1函數(shù)依賴,例:指出下列關(guān)系R中的函數(shù)依賴。,FD:AB-C、AC、CA、ABD?InsertintoRvalues(a1,b1,c2,d1)FD=keyconstraint?,4.1函數(shù)依賴,函數(shù)依賴與屬性間的關(guān)系有:若X,Y是11關(guān)系,則存在XY或YX。如學(xué)號(hào)與借書證號(hào)若X,Y是m1關(guān)系,則存在XY但Y+X。如學(xué)號(hào)與姓名若X,Y是mn關(guān)系,則X,Y間不存在函數(shù)依賴關(guān)系。如姓名與課程CF:實(shí)體間的聯(lián)系NOTE:函數(shù)依賴的方向性,4.1函數(shù)依賴,例試指出學(xué)生關(guān)系S(S#,SNAME,CLASS,C#,TNAME,TAGE,ADDRESS,GRADE)中存在的函數(shù)依賴關(guān)系。S#SNAME(每個(gè)學(xué)號(hào)只能有一個(gè)學(xué)生姓名)S#CLASS(每個(gè)學(xué)號(hào)只能有一個(gè)班級(jí))C#TNAME(設(shè)每門課程只有一個(gè)教師任教,而一個(gè)教師可教多門課程,見CT表)TNAMETAGE(每個(gè)教師只能有一個(gè)年齡)TNAMEADDRESS(每個(gè)教師只能有一個(gè)地址)(S#,C#)GRADE(每個(gè)學(xué)生學(xué)習(xí)一門課只能有一個(gè)成績(jī))(S#,C#)SNAME、(S#,C#)CLASS、(S#,C#)C#、(S#,C#)TNAME、(S#,C#)TAGE、(S#,C#)ADDRESS,4.1函數(shù)依賴,三、函數(shù)依賴的分類XY,但Y不包含于X則稱X是非平凡的函數(shù)依賴。XY,但YX則稱X是平凡的函數(shù)依賴。若XY,則X叫做決定因素。若XY,YX,則記作:XY。定義4.2:在R(U)中,X,Y,Z為U的不同子集。完全函數(shù)依賴:是指XY,且對(duì)任何X的真子集X,都有X+Y,記作:XFY。部分函數(shù)依賴:是指XY,且存在X的真子集X,有X-Y,記作:XPY。,定義4.3:在R(U)中傳遞函數(shù)依賴:是指若XY(Y不包含于X),Y+X,而YZ。記作:XTZ。,4.1函數(shù)依賴,左部為單屬性的函數(shù)依賴一定是完全函數(shù)依賴。左部為多屬性的函數(shù)依賴,如何判斷其是否為完全函數(shù)依賴?方法:取真子集,看其能否決定右部屬性。例:試指出學(xué)生關(guān)系S中存在的完全函數(shù)依賴和部分函數(shù)依賴。S#SNAME,S#CLASS,TNAMETAGE,TNAMEADDRESS,C#TNAME都是完全函數(shù)依賴。(S#,C#)GRADE是一個(gè)完全函數(shù)依賴,因?yàn)镾#+GRADE,C#+GRADE。,4.1函數(shù)依賴,例:試指出學(xué)生關(guān)系S中存在的傳遞函數(shù)依賴。解:因?yàn)镃#TNAME,TNAME+C#,TNAMETAGE,所以C#TAGE是一個(gè)傳遞函數(shù)依賴。類似地,C#ADDRESS也是一個(gè)傳遞函數(shù)依賴。,(S#,C#)SNAME,(S#,C#)CLASS,(S#,C#)TNAME,(S#,C#)TAGE,(S#,C#)ADDRESS都是部分函數(shù)依賴,因?yàn)镾#SNAME,S#CLASS,C#TNAME,C#TAGE,C#ADDRESS。,4.1函數(shù)依賴,四、候選碼用函數(shù)依賴的概念來(lái)定義碼。定義4.4:設(shè)X為R中的屬性或?qū)傩越M合,若XFU則X為R的候選碼。說(shuō)明:XFUX-UX能決定整個(gè)元組X+UX中無(wú)多余的屬性,術(shù)語(yǔ):主碼主屬性:侯選碼中的屬性非主屬性全碼:整個(gè)屬性組為碼例:R(顧客,商品,日期),4.1函數(shù)依賴,例:試指出下列關(guān)系R中的侯選碼、主屬性和非主屬性。,解:關(guān)系R的侯選碼為:A,(D,E)關(guān)系R的主屬性為:A,D,E關(guān)系R的非主屬性:無(wú),函數(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(傳遞律)又因?yàn)锳B-A(自反律),AB-B(自反律)和AB-D(已知)得:AB-ABCD。AB是R的唯一候選碼,同時(shí)也是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對(duì)ABCD是部分函數(shù)依賴,因此AB不能成為候選碼。A是R的唯一候選碼,A是主碼。,4.2關(guān)系模式的規(guī)范化,一、關(guān)系與范式關(guān)系的規(guī)范化是將一個(gè)低級(jí)范式的關(guān)系模式,通過(guò)關(guān)系模式的分解轉(zhuǎn)換為若干個(gè)高級(jí)范式的過(guò)程。關(guān)系模式分解的目的:去冗余、滿足約束。關(guān)系模式的冗余性問(wèn)題。例R(A,B,C),無(wú)任何約束可導(dǎo)致冗余,若規(guī)定FD:A-B,則冗余可利用FD預(yù)測(cè)到。約束條件通過(guò)函數(shù)的多值依賴和連接依賴及范式完成。,4.2關(guān)系模式的規(guī)范化,二、第一范式:1NF定義4.5:若R的每個(gè)分量都是不可分的數(shù)據(jù)項(xiàng),則R1NF。從型上看:不存在嵌套結(jié)構(gòu)從值上看,不存在重復(fù)組1NF是關(guān)系模式的最低要求。例:學(xué)生關(guān)系S(S#,SNAME,CLASS,C#,TNAME,TAGE,ADDRESS,GRADE)是1NF關(guān)系,但它存在數(shù)據(jù)冗余,插入異常和刪除異常等問(wèn)題。,4.2關(guān)系模式的規(guī)范化,三、第二范式:2NF定義4.6若R1NF,且R中的每一個(gè)非主屬性都完全函數(shù)依賴于R的任一候選碼,則R2NF。例:學(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#)PSNAMES2NF(每一個(gè)非主屬性!)。,4.2關(guān)系模式的規(guī)范化,分解為2NF的方法:破壞部分依賴的條件。將滿足部分函數(shù)依賴和滿足完全函數(shù)依賴的屬性分解到不同的關(guān)系中。對(duì)上例,考察非主屬性和侯選碼之間的函數(shù)依賴關(guān)系:(S#,C#)PSNAME,(S#,C#)PCLASS,(S#,C#)PTNAME,(S#,C#)PTAGE,(S#,C#)PADDRESS,(S#,C#)FGRADE區(qū)分出完全依賴和部分依賴,若是部分依賴,標(biāo)記出其中的主屬性。,4.2關(guān)系模式的規(guī)范化,關(guān)系S分解為三個(gè)關(guān)系:ST(S#,SNAME,CLASS)(只依賴S#的屬性分解到一個(gè)子模式中)CTA(C#,TNAME,TAGE,ADDRESS)(只依賴C#的屬性分解到另一個(gè)子模式中)SC(S#,C#,GRADE)(完全函數(shù)依賴于候選碼的屬性分解到第三個(gè)子模式中)分解后,關(guān)系ST、CTA和SC都為2NF。結(jié)論1:若關(guān)系R的侯選碼是單屬性的,則R必定是2NF。,4.2關(guān)系模式的規(guī)范化,達(dá)到2NF的關(guān)系仍然可能存在問(wèn)題。例如,在關(guān)系CTA中還存在以下問(wèn)題:(1)數(shù)據(jù)冗余。一個(gè)教師承擔(dān)多門課程時(shí),教師的姓名、年齡、地址要重復(fù)存儲(chǔ)。(2)修改復(fù)雜。一個(gè)教師更換地址時(shí),必須修改相關(guān)的多個(gè)元組。(3)插入異常。一個(gè)新教師報(bào)到,需將其有關(guān)數(shù)據(jù)插入到CTA關(guān)系中,但該教師暫時(shí)還未承擔(dān)任何教學(xué)任務(wù),則因缺碼C#值而不能進(jìn)行插入操作。(4)刪除異常。刪除某門課程時(shí),會(huì)丟失該課程任課教師的姓名、年齡和地址信息。,4.2關(guān)系模式的規(guī)范化,四、第三范式:3NF定義4.7如果關(guān)系R的任意一個(gè)非主屬性都不傳遞函數(shù)依賴于它的任意一個(gè)候選碼,則R3NF。關(guān)系CTA(C#,TNAME,TAGE,ADDRESS)是2NF,但不是3NF。候選碼:C#,非主屬性:TNAME、TAGE、ADDRESS。由于C#TNAME,TNAME+C#,TNAMETAGE,所以C#TTAGE,同樣有C#TADDRESS,即存在非主屬性對(duì)候選碼的傳遞函數(shù)依賴。,關(guān)系模式R(A,B,C,D),碼為AB,給出它的一個(gè)函數(shù)依賴集,使得R屬于2NF而不屬于3NF,4.2關(guān)系模式的規(guī)范化,分解為3NF的方法:破壞傳遞依賴的條件。將涉及傳遞函數(shù)依賴中的兩個(gè)依賴中的屬性分解到不同的關(guān)系中。例:CTA中,兩個(gè)傳遞依賴C#TTAGE,C#TADDRESSC#TNAME,TNAME+C#,TNAMETAGE。C#TNAME,TNAME+C#,TNAMEADDRESS。將CTA分解為:CT(C#,TNAME)TA(TNAME,TAGE,ADDRESS)則關(guān)系CT和TA都是3NF,關(guān)系CTA中存在的問(wèn)題得到了解決。,4.2關(guān)系模式的規(guī)范化,定理4.1一個(gè)3NF的關(guān)系必定是2NF。(3NF傳遞函數(shù)依賴,2NF完全函數(shù)依賴。)證明:用反證法。設(shè)R3NF,但R2NF,則R中必有非主屬性A、侯選碼X和X的真子集X存在,使得XA。X是侯選碼X的真子集,有X-X;A是非主屬性,A-X,A-X,這樣A、X、X是U的不同子集。X是侯選碼X的真子集,則有XX且X+X,聯(lián)合反證假設(shè)XA可知存在傳遞依賴(XX,X+X,XA)R不是3NF,與題設(shè)矛盾。,4.2關(guān)系模式的規(guī)范化,通過(guò)轉(zhuǎn)為2NF消除了部分依賴,通過(guò)轉(zhuǎn)為3NF消除了傳遞依賴,問(wèn)題:達(dá)到3NF的關(guān)系是否仍然存在問(wèn)題?例:每一教師只教一門課。每門課由若干教師教,某一學(xué)生選定某門課,就確定了一個(gè)固定的教師。某個(gè)學(xué)生選修某個(gè)教師的課就確定了所選課的名稱:,4.2關(guān)系模式的規(guī)范化,解:關(guān)系SCT的侯選碼:(S#,CNAME)和(S#,TNAME)非主屬性:無(wú)(SCT至少是一個(gè)3NF關(guān)系)結(jié)論2:若關(guān)系R的所有屬性都是主屬性,則R必定是3NF。,候選碼判斷:S#-S#CNAMETNAME.取左部的相同值,判斷右部。,4.2關(guān)系模式的規(guī)范化,在3NF關(guān)系SCT中存在:插入異常。例如,一個(gè)新課程和任課教師的數(shù)據(jù),在沒有學(xué)生選課時(shí)不能插入數(shù)據(jù)庫(kù)。刪除異常。例如,刪除某門課的所有選課記錄,會(huì)丟失課程與教師的數(shù)據(jù)。達(dá)到3NF的關(guān)系仍然可能存在問(wèn)題。,4.2關(guān)系模式的規(guī)范化(自學(xué)),五、BCNF定義4.8關(guān)系模式R1NF。若函數(shù)依賴集合F中的所有函數(shù)依賴XY(Y不包含于X)的左部都包含R的任一侯選碼,則RBCNF。換言之,BCNF中的所有依賴的左部都必須包含候選碼。例:關(guān)系SCT是否BCNF?因?yàn)門NAMECNAME,其左部未包含該關(guān)系的任一侯選碼,所以它不是BCNF。解決:BCNF分解。,4.2關(guān)系模式的規(guī)范化,分解為BCNF的方法:消除不包含關(guān)系。1.假設(shè)R(U)不是BCNF,X是R的屬性子集,A是R的單個(gè)屬性,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:TNAMECNAME??煞纸鉃镾C(S#,TNAME)和CT(CNAME,TNAME),它們都是BCNF。,4.2關(guān)系模式的規(guī)范化,定理4.2:一個(gè)BCNF的關(guān)系必定是3NF。(3NF:任意的非主屬性都不傳遞依賴于任意一個(gè)候選碼。)證明:用反證法。設(shè)R是一個(gè)BCNF,但不是3NF,則必存在一個(gè)非主屬性A和候選碼X以及屬性集Y,使得A傳遞依賴于X,即XY(Y不包含于X),Y+X,YA。這就是說(shuō)Y不包含R的候選碼,但YA卻成立。根據(jù)BCNF定義可知,R不是BCNF,與題設(shè)矛盾。結(jié)論3:任何的二元關(guān)系必定是BCNF。,4.2關(guān)系模式的規(guī)范化,3NF下仍然存在插入異常和刪除異常,原因在于可能存在主屬性對(duì)候選碼的部分函數(shù)依賴和傳遞函數(shù)依賴。一個(gè)模式中的關(guān)系模式如果都屬于BCNF,則在函數(shù)依賴的范疇內(nèi)實(shí)現(xiàn)了徹底的分離,已消除了插入和刪除的異常。其它問(wèn)題?,4.2關(guān)系模式的規(guī)范化(自學(xué)),六、第四范式:4NF定義4.10若R1NF,D是R上的依賴集,如果對(duì)于任何一個(gè)多值依賴XY(Y-X,XY沒有包含R的全部屬性),X都包含了R的一個(gè)候選關(guān)鍵詞,則R4NF。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ī)范化是將一個(gè)低級(jí)范式的關(guān)系模式,通過(guò)關(guān)系模式的分解轉(zhuǎn)換為若干個(gè)高級(jí)范式的過(guò)程。范式的轉(zhuǎn)換過(guò)程是通過(guò)分析和消除屬性間的數(shù)據(jù)依賴關(guān)系來(lái)實(shí)現(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ù)依賴中能夠推出XY,則稱F邏輯蘊(yùn)涵XY。在R中為F所邏輯蘊(yùn)含的函數(shù)依賴全體叫F的閉包,記為:F+。F+=F;F中推出的非平凡的函數(shù)依賴;平凡的函數(shù)依賴:A-、A-A、AB-A.例:有關(guān)系模式R(A,B,C),它的函依賴集F=AB,BC,計(jì)算F的閉包。,4.3數(shù)據(jù)依賴的公理系統(tǒng),Armstrong公理(阿氏公理):對(duì)R有:A1自反律:若YX,則XY。A2增廣律:若XY,則XZYZ。A3傳遞律:若XY、YZ,則XZ。Note:XY與YX的次序無(wú)關(guān)。,4.3數(shù)據(jù)依賴的公理系統(tǒng),證:設(shè)s,t是r的任意兩個(gè)元組,r是R的任意一個(gè)關(guān)系。A1自反律:若YX,則XY。若sx=tx,則在s和t中的x的任何子集也必相等。YX,sy=tyXY。A2增廣律:若XY,則XZYZ。若sxz=txz,即sxsz=txtz則sx=tx且sz=tzXY,sy=tysyz=sysz=tytz=tyzXZYZ,4.3數(shù)據(jù)依賴的公理系統(tǒng),A3傳遞律:若XY、YZ,則XZ。若sx=txXYsy=ty又YZsz=tzXZ。,4.3數(shù)據(jù)依賴的公理系統(tǒng),公理的推論:合并規(guī)則:若XY、XZ,則XYZ。分解規(guī)則:若XYZ,則XY,XZ。偽傳遞規(guī)則:若XY、WYZ,則WXZ。證明:合并規(guī)則:XYXXY(A2)又XZXYYZ(A2)XYZ(A3),4.3數(shù)據(jù)依賴的公理系統(tǒng),分解規(guī)則:YYZYZY(A1)又XYZ(已知)XY(A3)同理可證XZ。偽傳遞規(guī)則:XYWXWY(A2)又WYZ(已知)WXZ(A3)定理4.5:XA1A2AK成立的充分必要條件是XAi成立。,由合并律由分解律,4.3數(shù)據(jù)依賴的公理系統(tǒng),定義4.14:XF+=A|XA能由F用阿氏公理導(dǎo)出XF+稱為屬性集X關(guān)于F的閉包。定理4.6:XY能從F中用阿氏公理導(dǎo)出的充要條件是:YXF+,4.3數(shù)據(jù)依賴的公理系統(tǒng),定理4.6的證明證明:充分性(YXF+-XY)假設(shè)YXF+(其中Y=A1A2An)由屬性閉包定義可知,XA1,XA2,XAn能由阿氏公理導(dǎo)出,再由合并規(guī)則得XA1A2An,即XY。,4.3數(shù)據(jù)依賴的公理系統(tǒng),必要性:(XY-YXF+)假設(shè)XY能由阿氏公理導(dǎo)出(Y=A1A2An)則有XA1A2An由分解規(guī)則得:XA1,XA2,XAn由XF+的定義可知,AiXF+(i=1,2,n)即YXF+。,Armstrong公理系統(tǒng),Armstrong公理完備性的證明證明:(構(gòu)造性證明)用反證法假定存在函數(shù)依賴XY被F邏輯蘊(yùn)涵,但XY不能用Armstrong公理從F中導(dǎo)出由引理二,構(gòu)造R(U)上的關(guān)系r如下:下面證明(1)r滿足F,(2)r不滿足XY,Y,Y,U,4.3數(shù)據(jù)依賴的公理系統(tǒng),2.屬性閉包的計(jì)算算法4.1:求屬性集X關(guān)于F的閉包XF+(X+)。算法:設(shè)R,A為U中屬性(集)。(1)X(0)=X(2)X(i+1)=X(i)A其中:對(duì)F中任一個(gè)Y-A,且YX(i);求得X(i+1)后,對(duì)Y-A做刪除標(biāo)記。(3)若X(i+1)=X(i)或X(i+1)=U則結(jié)束,否則轉(zhuǎn)(2)。,最多|U-X|步,閉包的計(jì)算,示例1R,U=(A,B,C,G,H,I),F=AB,AC,CGH,CGI,BH,計(jì)算所用依賴ABAGBACAGBCCGHAGBCHCGIAGBCHI=AGBCHI,閉包的計(jì)算,示例2R,U=(A,B,C,D,E),F=ABC,BD,CE,CEB,ACB,計(jì)算所用依賴ABCABCBDABCDCEABCDE=ABCDE,閉包的計(jì)算,示例3R,U=(A,B,C,D,E,G),F=AE,BEAG,CEA,GD,計(jì)算所用依賴AEABEBEAGABEGGDABEGD=ABEGD,4.3數(shù)據(jù)依賴的公理系統(tǒng),3.函數(shù)依賴集的等價(jià)和覆蓋定義4.15:如果F+=G+,就說(shuō)函數(shù)依賴集F覆蓋G或F與G等價(jià)。定理4.9:F+=G+的充分必要條件是FG+,和GF+。(1)必要性F和G等價(jià),F(xiàn)+=G+,又FF+,F(xiàn)G+同理,GG+,GF+。(2)充分性任取XYF+,則有YXF+(定理4.6)又FG+(已知),YXG+XY(G+)+=G+,F(xiàn)+G+。同理可證G+F+,F(xiàn)+=G+,即F和G等價(jià)。,4.3數(shù)據(jù)依賴的公理系統(tǒng),如何判斷函數(shù)依賴集F和G是否等價(jià)?根據(jù)定理4.9:只需FG+和GF+,即證集合的包含關(guān)系。對(duì)每個(gè)TF,有TG+;對(duì)每個(gè)SG,有SF+,T和S是形如X-Y的屬性依賴。證X-YG+,根據(jù)定理4.6:只需YXG+轉(zhuǎn)為計(jì)算XG+,4.3數(shù)據(jù)依賴的公理系統(tǒng),例:F=AB,BC,G=ABC,BC,判斷F和G是否等價(jià)。解:(1)先檢查F中的每一個(gè)函數(shù)依賴是否屬于G+。AG+=ABC,BAG+,ABG+(定理4.6)又BG+=BC,CBG+,BCG+FG+(2)然后檢查G中的每一個(gè)函數(shù)依賴是否屬于F+。AF+=ABC,BCAF+,ABCF+又BF+=BC,CBF+,BCF+GF+由(1)和(2)可得F和G等價(jià)。,4.3數(shù)據(jù)依賴的公理系統(tǒng),4.最小函數(shù)依賴集定義4.16:若F滿足下列條件,則稱其為一個(gè)最小函數(shù)依賴集Fm。(1)F中每個(gè)函數(shù)依賴的右部都是單屬性;(2)對(duì)于F的任一函數(shù)依賴XA,F(xiàn)-XA與F都不等價(jià);(3)對(duì)于F中的任一函數(shù)依賴XA和X的真子集Z,(F-(XA)UZA與F都不等價(jià)。,最?。海?)F中每個(gè)函數(shù)依賴的右部沒有多余的屬性;(2)F中不存在多余的函數(shù)依賴;(3)F中每個(gè)函數(shù)依賴的左部沒有多余的屬性。,4.3數(shù)據(jù)依賴的公理系統(tǒng),定理4.10:每個(gè)F與Fm等價(jià)。如何求最小函數(shù)依賴集Fm?(1)分解:使F中任一函數(shù)依賴的右部?jī)H含有單屬性。(2)刪除冗余的函數(shù)依賴:方法:對(duì)F中任一XA,在F-XA中求X+,若AX+,則XA為多余的。(3)最小化左邊的多余屬性:方法:對(duì)F中任一XYA,在F中求X+,若AX+,則Y為多余的。(4)檢查:用公理或(2),4.3數(shù)據(jù)依賴的公理系統(tǒng),例:設(shè)有F=BC,CAB,BCA,求與F等價(jià)的最小函數(shù)依賴集。分解CAB,F(xiàn)=BC,CA,CB,BCA判斷BC是否冗余,F(xiàn)=CA,CB,BCAB+=B,BC非冗余。F=BC,CA,CB,BCA判斷CA是否冗余,F(xiàn)=BC,CB,BCAC+=ABC,CA冗余。F=BC,CB,BCA判斷CB是否冗余,F(xiàn)=BC,BCAC+=C,CB非冗余。F=BC,CB,BCA判斷BCA是否冗余,F(xiàn)=BC,CBBC+=BC,BCA非冗余。F=BC,CB,BCA判斷BCA。B+=ABC,AB+,則C在BCA中是多余的。Fmin=BC,CB,BA,注意:對(duì)當(dāng)前F求閉包,4.3數(shù)據(jù)依賴的公理系統(tǒng),例:設(shè)有函數(shù)依賴集F=AB,ABCDE,EFG,EFH,ACDFEG求與F等價(jià)的最小函數(shù)依賴集。注意:一個(gè)函數(shù)依賴集的最小集不是惟一的。例如,F(xiàn)=AB,BA,BC,AC,CAFm1=AB,BC,CA,F(xiàn)m2=AB,BA,AC,CA。方法1:無(wú)多余屬性;依次判斷B-A,A-C是否冗余;方法2:無(wú)多余屬性;依次判斷B-C是否冗余。,Fmin=AB,ACDE,EFG,EFH,4.4關(guān)系模式的分解,對(duì)于存在數(shù)據(jù)冗余、插入異常、刪除異常的關(guān)系模式,可以通過(guò)對(duì)關(guān)系模式的分解來(lái)解決問(wèn)題。關(guān)系模式分解后會(huì)帶來(lái)兩個(gè)問(wèn)題:(1)查詢時(shí)的連接操作是否會(huì)丟失某些信息或多出某些信息。這引出了無(wú)損連接的概念。(2)分解后的關(guān)系模式是否保持了原來(lái)的函數(shù)依賴。這是保持函數(shù)依賴性的問(wèn)題。,4.4關(guān)系模式的分解,1.等價(jià)模式分解的定義一個(gè)關(guān)系可以有多種分解方法,如何判斷分解的好與壞呢?例:關(guān)系模式R(S#,SD,MN),F=S#SD,SDMN分解一:1=R1(S#),R2(SD),R3(MN)不好!無(wú)法恢復(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),有損分解,無(wú)損分解,4.4關(guān)系模式的分解,2.無(wú)損連接性與依賴保持性對(duì)于R中任何一個(gè)關(guān)系r,R分解=R1,R2.RK無(wú)損連接性:r=R1(r)R2(r)RK(r)保持函數(shù)依賴:FR1(F)R2(F)RK(F)Ri(F)=X-Y|X-YF+XYRi,Ri所蘊(yùn)含的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)是無(wú)損連接分解。判斷2:FAB(F)AC(F)=A-B,A-C具有函數(shù)依賴保持性。,r,?=AB,BC,4.4關(guān)系模式的分解(自學(xué)),算法4.3無(wú)損連接性檢驗(yàn)。輸入:關(guān)系模式R(A1,A2,An),它的函數(shù)依賴集F,以及分解=R1,R2,Rk。輸出:確定是否具有無(wú)損連接性。方法:(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。(屬于用a代表,且位置信息用j表示;不屬于用b代表,且位置信息用ij表示。)(2)重復(fù)考察F中的每一個(gè)函數(shù)依賴,并修改表中的元素。其方法如下:取F中一個(gè)函數(shù)依賴XY,在X的分量中尋找相同的行,然后將這些行中Y的分量改為相同的符號(hào),如果其中有aj,則將bij改為aj;若其中無(wú)aj,則全部改為bij(i是這些行的行號(hào)最小值)。,4.4關(guān)系模式的分解,(3)如果發(fā)現(xiàn)表中某一行變成了al,a2,an,則分解具有無(wú)損連接性;如果F中所有函數(shù)依賴都不能再修改表中的內(nèi)容,且沒有發(fā)現(xiàn)這樣的行,則分解不具有無(wú)損連接性。,無(wú)損連接分解,示例一:U=A,B,C,D,E,F=ABC,CD,DE=(A,B,C),(C,D),(D,E),ABC,CD,DE,4.4關(guān)系模式的分解,示例二:U=A,B,C,D,E,F=AC,BC,CD,DEC,CEA=(A,D),(A,B),(B,E),(C,D,E),(A,E),AC,4.4關(guān)系模式的分解,BC,CD,4.4關(guān)系模式的分解,DEC,CEA,4.4關(guān)系模式的分解,定理4.12設(shè)=(R1,R2)是R的一個(gè)分解,F(xiàn)是R上的函數(shù)依賴集,分解具有無(wú)損連接性的充分必要條件是:R1R2(R1-R2)F+或R1R2(R2-R1)F+證明:(1)充分性:設(shè)R1R2(R1-R2),按算法5.2可構(gòu)造出下表。表中省略了a和b的下標(biāo),這無(wú)關(guān)緊要。,只能用于判斷分解為2個(gè)子模式的情況。,4.4關(guān)系模式的分解,如果R1R2(R1-R2)在F中,則可將表中第2行位于(R1-R2)列中的所有符號(hào)都改為a,這樣該表中第2行就全是a了,則具有無(wú)損連接性。同理可證R1R2(R2-R1)的情況。如果R1R2(R1-R2)不在F中,但在F+中,即它可以用公理從F中推出來(lái),從而也能推出R1R2Ax,其中AxR1-R2,所以可以將Ax列的第2行改為全a,同樣可以將R1-R2中的其他屬性的第2行也改為a,這樣第2行就變成全a行。所以分解=R1,R2具有無(wú)損連接性。同樣可以證明R1R2(R2-R1)的情況。(2)必要性:設(shè)構(gòu)造的表中有一行全為a,例如第1行全為a,則由函數(shù)依賴定義可知R1R2(R2-R1);如果是第2行全為a,則R1R2(R1-R2)。定理證畢。,4.4關(guān)系模式的分解,例:下列分解是否具有無(wú)損連接性和函數(shù)依賴保持性。已知:R(A,B,C)F=AB,CB(1)1=AB,BC(2)2=AC,BC,4.4關(guān)系模式的分解,(1)對(duì)1和F構(gòu)造表:,(2)檢查F=AB,CB對(duì)AB,A列中無(wú)相同的行;對(duì)CB,C列中無(wú)相同的行。1不具有無(wú)損連接性。,1=AB,BCF=AB,CB,4.4關(guān)系模式的分解,1=AB,BCF=AB,CB利用定理4.12解。R1R2=B(R1-R2)=AR1R2+(R1-R2)1不是無(wú)損連接分解。,4.4關(guān)系模式的分解,2=AC,BCF=AB,CB,對(duì)2和F構(gòu)造表:,檢查F=AB,CB對(duì)CB,C列有相同的行,改寫B(tài)列的相異符號(hào)為a,下標(biāo)為列號(hào)2。第一行變?yōu)閍1a2a3,2具有無(wú)損連接性。,4.4關(guān)系模式的分解,2=AC,BCF=AB,CB利用定理4.12解。R1R2=C(R1-R2)=A;(R2-R1)=B;R1R2+(R2-R1)2是無(wú)損連接分解。,4.4關(guān)系模式的分解,3.模式分解的方法3NF的保持無(wú)損連接及函數(shù)依賴的分解:設(shè):R1)對(duì)Fm中任一X-A,若XA=U則不分解,結(jié)束。2)若R中Z屬性在Fm中未出現(xiàn),則所有Z為一個(gè)子模式,令U=U-Z。3)對(duì)Fm中X-A1,.X-An,用合成規(guī)則合成一個(gè),再對(duì)Fm中每個(gè)X-A,令Ri=XA。4)R的分解為R1,R2,.RK,碼,依賴保持不需要;原包含有不需要。,4.4關(guān)系模式的分解,BCNF的保持無(wú)損連接的分解:(1)令=R;(2)如果中所有關(guān)系模式都是BCNF,則轉(zhuǎn)(4);(3)如果中有一個(gè)關(guān)系模式Ri不是BCNF,則Ri中必有XAFi+(AX),且X不是Ri的碼。設(shè)S1=XA,S2=Ui-A,用分解S1,S2代替Ri,轉(zhuǎn)(2);(4)分解結(jié)束,輸出。例:設(shè)R=A,B,C,D,F=AC,CA,BAC,DAC,BDA(1)將R分解為3NF且具有無(wú)損連接性和依賴保持性。(2)將R分解為BCNF且具有無(wú)損連接性。,關(guān)系模式的分解算法,示例:U=S#,SD,MN,C#,GF=S#SD,S#MN,SDMN,(S#,C#)GU1=S#,SD,F1=S#SDU2=S#,MN,C#,G,F2=S#MN,(S#,C#)GU1=S#,SD,F1=S#SDU2=S#,MN,F2=S#MNU3=S#,C#,G,F3=(S#,C#)G,4.4關(guān)系模式的分解,關(guān)系模式CTHRSG,其中C表示課程,T表示教師,H表示時(shí)間,R表示教室,S表示學(xué)生,G表示成績(jī)。函數(shù)依賴集F及其所反映的語(yǔ)義分別為:CT每門課程僅有一位教師擔(dān)任。HTR在任一時(shí)間,一個(gè)教師只能在一個(gè)教室上課。HRC在任一時(shí)間,每個(gè)教室只能上一門課。HSR在任一時(shí)間,每個(gè)學(xué)生只能在一個(gè)教室聽課。CSG每個(gè)學(xué)生學(xué)習(xí)一門課程只有一個(gè)成績(jī)。,4.4關(guān)系模式的分解,解:HSCTHRSG,HS是關(guān)系模式的關(guān)鍵字。,面向3NF且保持函數(shù)依賴的分解。最小函數(shù)依賴集為F=CT,CSG,HRC,HSR,THR分解為:CT,CSG,HRC,HSR,THR,面向3NF既有無(wú)損連接性又保持函數(shù)依賴的分解。HS是關(guān)鍵字,HS,HS是HSR的一個(gè)子集分解仍為:CT,CSG,HRC,HSR,THR,4.4關(guān)系模式的分解,面向BCNF且具有無(wú)損連接性的分解。,CTHRSGKey=HS,CSGKey=CSCSG,CTHRSKey=HSCT,THRHRC,HSR,CTKey=CCT,CHRSKey=HSCHR,HRCHSR,CHRKey=CH,HRCHR,HRC,CHSKey=HSHSC,4.5.多值依賴與第四范式4NF),例:學(xué)校中某一門課程由多個(gè)教師講授,他們使用相同的一套參考書。關(guān)系模式Teaching(C,T,B)課程C、教師T和參考書B,例:學(xué)校中某一門課程由多個(gè)教師講授,他們使用相同的一套參考書。關(guān)系模式Teaching(C,T,B)課程C、教師T和參考書B,4.5.多值依賴與第四范式4NF),4.5.多值依賴與第四范式4NF),TeachingBCNF:Teach具有唯一候選碼(C,T,B),即全碼Teaching模式中存在的問(wèn)題(1)數(shù)據(jù)冗余度大:有多少名任課教師,參考書就要存儲(chǔ)多少次(2)插入操作復(fù)雜:當(dāng)某一課程增加一名任課教師時(shí),該課程有多少本參照書,就必須插入多少個(gè)元組例如物理課增加一名教師劉關(guān),需要插入兩個(gè)元組:(物理,劉關(guān),普通物理學(xué))(物理,劉關(guān),光學(xué)原理),4.5.多值依賴與第四范式4NF),(3)刪除操作復(fù)雜:某一門課要去掉一本參考書,該課程有多少名教師,就必須刪除多少個(gè)元組(4)修改操作復(fù)雜:某一門課要修改一本參考書,該課程有多少名教師,就必須修改多少個(gè)元組產(chǎn)生原因存在多值依賴,4.5.多值依賴與第四范式4NF,第四范式:4NF定義4.10若R1NF,D是R上的依賴集,如果對(duì)于任何一個(gè)多值依賴XY(Y-X,XY沒有包含R的全部屬性),X都包含了R的一個(gè)候選關(guān)鍵詞,則R4NF。4NF必定是BCNF,但BCNF不一定是4NF。,4.5.多值依賴與第四范式4NF,在R(U)的任一關(guān)系r中,如果存在元組t,s使得tX=sX,那么就必然存在元組w,vr,(w,v可以與s,t相同),使得wX=vX=tX,而wY=tY,wZ=sZ,vY=sY,vZ=tZ(即交換s,t元組的Y值所得的兩個(gè)新元組必在r中),則Y多值依賴于X,記為XY。這里,X,Y是U的子集,Z=U-X-Y。txy1z2sxy2z1wxy1z1vxy2z2,4.5.多值依賴與第四范式4NF,平凡多值依賴和非平凡的多值依賴若XY,而Z,則稱XY為平凡的多值依賴否則稱XY為非平凡的多值依賴,4.5.多值依賴與第四范式4NF多值依賴的性質(zhì),(1)多值依賴具有對(duì)稱性若XY,則XZ,其中ZUXY多值依賴的對(duì)稱性可以用完全二分圖直觀地表示出來(lái)。(2)多值依賴具有傳遞性若XY,YZ,則XZ-Y,(3)函數(shù)依賴是多值依賴的特殊情況。若XY,則XY。(4)若XY,XZ,則XYZ。(5)若XY,XZ,則XYZ。(6)若XY,XZ,則XY-Z,XZ-Y。,4.5.多值依賴與第四范式4NF多值依賴與函數(shù)依賴的區(qū)別,(1)有效性多值依賴的有效性與屬性集的范圍有關(guān)若XY在U上成立,則在W(XYWU)上一定成立;反之則不然,即XY在W(WU)上成立,在U上并不一定成立多值依賴的定義中不僅涉及屬性組X和Y,而且涉及U中其余屬性Z。一般地,在R(U)上若有XY在W(WU)上成立,則稱XY為R(U)的嵌入型多值依賴,只要在R(U)的任何一個(gè)關(guān)系r中,元組在X和Y上的值滿足定義5.l(函數(shù)依賴),則函數(shù)依賴XY在任何屬性集W(XYWU)上成立。(2)若函數(shù)依賴XY在R(U)上成立,則對(duì)于任何YY均有XY成立多值依賴XY若在R(U)上成立,不能斷言對(duì)于任何YY有XY成立,4.5.多值依賴與第四范式4NF,例:Teach(C,T,B)4NF存在非平凡的多值依賴CT,且C不是候選碼用投影分解法把Teach分解為如下兩個(gè)關(guān)系模式:CT(C,T)4NFCB(C,B)4NFCT,CB是平凡多值依賴,4.5.多值依賴與第四范式4NF,定理4.3如果關(guān)系模式R4NF,則R必為BCNF。證明:用反證法。設(shè)R4NF,但RBCNF,則R中必有某個(gè)函數(shù)依賴XY(Y不包含于X),且X不包含R的侯選碼。由多值依賴公理可知,若XY,則XY,而此時(shí)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且具有無(wú)損連接性的分解。,關(guān)系模式R中存在多值依賴CHR,THR,顯然由于C或T都不含該關(guān)系模式的碼HS,R4NF。選擇CHR將它分解為CHR和CTSG;再將CTSG分解為CT和CSG。關(guān)系模式CTHRSG最后無(wú)損地分解為CHR、CT和CSG,其中每一個(gè)關(guān)系模式都屬于4NF。,4.6規(guī)范化的問(wèn)題,1.規(guī)范化的優(yōu)缺點(diǎn)關(guān)系模式的分解會(huì)降低查詢的效率。所討論的關(guān)系規(guī)范化是基于泛關(guān)系假設(shè)的,即只基于一個(gè)關(guān)系模式的規(guī)范化。但現(xiàn)實(shí)并不一定滿足。2.反規(guī)范化的設(shè)計(jì)對(duì)一些特定的應(yīng)用不規(guī)范化,而是通過(guò)使用冗余來(lái)改進(jìn)性能。例:account(帳號(hào),支行名,余額)depositor(客戶名,帳號(hào))每次訪問(wèn)帳戶時(shí),帳戶持有者的名字都與帳戶密碼和余額一起顯示。,4.6規(guī)范化的問(wèn)題,并不是規(guī)范化程度越高越好。例:earnings(公司號(hào),年份,數(shù)量)若設(shè)計(jì)成:(1)使用多個(gè)關(guān)系,每年建一個(gè)表。不好?。ㄊ荁CNF)(2)使用一個(gè)關(guān)系:company_year(公司號(hào),收入_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.模式分解的概念、方法,- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
14.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 關(guān)系數(shù)據(jù)理論 關(guān)系 數(shù)據(jù) 理論 PPT 課件
鏈接地址:http://www.szxfmmzy.com/p-11501959.html