kc第8講數(shù)據(jù)庫規(guī)范化理論.ppt

1、第8講: (第7章) 關(guān)系數(shù)據(jù)庫設(shè)計(jì)：規(guī)范化理論(一) 重慶大學(xué)計(jì)算機(jī)學(xué)院,課程名稱: 數(shù)據(jù)庫系統(tǒng) -,第8講：關(guān)系數(shù)據(jù)庫設(shè)計(jì)：規(guī)范化理論(一),項(xiàng)目驅(qū)動(dòng)目標(biāo)： 如何得到一個(gè)優(yōu)化的關(guān)系數(shù)據(jù)庫結(jié)構(gòu)！ 一、良好關(guān)系模式的標(biāo)準(zhǔn) 二、第一范式(1NF) 三、函數(shù)依賴 四、巴赫范式while (changes to result) dofor each in F dobeginif result then result := result end 例子：計(jì)算屬性集的閉包,5.2 屬性集的閉包,5-6 什么是屬性集的閉包？,5-7 如何計(jì)算a+？,問題7答案,Example of Attribute Se

2、t Closure,R = (A, B, C, G, H, I) F = A BA C CG HCG IB H (AG)+ 1.result = AG 2.result = ABCG(A C and A B) 3.result = ABCGH(CG H and CG AGBC) 4.result = ABCGHI(CG I and CG AGBCH) Is AG a candidate key? Is AG a super key? Does AG R? = Is (AG)+ R Is any subset of AG a superkey? Does A R? = Is (A)+ R Doe

3、s G R? = Is (G)+ R,5.2 屬性集的閉包,Uses of Attribute Closure,There are several uses of the attribute closure algorithm: 判定超鍵：Testing for superkey: To test if is a superkey, we compute +, and check if + contains all attributes of R. 判定函數(shù)依賴：Testing functional dependencies To check if a functional dependenc

4、y holds (or, in other words, is in F+), just check if +. That is, we compute + by using attribute closure, and then check if it contains . Is a simple and cheap test, and very useful 計(jì)算F+：Computing closure of F For each屬性集 R, we find the closure +, and for each S +, we output a functional dependency

5、 S.,5.2 屬性集的閉包,5-8 屬性集閉包有何用途？,Canonical Cover-要求,三大冗余現(xiàn)象：Sets of functional dependencies may have redundant dependencies that can be inferred from the others 依賴冗余現(xiàn)象：For example: A C is redundant in: A B, B C Parts of a functional dependency may be redundant 右方冗余現(xiàn)象：E.g.: on RHS: A B, B C, A CD can be

6、simplified to A B, B C, A D 左方冗余現(xiàn)象：E.g.: on LHS: A B, B C, AC D can be simplified to A B, B C, A D 正則覆蓋的直觀要求：Intuitively, a canonical cover of F is a “minimal” set of functional dependencies equivalent to F, having no redundant dependencies or redundant parts of dependencies (冗余屬性) (除不要求右方單屬性外，等效于：1

7、數(shù)據(jù)庫原理王能斌，p.380,最小函數(shù)依賴集概念),5.3 正則覆蓋,5-9 什么是正則覆蓋？,返 回,Extraneous多余 Attributes,Consider a set F of functional dependencies and the functional dependency in F. Attribute A is extraneous in if A and F logically implies (F ) ( A) . Attribute A is extraneous in if A and the set of functional dependencies (

8、F ) ( A) logically implies F. Note: implication in the opposite direction is trivial微不足道的 in each of the cases above, since a “stronger” functional dependency always implies a weaker one. 即上述左、右方是相互蘊(yùn)含的(等價(jià)的)! (學(xué)生作業(yè)) Example: Given F = A C, AB C B is extraneous in AB C because A C, AB C logically impl

9、ies A C (I.e. the result of dropping B from AB C). Example: Given F = A C, AB CD C is extraneous in AB CD since AB C can be inferred even after deleting C,5.3 正則覆蓋,5-10 正則覆蓋中的冗余屬性指什么？,Testing if an Attribute is Extraneous,Consider a set F of functional dependencies and the functional dependency in F

10、. 左方冗余屬性的判定：To test if attribute A is extraneous in compute ( A)+ using the dependencies in F check that ( A)+ contains ; if it does, A is extraneous in 右方冗余屬性的判定： To test if attribute A is extraneous in compute + using only the dependencies in F = (F ) ( A), check that + contains A; if it does, A i

11、s extraneous in ,5.3 正則覆蓋,5-11 如何判定是否存在冗余屬性？,Canonical Cover-定義及計(jì)算,形式化定義：A canonical cover for F is a set of dependencies Fc such that F logically implies all dependencies in Fc, and Fc logically implies all dependencies in F, and No functional dependency in Fc contains an extraneous attribute, and

