1、規(guī)范化,規(guī)范化的必要性與重要性,規(guī)范化在整個數(shù)據(jù)庫設計知識結構中的位置 規(guī)劃化解決的問題,規(guī)范化在數(shù)據(jù)庫概要設計中的位置,概念模型的設計（E/R圖）,關系模型,關系模型規(guī)范化,模式定義，建立數(shù)據(jù)庫,一個異常模式設計,例：lending(branch_name,branch_city,asset(分支機構的資產(chǎn)額)，customer_name,loan_number,amount),這個設計的問題： 冗余： 修改異常：修改Branch_name的asset 插入異常：新增加一個分支機構 刪除異常：刪除 貸款號222,結論： lending關系模式不是一個好的模式。,“好”的模式： 不會發(fā)生插入異

2、常、刪除異常、更新異常， 數(shù)據(jù)冗余應盡可能少。 異常原因： 解決方法：,一個異常模式設計,由存在于模式中的某些數(shù)據(jù)依賴引起的,通過分解關系模式來消除其中不合適的數(shù)據(jù)依賴。,規(guī)范化理論正是用來改造關系模式，通過分解關系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。,函數(shù)依賴 多值依賴,重點內容,函數(shù)依賴 三種范式、BCNF范式 模式分解,函數(shù)依賴,1 函數(shù)依賴定義 2 用函數(shù)依賴解釋候選碼、超碼 3 函數(shù)依賴的等價性 4 函數(shù)依賴的推理規(guī)則 5 最小函數(shù)依賴集,1 函數(shù)依賴的定義,關系R上的函數(shù)依賴：如果R的兩個元組在屬性A1,A2,.An上一致（也就是說，兩

