數(shù)據(jù)庫(kù)系統(tǒng)課件：ch7 Relational Database Design (2)

1、Chapter 7: Relational Database Design (2)關(guān)系模式的分解和問(wèn)題SCD(SNO,SN,AGE,DEPT,MN,CNO,SCORE)S(SNO,SN,AGE,DEPT)SC(SNO,CNO,SCORE)D(DEPT,MN)我們可以通過(guò)把一個(gè)關(guān)系模式的分解成多個(gè)關(guān)系模式，以解決它的插入、刪除和更新操作所帶來(lái)的一些問(wèn)題。為了在分解要保證原來(lái)模式所滿足的特性，要求分解處理具有無(wú)損連接和保持函數(shù)依賴。模式的分解定義 關(guān)系模式R的一個(gè)分解：= R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，F(xiàn)i 為 F在 Ui 上的投影模式的分解SnoSdeptSloc95

2、001CSA95002ISB95003MAC95004ISB95005PHB模式的分解SnoSdeptSloc95001CSA95002ISB95003MAC95004ISB95005PHB1. SL分解為下面三個(gè)關(guān)系模式： SN(Sno) SD(Sdept) SO(Sloc)分解后的關(guān)系為：Sno9500195002950039500495005分解后的數(shù)據(jù)庫(kù)丟失了許多信息。例如無(wú)法查詢95001學(xué)生所在學(xué)院或所在宿舍。 如果分解后的關(guān)系可以通過(guò)自然連接恢復(fù)為原來(lái)的關(guān)系，那么這種分解就沒(méi)有丟失信息。SdeptCSISMAPHSlocABC模式的分解SnoSdeptSloc95001CSA95

3、002ISB95003MAC95004ISB95005PHB2. SL分解為下面二個(gè)關(guān)系模式： NL(Sno, Sloc) DL(Sdept, Sloc)分解后的關(guān)系為：SnoSloc95001A95002B95003C95004B95005BSdeptSlocCSAISBMACPHB模式的分解NL DLNL DL比原來(lái)的SL關(guān)系多了3個(gè)元組無(wú)法知道95002、95004、95005究竟是哪個(gè)學(xué)院的學(xué)生元組增加了，信息丟失了SnoSlocSdept95001ACS95002BIS95002BPH95003CMA95004BIS95004BPH95005BIS95005BPH模式的分解3. 將S

4、L分解為下面二個(gè)關(guān)系模式： ND(Sno, Sdept) NL(Sno, Sloc) 分解后的關(guān)系為：SnoSdeptSloc95001CSA95002ISB95003MAC95004ISB95005PHBSnoSdept95001CS95002IS95003MA95004IS95005PHSnoSloc95001A95002B95003C95004B95005BSnoSdeptSloc95001CSA95002ISB95003MAC95004ISB95005PHB信息沒(méi)有丟失關(guān)系模式分解的標(biāo)準(zhǔn)三種模式分解的等價(jià)定義 分解具有無(wú)損連接性 分解要保持函數(shù)依賴 分解既要保持函數(shù)依賴，又要具有無(wú)損連

5、接性具有無(wú)損連接性的模式分解關(guān)系模式R的一個(gè)分解 = R1，R2， ，Rn若R與R1、R2、Rn自然連接的結(jié)果相等，則稱關(guān)系模式R的這個(gè)分解具有無(wú)損連接性(Lossless join)具有無(wú)損連接性的分解保證不丟失信息無(wú)損連接性不一定能解決插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問(wèn)題模式分解中存在的問(wèn)題R(A, B, C)ABC112221AB1122BC1221ABC112221AB(R)BC(R)AB(R)BC(R)R(A, B, C)ABC111212AB1121BC1112ABC111112211212AB(R)BC(R)AB(R)BC(R)有損分解無(wú)損分解定理如果R的分解為R1,R2