12、Each left side of functional dependency in Fc is unique. Having no redundant dependencies (注：書中沒有這一條!) To compute a canonical cover for F:repeatUse the union rule to replace any dependencies in F 1 1 and 1 2 with 1 1 2 Find a functional dependency with an extraneous attribute either in or in If an e

13、xtraneous attribute is found, delete it from until F does not change Note: Union rule may become applicable after some extraneous attributes have been deleted, so it has to be re-applied 例子：計(jì)算正則覆蓋,5.3 正則覆蓋,5-12 如何計(jì)算函數(shù)依賴集的正則覆蓋？,Computing a Canonical Cover-例子,R = (A, B, C)F = A BC B C A BAB C Combine

14、A BC and A B into A BC Set is now A BC, B C, AB C A is extraneous in AB C Check if the result of deleting A from AB C is implied by the other dependencies Yes: in fact, B C is already present! Set is now A BC, B C C is extraneous in A BC Check if A C is logically implied by A B and the other depende

15、ncies Yes: using transitivity on A B and B C. Can use attribute closure of A in more complex cases The canonical cover is: A BB C,5.3 正則覆蓋,Lossless-join Decomposition,形式化定義：For the case of R = (R1, R2), we require that for all possible relations r on schema R （注：多個(gè)模式分解類似） r = R1 (r ) R2 (r ) 充分必要條件(

16、僅一分為二情形)：A decomposition of R into R1 and R2 is lossless join if and only if at least one of the following dependencies is in F+: R1 R2 R1 R1 R2 R2 例子：無損連接分解(一分為二情形),5.4 無損連接分解與依賴保持,5-12 什么叫無損連接分解？,Example-無損連接分解,R = (A, B, C)F = A B, B C Can be decomposed in two different ways 分解方式一：R1 = (A, B), F1

17、= A B; R2 = (B, C), F1= B C Lossless-join decomposition: R1 R2 = B and B BC即 R1 R2 R2 Dependency preserving 分解方式二：R1 = (A, B) , F1= A B; R2 = (A, C), F1= A C Lossless-join decomposition: R1 R2 = A and A AB即 R1 R2 R1 Not dependency preserving (cannot check B C without computing R1 R2),5.4 無損連接分解與依賴保持

18、,Dependency Preservation,形式化定義：Let Fi be the set of dependencies F + that include only attributes in Ri. A decomposition is dependency preserving, if (F1 F2 Fn )+ = F + 依賴不保持的缺點(diǎn)：If it is not, then checking updates 數(shù)據(jù)更新 for violation of functional dependencies may require computing joins, which is ex

19、pensive.,5.4 無損連接分解與依賴保持,5-13 什么叫依賴保持？,5-14 依賴不保持的分解有何不足？,Testing for Dependency Preservation,計(jì)算方法： To check if a dependency is preserved in a decomposition of R into R1, R2, , Rn we apply the following test (with attribute closure done with respect to F) result = while (changes to result) dofor eac

20、h Ri in the decomposition 根據(jù)各子模式上的函數(shù)依賴判定決定屬性集t = (result Ri)+ Riresult = result t If result contains all attributes in , then the functional dependency is preserved. We apply the test on all dependencies in F to check if a decomposition is dependency preserving 效率：This procedure takes polynomial tim

21、e, instead of the exponential time required to compute F+ and (F1 F2 Fn)+ 例子：判定依賴保持,5.4 無損連接分解與依賴保持,5-15 如何檢查分解是否保持依賴？,Example-判定保持依賴,R = (A, B, C )F = A B B C Key = A R is not in BCNF Decomposition R1 = (A, B) F1 = A B R2 = (B, C) F2 = B C R1 and R2 is in BCNF Lossless-join decomposition Dependency

22、 preserving A B, B C顯然屬于(F1 F2 )+ 判定 A C 是否屬于(F1 F2 )+ 最初：result = =A 然后： t = (result R1)+ R1 = A+ A,B = A,B result = A,B 最終： t = (result R2)+ R2 = B+ B,C = B,C result = A,B,C 可見C屬于屬性集result中, 故為依賴保持的分解！,5.4 無損連接分解與依賴保持,假設(shè)F還有 A C,項(xiàng)目驅(qū)動(dòng)目標(biāo)： 關(guān)系數(shù)據(jù)庫優(yōu)化設(shè)計(jì)有哪些有效的實(shí)現(xiàn)途徑： 一、實(shí)用的范式分解算法 二、多值依賴與4NF知識 三、關(guān)系模式設(shè)計(jì)注意事項(xiàng) 四、觸發(fā)器及其用途 主要討論問題： 是否總可無損分解為一組BCNF？ 是否總可保持依賴分解為一組3NF？ 可否實(shí)現(xiàn)雙保持的分解？ 什么是多值依賴？ 什么是4NF？ 如何分解為4NF？ 關(guān)系模