3、個元組在這些屬性相對應的各個分量具有相同的值），則它們在另一個屬性B上也應該是一致。 記作：A1 A2.An B,關系：描述實體、屬性、實體間的聯(lián)系。 從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個子集。,元組：關系中的每一行,屬性：關系中的每一列,分量：屬性在某個元組上的取值,函數(shù)依賴舉例,Movie(title,year,length,filmType, studioName,starName） Title year-length Title year - filmtype Title year - studioName 簡寫： title year - length filmt

4、ype studioName,函數(shù)依賴說明,強調：函數(shù)依賴是針對關系模式， 而不是特定的實例。,2 用函數(shù)依賴解釋候選碼、超碼,如果一個或多個屬性的集合A1,A2,.An滿足如下條件，就稱該集合為關系R的鍵碼。 1 這些屬性函數(shù)決定該關系的所有其他屬性。 2 A1,A2,.An的任何真子集都不能函數(shù)決定R的所有其他屬性。,鍵碼舉例,MovieStar(title,year,length,filmType,studioName,starName） 屬性組title,year,starName構成了Movie關系的鍵碼。 Title year starName-length filmType 必須

5、證明：title,year,starName的任何真子集都不能函數(shù)決定所有其他的屬性。,鍵碼舉例,首先：觀察title 和year不能決定starName，因為很多電影有多個影星。 year,starName也不是鍵碼，因為一個影星在同一年中可能出演多部電影，因此， year,starnametitle 不是函數(shù)依賴。 同樣title,starName也不是鍵碼。 從而確定了title, year,starName是最小的集合,關系的鍵碼（候選碼）,說明： 有時一個關系有多個鍵碼（候選碼），這樣的話，通常要指定其中一個為主鍵碼。,超鍵碼,包含鍵碼（候選碼）的屬性集稱為“超鍵碼 superkey

6、”,即鍵碼的超集（superset of a key）。 鍵碼和超鍵碼的關系： 每個鍵碼都是超鍵碼 但是，某個超鍵碼不是（最小的）鍵碼 超鍵碼滿足鍵碼的第一個條件，但是不一定滿足鍵碼的第二個條件。,尋找關系的鍵碼,判斷鍵碼的第一條規(guī)則：來自實體集的關系的鍵碼就是該實體集或類的鍵碼屬性。 例：Movie(title,year,length,filmtype) Stars(name,address),尋找關系的鍵碼,第二條規(guī)則：如果關系R來自一個聯(lián)系，則該聯(lián)系的多樣性將會影響R的鍵碼。有三種情況： l 如果聯(lián)系是“多對多”的，則相連的兩個實體集的鍵碼都是R 的鍵碼屬性。 l 如果是從實體集E1到實

7、體集E2的“多對一”聯(lián)系，那么實體集E1的鍵碼屬性是R的鍵碼屬性，而E2的鍵碼屬性則不是R的鍵碼屬性。 l 如果聯(lián)系是“一對一”的，則聯(lián)系兩端的任何一個實體集的鍵碼屬性都是R的鍵碼屬性，即R的鍵碼屬性不是唯一的。,尋找關系的鍵碼,例： Movie(title,year,length,filmtype) 多 Studios(name,address) 一 Owns(title,year,studioName) Movie 與 Stars 多對多 Stars-in(主演) Stars-in(title,year,starName),尋找關系的鍵碼,多向聯(lián)系的情況： 如果多向聯(lián)系R有一個箭頭指向實體

8、集E，則相應的關系中，除了E的鍵碼以外，至少還存在一個鍵碼。,3 函數(shù)依賴的等價性,在不改變關系的合法實例集的條件下，函數(shù)依賴通?？梢杂脦追N不同的的方式來表示。如果滿足這種情況，我們就稱這樣的函數(shù)依賴集是等價的（equivalent）。 對于函數(shù)依賴集T，S，如果滿足T中所有依賴的每個關系實例都滿足S中的所有依賴，稱函數(shù)依賴集S“蘊含于 follow from”函數(shù)依賴集T. 如果S蘊含于T，同時T也蘊含于S，則S和T兩個函數(shù)依賴是等價的。,4 函數(shù)依賴的規(guī)則,分解/合并規(guī)則： 平凡依賴規(guī)則： 計算屬性的閉包： 傳遞規(guī)則： 函數(shù)依賴的閉包：,分解/合并規(guī)則,如果一組屬性A1,A2,.An 函數(shù)

9、決定了多個屬性，比方說： A1A2.An B1 A1A,.An B2 . A,A,.An Bm 可以把這一組依賴關系簡記為： A1A2.An B1,B2,Bm,分解/合并規(guī)則,反過來： 可以把依賴關系： A1A2.An B1,B2,Bm 分解為下列多個函數(shù)依賴： A1A2.An B1 A1A,.An B2 . A,A,.An Bm 兩種情況下，新的依賴集等價于舊的依賴集。 這個等價關系用于兩個方向：分解/合并,分解/合并規(guī)則證明,已知各個單個依賴，證明合并后是成立的 已知合并后的依賴，證明分解后是成立的 既：證明了它們互相蘊含，因此是等價的,平凡依賴概念,對于依賴：A1A2.An B1,B2,

10、Bm： 如果B是A 的子集，則稱依賴為平凡依賴的 如果B中至少有一個屬性不在A 中，則稱該依賴為非平凡依賴的。 如果B中沒有一個屬性在A中，則稱該依賴為完全非平凡依賴的。 例：平凡依賴 title,year-title 恒真,平凡依賴規(guī)則,函數(shù)依賴A1A2.An B1,B2,Bm 等價于A1A2.An C1,C2,Ck ,其中C是B的子集，但屬性C不在A中出現(xiàn)。,傳遞規(guī)則,傳遞規(guī)則使我們級聯(lián)兩個函數(shù)依賴。 如果A1A2.An -B1B2.Bm 和 B1B2.Bm C1C2.Ck在關系R中成立，則A1A2.AnC1C2.Ck在R中也成立。,例326 ：,已知關系R擁有屬性A,B和C，它滿足如下函

11、數(shù)依賴：A-B和B-C， 則可以推斷出R滿足A-C。 分析：,考察R的任意兩個在屬性A上取值一致的元組，證明它們在屬性C上也取得一致。,證明傳遞規(guī)則,假設：存在在屬性A上取值一致的元組（a,b1,c1,）和（a,b2,c2）。 對應的屬性是A,B,C。 滿足：A-B,B-C。 由于A-B, 所以： b1= b2 又由于B-C， 所以：c1 =c2 結論：A-C,傳遞規(guī)則,關系模式：Movie(title,year,length,filmType,studioName,studioAddr) 下面兩個依賴成立： title year-studioName studioName- studioAd

12、dr 根據(jù)傳遞規(guī)則，可以得到一個新的依賴： title year - studioAddr,計算屬性的閉包,定義： 假設 A1,A2,.,An 是屬性集， S 是函數(shù)依賴集。 屬性集A1,A2,.,An 在依賴集S下的閉包是這樣的屬性集B， 它使得滿足依賴集S中的所有依賴的每個關系也都滿足A1A2.An B。也就是說A1A2.An B蘊含于S中的函數(shù)依賴。 用 A1,A2,.,An + 來表示屬性集A1A2.An的閉包。,計算屬性的閉包,求閉包的過程： 從給定的屬性集出發(fā)，一旦包含了某函數(shù)依賴左邊的屬性，就把其右邊的屬性增加進來，這樣不斷地擴展該集合。最終，當該集合再也無法擴展時，得到的結果就

13、是閉包。,計算屬性的閉包,求解屬性集 A1,A2,.,An 在某函數(shù)依賴集下的閉包的算法的詳細描述： 1 設屬性集X最終將成為閉包。首先將X初始化為 A1,A2,.,An 。 2 然后，重復地搜索某個函數(shù)依賴B 1B2.Bm C,使得所有的B 1B2.Bm都在屬性集X中，但C不在其中。于是將C加到屬性集X中。 3 根據(jù)需要多次重復步驟2，直到?jīng)]有屬性能加到X中。 4 最后得到的不能再增加的屬性集X就是 A1,A2,.,An + 的正確值。,計算屬性的閉包,例：某個關系，具有屬性：A,B,C,D,E,F。假設該關系有如下的函數(shù)依賴： AB-C BC-AD D-E CF-B 問AB的閉包是什么，即