6、，F(xiàn)為R上的函數(shù)依賴集合，分解具有無(wú)損連接性的充分必要條件為： R1 R2 (R1-R2)或 R1 R2 (R2-R1)兩個(gè)模式的公共屬性可以函數(shù)確定其中一個(gè)模式舉例：設(shè)R=, U=ABC,F=AB,證明1R1(AB), R2(AC) 是無(wú)損連接，2R1(AB),R3(BC)不是無(wú)損連接。解：1=R1(AB), R2(AC)R1R2 = A, R1R2 = B由A B ，得到1是無(wú)損連接分解2=R1(AB), R2(BC)R1R2 = B, R1R2 = A, R2R1 = CBA, BC均不成立，所以1不是無(wú)損連接分解保持函數(shù)依賴的分解保持關(guān)系模式分解等價(jià)的另一個(gè)重要條件是關(guān)系模式的函數(shù)依賴

7、集在分解后仍在數(shù)據(jù)庫(kù)模式中保持不變。即關(guān)系模式R 到=R1,R2Rk的分解，應(yīng)使函數(shù)依賴集F，被F在這些Ri上的投影蘊(yùn)涵保持函數(shù)依賴的模式分解設(shè)關(guān)系模式R被分解為若干個(gè)關(guān)系模式R1，R2，Rn (其中U=U1U2Un，且不存在Ui Uj，F(xiàn)i為F在Ui上的投影)，若F所邏輯蘊(yùn)含的函數(shù)依賴一定也由分解得到的某個(gè)關(guān)系模式中的函數(shù)依賴Fi所邏輯蘊(yùn)含，則稱關(guān)系模式R的這個(gè)分解是保持函數(shù)依賴的(Preserve dependency)。保持函數(shù)依賴的分解保持函數(shù)依賴的模式分解Z是U的子集，函數(shù)依賴集合F在Z上的投影定義為Z(F) = XY | XYF+ XY Z設(shè) = R1, R2, , Rn是關(guān)系模式

