數(shù)據(jù)庫原理與應用第四章PPT課件PPT課件

1、4.1 問題的提出關系數(shù)據(jù)庫邏輯設計 針對具體問題，如何構造一個適合于它的數(shù)據(jù)模式 數(shù)據(jù)庫邏輯設計的工具關系數(shù)據(jù)庫的規(guī)范化理論第1頁/共137頁問題的提出一、概念回顧二、關系模式的形式化定義三、什么是數(shù)據(jù)依賴四、關系模式的簡化定義五、數(shù)據(jù)依賴對關系模式影響第2頁/共137頁一、概念回顧 關系：描述實體、屬性、實體間的聯(lián)系。 從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個子集。 關系模式：用來定義關系。 關系數(shù)據(jù)庫：基于關系模型的數(shù)據(jù)庫，利用關系來描述現(xiàn)實世界。 從形式上看，它由一組關系組成。 關系數(shù)據(jù)庫的模式：定義這組關系的關系模式的全體。第3頁/共137頁二、關系模式的形式化定義關

2、系模式由五部分組成，即它是一個五元組： R(U, D, DOM, F)R： 關系名U： 組成該關系的屬性名集合D： 屬性組U中屬性所來自的域DOM：屬性向域的映象集合F： 屬性間數(shù)據(jù)的依賴關系集合第4頁/共137頁三、什么是數(shù)據(jù)依賴1. 完整性約束的表現(xiàn)形式 限定屬性取值范圍：例如學生成績必須在0-100之間 定義屬性值間的相互關連（主要體現(xiàn)于值的相等與否），這就是數(shù)據(jù)依賴，它是數(shù)據(jù)庫模式設計的關鍵第5頁/共137頁什么是數(shù)據(jù)依賴（續(xù)）2. 數(shù)據(jù)依賴 是通過一個關系中屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間的相互關系 是現(xiàn)實世界屬性間相互聯(lián)系的抽象 是數(shù)據(jù)內在的性質 是語義的體現(xiàn)第6頁/共137頁什

3、么是數(shù)據(jù)依賴（續(xù)）3. 數(shù)據(jù)依賴的類型 函數(shù)依賴（Functional Dependency，簡記為FD） 多值依賴（Multivalued Dependency，簡記為MVD） 其他第7頁/共137頁四、關系模式的簡化表示關系模式R（U, D, DOM, F） 簡化為一個三元組： R（U, F）當且僅當U上的一個關系r 滿足F時，r稱為關系模式 R（U, F）的一個關系第8頁/共137頁五、數(shù)據(jù)依賴對關系模式的影響例：描述學校的數(shù)據(jù)庫：學生的學號（Sno）、所在系（Sdept）系主任姓名（Mname）、課程名（Cname）成績（Grade）單一的關系模式 ： Student U Sno, S

4、dept, Mname, Cname, Grade 第9頁/共137頁數(shù)據(jù)依賴對關系模式的影響（續(xù)）學校數(shù)據(jù)庫的語義： 一個系有若干學生， 一個學生只屬于一個系； 一個系只有一名主任； 一個學生可以選修多門課程， 每門課程有若干學生選修； 每個學生所學的每門課程都有一個成績。 第10頁/共137頁數(shù)據(jù)依賴對關系模式的影響（續(xù)）屬性組U上的一組函數(shù)依賴F： F Sno Sdept, Sdept Mname, (Sno, Cname) Grade SnoCnameSdeptMnameGrade第11頁/共137頁關系模式Student中存在的問題 數(shù)據(jù)冗余太大 浪費大量的存儲空間 例：每一個系主任

5、的姓名重復出現(xiàn) 更新異常（Update Anomalies） 數(shù)據(jù)冗余 ，更新數(shù)據(jù)時，維護數(shù)據(jù)完整性代價大。例：某系更換系主任后，系統(tǒng)必須修改與該系學生有關的每一個元組第12頁/共137頁關系模式Student中存在的問題 插入異常（Insertion Anomalies） 該插的數(shù)據(jù)插不進去 例，如果一個系剛成立，尚無學生，我們就無法把這個系及其系主任的信息存入數(shù)據(jù)庫。 刪除異常（Deletion Anomalies） 不該刪除的數(shù)據(jù)不得不刪例，如果某個系的學生全部畢業(yè)了， 我們在刪除該系學生信息的同時，把這個系及其系主任的信息也丟掉了。第13頁/共137頁數(shù)據(jù)依賴對關系模式的影響（續(xù)）結論