14、A,B + ？,計算屬性的閉包,求解： 初始化X: X=A,B 從AB-C, A,B都在X中，將C加入。因此X=A,B,C 從BC-AD, B，C都在X中，將A,D加入，因此 X=A,B,C,D 從D-E, D都在X中，將E加入，因此 X=A,B,C,D,E 從CF-B, 由于F不在X中，不能加入。 A,B +=A,B,C,D,E,證明閉包算法的有效性：,假設 A1,A2,.,An 是屬性集， S 是函數(shù)依賴集。 初始：X=A1,A2,.,An 最終要證明：A1A2.An- X D,證明閉包算法的有效性,假設已經(jīng)得到了：X包含 B 1B2.Bm , 準備利用依賴集S 上的一個依賴B 1B2.B

15、m D,將D加入到X中 可以肯定函數(shù)依賴：A1A2.An-X, 只需要證明A1A2.An-D ，則可以證明A1A2.An- X D 由于X包含了 B 1B2.Bm ，根據(jù)分解規(guī)則： A1A2,.An-B 1 A1A2.An-B2 . A1A2.An-Bm 再合并，可以得到：A1A2.An-B 1B2.Bm。 已知B 1B2.Bm D根據(jù)傳遞規(guī)則：滿足A1,A2,.,An-D.,檢驗給定的任一函數(shù)依賴A1A2.An B是否蘊含于依賴集S,分析： 根據(jù)屬性集閉包的定義， 可知A1A2.An A1,A2,.,An + 蘊含于S。 只要證明B在 A1,A2,.,An + 中，那么函數(shù)依賴A1A2.An

16、 B 肯定蘊含于依賴集S中。,檢驗給定的任一函數(shù)依賴A1A2.An B是否蘊含于依賴集S,求解過程： （1） 利用依賴集計算閉包 （2） 如果B在閉包中，則函數(shù)依賴A1A2.An B是否蘊含于依賴集S，否則不蘊含于s.,某個關系，具有屬性：A,B,C,D,E,F。假設該關系有如下的函數(shù)依賴： AB-C BC-AD D-E CF-B 檢驗AB-D是否蘊含于這些函數(shù)依賴中。 因為A,B +=A,B,C,D,E，D在集合中，所以AB-D蘊含于這些函數(shù)依賴中。,某個關系，具有屬性：A,B,C,D,E,F。假設該關系有如下的函數(shù)依賴： AB-C BC-AD D-E CF-B 檢驗依賴：D-A 是否蘊含于

17、這些函數(shù)依賴中 求閉包：D +=D,E ，所以，D-A 不蘊含于這些函數(shù)依賴中,Armstrong公理,自反律：如果 B1,B2,.,Bm包含于 A1,A2,.,An ,則A1A2.An- B1B2.Bm是平凡依賴 增長律：如果A1A2.An- B1B2.Bm，則對于任何屬性集C1C2.Ck, A1A2.AnC1CC2.Ck- B1B2.BmC1C2.Ck 傳遞律：如果A1A2.An- B1B2.Bm，且B1B2.Bm-C1C2.Ck，則A1A2.An- C1C2.Ck,偽傳遞律,若A-B， BC-D 則 AC-D,基的概念,基：任何一個能從中導出關系的所有依賴的給定依賴集稱為該關系的一個“基

18、”。 最小的基：如果一個基的任何真子集都不能推導出該關系的依賴全集，則稱此基為最小基。,基的概念舉例,例：關系R(A,B,C),其中每個屬性都決定其他兩個屬性。因此推導的依賴全集包括六個左、右各有一個屬性的依賴： A - B A-C B-A B-C C-A C-B 還有三個左邊有兩個屬性的非平凡依賴： AB-C AC-B BC-A 幾個最小的基：A-B,B-A,B-C,C-B A-B,B-C,C-A,函數(shù)依賴的閉包,給定函數(shù)依賴集F,可以證明其他某些函數(shù)依賴也成立，稱這些函數(shù)依賴被F蘊含。 令F為一個函數(shù)依賴集，F(xiàn)的閉包是指F邏輯蘊含的所有函數(shù)依賴的集合。記為F+,求函數(shù)依賴閉包的方法,求函數(shù)

