[小學(xué)教育]數(shù)據(jù)庫系統(tǒng)概論 高等教育出版社chp.ppt

1、,數(shù)據(jù)庫系統(tǒng)概論 An Introduction to Database System 第六章 關(guān)系數(shù)據(jù)理論,主要內(nèi)容：關(guān)系數(shù)據(jù)庫理論的主要內(nèi)容， 包括函數(shù)依賴及相關(guān)概念的定義、 函數(shù)依賴的公理系統(tǒng)、 關(guān)系模式的規(guī)范形式、 關(guān)系模式的規(guī)范化等內(nèi)容。 重點(diǎn)：關(guān)系規(guī)范化理論，模式分解。,第六章 關(guān)系數(shù)據(jù)理論,6.1 問題的提出 6.2 規(guī)范化 6.3 數(shù)據(jù)依賴的公理系統(tǒng) *6.4 模式的分解 6.5 小結(jié),6.1 問題的提出,關(guān)系數(shù)據(jù)庫邏輯設(shè)計(jì) 針對具體問題，如何構(gòu)造一個(gè)適合于它的數(shù)據(jù)模式 數(shù)據(jù)庫邏輯設(shè)計(jì)的工具關(guān)系數(shù)據(jù)庫的規(guī)范化理論,一、概念回顧,關(guān)系 關(guān)系模式 關(guān)系數(shù)據(jù)庫 關(guān)系數(shù)據(jù)庫的模式,二、

2、關(guān)系模式的形式化定義,關(guān)系模式由五部分組成，即它是一個(gè)五元組： R(U, D, DOM, F) R： 關(guān)系名 U： 組成該關(guān)系的屬性名集合 D： 屬性組U中屬性所來自的域 DOM： 屬性向域的映象集合 F： 屬性間數(shù)據(jù)的依賴關(guān)系集合,三.什么是數(shù)據(jù)依賴,1.數(shù)據(jù)依賴 一個(gè)關(guān)系內(nèi)部屬性與屬性之間的約束關(guān)系 現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象 數(shù)據(jù)內(nèi)在的性質(zhì) 語義的體現(xiàn),2. 數(shù)據(jù)依賴的類型 函數(shù)依賴（Functional Dependency，簡記為FD） 多值依賴（Multivalued Dependency，簡記為MVD） 其他,四、關(guān)系模式的簡化表示,關(guān)系模式R（U, D, DOM, F） 簡化

3、為一個(gè)三元組： R（U, F） 當(dāng)且僅當(dāng)U上的一個(gè)關(guān)系r滿足F時(shí)，r稱為關(guān)系模式 R（U, F）的一個(gè)關(guān)系,考慮這樣一個(gè)例子：描述一個(gè)在校大學(xué)生的學(xué)習(xí)情況會涉及以下一些屬性： 學(xué)號（S），姓名（SN）、 性別（SS）、 系別（SD）、 專業(yè)（SG）、 班級(SC)、 課程號（CB）、 課程名（CN）、 學(xué)期數(shù)（T）、 學(xué)分（CG）和成績（G）， 其屬性集合表示為: U=S, SN, SS, SD, SG, SC, CB, CN, T, CG, G。 有以下兩種數(shù)據(jù)庫模式：,五、數(shù)據(jù)依賴對關(guān)系模式的影響,第一種： 1=R11， R12 關(guān)系模式R11=S, SN, SS, SD, SG, SC

4、關(guān)系模式R12=S, CB, CN, T, CG, G 第二種： 2=R21, R22, R23 關(guān)系模式R21=S, SN, SS, SD, SG, SC 關(guān)系模式R22=S, CB, G 關(guān)系模式R23=CB, CN, T, CG,先來看1。 假設(shè)r1是R12上的一個(gè)關(guān)系,這個(gè)關(guān)系r1存在以下一些弊病： (1) 冗余 (2) 插入異常 (3) 刪除異常,假設(shè)r2是R22的一個(gè)關(guān)系，如圖：,結(jié)論： R12關(guān)系模式不是一個(gè)好的模式。 “好”的模式： 不會發(fā)生插入異常、刪除異常、更新異常， 數(shù)據(jù)冗余應(yīng)盡可能少 “不好”的原因：由存在于模式中的某些數(shù)據(jù)依賴引起的 解決方法：通過分解關(guān)系模式來消除其

5、中不合適 的數(shù)據(jù)依賴,R22是一個(gè)好的關(guān)系模式 R22=S, CB, G R22是通過將R11分解后得到 R12=S, CB, CN, T, CG, G,6.2 規(guī)范化,規(guī)范化理論正是用來改造關(guān)系模式，通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。,6.2.1 函數(shù)依賴,函數(shù)依賴 平凡函數(shù)依賴與非平凡函數(shù)依賴 完全函數(shù)依賴與部分函數(shù)依賴 傳遞函數(shù)依賴,一、函數(shù)依賴,定義6.1 設(shè)R(U)是一個(gè)屬性集U上的關(guān)系模式，X和Y是U的子集。 若對于R(U)的任意一個(gè)可能的關(guān)系r，r中不可能存在兩個(gè)元組在X上的屬性值相等， 而在Y上的屬性值不等， 則稱 “

6、X函數(shù)確定Y” 或 “Y函數(shù)依賴于X”，記作XY。,設(shè)R(U)是屬性集U上的一個(gè)關(guān)系模式， X，YU。 對R(U)中任意一個(gè)可能關(guān)系r中的任意兩個(gè)元組t和s， 若有tX=sX， 則有tY=sY， 就稱“X函數(shù)決定Y”， 或“Y函數(shù)依賴于X”。,強(qiáng)調(diào)： (1) 關(guān)系模式R中的某個(gè)函數(shù)依賴，R的所有可能關(guān)系r都必須滿足這個(gè)函數(shù)依賴； 反之， 如果R中只要有一個(gè)關(guān)系r不滿足這個(gè)函數(shù)依賴， 我們就認(rèn)為R不存在這個(gè)函數(shù)依賴。,(2) 當(dāng)在確定一個(gè)關(guān)系模式中的函數(shù)依賴時(shí)， 只能從屬性含義上加以說明， 而不能在數(shù)學(xué)上加以證明。 (3) 只有數(shù)據(jù)庫設(shè)計(jì)者才能決定是否存在某種函數(shù)依賴。 這就使得數(shù)據(jù)庫系統(tǒng)可以根