6、： Student關系模式不是一個好的模式。 “好”的模式：不會發(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應盡可能少。原因：由存在于模式中的某些數(shù)據(jù)依賴引起的解決方法：通過分解關系模式來消除其中不合適 的數(shù)據(jù)依賴。第14頁/共137頁4.2 規(guī)范化 規(guī)范化理論正是用來改造關系模式，通過分解關系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。第15頁/共137頁函數(shù)依賴一、函數(shù)依賴二、平凡函數(shù)依賴與非平凡函數(shù)依賴三、完全函數(shù)依賴與部分函數(shù)依賴四、傳遞函數(shù)依賴第16頁/共137頁一、函數(shù)依賴定義5.1 設R(U)是一個屬性集U上的關系模式，X和Y是U的子集。 若對

7、于R(U)的任意一個可能的關系r，r中不可能存在兩個元組在X上的屬性值相等， 而在Y上的屬性值不等， 則稱 “X函數(shù)確定Y” 或 “Y函數(shù)依賴于X”，記作XY。 X稱為這個函數(shù)依賴的決定屬性集(Determinant)。 Y=f(x)第17頁/共137頁說明： 1. 函數(shù)依賴不是指關系模式R的某個或某些關系實例滿足的約束條件，而是指R的所有關系實例均要滿足的約束條件。2. 函數(shù)依賴是語義范疇的概念。只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴。 例如“姓名年齡”這個函數(shù)依賴只有在不允許有同名人的條件下成立3. 數(shù)據(jù)庫設計者可以對現(xiàn)實世界作強制的規(guī)定。例如規(guī)定不允許同名人出現(xiàn)，函數(shù)依賴“姓名年齡”成立。所插

8、入的元組必須滿足規(guī)定的函數(shù)依賴，若發(fā)現(xiàn)有同名人存在， 則拒絕裝入該元組。第18頁/共137頁函數(shù)依賴（續(xù)）例: Student(Sno, Sname, Ssex, Sage, Sdept) 假設不允許重名，則有:Sno Ssex， Sno Sage , Sno Sdept， Sno Sname, Sname Ssex， Sname SageSname Sdept但Ssex Sage若XY，并且YX, 則記為XY。 若Y不函數(shù)依賴于X, 則記為XY。第19頁/共137頁二、平凡函數(shù)依賴與非平凡函數(shù)依賴在關系模式R(U)中，對于U的子集X和Y，如果XY，但Y X，則稱XY是非平凡的函數(shù)依賴若XY，

9、但Y X, 則稱XY是平凡的函數(shù)依賴例：在關系SC(Sno, Cno, Grade)中， 非平凡函數(shù)依賴： (Sno, Cno) Grade 平凡函數(shù)依賴： (Sno, Cno) Sno (Sno, Cno) Cno第20頁/共137頁平凡函數(shù)依賴與非平凡函數(shù)依賴（續(xù)） 對于任一關系模式，平凡函數(shù)依賴都是必然成立的，它不反映新的語義，因此若不特別聲明， 我們總是討論非平凡函數(shù)依賴。第21頁/共137頁三、完全函數(shù)依賴與部分函數(shù)依賴定義5.2 在關系模式R(U)中，如果XY，并且對于X的任何一個真子集X，都有 X Y, 則稱Y完全函數(shù)依賴于X，記作X Y。 若XY，但Y不完全函數(shù)依賴于X，則稱Y

10、部分函數(shù)依賴于X，記作X P Y。 第22頁/共137頁完全函數(shù)依賴與部分函數(shù)依賴（續(xù)）例: 在關系SC(Sno, Cno, Grade)中， 由于：Sno Grade，Cno Grade， 因此：(Sno, Cno) Grade 第23頁/共137頁四、傳遞函數(shù)依賴定義5.3 在關系模式R(U)中，如果XY，YZ，且Y X，YX，則稱Z傳遞函數(shù)依賴于X。注: 如果YX， 即XY，則Z直接依賴于X。例: 在關系Std(Sno, Sdept, Mname)中，有：Sno Sdept，Sdept Mname Mname傳遞函數(shù)依賴于Sno第24頁/共137頁碼定義5.4 設K為關系模式R中的屬性或

11、屬性組合。若K U，則K稱為R的一個侯選碼（Candidate Key）。若關系模式R有多個候選碼，則選定其中的一個做為主碼（Primary key）。 主屬性與非主屬性 ALL KEY第25頁/共137頁外部碼定義5.5 關系模式 R 中屬性或屬性組X 并非 R的碼，但 X 是另一個關系模式的碼，則稱 X 是R 的外部碼（Foreign key）也稱外碼 主碼又和外部碼一起提供了表示關系間聯(lián)系的手段。第26頁/共137頁范式 范式是符合某一種級別的關系模式的集合。 關系數(shù)據(jù)庫中的關系必須滿足一定的要求。滿足不同程度要求的為不同范式。 范式的種類：第一范式(1NF)第二范式(2NF)第三范式(

12、3NF)BC范式(BCNF)第四范式(4NF)第五范式(5NF)第27頁/共137頁范式各種范式之間存在聯(lián)系：某一關系模式R為第n范式，可簡記為RnNF。NF5NF4BCNFNF3NF2NF1第28頁/共137頁 1NF的定義如果一個關系模式R的所有屬性都是不可分的基本數(shù)據(jù)項，則R1NF。 第一范式是對關系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫模式不能稱為關系數(shù)據(jù)庫。 但是滿足第一范式的關系模式并不一定是一個好的關系模式。第29頁/共137頁2NF例: 關系模式 SLC(Sno, Sdept, Sloc, Cno, Grade) Sloc為學生住處，假設每個系的學生住在同一個地方。 函數(shù)依

13、賴包括： (Sno, Cno) f Grade Sno Sdept (Sno, Cno) P Sdept Sno Sloc (Sno, Cno) P Sloc Sdept Sloc第30頁/共137頁 2NF SLC的碼為(Sno, Cno) SLC滿足第一范式。 非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno, Cno)SnoCnoGradeSdeptSlocSLC第31頁/共137頁SLC不是一個好的關系模式(1) 插入異常假設Sno95102，SdeptIS，SlocN的學生還未選課，因課程號是主屬性，因此該學生的信息無法插入SLC。(2) 刪除異常 假定某個學生本來只選修了3號課