19、依賴閉包的方法，基于三個公理（Armstrong公理）或稱函數(shù)依賴推理規(guī)則。通過反復使用這些規(guī)則，可以找出函數(shù)依賴集F的 F+,求函數(shù)依賴閉包,例：R=(A,B,C,G,H,I) 已知FA-B,A-C,CG-H,CG-I,B-H 堆導得出：F+ 的部分： A-H CG-HI AG-I,求函數(shù)依賴的閉包,問題：推導過程中可能會忽略某些依賴 一個求函數(shù)依賴的畢包的思路：逐一排查所有的可能的函數(shù)依賴，檢查是否可以推導得出。,求函數(shù)依賴的閉包,例：R=(A,B,C,G,H,I) 已知FA-B,A-C,CG-H,CG-I,B-H 求F+ ： 解： 考察左邊是單個屬性的依賴： A-H 考察左邊是兩個屬性的

20、依賴： AB-C AB -H AC-B AC-H AD-B AD-C AD-H AG-B AG-C AG-H AG-I AH-B AH-C AI-B AI-C AI-H BC-H BG-H BI-H CG-H CG-I 考察左邊是多了屬性的依賴：ABC ABG ABH ABI ACG ACH ACI AGH AGI AHI BCG BCH BCI BGH BGI CGH CGI GHI .,函數(shù)依賴的等價,如果函數(shù)依賴集E中的每一個函數(shù)依賴也在函數(shù)依賴集F的 F+ 中， 即E中的每一個依賴可以從F中推導得出，那么就稱E被F覆蓋，或者說F覆蓋(cover)E。如果E+ = F+ 的話，兩個函數(shù)依

21、賴集E ,F是等價（ equivalent）的。,如何確定F是否覆蓋E.,問題：如何確定F是否覆蓋E. 方法：對E中的每個函數(shù)依賴X-Y,計算X關于F的X+,然后檢查這個X+是否包含Y中的屬性。如果E中的每個函數(shù)都是X+ 包含Y中的屬性這種情況，那么F覆蓋E。,確定F是否覆蓋E,已知：R(A,B,C) F=A-B ,B-C,C-A E=B-A,A-C,C-A 確定F是否覆蓋E 解： 對于B-A ，在F當中求B+ =ABC,包含了A,也就是說B-A可以被F推導得出 對于A-C ，在F當中求A+ =ABC,包含了C,也就是說A-C可以被F推導得出 對于C-A ，在F當中求C+ =ABC,包含了A,

22、也就是說C-A可以被F推導得出 因此F覆蓋了E,最小函數(shù)依賴集（最小基）,滿足下列條件的函數(shù)依賴集F 是最小的： l F中每個依賴的右邊只含有單個屬性。 l 不能從F中刪除任何依賴。（不存在這樣的依賴，X-A, 使得F與F-X-A等價） l 不能用依賴Y-A來替換F中的任意一個依賴X-A,其中Y是X的一個真子集。（不存在這樣的依賴，X-A，Y是X 的真子集，使得F-X-A (Y-A) 與F等價） 最小函數(shù)依賴集，也就是F的最小基Fmin,定理：每一個函數(shù)依賴集F均等價于一個極小函數(shù)依賴集。,例,例：模式（A,B,C）,函數(shù)依賴集F： A-BC B-C A-B AB-C 計算F的最小函數(shù)依賴集：

23、,1 A-BC B-C A-B AB-C 逐一檢查F中的各個函數(shù)依賴，使用分解規(guī)則，將依賴右邊轉換為單個屬性 A-BC : A-B A-C 2 逐一檢查F中的各個函數(shù)依賴X-A, 令G=F-X-A,若A 屬于X關于 G的閉包，則從F中去掉此函數(shù)依賴。 檢查 A-C B-C A-B AB-C 3 逐一取出F中各個函數(shù)依賴X-A, 設X= B1B2.Bm ,逐一考察Bi ，若A 屬于（X-Bi） 在F上的閉包，則以X -Bi 取代X。 最后剩下的F就是極小依賴集。 B-C A-B,例,已知：R(A,B,C) F=A-B , B-A,B-C,A-C,C-A 計算最小函數(shù)依賴集 A-B, B-C, C

24、-A A-B,B-A,A-C,C-A,兩種方式使用函數(shù)依賴,1） 用于指明合法關系集上的約束。這樣就可以只考慮碼滿足給定函數(shù)依賴集的那些關系。如果希望只局限于模式R上滿足函數(shù)依賴集F的關系，我們說R上F成立 2） 用于檢測關系是否在給定函數(shù)依賴集上合法。如果關系 R在函數(shù)依賴集F上合法，則稱R 滿足函數(shù)依賴集F.,舉例,例：假如現(xiàn)有數(shù)據(jù)能夠反映關系的函數(shù)依賴，找出所有可能的函數(shù)依賴,函數(shù)依賴的規(guī)則,學習如何推導函數(shù)依賴。即，已經(jīng)知道某關系所滿足的函數(shù)依賴集，在不知道該關系具體元組的情況下，通常可以推斷出該關系必然滿足的其他某些函數(shù)依賴。,習題,關系R=(A,B,C,D,E) 函數(shù)依賴集F A-