8、R的一個(gè)分解，如果F+ = ( Ri(F)+，則稱是保持函數(shù)依賴的分解保持函數(shù)依賴的分解如何判斷分解保持函數(shù)依賴？回憶： F+ = ( Fi)+ F ( Fi )+， Fi F+如對(duì)于ABC，AB , BC的分解，思考：BC AB，AC+ ?檢驗(yàn)：C ？模式的分解如果一個(gè)分解具有無(wú)損連接性，則它能夠保證不丟失信息。如果一個(gè)分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況。分解具有無(wú)損連接性和分解保持函數(shù)依賴是兩個(gè)互相獨(dú)立的標(biāo)準(zhǔn)。具有無(wú)損連接性的分解不一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一定具有無(wú)損連接性。保持函數(shù)依賴的分解關(guān)系模式RU = CITY, ST, ZIP,F = (

9、CITY, ST) ZIP, ZIP CITY = R1 = ST, ZIP, R2 = CITY, ZIPR1R2 =ZIP, R2R1 =CITY R1R2 R2R1 分解是無(wú)損的R1(F) = ， R2(F) = ZIP CITYR1(F) R2(F) = ZIP CITY丟失了函數(shù)依賴(CITY, ST) ZIP練習(xí)分析下列分解是否具有無(wú)損連接和保持FD的特點(diǎn)。1、R(ABC),F=CA, =AC,BC2、R(ABC),F=CB,AB, =AC,BC3、R(ABC),F=CA, =AB,AC4、R(ABC),F=CA,BC, =AB,AC1、無(wú)損，保持FD2、無(wú)損，不保持FD,丟失AB

10、3、有損分解，保持FD4、有損，不保持FD(丟失BC)F在AB,AC, BD,CD上的投影分別為AB,AC,DC丟失了BC,AD,所以此分解不保持FD題目：設(shè)關(guān)系模式R(A,B,C,D)F是R上成立的FD集，F(xiàn)=AB,BC,AD,DC, =AB,AC,BD,CD是R的一個(gè)分解。1、試求F在的每個(gè)模式上的投影？2、保持FD嗎？為什么？不良的模式設(shè)計(jì)不良的數(shù)據(jù)依賴范式范式的判定模式分解各種異常部分函數(shù)依賴、傳遞函數(shù)依賴、多值依賴1NF、2NF、3NF、BCNF、4NFArmstrong公理、屬性集的閉包、函數(shù)依賴的推導(dǎo)、候選碼的計(jì)算、函數(shù)依賴集的等價(jià)和最小覆蓋、模式分解的定義、保持函數(shù)依賴分解和保

11、持無(wú)損連接分解的判定和分解算法良好的模式設(shè)計(jì)范式定義范式是對(duì)關(guān)系的不同數(shù)據(jù)依賴程度的要求通過(guò)模式分解將一個(gè)低級(jí)范式轉(zhuǎn)換為若干個(gè)高級(jí)范式的過(guò)程稱作規(guī)范化（概念的純粹化）1NF2NF3NF4NFBCNF5NF1NF定義關(guān)系中每一分量不可再分。即不能以集合、序列等作為屬性值SNOCNOS1C1，C2，C3SNOCNOS1C1S1C2S1C31NF對(duì)象關(guān)系數(shù)據(jù)庫(kù)嵌套關(guān)系傳統(tǒng)數(shù)據(jù)庫(kù)平面關(guān)系1NFSNOCNOS1C1，C2，C3適合于查詢每個(gè)學(xué)生的選修課程SNOCNOS1, S2, S3C1適合于查詢每門課程的選修學(xué)生兩個(gè)都保存，數(shù)據(jù)冗余，更新困難只保存一個(gè)，某些查詢困難1NF原子粒度的選擇分量是否需要再

12、分，與具體應(yīng)用有關(guān)。如果用到值的一部分，則需要進(jìn)一步分割否則需要應(yīng)用編碼解析姓名生日王軍68.7.10張立69.7.10李明80.3.28姓名年月日王軍687.10張立697.10李明803.28只是查詢出生日期比較兩人生肖是否相同姓名年月日王軍68710張立69710李明80328比較兩人生日是否相同1NF較細(xì)的原子粒度有助于標(biāo)準(zhǔn)化，施加約束，避免輸入錯(cuò)誤，從而提高數(shù)據(jù)質(zhì)量北京大學(xué)，北京，中國(guó)，100871，11/25/2006中國(guó)，北京，北京大學(xué)，100871，25/11/2006國(guó)家城市單位郵編年月日中國(guó)北京北京大學(xué)100871200611252NFSNOSNSDDEANCNOGSNOS

13、NSDDEANCNOGS01楊明D01思齊C0190S02李婉D01思齊C0187S01楊明D01思齊C0292S03劉海D02述圣C0195S04安然D02述圣C0278S05樂(lè)天D03省身C01822NF不良特性插入異常：如果學(xué)生沒(méi)有選課，關(guān)于他的個(gè)人信息及所在系的信息就無(wú)法插入刪除異常：如果刪除學(xué)生的選課信息，則有關(guān)他的個(gè)人信息及所在系的信息也隨之刪除了更新異常：如果學(xué)生轉(zhuǎn)系，若他選修了k門課，則需要修改k次數(shù)據(jù)冗余：如果一個(gè)學(xué)生選修了k門課，則有關(guān)他的所在系的信息重復(fù)SNOSNSDDEANCNOG2NF定義若R1NF，且每個(gè)非主屬性完全依賴于R的每一個(gè)候選關(guān)鍵字 ，則稱R2NF消除非主

14、屬性對(duì)碼的部分依賴如S2NF，因?yàn)椋⊿NO，CNO） SN （SNO，CNO） SD2NF改造非主屬性有兩種，一種完全依賴于碼，一種部分依賴于碼。將S分解為：SC(SNO , CNO , G)S_SD(SNO, SN , SD , DEAN)快速熱身關(guān)系模式R（A，B，C，D），碼為AB，給出它的一個(gè)函數(shù)依賴集，使得R屬于1NF而不屬于2NF分解說(shuō)明一個(gè)1NF，但非2NF的關(guān)系總是可以被分解成為一組2NF的關(guān)系規(guī)范化過(guò)程中通過(guò)一組投影運(yùn)算消除部分依賴，建議作如下分解(第一步分解)已知關(guān)系R(A,B,C,D), (A,B)為主碼，即(A,B) C, (A,B) D，且A D, 則將R分解成為兩個(gè)