14、程這一門課。現(xiàn)在因身體不適，他連3號課程也不選修了。因課程號是主屬性，此操作將導致該學生信息的整個元組都要刪除。 第32頁/共137頁SLC不是一個好的關系模式(3) 數(shù)據(jù)冗余度大 如果一個學生選修了10門課程，那么他的Sdept和Sloc值就要重復存儲了10次。(4) 修改復雜 例如學生轉系，在修改此學生元組的Sdept值的同時，還可能需要修改住處（Sloc）。如果這個學生選修了K門課，則必須無遺漏地修改K個元組中全部Sdept、Sloc信息。 第33頁/共137頁 2NF 原因 Sdept、 Sloc部分函數(shù)依賴于碼。 解決方法 SLC分解為兩個關系模式，以消除這些部分函數(shù)依賴 SC（Sn

15、o， Cno， Grade） SL（Sno， Sdept， Sloc）第34頁/共137頁 2NF SLC的碼為(Sno, Cno) SLC滿足第一范式。 非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno, Cno)SnoCnoGradeSdeptSlocSLC第35頁/共137頁2NF函數(shù)依賴圖：SnoCnoGradeSCSLSnoSdeptSloc第36頁/共137頁 2NF2NF的定義定義5.6 若關系模式R1NF，并且每一個非主屬性都完全函數(shù)依賴于R的碼，則R2NF。例：SLC(Sno, Sdept, Sloc, Cno, Grade) 1NF SLC(Sno, Sdept, Sl

16、oc, Cno, Grade) 2NF SC（Sno， Cno， Grade） 2NF SL（Sno， Sdept， Sloc） 2NF第37頁/共137頁 第二范式（續(xù)） 采用投影分解法將一個1NF的關系分解為多個2NF的關系，可以在一定程度上減輕原1NF關系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復雜等問題。 將一個1NF關系分解為多個2NF的關系，并不能完全消除關系模式中的各種異常情況和數(shù)據(jù)冗余。第38頁/共137頁例：2NF關系模式SL(Sno, Sdept, Sloc)中函數(shù)依賴： SnoSdept SdeptSloc SnoSlocSloc傳遞函數(shù)依賴于Sno，即SL中存在非

17、主屬性對碼的傳遞函數(shù)依賴。第39頁/共137頁 3NF函數(shù)依賴圖：SLSnoSdeptSloc第40頁/共137頁 3NF 解決方法 采用投影分解法，把SL分解為兩個關系模式，以消除傳遞函數(shù)依賴： SD（Sno， Sdept） DL（Sdept， Sloc）SD的碼為Sno， DL的碼為Sdept。第41頁/共137頁 3NFSD的碼為Sno， DL的碼為Sdept。SnoSdeptSDSdeptSlocDL第42頁/共137頁 3NF 3NF的定義定義5.8 關系模式R 中若不存在這樣的碼X、屬性組Y及非主屬性Z（Z Y）, 使得XY，Y X，YZ，成立，則稱R 3NF。例， SL(Sno,

18、 Sdept, Sloc) 2NF SL(Sno, Sdept, Sloc) 3NF SD（Sno， Sdept） 3NF DL（Sdept， Sloc） 3NF第43頁/共137頁 3NF 若R3NF，則R的每一個非主屬性既不部分函數(shù)依賴于候選碼也不傳遞函數(shù)依賴于候選碼。 如果R3NF，則R也是2NF。 采用投影分解法將一個2NF的關系分解為多個3NF的關系，可以在一定程度上解決原2NF關系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復雜等問題。 將一個2NF關系分解為多個3NF的關系后，并不能完全消除關系模式中的各種異常情況和數(shù)據(jù)冗余。第44頁/共137頁范式（BCNF） 定義5.9 設