25、BC CD-E B-D E-A 計算F的閉包 列出R的候選碼 計算B的閉包 計算最小覆蓋集,模式分解,一個異常模式設計,從E/ R到關系數(shù)據(jù)庫轉換時的問題：數(shù)據(jù)冗余,不能表示某些信息。 例：lending(branch_name,branch_city,asset(分支機構的資產(chǎn)額)，customer_name,loan_number,amount),這個設計的問題： 冗余： 修改異常：修改Branch_name的asset 刪除異常：刪除 貸款號222,異常設計的問題,已知函數(shù)依賴： Branch_name-branch_city 但是沒有函數(shù)依賴： Branch_name-Loan_num

26、ber 一個分支機構位于一個城市與一個分支機構貸了一筆款是兩個獨立的事實。 這個設計的另一個問題是不能直接表示有關一個分支機構的信息,消除異常,消除異常的一個可行的辦法：“分解”關系。 R的分解的方法：把R的屬性分開，以構成兩個新的關系模式?；驅 的元組進行投影，增加新關系。 如何選擇一個能消除異常的分解方法?,消除異常,將lending模式分解： 假如lending被分解成下列兩個模式： Branch_customer=(branch_name,branch_city,asset,customer_name) Customer_loan=(Customer_name,Loan_number

27、,ammout),消除異常,問題： 找出金額大于15元的貸款所有的分支機構 關系代數(shù)解決： branch_name(ammount15（branch_customercustomer_loan）),消除異常,結果: A, C兩家 更深入的結果：無法確定用戶從哪家分支結構貸了多少款，因此實際上是丟失了信息。稱Lending 到Branch_Customer和Customer_Loan的分解為有損分解，或者有損連接分解,消除異常,錯誤分析：為什么剛才的分解是有損的。 原因公共屬性：公共屬性：Customer_name。這樣表示信息有問題，因為一個客戶可能有多筆貸款，而這些貸款不一定來自同一個分支機

28、構。,消除異常,重新分解：Branch=(branch_name,branch_city,assets) Loan_Info=(branch_name,Customer_name,Loan_number,ammount) 分析：公共屬性：Branch_name branch_name-assets branch_city,模式分解,對于一個模式的分解是多種多樣的，但是分解后產(chǎn)生的模式應與原模式等價 具體的說就是： 分解具有 “無損連接性” LossLess join 分解要“保持函數(shù)依賴” Preserve dependency,模式分解,模式分解的評判標準：范式 規(guī)范化：一個低一級范式的關系

29、模式，通過模式分解可以轉換為若干個高一級范式的關系模式的集合，這種過程就叫做規(guī)范化。,范式,第一范式 第二范式 第三范式 BC范式 第四范式,第一范式,第一范式：first normal form (1NF) 規(guī)定屬性域只能是原子的（簡單的、不可分割的）值，且元組中任何屬性的值必須是一個來自于該屬性域的單個值。,第二范式,第二范式：每一個非主屬性，完全函數(shù)依賴于碼。 非主屬性：不是候選碼的成員 完全函數(shù)依賴：函數(shù)依賴X-Y是完全函數(shù)依賴的條件是：從X中移去任何屬性A就意味著依賴不再成立。,第三范式,傳遞依賴：關系模式R中的函數(shù)依賴X-Y是傳遞函數(shù)依賴（transitive functional

30、 dependency）的條件是屬性集Z既不是R的候選碼也不是R中任何碼的子集，且X-Z, Z-Y成立。 對于第三范式的理解：R中的每一個非主屬性，均滿足以下兩個條件： n 完全地函數(shù)依賴于 R 的每一個碼 n 非傳遞依賴于R 的每一個碼,BC范式,BC范式 （Boyee Codd Normal Form ）是由Boyce 與Codd提出的。 BCNF定義：當且僅當：只要非平凡依賴A1A2.An-B1B2.Bm 在關系R 中成立，則必然 A1,A2,.,An 是 R 的超鍵碼。滿足該條件的關系R就屬于BCNF。,分解為BCNF,給定一個模式為 A1,A2,.,An 的關系R，可以把R 分解成為

31、兩個關系S和T。模式分別為 B1,B2,.,Bm 和 C1,C2,.,CK ，使得： 1 A1,A2,.,An = B1,B2,.,Bm C1,C2,.,CK 2關系S中元組是R的所有元組在 B1,B2,.,Bm 上的投影。 1 關系T中元組是R的所有元組在 C1,C2,.,CK 上的投影。,一個存在異常的設計,如果關系Movie的鍵碼是title,year，則該關系不是BCNF，因為 title year -starName不成立。,消除異常,例：分解上表中的關系Movie。首先進行模式分解。我們選擇下面兩個關系： 1 一個關系稱為Movie1，其模式是除了starName以外的所有屬性。