15、投影:R1(A,D), A為主碼R2(A,B,C), (A,B)為主碼，A為外碼這樣，R可以通過(guò)R1和R2的自然連接運(yùn)算得以恢復(fù)，即滿足分解的無(wú)損連接性3NFSNOSNSDDEANS01楊明D01思齊S02李婉D01思齊S03劉海D02述圣S04安然D02述圣S05樂(lè)天D03省身SNOCNOGS01C0190S02C0187S01C0292S03C0195S04C0278S05C0182SNOSNSDDEANSNOCNOG3NFS_SD(SNO , SN , SD , DEAN)不良特性插入異常：如果系中沒(méi)有學(xué)生，則有關(guān)系的信息就無(wú)法插入刪除異常：如果學(xué)生全部畢業(yè)了，則在刪除學(xué)生信息的同時(shí)有關(guān)

16、系的信息也隨之刪除了更新異常：如果學(xué)生轉(zhuǎn)系，不但要修改SD，還要修改DEAN，如果換系主任，則該系每個(gè)學(xué)生元組都要做相應(yīng)修改數(shù)據(jù)冗余：每個(gè)學(xué)生都存儲(chǔ)所在系的系主任的信息3NF定義關(guān)系模式R中，若不存在這樣的碼X，屬性組Y及非主屬性Z(Z Y)，使得下式成立，XY , YZ , YX則稱R3NF如果R的任何一個(gè)非主屬性都不傳遞依賴于它的任何一個(gè)侯選關(guān)鍵字，則稱R是第三范式，簡(jiǎn)記為3NF。 消除非主屬性對(duì)碼的傳遞依賴 如S_SD 3NF，因?yàn)橛蠸NOSD，SDDEAN3NF改造將S分解為STUDENT(SNO , SN , SD)DEPT(SD , DEAN)快速熱身關(guān)系模式R（A，B，C，D），

17、碼為AB，給出它的一個(gè)函數(shù)依賴集，使得R屬于2NF而不屬于3NFSNOSNSDS01楊明D01S02李婉D01S03劉海D02S04安然D02S05樂(lè)天D03SDDEAND01思齊D02述圣D03省身分解說(shuō)明一個(gè)2NF，但非3NF的關(guān)系總是可以被分解成為一組3NF的關(guān)系規(guī)范化過(guò)程中通過(guò)一組投影運(yùn)算消除傳遞依賴，建議作如下分解(第二步分解)已知關(guān)系R(A,B,C), A為主碼(A B, A C)，且 B C,則將R分解成為兩個(gè)投影:R1(B,C), B為主碼R2(A,B), A為主碼，B為外碼這樣，R可以通過(guò)R1和R2的自然連接運(yùn)算得以恢復(fù)，分解滿足分解的無(wú)損連接性BCNFCNOTNOSNOST