19、關系模式R1NF，如果對于R的每個函數(shù)依賴XY，若Y不屬于X，則X必含有候選碼，那么RBCNF。若RBCNF 每一個決定屬性集（因素）都包含（候選）碼 R中的所有屬性（主，非主屬性）都完全函數(shù)依賴于碼 R3NF（證明） 若R3NF 則 R不一定BCNF第45頁/共137頁 BCNF例：在關系模式STJ（S，T，J）中，S表示學生，T表示教師，J表示課程。 每一教師只教一門課。每門課由若干教師教，某一學生選定某門課，就確定了一個固定的教師。某個學生選修某個教師的課就確定了所選課的名稱 ： (S，J)T，(S，T)J，TJ第46頁/共137頁 SJTSTJSTJ第47頁/共137頁BCNFSTJ3

20、NF (S，J)和(S，T)都可以作為候選碼 S、T、J都是主屬性STJBCNF TJ，T是決定屬性集，T不是候選碼第48頁/共137頁BCNF解決方法：將STJ分解為二個關系模式： SJ(S，J) BCNF， TJ(T，J) BCNF 沒有任何屬性對碼的部分函數(shù)依賴和傳遞函數(shù)依賴SJSTTJTJ第49頁/共137頁3NF與BCNF的關系 如果關系模式RBCNF， 必定有R3NF 如果R3NF，且R只有一個候選碼， 則R必屬于BCNF。第50頁/共137頁BCNF的關系模式所具有的性質 所有非主屬性都完全函數(shù)依賴于每個候選碼 所有主屬性都完全函數(shù)依賴于每個不包含它的候選碼 沒有任何屬性完全函數(shù)

21、依賴于非碼的任何一組屬性第51頁/共137頁多值依賴與第四范式（4NF）例: 學校中某一門課程由多個教師講授，他們使用相同的一套參考書。關系模式Teaching(C, T, B) 課程C、教師T 和 參考書B第52頁/共137頁課 程 C教 員 T參 考 書 B 物理 數(shù)學 計算數(shù)學李 勇王 軍 李 勇張 平 張 平周 峰 普通物理學光學原理 物理習題集 數(shù)學分析微分方程高等代數(shù) 數(shù)學分析 表4.1第53頁/共137頁普通物理學光學原理物理習題集普通物理學光學原理物理習題集數(shù)學分析微分方程高等代數(shù)數(shù)學分析微分方程高等代數(shù)李 勇李 勇李 勇王 軍王 軍王 軍李 勇李 勇李 勇張 平張 平張 平