32、2 另一個關系稱為Movie2，其模式是包括屬性title,year和starName.,消除異常,消除異常,分解結果中， Movie1(title, year, length, filmType, studioName) 屬于BCNF范式 title year - length filmType studioName,一個斷言,斷言：任何雙屬性關系都屬于BCNF。 可能的情形： 1.沒有非平凡函數(shù)依賴 2.A-B 3.B-A 4.A-B 和B-A,分解成BCNF,通過分解，可以把任何關系模式分解成若干個屬性子集，而這些子集有如下特性： 1 這些子集都屬于BCNF的關系模式 2 在某種意義上，

33、分解后關系中的數(shù)據(jù)如實地表示原始關系中的數(shù)據(jù)。,分解成BCNF,我們將要采取的分解策略是尋找一個違背BCNF的非平凡依賴： A1A2.An-B1B2.Bm 也就是說A1,A2,.,An 不是超鍵碼。 例：Movie(title,year,length,filmType,studioName,starName) 鍵碼：title, year, starName 一個BCNF違例：title year - length filmType studioName,分解成BCNF,根據(jù)這個違例分解Movie: 1. 包含了該依賴所有屬性的模式： title, year, length，filmType,

34、 studioName 2. 包含除了該依賴右邊的三個屬性之外的所有 Movie屬性的模式。因此，除去length, filmType和studioName,得到第二個模式： title, year, starName,分解成為BCNF舉例（1）,MovieStudiotitle, year, length,filmType, studioName, studioAddr 已知依賴集： title year - studioName studioName - studioAddr title year - length filmType 存在的問題： 數(shù)據(jù)可能出現(xiàn)冗余 傳遞依賴,分解成為BCN

35、F舉例（1）,(1)找到鍵碼 title , year 是一個鍵碼 (2) 一個違背BCNF的依賴。依賴studioName - studioAddr 是非平凡依賴。但是，它 studioName 并不是超鍵碼。所以，Moviestudio不屬于BCNF,分解成為BCNF舉例（1）,(3)分解： studioName,studioAddr title, year, length, filmType, studioName,分解成為BCNF舉例（2）,例：模式：title, year, studioName,president, presAddr 三個函數(shù)依賴： title year - stu

36、dioName studioName - president president - presAddr 該關系的唯一鍵碼：title, year 有兩個非平凡函數(shù)依賴違背了BCNF規(guī)則 所以不屬于BCNF,分解成為BCNF舉例（2）,應用依賴傳遞規(guī)則： studioName -presAddr 把兩個依賴和起來： studioName - president, presAddr 分解： title, year, studioName 屬于BCNF studioName,president, presAddr 不屬于BCNF,分解成為BCNF舉例（2）,因為，根據(jù) studioName - pr

37、esident, presAddr, 可以得出 studioName 是候選碼 而函數(shù)依賴：president - presAddr 違背了BCNF。 所以需要繼續(xù)分解： studioName, president president, presAddr,分解成為BCNF舉例（2）,最終分解結果： title, year, studioName studioName, president president, presAddr,分解為BCNF關系且具有無損連接性質的算法,已知：關系R和R上的函數(shù)依賴集F 1.令D:=R 2. While (D中有不屬于BCNF的關系模式Q時) do 選擇D中的

38、一個不屬于BCNF的關系模式Q； 在Q 中找出一個違背BCNF范式的函數(shù)依賴X-Y 把D中的Q用兩個關系模式（Q-Y）和(XY) ,關于分解的討論,函數(shù)依賴的投影 從分解中恢復信息,函數(shù)依賴的投影,找到分解得到的關系中成立的函數(shù)依賴 為什么要找分解得到的模式當中成立的函數(shù)依賴？ 目的：根據(jù)函數(shù)依賴，判斷分解得到的模式是否符合BCNF,函數(shù)依賴的投影,找到分解得到的關系中成立的函數(shù)依賴的方法： 假設把關系R分解為關系S和另一個關系。設F是已知的R中成立的依賴集。計算S中成立的函數(shù)依賴集的步驟是： 考慮包含于S的屬性集的每個屬性集X。計算X+ 。對于滿足下列條件的每個屬性B,函數(shù)依賴X-B在S中成