7、據(jù)設(shè)計(jì)者的意圖來維護(hù)數(shù)據(jù)庫的完整性。 例如：,關(guān)系模式S=S, CB, CN, T, CG, G中的函數(shù)依賴可表示為： CBT; (S, CB)G; CBCN; CBCG等等。,二、平凡函數(shù)依賴與非平凡函數(shù)依賴,在關(guān)系模式R(U)中，對于U的子集X和Y， 如果XY，但Y X，則稱XY是非平凡的函數(shù)依賴 若XY，但Y X, 則稱XY是平凡的函數(shù)依賴,例：在關(guān)系SC(Sno, Cno, Grade)中， (Sno, Cno) Grade (Sno, Cno) Sno (Sno, Cno) Cno,非平凡函數(shù)依賴,平凡函數(shù)依賴,若XY，則X稱為這個(gè)函數(shù)依賴的決定屬性組，也稱為決定因素（Determi

8、nant）。 若XY，YX，則記作XY。 若Y不函數(shù)依賴于X，則記作XY。,三、完全函數(shù)依賴與部分函數(shù)依賴,定義6.2 在R(U)中，如果XY，并且對于X的任何一個(gè)真子集X，都有X Y, 則稱Y對X完全函數(shù)依賴，記作X F Y。 若XY，但Y不完全函數(shù)依賴于X，則稱Y對X部分函數(shù)依賴，記作X P Y。,例1建立一個(gè)描述學(xué)校教務(wù)的數(shù)據(jù)庫： 學(xué)生的學(xué)號（Sno）、所在系（Sdept） 系主任姓名（Mname）、課程名（Cname） 成績（Grade） Student U Sno, Sdept, Mname, Cname, Grade (Sno,Cno)Grade是完全函數(shù)依賴， (Sno,Cno)

9、Sdept是部分函數(shù)依賴,F,P,四、傳遞函數(shù)依賴,定義6.3 在R(U)中，如果XY，(Y X) ,YX YZ， 則稱Z對X傳遞函數(shù)依賴。 記為：X Z 注: 如果YX， 即XY，則Z直接依賴于X。 例: 在關(guān)系Std(Sno, Sdept, Mname)中，有： Sno Sdept，Sdept Mname Mname傳遞函數(shù)依賴于Sno,傳遞,6.2.2 碼,定義6.4 設(shè)K為R中的屬性或?qū)傩越M合。若K U， 則K稱為R的侯選碼（Candidate Key）。若候選碼多于一個(gè)，則選定其中的一個(gè)做為主碼（Primary Key）。,F,主屬性與非主屬性 包含在任何一個(gè)候選碼中的屬性 ，稱為主

10、屬性（Prime attribute） 不包含在任何碼中的屬性稱為非主屬性（Nonprime attribute）或非碼屬性（Non-key attribute） 全碼：整個(gè)屬性組是碼，稱為全碼（All-key）,例2 關(guān)系模式S(Sno,Sdept,Sage) 單個(gè)屬性Sno是碼， SC（Sno，Cno，Grade）中， （Sno，Cno）是碼,例3關(guān)系模式R（P，W，A） P：演奏者 W：作品 A：聽眾 一個(gè)演奏者可以演奏多個(gè)作品 某一作品可被多個(gè)演奏者演奏 聽眾可以欣賞不同演奏者的不同作品 碼為(P，W，A)，即All-Key,外部碼,定義6.5 關(guān)系模式 R 中屬性或?qū)傩越MX 并非 R

11、的碼，但 X 是另一個(gè)關(guān)系模式的碼，則稱 X 是R 的外部碼（Foreign key）也稱外碼 如在SC（Sno，Cno，Grade）中，則Sno是關(guān)系模式SC的外部碼 主碼與外部碼一起提供了表示關(guān)系間聯(lián)系的手段,6.2.3 范式,范式是符合某一種級別的關(guān)系模式的集合 關(guān)系數(shù)據(jù)庫中的關(guān)系必須滿足一定的要求。滿足不同程度要求的為不同范式 范式的種類： 第一范式(1NF) 第二范式(2NF) 第三范式(3NF) BC范式(BCNF) 第四范式(4NF) 第五范式(5NF),6.2.4 2NF,1NF的定義 設(shè)R是一個(gè)關(guān)系模式。 如果R的每個(gè)屬性的值域（更確切地說是R的每一個(gè)關(guān)系r的屬性值域）都是不

12、可分的簡單數(shù)據(jù)項(xiàng)（即是原子）的集合， 則稱這個(gè)關(guān)系模式屬于第一范式（first normal form）， 簡記作R1NF。,注意：不滿足1NF的關(guān)系稱為非規(guī)范化的關(guān)系， 滿足1NF的關(guān)系稱為規(guī)范化的關(guān)系。 在任何一個(gè)關(guān)系數(shù)據(jù)庫系統(tǒng)中， 關(guān)系至少應(yīng)該是第一范式。 不滿足第一范式的數(shù)據(jù)庫模式不能稱為關(guān)系數(shù)據(jù)庫。,【例】 如表描述的是學(xué)生選課的情況。,表 學(xué)生選課關(guān)系,表學(xué)生選課關(guān)系,6.2.4第二范式（2NF） 1. 2NF 若關(guān)系模式R是1NF， 而且每一個(gè)非主屬性都完全函數(shù)依賴于R的候選鍵，則R稱為第二范式， 記作R2NF。,例4 關(guān)系模式 S-L-C(Sno, Sdept, Sloc, C

13、no,Grade) 函數(shù)依賴包括： (Sno, Cno) F Grade Sno Sdept (Sno, Cno) P Sdept Sno Sloc (Sno, Cno) P Sloc Sdept Sloc,2NF（續(xù)）,S-L-C的碼為(Sno, Cno) S-L-C滿足第一范式。 非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno, Cno),Sno,Cno,Grade,Sdept,Sloc,S-L-C,S-L-C不是一個(gè)好的關(guān)系模式（續(xù)）,(1) 插入異常 (2) 刪除異常 (3) 數(shù)據(jù)冗余度大 (4) 修改復(fù)雜,S-L-C不是一個(gè)好的關(guān)系模式（續(xù)）,原因 Sdept、 Sloc部分函