22、物 理物 理物 理物 理物 理物 理數(shù) 學數(shù) 學數(shù) 學數(shù) 學數(shù) 學數(shù) 學 參考書B教員T課程C用二維表表示Teaching 第54頁/共137頁多值依賴與第四范式（續(xù)） TeachingBCNF: Teach具有唯一候選碼(C，T，B)， 即全碼 Teaching模式中存在的問題 (1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲多少次 第55頁/共137頁多值依賴與第四范式（續(xù)） (2)插入操作復雜：當某一課程增加一名任課教師時，該課程有多少本參照書，就必須插入多少個元組例如物理課增加一名教師劉關，需要插入兩個元組： （物理，劉關，普通物理學） （物理，劉關，光學原理）第56頁/共137頁

23、多值依賴與第四范式（續(xù)）(3) 刪除操作復雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個元組(4) 修改操作復雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個元組 產生原因存在多值依賴第57頁/共137頁一、多值依賴 定義5.10 設R(U)是一個屬性集U上的一個關系模式， X、 Y和Z是U的子集，并且ZUXY，多值依賴 XY成立當且僅當對R的任一關系r，r在（X，Z）上的每個值對應一組Y的值，這組值僅僅決定于X值而與Z值無關 例 Teaching（C, T, B） 對于C的每一個值，T有一組值與之對應，而不論B取何值第58頁/共137頁一、多值依賴 在R

24、（U）的任一關系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值所得的兩個新元組必在r中），則Y多值依賴于X，記為XY。 這里，X，Y是U的子集，Z=U-X-Y。 t x y1 z2 s x y2 z1 w x y1 z1 v x y2 z2第59頁/共137頁多值依賴（續(xù)） 平凡多值依賴和非平凡的多值依賴若XY，而Z，則稱 XY為平凡的多值依賴否則稱XY為非平凡的多值依賴第60頁/共137頁多值依賴的性質（1）多值依賴具有對稱性 若XY，則XZ，

25、其中ZUXY 多值依賴的對稱性可以用完全二分圖直觀地表示出來。（2）多值依賴具有傳遞性 若XY，YZ， 則XZ -Y第61頁/共137頁多值依賴的對稱性 XiZi 1 Zi 2 ZimYi 1 Yi 2 Yin第62頁/共137頁多值依賴的對稱性 物 理普通物理學 光學原理 物理習題集李勇 王軍第63頁/共137頁多值依賴（續(xù)）（3）函數(shù)依賴是多值依賴的特殊情況。 若XY，則XY。（4）若XY，XZ，則XY Z。（5）若XY，XZ，則XYZ。（6）若XY，XZ，則XY-Z，XZ -Y。第64頁/共137頁多值依賴與函數(shù)依賴的區(qū)別(1) 有效性 多值依賴的有效性與屬性集的范圍有關若XY在U上成立

26、，則在W（X Y W U）上一定成立；反之則不然，即XY在W（W U）上成立，在U上并不一定成立 多值依賴的定義中不僅涉及屬性組 X和 Y，而且涉及U中其余屬性Z。 一般地，在R（U）上若有XY在W（W U）上成立，則稱XY為R（U）的嵌入型多值依賴第65頁/共137頁多值依賴與函數(shù)依賴的區(qū)別 只要在R（U）的任何一個關系r中，元組在X和Y上的值滿足定義5.l（函數(shù)依賴）， 則函數(shù)依賴XY在任何屬性集W（X Y W U）上成立。第66頁/共137頁多值依賴（續(xù)）(2) 若函數(shù)依賴XY在R（U）上成立，則對于任何Y Y均有XY 成立 多值依賴XY若在R(U)上成立，不能斷言對于任何Y Y有XY

27、成立第67頁/共137頁二、第四范式（4NF） 定義4.10 關系模式R1NF，如果對于R的每個非平凡多值依賴XY（Y X），X都含有候選碼，則R4NF。 （XY） 如果R 4NF， 則R BCNF 不允許有非平凡且非函數(shù)依賴的多值依賴 允許的是函數(shù)依賴（是非平凡多值依賴）第68頁/共137頁第四范式（續(xù)）例： Teach(C,T,B) 4NF 存在非平凡的多值依賴CT，且C不是候選碼 用投影分解法把Teach分解為如下兩個關系模式： CT(C, T) 4NF CB(C, B) 4NF CT， CB是平凡多值依賴 第69頁/共137頁4.2 規(guī)范化第一范式（1NF）第二范式（2NF）第三范式（

28、3NF）范式（BCNF）多值依賴與第四范式（4NF）規(guī)范化第70頁/共137頁規(guī)范化 關系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設計的工具。 一個關系只要其分量都是不可分的數(shù)據(jù)項，它就是規(guī)范化的關系，但這只是最基本的規(guī)范化。 規(guī)范化程度可以有多個不同的級別第71頁/共137頁規(guī)范化（續(xù)） 規(guī)范化程度過低的關系不一定能夠很好地描述現(xiàn)實世界，可能會存在插入異常、刪除異常、修改復雜、數(shù)據(jù)冗余等問題 一個低一級范式的關系模式，通過模式分解可以轉換為若干個高一級范式的關系模式集合，這種過程就叫關系模式的規(guī)范化第72頁/共137頁規(guī)范化（續(xù)） 關系模式規(guī)范化的基本步驟 1NF 消除非主屬性對碼的部分函數(shù)依賴消除決

29、定屬性 2NF集非碼的非平 消除非主屬性對碼的傳遞函數(shù)依賴凡函數(shù)依賴 3NF 消除主屬性對碼的部分和傳遞函數(shù)依賴 BCNF 消除非平凡且非函數(shù)依賴的多值依賴 4NF第73頁/共137頁規(guī)范化的基本思想 消除不合適的數(shù)據(jù)依賴 的各關系模式達到某種程度的“分離” 采用“一事一地”的模式設計原則 讓一個關系描述一個概念、一個實體或者實體間的一種聯(lián)系。若多于一個概念就把它“分離”出去 所謂規(guī)范化實質上是概念的單一化第74頁/共137頁規(guī)范化（續(xù)） 不能說規(guī)范化程度越高的關系模式就越好 在設計數(shù)據(jù)庫模式結構時，必須對現(xiàn)實世界的實際情況和用戶應用需求作進一步分析，確定一個合適的、能夠反映現(xiàn)實世界的模式 上

30、面的規(guī)范化步驟可以在其中任何一步終止第75頁/共137頁第四章 關系數(shù)據(jù)理論4.1 數(shù)據(jù)依賴4.2 規(guī)范化4.3 數(shù)據(jù)依賴的公理系統(tǒng)4.4 模式的分解第76頁/共137頁4.3 數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊含定義5.11 對于滿足一組函數(shù)依賴 F 的關系模式R ，其任何一個關系r，若函數(shù)依賴XY都成立, 則稱 F邏輯蘊含X Y第77頁/共137頁Armstrong公理系統(tǒng) 一套推理規(guī)則，是模式分解算法的理論基礎 用途 求給定關系模式的碼 從一組函數(shù)依賴求得蘊含的函數(shù)依賴第78頁/共137頁1. Armstrong公理系統(tǒng) 關系模式R 來說有以下的推理規(guī)則： Al.自反律（Reflexivity）：

31、 若Y X U，則X Y為F所蘊含。 A2.增廣律（Augmentation）：若XY為F所蘊含，且Z U，則XZYZ為F所蘊含。 A3.傳遞律（Transitivity）：若XY及YZ為F所蘊含，則XZ為F所蘊含。注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F第79頁/共137頁（l）自反律:若Y X U，則X Y為F所蘊含證: 設Y X U 對R 的任一關系r中的任意兩個元組t，s：若tX=sX，由于Y X，有ty=sy，所以XY成立.自反律得證定理4.1 Armstrong推理規(guī)則是正確的第80頁/共137頁(2)增廣律: 若XY為F所蘊含，且Z U，則XZY

32、Z 為F所蘊含。 證：設XY為F所蘊含，且Z U。 設R 的任一關系r中任意的兩個元組t，s；若tXZ=sXZ，則有tX=sX和tZ=sZ；由XY，于是有tY=sY，所以tYZ=sYZ，所以XZYZ為F所蘊含.增廣律得證。第81頁/共137頁(3) 傳遞律：若XY及YZ為F所蘊含，則 XZ為 F所蘊含。證：設XY及YZ為F所蘊含。對R 的任一關系 r中的任意兩個元組 t，s。若tX=sX，由于XY，有 tY=sY；再由YZ，有tZ=sZ，所以XZ為F所蘊含.傳遞律得證。第82頁/共137頁2. 導出規(guī)則1.根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： 合并規(guī)則：由XY，XZ，有

33、XYZ。 （A2， A3） 偽傳遞規(guī)則：由XY，WYZ，有XWZ。 （A2， A3） 分解規(guī)則：由XY及 ZY，有XZ。 （A1， A3）第83頁/共137頁導出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理5.1 引理5.l XA1 A2Ak成立的充分必要條件是XAi成立（i=l，2，k）。第84頁/共137頁3. 函數(shù)依賴閉包定義4.l2 在關系模式R中為F所邏輯蘊含的函數(shù)依賴的全體叫作 F的閉包，記為F+。定義4.13 設F為屬性集U上的一組函數(shù)依賴，X U， XF+ = A|XA能由F 根據(jù)Armstrong公理導出，XF+稱為屬性集X關于函數(shù)依賴集F 的閉包第85頁/共137頁關于閉包的引

34、理 引理4.2 設F為屬性集U上的一組函數(shù)依賴，X，Y U，XY能由F 根據(jù)Armstrong公理導出的充分必要條件是Y XF+ 用途 將判定XY是否能由F根據(jù)Armstrong公理導出的問題， 就轉化為求出XF+ ，判定Y是否為XF+的子集的問題第86頁/共137頁求閉包的算法算法4.l 求屬性集X（X U）關于U上的函數(shù)依 賴集F 的閉包XF+ 輸入：X，F(xiàn)輸出：XF+步驟：（1）令X（0）=X，i=0（2）求B，這里B = A |( V)( W)(VWF V X（i）A W)；（3）X（i+1）=BX（i） 第87頁/共137頁算法4.l（4）判斷X（i+1）= X （i）嗎?（5）若相

35、等或X（i）=U , 則X（i）就是XF+ , 算法終止。（6）若否，則 i=i+l，返回第（2）步。對于算法5.l， 令ai =|X（i）|，ai 形成一個步長大于1的嚴格遞增的序列，序列的上界是 | U |，因此該算法最多 |U| - |X| 次循環(huán)就會終止。第88頁/共137頁 Define XF+ = closure of X = set of attributes functionally determined byX Basis: XF+ :=X Induction: If Y XF+, and Y A is a given FD, then add A to XF+ End wh

36、en XF+ cannot be changed.AlgorithmyX+New X+A第89頁/共137頁 U=A, B, C, D; F=A B, BC D; A+ = AB. C+ = C. (AC)+ = ABCD.ExampleACB第90頁/共137頁 ExampleACDBU=A, B, C, D; A B, BC D.(AC)+ = ABCD.第91頁/共137頁函數(shù)依賴閉包例1 已知關系模式R，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，ACB。求（AB）F+ 。解 設X（0）=AB；(1)計算X（1）: 逐一的掃描F集合中各個函數(shù)依賴， 找左部為A，B或AB

37、的函數(shù)依賴。得到兩個： ABC，BD。 于是X（1）=ABCD=ABCD。第92頁/共137頁函數(shù)依賴閉包(2)因為X（0） X（1） ，所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到ABC，BD， CE，ACB， 于是X（2）=X（1）BCDE=ABCDE。(3)因為X（2）=U，算法終止所以（AB）F+ =ABCDE。第93頁/共137頁4. Armstrong公理系統(tǒng)的有效性與完備性 有效性：由F出發(fā)根據(jù)Armstrong公理推導出來的每一個函數(shù)依賴一定在F+中 /* Armstrong正確 完備性：F+中的每一個函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導出來 /* A

38、rmstrong公理夠用，完全完備性：所有不能用Armstrong公理推導出來f, 都不為真 若 f 不能用Armstrong公理推導出來， f F+ 第94頁/共137頁有效性與完備性的證明證明：1. 有效性 可由定理5.l得證2. 完備性只需證明逆否命題: 若函數(shù)依賴XY不能由F從Armstrong公理導出，那么它必然不為F所蘊含分三步證明：第95頁/共137頁有效性與完備性的證明(1)引理: 若VW成立，且V XF+，則W XF+ 證 因為 V XF+ ，所以有XV成立； 因為X V，VW，于是XW成立 所以W XF+ (2)/* 若 f 不能用Armstrong公理推導出來， f F+

39、 /* 若存在r， F+中的全部函數(shù)依賴在 r上成立。 /* 而不能用Armstrong公理推導出來的f , 在r上不成立。 構造一張二維表r，它由下列兩個元組構成，可以證明r必是R（U，F(xiàn)）的一個關系，即F+中的全部函數(shù)依賴在 r上成立。 第96頁/共137頁Armstrong公理系統(tǒng)的有效性與完備性(續(xù)) XF+ U-XF+ 11.1 00.0 11.1 11.1 若r不是R 的關系，則必由于F中有函數(shù)依賴VW在r上不成立所致。由r的構成可知，V必定是XF+ 的子集，而W不是XF+ 的子集，可是由第（1）步，W XF+，矛盾。所以r必是R的一個關系。 第97頁/共137頁Armstrong

40、公理系統(tǒng)的有效性與完備性(續(xù))(3) )/* 若 f 不能用Armstrong公理推導出來， f F+ /* 而不能用Armstrong公理推導出來的 f , 在r上不成立。 若XY 不能由F從Armstrong公理導出，則Y 不是 XF+ 的子集。（引理5.2） 因此必有Y 的子集Y 滿足 Y U-XF+， 則XY在 r 中不成立，即XY必不為 R 蘊含 /* 因為 F+中的全部函數(shù)依賴在 r上成立。第98頁/共137頁Armstrong公理系統(tǒng)的有效性與完備性(續(xù))Armstrong公理的完備性及有效性說明:“蘊含” = “導出” 等價的概念 F+ =由F出發(fā)借助Armstrong公理導出

41、的函數(shù)依賴的集合第99頁/共137頁5. 函數(shù)依賴集等價定義4.14 如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價。第100頁/共137頁函數(shù)依賴集等價的充要條件引理4.3 F+ = G+ 的充分必要條件是 F G+ ，和G F+ 證: 必要性顯然，只證充分性。（1）若FG+ ，則XF+ XG+ 。（2）任取XYF+ 則有 Y XF+ XG+ 。 所以XY (G+）+= G+。即F+ G+。（3）同理可證G+ F+ ，所以F+ = G+。第101頁/共137頁函數(shù)依賴集等價 要判定F G+，只須逐一對F中的函數(shù)依賴XY，考察 Y 是否屬于XG+ 就行了。

42、因此引理5.3 給出了判斷兩個函數(shù)依賴集等價的可行算法。 第102頁/共137頁6. 最小依賴集 定義4.15 如果函數(shù)依賴集F滿足下列條件，則稱F為一個極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。 (1) F中任一函數(shù)依賴的右部僅含有一個屬性。 (2) F中不存在這樣的函數(shù)依賴XA，使得F與F-XA等價。 (3) F中不存在這樣的函數(shù)依賴XA， X有真 子集Z使得F-XAZA與F等價。 第103頁/共137頁最小依賴集例2 對于5.l節(jié)中的關系模式S，其中： U= SNO，SDEPT，MN，CNAME，G ， F= SNOSDEPT，SDEPTMN， （SNO，CNAME）G 設F=SNOS

43、DEPT，SNOMN， SDEPTMN，(SNO，CNAME)G， (SNO，SDEPT)SDEPTF是最小覆蓋，而F 不是。因為：F -SNOMN與F 等價 F -(SNO，SDEPT)SDEPT也與F 等價 F -(SNO，SDEPT)SDEPT SNOSDEPT也與F 等價第104頁/共137頁7. 極小化過程定理4.3 每一個函數(shù)依賴集F均等價于一個極小 函數(shù)依賴集Fm。此Fm稱為F的最小依賴集證:構造性證明，依據(jù)定義分三步對F進行“極小化處理”，找出F的一個最小依賴集。(1)逐一檢查F中各函數(shù)依賴FDi：XY， 若Y=A1A2 Ak，k 2， 則用 XAj |j=1，2， k 來取代

44、XY。 引理5.1保證了F變換前后的等價性。第105頁/共137頁極小化過程(2)逐一檢查F中各函數(shù)依賴FDi：XA， 令G=F-XA， 若AXG+， 則從F中去掉此函數(shù)依賴。 由于F與G =F-XA等價的充要條件是AXG+ 因此F變換前后是等價的。第106頁/共137頁極小化過程(3)逐一取出F中各函數(shù)依賴FDi：XA， 設X=B1B2Bm， 逐一考查Bi （i=l，2，m）， 若A （X-Bi ）F+ ， 則以X-Bi 取代X。 由于F與F-XAZA等價的充要條件是AZF+ ，其中Z=X-Bi 因此F變換前后是等價的。第107頁/共137頁極小化過程由定義，最后剩下的F就一定是極小依賴集。

45、 因為對F的每一次“改造”都保證了改造前后的兩個函數(shù)依賴集等價，因此剩下的F與原來的F等價。 證畢 定理5.3的證明過程 也是求F極小依賴集的過程第108頁/共137頁極小化過程例3 F = AB，BA，BC， AC，CA Fm1、Fm2都是F的最小依賴集： Fm1= AB，BC，CA Fm2= AB，BA，AC，CA F的最小依賴集Fm不一定是唯一的它與對各函數(shù)依賴FDi 及XA中X各屬性的處置順序有關第109頁/共137頁極小化過程 極小化過程( 定理4.3的證明 )也是檢驗F是否為極小依賴集的一個算法 若改造后的F與原來的F相同，說明F本身就是一個最小依賴集第110頁/共137頁極小化過

46、程 在R中可以用與F等價的依賴集G來取代F 原因：兩個關系模式R1 ，R2，如果F與G等價，那么R1的關系一定是R2的關系。反過來，R2的關系也一定是R1的關系。 第111頁/共137頁第四章 關系數(shù)據(jù)理論4.1 數(shù)據(jù)依賴4.2 規(guī)范化4.3 數(shù)據(jù)依賴的公理系統(tǒng)4.4 模式的分解第112頁/共137頁4.4 模式的分解 把低一級的關系模式分解為若干個高一級的關系模式的方法并不是唯一的 只有能夠保證分解后的關系模式與原關系模式等價，分解方法才有意義第113頁/共137頁關系模式分解的標準三種模式分解的等價定義 分解具有無損連接性 分解要保持函數(shù)依賴 分解既要保持函數(shù)依賴，又要具有無損連接性第11

47、4頁/共137頁模式的分解（續(xù)）定義定義4.16 關系模式R的一個分解：= R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，F(xiàn)i 為 F在 Ui 上的投影定義定義4.17 函數(shù)依賴集合XY | XY F+XY Ui 的一個覆蓋 Fi 叫作 F 在屬性 Ui 上的投影第115頁/共137頁模式的分解（續(xù)）例: SL（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSloc SL2NF 存在插入異常、刪除異常、冗余度大和修改復雜等問題分解方法可以有多種 第116頁/共137頁模式的分解（續(xù)）SL SnoSdeptSloc 95001 CS A 950

48、02 IS B 95003 MA C 95004 IS B 95005 PH B 第117頁/共137頁模式的分解（續(xù)）1. SL分解為下面三個關系模式： SN(Sno) SD(Sdept) SO(Sloc)第118頁/共137頁分解后的關系為： SN SD SO S n o S d e p t Sloc 95001 CS A 95002 IS B 95003 MA C 9 5 0 0 4 P H 95005 第119頁/共137頁模式的分解（續(xù)）分解后的數(shù)據(jù)庫丟失了許多信息 例如無法查詢95001學生所在系或所在宿舍。 如果分解后的關系可以通過自然連接恢復為原來的關系，那么這種分解就沒有丟失

49、信息第120頁/共137頁模式的分解（續(xù)）2. SL分解為下面二個關系模式： NL(Sno, Sloc) DL(Sdept, Sloc)分解后的關系為： NL DL Sno Sloc Sdept Sloc 95001 A CS A 95002 B IS B 95003 C MA C 95004 B PH B 95005 B 第121頁/共137頁模式的分解（續(xù)）NL DL Sno Sloc Sdept 95001 A CS 95002 B IS 95002 B PH 95003 C MA 95004 B IS 95004 B PH 95005 B IS 95005 B PH 第122頁/共137頁模式的分解（續(xù)）NL DL比原來的SL關系多了3個元組 無法知道95002、95004、95005 究竟是哪個系的學生 元組增加了，信息丟失了第123頁/