39、立： 1 B是S的一個屬性 2 B屬于X+ ，而且 3 B不屬于X。,函數(shù)依賴的投影,例：設R的模式為R（A,B,C,D）。給定的函數(shù)依賴集：A - B B -C 設S(A,C)是R經(jīng)過某種分解得到的一個關系。我們來計算S中成立的函數(shù)依賴。,函數(shù)依賴的投影,計算S的屬性集A,C的每個子集的閉包。 首先計算：A+ =A,B,C,由于B不在S中，而C在S中。所以斷言A-C成立。 計算C+ ：因為C不在已知依賴的左邊，所以，C+ =C,得不到任何依賴。 計算A,C+ ：=A,B,C ：AC-C A-C A-A C- C,函數(shù)依賴的投影,例：考慮R(A,B,C,D,E)分解為S(A,B,C)和另一個關

40、系。推導S的依賴。設 R的函數(shù)依賴為：A-D B-E 和 DE-C 首先，考慮A+ =A,D A-D 不是新的依賴B+ =B,E B - E不是新的依賴 C+ =C 沒有新的依賴 A,B+ =A,B,C,D,E 得出新的依賴：AB - C,從分解中恢復信息,討論： 考慮關系R，其模式為A,B,C 函數(shù)依賴：B-C是BCNF違例。 可能出現(xiàn)的情況之一：存在另一個依賴A-B,形成傳遞依賴。在這種情況下，A是唯一的鍵碼。 另一種可能出現(xiàn)的情形：B-C是唯一的非平凡依賴。在這種情況下，A,B是唯一的鍵碼。,從分解中恢復信息,上述兩種情況的可能分解結果是：A,B和（B,C） 設 t 是R的一個元組:T=

41、(a,b,c)。 t 在模式為 A,B的關系上的投影是：(a,b) t 在模式為 B,c的關系上的投影是：(b,c) 將這兩個投影連接起來，得到原來的t是可能的。,從分解中恢復信息,另一種情況： R的兩個元組：t=(a,b,c) v=(d,b,e) t 在模式為 A,B的關系上的投影是：(a,b) t 在模式為 B,c的關系上的投影是：(b,c) v 在模式為 A,B的關系上的投影是：(d,b) v 在模式為 B,c的關系上的投影是：(b,e) 連接得到了一個x=(a,b,e) 是原來的關系中不存在的元組,從分解中恢復信息,關于x的討論: 因為B-C, 所以，e=c,因此，結果仍然是x=(a,

42、b,c) 對上面討論的推廣： 對于A,B,C是屬性集的情況，上面的討論仍然成立。 結論： 如果我們按照前面介紹的方法進行分解，則以所有可能的方式對新關系的元組進行連接就可以準確地恢復原始關系。,從分解中恢復信息,如果不是基于一個函數(shù)依賴對關系進行分解：則可能無法恢復原始關系。 例： 假設關系R的模式為(A,B,C),這和上面一樣，但依賴B-C不成立。 R可能包含兩個元組：,從分解中恢復信息,R在模式為A,B和B,C的關系上的投影分別是：,從分解中恢復信息,無損分解,討論無損分解： 設R為關系模式，將R分解為關系模式集 R1R2.Rn R= R1R2. .Rn 令r為模式R上的關系，ri = R

43、i (r) ,即 r1r2.rn 是將R分解為 R1R2.Rn 對應的數(shù)據(jù)庫。 總有： r r1 r2 . .rn,無損分解,為了得到無損分解，需要在可能的關系集上加約束。 令C表示數(shù)據(jù)庫上的約束集。如果對模式R上滿足C的所有合法關系r,均有 r= R1 (r) R2 (r) . . Rn (r) 則稱關系模式R的分解 R1R2.Rn 是關于R的無損連接分解,無損連接分解的判定 （1）,判定分解無損的標準： 令R為一個關系模式，F(xiàn) 為R上函數(shù)依賴集。R1 和R2 為R的分解。該分解為R的無損連接分解的條件是，只要F+ 中至少有如下函數(shù)依賴中的一個： R1 R2 - R1 R1 R2 - R2,

44、無損連接分解的判定（1）,例：lending(branch_name,branch_city,asset，customer_name,loan_number,amount) 分解結果： Branch=(branch_name,branch_city,assets) Loan=(branch_name,loan_number,amount) Borrow=(customer_name,loan_number) 已知函數(shù)依賴： branch_name-assets branch_city Loan_number-amount,branch_name,無損連接分解的判定（1）,證明是無損分解： 先分

45、解為：Branch=(branch_name,branch_city,assets) Loan_Info=(branch_name,Customer_name,Loan_number,ammount) Branch Loan_Info = Branch_name 由branch_name-assets branch_city branch_name-branch_name 可以得到： branch_name-branch_name assets branch_city,無損連接分解的判定（1）,下一步：將 Loan_Info分解為： Loan=(branch_name, loan_number

46、, amount) Borrow=(customer_name,loan_number) Loan Borrow = Loan_number 由 Loan_number-amount branch_name 可得： Loan_number-LoanNumber mount branch_name 所以是無損連接分解,無損分解性質,如果R的一個分解R1,R2,Rm是關于函數(shù)依賴F的無損連接分解，并接Ri的分解Q1,Q2,Rn具有關于F在Ri上的投影的無損連接性質，那么R的分解R1,R2,Q1,Q2,Qn,.Rm就具有關于F的無損連接性質。,分解為第三范式,不屬于BCNF的關系模式和依賴 例： 假