14、數(shù)依賴于碼。 解決方法 S-L-C分解為兩個(gè)關(guān)系模式，以消除這些部分函數(shù)依賴 SC（Sno， Cno， Grade） S-L（Sno， Sdept， Sloc）,2NF（續(xù)）,函數(shù)依賴圖：,關(guān)系模式SC的碼為（Sno，Cno） 關(guān)系模式S-L的碼為Sno 這樣非主屬性對碼都是完全函數(shù)依賴,2NF（續(xù)）,例：S-L-C(Sno, Sdept, Sloc, Cno, Grade) 1NF SC（Sno， Cno， Grade） 2NF S-L（Sno， Sdept， Sloc） 2NF,2NF（續(xù)）,采用投影分解法將一個(gè)1NF的關(guān)系分解為多個(gè)2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的插

15、入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。 將一個(gè)1NF關(guān)系分解為多個(gè)2NF的關(guān)系，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。,6.2.5 3NF,如果關(guān)系模式R是1NF， 而且它的任何一個(gè)非主屬性都不傳遞地依賴于任何候選鍵， 則R稱為第三范式， 記作R3NF。 注：若R3NF， 則R的每一個(gè)非主屬性既不部分函數(shù)依賴于候選鍵， 也不傳遞函數(shù)依賴于候選鍵。,3NF（續(xù)）,例：2NF關(guān)系模式S-L(Sno, Sdept, Sloc)中 函數(shù)依賴： SnoSdept SdeptSloc 可得： SnoSloc 即S-L中存在非主屬性對碼的傳遞函數(shù)依賴， S-L 不屬于3NF,3NF（續(xù)

16、）,函數(shù)依賴圖：,3NF（續(xù)）,解決方法 采用投影分解法，把S-L分解為兩個(gè)關(guān)系模式，以消除傳遞函數(shù)依賴： S-D（Sno， Sdept） D-L（Sdept，Sloc） S-D的碼為Sno， D-L的碼為Sdept。 分解后的關(guān)系模式S-D與D-L中不再存在傳遞依賴,采用投影分解法將一個(gè)2NF的關(guān)系分解為多個(gè)3NF的關(guān)系，可以在一定程度上解決原2NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。 將一個(gè)2NF關(guān)系分解為多個(gè)3NF的關(guān)系后，仍然不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。,例： 有一個(gè)關(guān)系模式R(U)， U=S, T, C， 這些數(shù)據(jù)的語義描述如下： 一名教

17、師只能教一門課程； 若干教師可以教同一門課程； 一旦某一個(gè)學(xué)生選定了某門課程， 就確定了一個(gè)固定的一個(gè)教師。 函數(shù)依賴模式（R, F）有： 候選鍵集合KEY=(S, C), (S, T)； 主屬性集合PA=S, C, T； 非主屬性集合NPA=。 R3NF,R上的函數(shù)依賴集合 F=(S, C)T, (S, T) C, TC,關(guān)系模式R存在如下一些問題： (1) 數(shù)據(jù)冗余較大。 (2) 插入異常。 (3) 刪除異常。 原因： 主屬性C對候選鍵(S, T)的部分依賴,6.2.6 BC范式（BCNF）,定義6.8 關(guān)系模式R1NF，若XY且Y X時(shí)X必含有碼，則R BCNF。 等價(jià)于：每一個(gè)決定屬性