18、C(SNO , TNO , CNO)每位老師只教授一門課某學(xué)生選定一門課，就對(duì)應(yīng)一位老師STC 3NF ？TNO CNO(SNO，CNO) TNO候選碼(SNO，TNO) or (SNO，CNO)BCNFSNOTNOCNOs1t1c1s2t2c2s3t3c2s3t1c1BCNF不良特性插入異常：如果沒(méi)有學(xué)生選修某位老師的任課，則該老師擔(dān)任課程的信息就無(wú)法插入刪除異常：刪除學(xué)生選課信息，會(huì)刪除掉老師的任課信息更新異常：如果老師所教授的課程有所改動(dòng)，則所有選修該老師課程的學(xué)生元組都要做改動(dòng)數(shù)據(jù)冗余：每位學(xué)生都存儲(chǔ)了有關(guān)老師所教授的課程的信息癥由：TNO CNO，屬性對(duì)碼的不良依賴STC(SNO ,

19、 TNO , CNO)BCNF定義關(guān)系模式R中，對(duì)于屬性組X，Y，若XY且 Y X時(shí)X必含有碼，則RBCNF如STC BCNF，因?yàn)門NO CNO，而TNO不含有碼改造將S分解為(SNO，TNO)，(TNO，CNO)SNOTNOs1t1s2t2s3t3s3t1TNOCNOt1c1t2c2t3c2關(guān)系模式的分解算法算法：（達(dá)到BCNF無(wú)損連接分解算法）給定關(guān)系模式R ，令 = R檢查中各關(guān)系模式是否屬于BCNF，若是，則算法終止 設(shè) 中Ri不屬于BCNF，則存在函數(shù)依賴XA ，且X不是Ri的碼，則XA是Ri的真子集，將Ri分解為=S1，S1，其中US1 = XA， US2 = Ui A以代替Ri

20、 ，返回到志能總結(jié)：把不合格的兩個(gè)放到一個(gè)集合，再將推出者放回到原集合中關(guān)系模式的分解算法示例：R=，U=A，B，C，D，EF=AB，BC，(A,D)E ,求R的一個(gè)BCNF分解解：1. 求候選碼碼是AD2. 檢查AB，由于A不是碼，因此U1=A，B , F1=AB U2=A, C, D, E, F2=AC, (A,D)E3. 檢查AC，由于A不是碼，因此U1 = A, B, F1=AB U2 = A, C, F2=AC U3 = A, D, E, F3 = (A,D)E關(guān)系模式的分解算法示例：U=(SNO，TNO，CNO)F=(SNO，CNO)TNO, TNOCNO解：不屬于BCNF，分解為

21、U1=(SNO，TNO)，U2=(TNO，CNO)，F(xiàn)2=TNOCNO丟失了函數(shù)依賴(SNO，CNO)TNO，原來(lái)一個(gè)學(xué)生選修一門課程時(shí)，只能對(duì)應(yīng)一個(gè)老師；在新的關(guān)系模式下現(xiàn)在一個(gè)學(xué)生選修一門課程時(shí)，可能會(huì)對(duì)應(yīng)多個(gè)老師。關(guān)系分解為BCNF，不一定能保持函數(shù)依賴關(guān)系模式的分解算法結(jié)論：若要求分解保持函數(shù)依賴，那么分解后的模式總可以達(dá)到3NF，但不一定能達(dá)到BCNF算法：（達(dá)到3NF且保持函數(shù)依賴的分解）求F的最小覆蓋Fmin 找出不在Fmin中出現(xiàn)的屬性，將它們構(gòu)成一個(gè)關(guān)系模式，并從U中去掉它們(剩余屬性仍記為U)若有XA Fmin，且XA=U，則=R，算法終止關(guān)系模式的分解算法對(duì)Fmin按具有相同左部的原則進(jìn)行分組（設(shè)為k組），每一組函數(shù)依賴所涉及的屬性全體為Ui，令Fi為Fmin在Ui上的投影，則=R1 , , Rk是R的一個(gè)保持函數(shù)依賴的分解，并且每個(gè)Ri 3NFP-PROVINCE,C-CITY,S-STREET,Z-ZIP設(shè)有關(guān)系模式R(SNO, SN, P, C, S, Z)F=SNOSN, SNOP, SNOC, SNOS, SNOZ, P,C,SZ, ZP, Z C，試分解R為3NF。解：求F的最小覆蓋Fc=SNOSN,P,C,S, P,C,SZ, ZP,C根據(jù)上述算法，則分解為