47、設關系Booking的屬性如下： 1 Title, 電影名 2 Theater,正在上映該電影的電影院名 3 City, 電影院所在的城市 合理的函數(shù)依賴： theater -city title city -theater （不在同一個城市的同一個電影院中重復預定同一部電影的票）,分解為第三范式,確定鍵碼： 任何一個單獨屬性都不是鍵碼 顯然 title , city是鍵碼 可以得到： title theater -city 得到另一個鍵碼 title , theater 出現(xiàn)了BCNF違例：theater -city,分解為第三范式,分解： title, theater theater, c

48、ity,分解為第三范式,連接得到了違背依賴title city - theater 的兩個元組： 該分解沒有保持依賴,分解為第三范式,解決這一問題的辦法：將BCNF限制稍微放寬一些，放寬后的條件是“第三范式” 如果對于任何非平凡依賴：A1A2.An-B ，或者 A1A2.An是超鍵碼，或者B是某個鍵碼的組成部分，則關系R就是屬于“第三范式”（ 3NF）。,分解為第三范式,前面的例子屬于3NF。 Booking(title,city, theater) 依賴：theater -city title city -theater 求得的超碼兩個： title , city title , theat

49、er 依賴theater -city ，左邊雖然不是鍵碼，但是右邊是鍵碼的一部分。,模式分解算法,關于模式分解的幾個重要事實： l 若要求分解保持函數(shù)依賴，那么模式分解總可以達到3NF,但不一定達到BCNF. l 若要求分解既保持函數(shù)依賴，又具有無損連接性，可以達到3NF,但不一定達到BCNF. l 若要求分解具有無損連接性，那一定可以達到4NF。,模式分解算法,關系R ,函數(shù)依賴集F 算法1：（合成法）保持函數(shù)依賴F的分解： 保證3NF l 對F進行“極小化處理” l 找出不在F中出現(xiàn)的屬性，把這樣的屬性構成一個關系模式R1,剩余的屬性仍然記為R. l 若有X-AF,且XA=R,則=R,算法

50、終止。否則，對F按照具有相同左部的原則分組，每一組函數(shù)依賴集所涉及的全部屬性形成一個屬性集Ui.若Ui包含于Uj當中，則將Ui去掉。,算法2：既保持函數(shù)依賴，又具有無損連接性的分解 保證3NF l 找出F 的最小覆蓋G l 對于每個出現(xiàn)在G中的函數(shù)依賴，為這個依賴的左邊X在D中創(chuàng)建一個關系模式,其屬性為XA1A2Ak,其中X-A1,X-A2,.X-An是G中僅有的X作為左邊的依賴（X是這個關系的碼）。 l 如果D中沒有任何一個關系模式包含R的碼，那么就在D中再創(chuàng)建一個關系模式，其中要包含能形成R的碼的屬性。,模式分解算法,多值依賴,屬性的獨立性及其帶來的冗余,某關系模式屬于BCNF，但該關系有

51、和函數(shù)依賴無關的某種冗余。 例：stars(name,street,city,title,year),屬性的獨立性及其帶來的冗余,把地址和電影兩個毫不相關的屬性放在一起，出現(xiàn)數(shù)據(jù)冗余。 判斷該關系是否違背了BCNF：star的五個屬性中，沒有一個可以由其他的四個屬性函數(shù)決定。所以，star中根本不存在非平凡依賴。 結論：所有這五個屬性組成唯一的鍵碼，這個關系模式卻沒有BCNF違例。,多值依賴的定義,多值依賴是關于某個關系R的陳述，其含義是如果確定了R 在一個屬性集的取值，則其他某些特定的屬性的取值與該關系的所有其他屬性的取值無關。 也就是說：如果我們限定了元組R，在屬于A上的每個屬性上取某特定的值，結果屬于B的屬性取值的集合與既不屬于A, 也不屬于B但屬于R的屬性取值的集合無關。 多值依賴的表示： A1A2.An -B1B2.Bm,多值依賴的定義,設關系R中在A的所有屬性上的取值一致的每對元組t和u,我們可以在R中找到某個元組 V,滿足： 1.和t,u在A上的取值一致 2.和t在B上的取值一致。 3.和u在除了A和B之外R的所有屬性上取得一致。,多值依賴的定義,在這個規(guī)則中，t和u可以交換。 結果是，對于A的任何固定值，B和其他屬性的相關值在不