18、因素都包含碼,若RBCNF 所有非主屬性對每一個(gè)碼都是完全函數(shù)依賴 所有的主屬性對每一個(gè)不包含它的碼，也是完全函數(shù)依賴 沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性 R BCNF R 3NF,例5 關(guān)系模式C（Cno，Cname，Pcno） C3NF CBCNF 例6 關(guān)系模式S（Sno，Sname，Sdept，Sage） 假定S有兩個(gè)碼Sno，Sname S2NF S BCNF,例7關(guān)系模式SJP（S，J，P） 函數(shù)依賴：（S，J）P；(J，P）S （S，J）與（J，P）都可以作為候選碼,屬性相交 SJP3NF， SJPBCNF,R BCNF R 3NF 如果R3NF，且R只有一個(gè)候選碼 R

19、 BCNF R 3NF,說明： BCNF的定義包含了3NF的定義。 但是， 反過來， 如果R是3NF， R未必是BCNF。 各種范式之間的聯(lián)系有BCNF包含3NF包含2NF包含1NF 轉(zhuǎn)換方法為： 對于1NF， 通過消除它中任何非主屬性對候選鍵的部分依賴， 可以變成2NF;對于2NF， 通過消除它中任何非主屬性對候選鍵的傳遞依賴， 可以變成3NF; 對于3NF， 通過消除它中任何主屬性對候選鍵的部分依賴和傳遞依賴， 可以變成BCNF。,如果一個(gè)關(guān)系數(shù)據(jù)庫中的所有關(guān)系模式都屬于BCNF, 那么在函數(shù)依賴范疇內(nèi)， 它已實(shí)現(xiàn)了模式的徹底分解， 達(dá)到了最高的規(guī)范化程度， 消除了插入異常和刪除異常。通過

20、對關(guān)系模式的分解，可以達(dá)到使關(guān)系模式變成第三范式或更高級范式的要求。,6.2.7 多值依賴,引例 分析學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的一套參考書。每個(gè)教師可以講授多門課程，每種參考書可以供多門課程使用。,非規(guī)范化關(guān)系描述,用二維表表示Teaching,TeachingBCNF Teaching具有唯一候選碼(C，T，B)， 即全碼,結(jié)論：,Teaching模式中存在的問題 (1)數(shù)據(jù)冗余度大 (2)插入操作復(fù)雜 (3)刪除操作復(fù)雜 (4)修改操作復(fù)雜,原因：存在 多值依賴,定義6.9 設(shè)R(U)是一個(gè)屬性集U上的一個(gè)關(guān)系模式， X、 Y和Z是U的子集，并且ZUXY。關(guān)系模式R(U

21、)中多值依賴 XY成立，當(dāng)且僅當(dāng)對R(U)的任一關(guān)系r，給定的一對（x，z）值，有一組Y的值，這組值僅僅決定于x值而與z值無關(guān)。,什么是多值依賴？,例 Teaching（C, T, B）就屬于多值依賴,在R（U）的任一關(guān)系r中，如果存在元組t，s 使得tX=sX，那么就必然存在元組 w，v r，（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。,多值依賴的等價(jià)形式化的定義：,若XY，而Z，則稱 XY為平凡的多值依賴 否則稱XY

22、為非平凡的多值依賴,平凡多值依賴和非平凡的多值依賴,例關(guān)系模式WSC（W，S，C） W表示倉庫，S表示保管員，C表示商品 假設(shè)每個(gè)倉庫有若干個(gè)保管員，有若干種商品 每個(gè)保管員保管所在的倉庫的所有商品 每種商品被所有保管員保管,二維表的描述,WS且WC,圖的描述：,結(jié)論：,多值依賴的性質(zhì),（1）多值依賴具有對稱性 若XY，則XZ，其中ZUXY （2）多值依賴具有傳遞性 若XY，YZ， 則XZ Y （3）函數(shù)依賴是多值依賴的特殊情況。 若XY，則XY。 （4）若XY，XZ，則XY Z。 （5）若XY，XZ，則XYZ。 （6）若XY，XZ，則XY-Z，XZ -Y。,多值依賴與函數(shù)依賴的區(qū)別,(1)

23、多值依賴的有效性與屬性集的范圍有關(guān) (2) 若函數(shù)依賴XY在R（U）上成立，則對于任何Y Y均有XY 成立 多值依賴XY若在R(U)上成立，不能斷言對于任何Y Y有XY 成立,6.2.8 4NF,定義6.10 關(guān)系模式R1NF，如果對于R的每個(gè)非平凡多值依賴XY（Y X），X都含有碼，則R4NF。 如果R 4NF， 則R BCNF,例： Teaching(C,T,B) 4NF 存在非平凡的多值依賴CT，且C不是碼 用投影分解法把Teaching分解為如下兩個(gè)關(guān)系模式： CT(C, T) 4NF CB(C, B) 4NF CT， CB是非平凡多值依賴,分析teaching關(guān)系,6.2.9 規(guī)范化

24、小結(jié),關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計(jì)的工具 目的：盡量消除插入、刪除異常，修改復(fù)雜，數(shù)據(jù)冗余 基本思想：消除不合適的數(shù)據(jù)依賴，使各關(guān)系模式達(dá)到某種程度的“分離”，采用“一事一地”的模式設(shè)計(jì)原則讓一個(gè)關(guān)系描述一個(gè)概念、一個(gè)實(shí)體或者實(shí)體間的一種聯(lián)系。若多于一個(gè)概念就把它“分離”出去 實(shí)質(zhì)：概念的單一化,關(guān)系模式規(guī)范化的基本步驟 1NF 消除非主屬性對碼的部分函數(shù)依賴 消除決定屬性 2NF 集非碼的非平 消除非主屬性對碼的傳遞函數(shù)依賴 凡函數(shù)依賴 3NF 消除主屬性對碼的部分和傳遞函數(shù)依賴 BCNF 消除非平凡且非函數(shù)依賴的多值依賴 4NF,不能說規(guī)范化程度越高的關(guān)系模式就越好 在設(shè)計(jì)數(shù)據(jù)庫

25、模式結(jié)構(gòu)時(shí)，必須對現(xiàn)實(shí)世界的實(shí)際情況和用戶應(yīng)用需求作進(jìn)一步分析，確定一個(gè)合適的、能夠反映現(xiàn)實(shí)世界的模式 上面的規(guī)范化步驟可以在其中任何一步終止,6.3 數(shù)據(jù)依賴的公理系統(tǒng),從一些已知的函數(shù)依賴去判斷另一些函數(shù)依賴是否成立。 這個(gè)問題稱為邏輯蘊(yùn)涵問題。 定義6.11 :F邏輯蘊(yùn)涵XY 設(shè)關(guān)系模式R(U)，X,Y U ，F(xiàn)是關(guān)于R的函數(shù)依賴集合。 又設(shè)XY為R中的一個(gè)函數(shù)依賴，若對R的每一個(gè)關(guān)系r， 滿足F中每一個(gè)依賴， 則r也必須滿足XY，(即r中任意兩個(gè)元組t，s，若tXSX，則tY=sY） 我們就說F邏輯蘊(yùn)涵XY， 或稱XY從F推導(dǎo)出來的， 或稱XY邏輯蘊(yùn)涵于F。,1. Armstrong公

26、理系統(tǒng),關(guān)系模式R 來說有以下的推理規(guī)則： A1.自反律（Reflexivity）：若Y X U， 則X Y為F所蘊(yùn)含。 A2.增廣律（Augmentation）：若XY為F所蘊(yùn)含，且Z U，則XZYZ為F所蘊(yùn)含。 A3.傳遞律（Transitivity）：若XY及YZ為F所蘊(yùn)含，則XZ為F所蘊(yùn)含。,定理 6.1 Armstrong推理規(guī)則是正確的,（l）自反律: 若Y X U，則X Y為F所蘊(yùn)含 證: 設(shè)Y X U 對R 的任一關(guān)系r中的任意兩個(gè)元組t，s： 若tX=sX 由于Y X，有ty=sy 所以XY成立，自反律得證,(2)增廣律: 若XY為F所蘊(yùn)含，且Z U，則XZYZ 為F所蘊(yùn)含。

27、 證：已知XY為F所蘊(yùn)含，且Z U。 設(shè)R 的任一關(guān)系r中任意的兩個(gè)元組t，s： 若tXZ=sXZ 則有tX=sX和tZ=sZ 由XY，于是有tY=sY，所以tYZ=sYZ 所以XZYZ為F所蘊(yùn)含，增廣律得證。,(3) 傳遞律：若XY及YZ為F所蘊(yùn)含，則 XZ為 F所蘊(yùn)含。 證：已知XY及YZ為F所蘊(yùn)含 對R 的任一關(guān)系 r中的任意兩個(gè)元組 t，s： 若tX=sX，由于XY，有 tY=sY； 已知XZ，有tZ=sZ，所以XZ為F所蘊(yùn)含，傳遞律得證。,2. 導(dǎo)出規(guī)則,1.根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： 合并規(guī)則：由XY，XZ，有XYZ。 偽傳遞規(guī)則：由XY，WYZ，

28、有XWZ。 分解規(guī)則：由XY及 ZY，有XZ。,合并規(guī)則、 分解規(guī)則、 偽傳遞規(guī)則是正確的。 合并規(guī)則證明：若XY，XZ， 則XYZ 若XY, 根據(jù)增廣律得,XXXY， 即XXY。 若XZ， 根據(jù)增廣律得， XYYZ， 根據(jù)傳遞律得， XYZ。,分解規(guī)則證明：若XY且Z Y， 則XZ 若Z Y， 根據(jù)自反律得，YZ， 又已知XY， 根據(jù)傳遞律得， XZ。 偽傳遞規(guī)則證明：若XY， YZW，則XZW。 若XY， 根據(jù)增廣律得， XZYZ， 又已知YZW， 根據(jù)傳遞律得， XZW。,例: 關(guān)系模式R(CITY, ST, ZIP)， 函數(shù)依賴集合F=(CITY, ST)ZIP, ZIPCITY， 證

29、明ST, ZIP和CITY, ST是候選鍵。 證： ZIPCITY （由給定條件得出） (ST, ZIP)(CITY, ST) （由增廣律得出） (CITY, ST)ZIP （由給定條件得出） (CITY, ST)(CITY, ST, ZIP) (由增廣律得出） (ST, ZIP)(CITY, ST, ZIP) （由傳遞律得出） 并且，ST(CITY, ST, ZIP)和 ZIP(CITY, ST, ZIP) 均不成立， 所以(ST, ZIP)是候選鍵。 同理可證 (CITY, ST)也是候選鍵。 證畢。,2.引理6.1 XA1 A2Ak成立的充分必要條件是XAi成立（i=1，k）（證明省略）

30、,Armstrong公理系統(tǒng)是有效的、完備的。 有效性：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個(gè)函數(shù)依賴一定在F+中。 完備性：F+中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來。,3. 函數(shù)依賴閉包,定義6.l2 在關(guān)系模式R中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體稱作 F的閉包，記為F+。 例：設(shè)關(guān)系模式R(U)， U=A, B, C, F=ABC, CB是R(U)上的一組函數(shù)依賴， 則 F+=AA, ABA, ACA, ABCA, BB, ABB, BCB, ABCB, CC, ACC, BCC, ABCC, ABAB, ABCAB, ACAC, ABCAC,

31、BCBC, ABCBC, ABCABC, ABC, ABAC, ABBC, ABABC, CB, CBC, ACB,定義6.13 設(shè)F為屬性集U上的一組函數(shù)依賴，X U， XF+ = A|XA能由F 根據(jù)Armstrong公理導(dǎo)出，XF+稱為屬性集X關(guān)于函數(shù)依賴集F 的閉包。,【例】 設(shè)有關(guān)系模式R(U)， U=A, B, C, D, E， F=ABC, CDE, BD, EA， 則 B+F= A+F =,=B, D,=A, B, C, D, E,關(guān)于閉包的引理,引理6.2 設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y U，XY能由F 根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y XF+ 用途：

32、 將判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出的問題轉(zhuǎn)化為： 求出XF+ 判定Y是否為XF+的子集的問題,證明： 充分性 設(shè)Y=A1A2An（A1, A2, , An為屬性） 假設(shè)Y X+F， 根據(jù)X+F的定義， 對所有i=1, ， n, XAi可用Armstrong公理系統(tǒng)從F推出。 根據(jù)合并規(guī)則， XY也能從F推出。 必要性 假設(shè)XY能用Armstrong公理系統(tǒng)推出。 根據(jù)分解規(guī)則， 對于所有i=1, 2, ， n, XAi成立。 根據(jù)X+的定義有 Ai X+F， 故有A1A2An X+F， 即Y X+F。證畢,求閉包的算法,算法6.1 求屬性集X（X U）關(guān)于U上的函數(shù)依賴集F

33、的閉包XF+ 輸入：X，F(xiàn) 輸出：XF+ 步驟： 令X(0)=X， i=0; 令X(i+1)=X(i)A|V-X(i)， VWF, AW; 若已經(jīng)沒有VWF， 能使X(i+1)X(i)， 則X+=X(i),輸出X+， 算法結(jié)束； 否則， 令i=i+1， 轉(zhuǎn)去執(zhí)行第(2)步。,例 已知關(guān)系模式R，其中 U=A，B，C，D，E； F=ABC，BD，CE，ECB，ACB。 求（AB）F+ 。 解 設(shè)X（0）=AB； (1) X（1）=ABCD=ABCD。 (2) X（0） X（1） X（2）=X（1）BE=ABCDE。 (3) X（2）=U，算法終止 （AB）F+ =ABCDE。,4. Armstr

34、ong公理系統(tǒng)的有效性與完備性,定理6.2 Armstrong公理系統(tǒng)是有效的、完備的 證明： 1. 有效性 可由定理6.1得證 2. 完備性 只需證明逆否命題: 若函數(shù)依賴XY不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)含,Armstrong公理系統(tǒng)完備性證明：,(1) 引理: 若VW成立，且V XF+，則W XF+ 證 因?yàn)?V XF+ ，所以有XV成立； 因?yàn)閄 V，VW，于是XW成立 所以W XF+,(2) 構(gòu)造一張二維表r，它由下列兩個(gè)元組構(gòu)成，先證明r必是R（U，F(xiàn)）的一個(gè)關(guān)系，再證明F+中的全部函數(shù)依賴在 r上成立，則證明了定理的完備性。,XF+U-XF+ 11.1

35、 00.0 11.1 11.1,反證法： 若r不是R 的關(guān)系，則必由F中有函數(shù)依賴VW在r上不成立所致。由表中可以看到，V是XF+ 的子集，而W不是XF+ 的子集，可是由第（1）步W XF+矛盾。所以r必是R的一個(gè)關(guān)系。,(3)證明F+中的全部函數(shù)依賴在 r上成立 若XY 不能由F從Armstrong公理導(dǎo)出，則Y不是XF+ 的子集。 （引理6.2） 必有Y的子集Y滿足 Y U-XF+ 因?yàn)閞中u1X=u2X而 u1Y u2Y 則XY在 r 中不成立，即XY必不為R 蘊(yùn)含 /* 因?yàn)?F+中的全部函數(shù)依賴在 r上成立。 綜上所述,定理得證.,說明： Armstrong公理系統(tǒng)的正確性和完備性說

36、明了“通過F推導(dǎo)出的函數(shù)依賴”與“F所蘊(yùn)涵的函數(shù)依賴”兩種說法是完全等價(jià)的。 F+也可以說成是由F出發(fā)經(jīng)Armstrong公理系統(tǒng)導(dǎo)出的函數(shù)依賴集合。,5. 函數(shù)依賴集等價(jià),在實(shí)際應(yīng)用中， 經(jīng)常需要將一個(gè)已知的函數(shù)依賴集變換為其它的或更簡潔的表示形式。 例如， 需要把一個(gè)大的關(guān)系模式分解為幾個(gè)小的關(guān)系模式， 這時(shí)就需要將相應(yīng)的函數(shù)依賴也投影到分解后的模式上。 這就涉及一個(gè)函數(shù)依賴集的等價(jià)問題。,定義6.14 如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。 引理6.3 F+ = G+ 的充分必要條件是F G+ ，和G F+,證明： （必要性） 設(shè)G+=F+

37、， 由于FF+，所以有FG+。 同理可得 GF+。 （充分性） 設(shè)FG+且GF+。 對于每個(gè)XYF+， 則有XY由F出發(fā)使用Armstrong公理導(dǎo)出。 由FG+， 則XY就可以由G+使用Armstrong公理導(dǎo)出， 所以XY(G+)+=G+， 即XYG+。 所以F+G+。 同理可證 G+F+。 所以F+=G+， 即F與G等價(jià)。,6. 最小依賴集,定義6.15 如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。 (1) F中任一函數(shù)依賴的右部僅含有一個(gè)屬性。 (2) F中不存在這樣的函數(shù)依賴XA，使得F與F-XA等價(jià)。 (3) F中不存在這樣的函數(shù)依賴XA，

38、 X有真子集Z使得F-XAZA與F等價(jià)。,注： 條件(1)保證了函數(shù)依賴的右部沒有多余的屬性 條件(2)保證了F中不存在多余的函數(shù)依賴 條件(3)保證了每個(gè)函數(shù)依賴的左部沒有多余的屬性 F 的極小依賴集不一定是惟一的。,例2 關(guān)系模式S，其中： U= Sno，Sdept，Mname，Cno，Grade ， F= SnoSdept，SdeptMname，(Sno,Cno)Grade F=SnoSdept，SnoMname，SdeptMname，(Sno，Cno)Grade，(Sno，Sdept)Sdept F是最小覆蓋，而F不是。 因?yàn)椋篎 - SnoMname與F 等價(jià) F - (Sno，Sd

39、ept)Sdept也與F 等價(jià),F = AB，BA，BC，AC，CA Fm1、Fm2都是F的最小依賴集么？ Fm1= AB，BC，CA Fm2= AB，BA，AC，CA,7. 極小化過程,定理6.3 每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小函數(shù)依賴集Fm。此Fm稱為F的最小依賴集。 證明: 構(gòu)造性證明，找出F的一個(gè)最小依賴集。,方法：(1) 應(yīng)用分解規(guī)則， 使F的每一個(gè)函數(shù)依賴的右部屬性單一化。 (2) 去掉各函數(shù)依賴左部多余的屬性。 具體辦法是： 逐個(gè)循環(huán)檢查F中左邊是非單屬性的依賴XY 。 設(shè)X=B1B2Bn， 若Y(X-Bi)+F， 則以(X-Bi)Y取代XY， 直到F不再改變?yōu)橹埂?(3)

40、去掉多余的函數(shù)依賴。 具體辦法是： 循環(huán)檢查F中各函數(shù)依賴XY， 令G=F-XY， 若YX+G， 則從F中去掉XY； 否則， 不能去掉XY。 直到F不再改變?yōu)橹埂?【例】 設(shè)關(guān)系模式R(U)上的函數(shù)依賴集為F, U=A, B, C, D, E, G, ; F=ABC, BCD, ACDB, DEG, CA, BEC, CGBD, CEAG。 試計(jì)算其等價(jià)的極小函數(shù)依賴集F。 解(1)應(yīng)用分解規(guī)則， 使F的每一個(gè)函數(shù)依賴的右部屬性單一化。 結(jié)果為： F1=ABC, BCD, ACDB, DE, DG, CA,BEC, CGB,CGD, CEA, CEG。,（2） 去掉各函數(shù)依賴左部多余的屬性。

41、因?yàn)镃EA, CA, 則E是多余的； 對于ACDB,由(CD)+F1=ABCDEG，則A是多余的。 其它函數(shù)依賴中無左部多余的屬性。 刪除函數(shù)依賴左部多余的函數(shù)依賴后的結(jié)果為： F2=ABC,BCD, CDB, DE, DG, CA, BEC, CGB, CGD, CEG。 ,F1=ABC, BCD, ACDB, DE, DG, CA, BEC, CGB, CGD, CEA, CEG,(3) 在F2中去掉多余的函數(shù)依賴。 對于CGB, 由于 （CG）+=ABCDEG, 則是多余的。 其等價(jià)的極小函數(shù)依賴集F的結(jié)果為： F=ABC, BCD, CDB, DE, DG, CA, BEC, CGD,

42、 CEG。,補(bǔ)充內(nèi)容：求關(guān)系模式候選碼的方法:,方法:按以下幾步來求候選鍵 1.只在FD右部出現(xiàn)的屬性,不屬于候選碼; 2.只在FD左部出現(xiàn)的屬性,一定存在與任何候選碼當(dāng)中; 3.兩邊均不出現(xiàn)的屬性一定存在于任何候選碼當(dāng)中; 4.其他屬性逐個(gè)與2,3的屬性組合,求屬性閉包,直至X的閉包等于U,若等于U,則X為候選碼.,舉例說明: R(U)=(ABCDEG),F=AB-C,CD-E,E-A,A-G,求候選碼.,6.4 模式的分解,根據(jù)需求分析中得到的用戶要求， 我們可以把關(guān)系分為兩類。 (1) 靜態(tài)關(guān)系： 其特點(diǎn)是一旦數(shù)據(jù)已加載， 用戶只能在這個(gè)關(guān)系上運(yùn)行查詢操作。 這種關(guān)系的要求是必須屬于1N

43、F。 (2) 動態(tài)關(guān)系： 其特點(diǎn)是當(dāng)數(shù)據(jù)加載后， 經(jīng)常對數(shù)據(jù)進(jìn)行增、 刪、 改操作。 這種關(guān)系的要求是至少屬于3NF。,把低一級的關(guān)系模式分解為若干個(gè)高一級的關(guān)系模式的方法不是唯一的 只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義,關(guān)系模式分解的標(biāo)準(zhǔn),三種模式分解等價(jià)的定義： 分解具有無損連接性 分解要保持函數(shù)依賴 分解既要保持函數(shù)依賴，又要具有無損連接性,定義6.16 關(guān)系模式R的一個(gè)分解： = R1，R2，Rn U= Ui，且不存在 Ui Uj，F(xiàn)i 為 F在 Ui 上的投影 定義6.17 函數(shù)依賴集合XY | XY F+XY Ui 的一個(gè)覆蓋 Fi 叫作 F 在屬性 Ui

44、 上的投影,i=1,n,例: SL（Sno， Sdept， Sloc） F= SnoSdept, SdeptSloc, SnoSloc,SL2NF 存在插入異常、刪除異常、冗余度大和修改復(fù)雜等問題,SL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B ,分解方法可以有多種,1. SL分解為下面三個(gè)關(guān)系模式： SN(Sno) SD(Sdept) SO(Sloc),分解后的關(guān)系為：,SN SD SO Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004

45、PH 95005 ,SNO SDEPT Sloc 95001 CS A 95001 CS B 95001 CS C 95001 IS A 95001 IS B 95001 IS C ,分解后的數(shù)據(jù)庫丟失了許多信息,2. SL分解為下面二個(gè)關(guān)系模式： NL(Sno, Sloc) DL(Sdept, Sloc) 分解后的關(guān)系為： N DL Sno Sloc Sdept Sloc 95001 A CS A 95002 B IS B 95003 C MA C 95004 B PH B 95005 B ,NL DL Sno Sloc Sdept 95001 A CS 95002 B IS 95002 B

46、 PH 95003 C MA 95004 B IS 95004 B PH 95005 B IS 95005 B PH 元組增加了，信息丟失了,3. 將SL分解為下面二個(gè)關(guān)系模式： ND(Sno, Sdept) NL(Sno, Sloc) 分解后的關(guān)系為：,ND NL Sno Sdept Sno Sloc 95001 CS 95001 A 95002 IS 95002 B 95003 MA 95003 C 95004 IS 95004 B 95005 PH 95005 B,ND NL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 CS

47、 A 95005 PH B 與SL關(guān)系一樣，因此沒有丟失信息,6.4.2 具有無損連接性的關(guān)系模式分解 1. 分解具有無損連接性 設(shè)關(guān)系模式R(U)，F(xiàn)是R上的函數(shù)依賴集合，=R1, R2, , Rn是R的一個(gè)分解，如果對R的任一滿足F的關(guān)系r下式成立：,則稱分解為具有無損連接性或分解為無損連接分解。,一般把關(guān)系r在分解上的投影連接記為m(r), 即,滿足無損連接的條件可表示為： r=m(r)。,無損連接分解的特性說明：,關(guān)系模式分解后所表示的信息應(yīng)與原模式等價(jià)， 即分解后的多個(gè)關(guān)系再連接得到的新關(guān)系不能“丟失”信息。 實(shí)際上， 連接后的關(guān)系不會少了任何元組， 而是可能多出一些元組，與原來的關(guān)

48、系不等價(jià)， 所以是有損的。,r和m(r)的關(guān)系: 引理6.4 設(shè)關(guān)系模式R(U)及R上的關(guān)系r, =R1, R2, Rn是R的一個(gè)分解， 則有： (1) r m(r) (2) (3) m(m(r)= m(r),分析： 將SL分解為下面二個(gè)關(guān)系模式： ND(Sno, Sdept) NL(Sno, Sloc) 具有無損連接性 問題:這種分解方法沒有保持原關(guān)系中的函數(shù)依賴 SL中的函數(shù)依賴SdeptSloc沒有投影到關(guān)系模式ND、NL上,2. 判定一個(gè)分解的無損連接性算法 算法6.2 判定一個(gè)分解的無損連接性算法。 輸入： 關(guān)系模式R(A1, A2, , An)， R上的分解=R1, R2, ,Rn

49、， R上的函數(shù)依賴集為F。 輸出： 分解是否具有無損連接性。,方法： (1) 構(gòu)造一個(gè)k行n列的初始表， 第i 行對應(yīng)于關(guān)系模式Ri， 第j列對應(yīng)于屬性Aj。如果AjRi， 則在第i行第j列上填符號ai； 否則填符號bij。 (2) 逐個(gè)檢查F中的每一個(gè)函數(shù)依賴， 并修改表中的元素。 具體辦法如下： 從函數(shù)依賴集F中取一個(gè)函數(shù)依賴XY， 在X的分量中尋找相同的行， 然后將這些行中Y的分量改為相同的符號。 如果其中有aj, 則將bij改為aj; 否則， 改為bij(指用其中的一個(gè)bij 替換另一個(gè)， 通常是把下標(biāo)改為較小的那個(gè)數(shù))。 (3) 這樣反復(fù)進(jìn)行， 如果發(fā)現(xiàn)某一行變成了a1, a2, ,

50、 an， 即存在某一行全為a 類符號， 則分解具有無損連接性； 如果 F中所有函數(shù)依賴都不能再修改表中的內(nèi)容， 且沒有發(fā)現(xiàn)這樣的行， 則分解不具有無損連接性。,【例】 已知關(guān)系模式R(U)， U=A, B, C, D, E， R上的函數(shù)依賴集F=AC, BC, CD, DEC, CEA， 分解=R1(A, D), R2(A, B), R3(B, E), R4(C, D, E), R5(A, E), 判定是否具有無損連接性。 解： (1) 首先構(gòu)造初始表（見表）。,表,(2) 檢查AC， 修改結(jié)果如表。,(3) 檢查BC， 修改結(jié)果如表。,(4) 檢查CD， 修改結(jié)果如表。,(5) 檢查DEC，

51、修改結(jié)果如表。,(6) 檢查CEA，修改結(jié)果如表。,定理6.4 算法6.2能正確判斷分解是否是無損連接分解。 定理6.5 設(shè)關(guān)系模式R的一個(gè)分解=R1, R2, U1、U2和U分別是R1、 R2和R的屬性集合， F是R上的函數(shù)依賴集。 具有無損連接性的充分必要條件是： (U1U2)(U1-U2)F+ 或 (U1U2)(U2-U1)F+,定義6.19 具有保持函數(shù)依賴的關(guān)系模式分解 1. 分解具有保持函數(shù)依賴 設(shè)關(guān)系模式R(U)， =R1, R2, , Rn是R的一個(gè)分解， Ui是Ri的屬性集合， Fi是F在Ui上的投影。 如果F等價(jià)于F1F2Fn, 則稱分解具有函數(shù)依賴保持性或具有保持函數(shù)依賴

52、的分解。,2. 判斷分解是函數(shù)依賴保持性算法 引理6.3 判斷分解的函數(shù)依賴保持性。 輸入： 關(guān)系模式R上的函數(shù)依賴集F， R的一個(gè)分解=R1, R2, , Rn。 輸出： 確定是否具有函數(shù)依賴保持性。,方法1： (1) 計(jì)算F到每一個(gè)Ri上的投影（i=1, 2, , k）； (2) FOR 每一個(gè) XYF DO Z1=X; Z0=; DO WHILE Z1Z0 Z0=Z1; FOR 每一個(gè)Ri DO Z1=Z1(Z1Ri)+Ri) ENDFOR ENDDO IF Y-Z1= RETURN(true) ENDFOR RETURN(false),【例】 給定關(guān)系模式 R(U), U=A, B,

53、C, D, R上的函數(shù)依賴集F=AB, BC, CD, DA， 關(guān)系模式R上的分解=R1, R2, R3， 其中R1=AB， R2=BC， R3=CD。 試判斷： 分解是否具有保持函數(shù)依賴性。 解： (1) 先計(jì)算F到每一個(gè) Ri上的投影。 AB(F)=AB BC(F)=BC CD(F)=CD,(2) 顯然， AB, BC, CD均得以保持。下面應(yīng)用算法來判斷DA 是否會保持。 初始： Z1=D， Z0=； 第一遍:對R1: Z0=D， Z1 =D(DA,B)+A,B)=D 對R2: Z0=D， Z1=D(DB,C)+B,C)=D 對R3: Z0=D， Z1=D(DC,D)+C,D) =D(A

54、, B, C, DC, D) =C, D,第二遍： 對R1: Z0=C,D， Z1=C,D Z1=C,D(C,DA,B)+A,B)=C,D 對R2: Z0=C,D Z1=C,D(C,DB,C)+B,C) =B, C, D 對R3: Z1=B,C,D， Z1=B,C,D(B,C,DC,D)+C,D) =B, C, D,第三遍： 對R1: Z0=B,C,D， Z1=B,C,D(B,C,DA,B)+A,B) =A,B,C,D 對R2: Z1=A,B,C,D， Z1=A,B,C,D 對R3: Z1=A,B,C,D， Z1=A,B,C,D 第四遍： Z0=Z1=A, B, C, D， 根據(jù)算法6.3，

55、下一步應(yīng)該執(zhí)行IF語句， 因?yàn)?A-Z1=, 返回true。 綜上所述， 分解是具有保持函數(shù)依賴性。,方法2： F= 則R的分解=R1, R2, , Rn保持函數(shù)依賴。,【例】 給定關(guān)系模式 R(U), U=A, B, C, D, R上的函數(shù)依賴集F=AB, BC, CD, DA， 關(guān)系模式R上的分解=R1, R2, R3， 其中R1=AB， R2=BC， R3=CD。 試判斷： 分解是否具有保持函數(shù)依賴性。,6.4.3 模式分解的算法 關(guān)系模式分解的兩個(gè)重要目標(biāo)是： 無損連接性和函數(shù)依賴保持性。 任一個(gè)不是3NF的關(guān)系模式通過分解總可以成為3NF。 只要關(guān)系模式在分解中保持函數(shù)依賴， 或既保持函數(shù)依賴又具有無損連接性， 就一定能達(dá)到3NF， 但