第五章 關系數(shù)據(jù)理論

第五章關系數(shù)據(jù)理論第一頁，共七十九頁，編輯于2023年，星期四5.1問題的提出關系數(shù)據(jù)庫邏輯設計針對具體問題，如何構造一個適合于它的數(shù)據(jù)模式數(shù)據(jù)庫邏輯設計的工具──關系數(shù)據(jù)庫的規(guī)范化理論第二頁，共七十九頁，編輯于2023年，星期四一、概念回顧關系：描述實體、屬性、實體間的聯(lián)系。從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個子集。關系模式：用來定義關系。關系數(shù)據(jù)庫：基于關系模型的數(shù)據(jù)庫，利用關系來描述現(xiàn)實世界。從形式上看，它由一組關系組成。關系數(shù)據(jù)庫的模式：定義這組關系的關系模式的全體。第三頁，共七十九頁，編輯于2023年，星期四二、關系模式的形式化定義關系模式由五部分組成，即它是一個五元組：

R(U,D,DOM,F)R：關系名U：組成該關系的屬性名集合D：屬性組U中屬性所來自的域DOM：屬性向域的映象集合F：屬性間數(shù)據(jù)的依賴關系集合第四頁，共七十九頁，編輯于2023年，星期四三、什么是數(shù)據(jù)依賴1.完整性約束的表現(xiàn)形式限定屬性取值范圍：例如學生成績必須在0-100之間定義屬性值間的相互關連（主要體現(xiàn)于值的相等與否），這就是數(shù)據(jù)依賴，它是數(shù)據(jù)庫模式設計的關鍵第五頁，共七十九頁，編輯于2023年，星期四數(shù)據(jù)依賴2.數(shù)據(jù)依賴是通過一個關系中屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間的相互關系是現(xiàn)實世界屬性間相互聯(lián)系的抽象是數(shù)據(jù)內在的性質是語義的體現(xiàn)第六頁，共七十九頁，編輯于2023年，星期四數(shù)據(jù)依賴的類型3.數(shù)據(jù)依賴的類型函數(shù)依賴（FunctionalDependency，簡記為FD）多值依賴（MultivaluedDependency，簡記為MVD）其他第七頁，共七十九頁，編輯于2023年，星期四四、關系模式的簡化表示關系模式R（U,D,DOM,F）簡化為一個三元組：

R（U,F）當且僅當U上的一個關系r滿足F時，r稱為關系模式R（U,F）的一個關系第八頁，共七十九頁，編輯于2023年，星期四五、數(shù)據(jù)依賴對關系模式的影響例：描述學校的數(shù)據(jù)庫：

學生的學號（Sno）、所在系（Sdept） 系主任姓名（Mname）、課程名（Cname） 成績（Grade）單一的關系模式：Student<U、F>U＝｛Sno,Sdept,Mname,Cname,Grade｝第九頁，共七十九頁，編輯于2023年，星期四數(shù)據(jù)依賴對關系模式的影響學校數(shù)據(jù)庫的語義：

⒈一個系有若干學生，一個學生只屬于一個系；⒉一個系只有一名主任；⒊一個學生可以選修多門課程，每門課程有若干學生選修；⒋每個學生所學的每門課程都有一個成績。

第十頁，共七十九頁，編輯于2023年，星期四數(shù)據(jù)依賴對關系模式的影響

屬性組U上的一組函數(shù)依賴F：

F＝｛Sno→Sdept,Sdept→Mname,(Sno,Cname)→Grade｝

SnoCnameSdeptMnameGrade第十一頁，共七十九頁，編輯于2023年，星期四關系模式Student<U,F>中存在的問題⒈數(shù)據(jù)冗余太大浪費大量的存儲空間

例：每一個系主任的姓名重復出現(xiàn)⒉更新異常（UpdateAnomalies）數(shù)據(jù)冗余，更新數(shù)據(jù)時，維護數(shù)據(jù)完整性代價大。 例：某系更換系主任后，系統(tǒng)必須修改與該系學生有關的每一個元組第十二頁，共七十九頁，編輯于2023年，星期四關系模式Student<U,F>中存在的問題⒊插入異常（InsertionAnomalies）該插的數(shù)據(jù)插不進去例，如果一個系剛成立，尚無學生，我們就無法把這個系及其系主任的信息存入數(shù)據(jù)庫。⒋刪除異常（DeletionAnomalies）不該刪除的數(shù)據(jù)不得不刪 例，如果某個系的學生全部畢業(yè)了，我們在刪除該系學生信息的同時，把這個系及其系主任的信息也丟掉了。第十三頁，共七十九頁，編輯于2023年，星期四數(shù)據(jù)依賴對關系模式的影響結論：Student關系模式不是一個好的模式?！昂谩钡哪Ｊ剑翰粫l(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應盡可能少。原因：由存在于模式中的某些數(shù)據(jù)依賴引起的解決方法：通過分解關系模式來消除其中不合適的數(shù)據(jù)依賴。第十四頁，共七十九頁，編輯于2023年，星期四規(guī)范化

規(guī)范化理論正是用來改造關系模式，通過分解關系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。第十五頁，共七十九頁，編輯于2023年，星期四5.2規(guī)范化

數(shù)據(jù)依賴：關系中屬性值之間的這種相互依賴又相互制約的聯(lián)系，稱為數(shù)據(jù)依賴。包括：函數(shù)依賴、多值依賴。一、函數(shù)依賴定義1：設R(U)是屬性集U上的關系模式。X，Y是U的子集。若對于R(U)的任意一個可能的關系r，r中不可能存在兩個元組在X上的屬性值相等，而在Y上的屬性值不等，則稱X函數(shù)決定Y或Y函數(shù)依賴于X，記作X→Y。第十六頁，共七十九頁，編輯于2023年，星期四說明：

1.函數(shù)依賴不是指關系模式R的某個或某些關系實例滿足的約束條件，而是指R的所有關系實例均要滿足的約束條件。2.函數(shù)依賴是語義范疇的概念。只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴。例如“姓名→年齡”這個函數(shù)依賴只有在不允許有同名人的條件下成立3.數(shù)據(jù)庫設計者可以對現(xiàn)實世界作強制的規(guī)定。例如規(guī)定不允許同名人出現(xiàn)，函數(shù)依賴“姓名→年齡”成立。所插入的元組必須滿足規(guī)定的函數(shù)依賴，若發(fā)現(xiàn)有同名人存在，則拒絕裝入該元組。第十七頁，共七十九頁，編輯于2023年，星期四根據(jù)函數(shù)依賴的定義，可找出下面規(guī)律：1、在一個關系模式中，如屬性X，Y有1：1聯(lián)系，則存在函數(shù)依賴X→Y、Y→X，可記作XY2、X、Y是1：m聯(lián)系，則存在Y→X，但X→Y3、X、Y是n:m聯(lián)系，則X、Y之間不存在任何函數(shù)依賴第十八頁，共七十九頁，編輯于2023年，星期四平凡函數(shù)依賴與非平凡函數(shù)依賴于任一關系模式，平凡函數(shù)依賴都是必然成立的，它不反映新的語義，因此若不特別聲明，我們總是討論非平凡函數(shù)依賴。X→Y，但YX則稱X→Y是平凡的函數(shù)依賴。否則，稱非平凡的函數(shù)依賴。第十九頁，共七十九頁，編輯于2023年，星期四定義2：在R（U）中，如果X→Y，并且對于X的任何一個真子集X′，都有X′→Y，則稱Y對X部分函數(shù)依賴，否則，稱Y完全函數(shù)依賴于X。定義3：在R（U）中，如果X→Y，（YX），Y→X，Y→Z，則稱Z對X傳遞函數(shù)依賴。第二十頁，共七十九頁，編輯于2023年，星期四定義4：設K為R<U，F(xiàn)>中的屬性或屬性組合，若K→U則K為R的候選碼。若候選碼多于一個，則選定其中的一個為主碼（PrimaryKey）。包含在任何一個候選碼中的屬性，叫做主屬性。不包含在任何碼中的屬性稱為非主屬性或非碼屬性。整個屬性組是碼，稱為全碼。定義5：關系模式R中屬性或屬性組X并非R的碼，但X是另一個關系模式的碼，則稱X是R的外部碼（ForeignKey），也稱外碼。二、碼f第二十一頁，共七十九頁，編輯于2023年，星期四5.2.3范式范式是符合某一種級別的關系模式的集合。關系數(shù)據(jù)庫中的關系必須滿足一定的要求。滿足不同程度要求的為不同范式。范式的種類：

第一范式(1NF) 第二范式(2NF) 第三范式(3NF) BC范式(BCNF) 第四范式(4NF) 第五范式(5NF)第二十二頁，共七十九頁，編輯于2023年，星期四三、范式各種范式之間存在聯(lián)系：某一關系模式R為第n范式，可簡記為R∈nNF。第二十三頁，共七十九頁，編輯于2023年，星期四1NF的定義 如果一個關系模式R的所有屬性都是不可分的基本數(shù)據(jù)項，則R∈1NF。第一范式是對關系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫模式不能稱為關系數(shù)據(jù)庫。但是滿足第一范式的關系模式并不一定是一個好的關系模式。第二十四頁，共七十九頁，編輯于2023年，星期四四、2NF定義6：若R1NF，且每一個非主屬性完全函數(shù)依賴于碼，則R2NF。SNOCNOGSDEPTSLOC第二十五頁，共七十九頁，編輯于2023年，星期四不是2NF的SLC不是一個好的關系模式(1)插入異常 假設Sno＝95102，Sdept＝IS，Sloc＝N的學生還未選課，因課程號是主屬性，因此該學生的信息無法插入SLC。(2)刪除異常假定某個學生本來只選修了3號課程這一門課?，F(xiàn)在因身體不適，他連3號課程也不選修了。因課程號是主屬性，此操作將導致該學生信息的整個元組都要刪除。

第二十六頁，共七十九頁，編輯于2023年，星期四SLC不是一個好的關系模式(3)數(shù)據(jù)冗余度大如果一個學生選修了10門課程，那么他的Sdept和Sloc值就要重復存儲了10次。(4)修改復雜例如學生轉系，在修改此學生元組的Sdept值的同時，還可能需要修改住處（Sloc）。如果這個學生選修了K門課，則必須無遺漏地修改K個元組中全部Sdept、Sloc信息。

第二十七頁，共七十九頁，編輯于2023年，星期四原因Sdept、Sloc部分函數(shù)依賴于碼。解決方法SLC分解為兩個關系模式，以消除這些部分函數(shù)依賴

SC（Sno，Cno，Grade）SL（Sno，Sdept，Sloc）第二十八頁，共七十九頁，編輯于2023年，星期四采用投影分解法將一個1NF的關系分解為多個2NF的關系，可以在一定程度上減輕原1NF關系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復雜等問題。將一個1NF關系分解為多個2NF的關系，并不能完全消除關系模式中的各種異常情況和數(shù)據(jù)冗余。第二十九頁，共七十九頁，編輯于2023年，星期四五、3NF定義7：若R2NF，且R中任一非主屬性都不傳遞函數(shù)依賴于碼，則R3NF。SNOCNOGSDEPTSLOCSNOSLSC上例SL分解為：SD（SNO，SDEPT）DL（SDEPT，SLOC）由于第三范式有效地消除了非主屬性對碼的部分和傳遞依賴，因而消除了一大類操作異常問題。因此，3NF在數(shù)據(jù)庫設計中得到了廣泛應用。第三十頁，共七十九頁，編輯于2023年，星期四若R∈3NF，則R的每一個非主屬性既不部分函數(shù)依賴于候選碼也不傳遞函數(shù)依賴于候選碼。如果R∈3NF，則R也是2NF。采用投影分解法將一個2NF的關系分解為多個3NF的關系，可以在一定程度上解決原2NF關系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復雜等問題。將一個2NF關系分解為多個3NF的關系后，并不能完全消除關系模式中的各種異常情況和數(shù)據(jù)冗余。第三十一頁，共七十九頁，編輯于2023年，星期四六、BCNF定義8：RBCNF，當且僅當每個決定因素都是碼（候選鍵）。⒈所有非主屬性都完全函數(shù)依賴于每個候選碼⒉所有主屬性都完全函數(shù)依賴于每個不包含它的候選碼⒊沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性第三十二頁，共七十九頁，編輯于2023年，星期四例：關系模式STJ（S，T，J）中，S表示學生，T表示教師，J表示教師，J表示課程。每一教師只教一門課。每門課有若干教師，某一學生選定某門課，就對應一個固定的教師。由語義可得到如下的函數(shù)依賴：（S，J）→T；（S，T）→J；T→J關系有兩個候選鍵，是（S，J）和（S，T）第三十三頁，共七十九頁，編輯于2023年，星期四S、T、J都是主屬性，不存在非主屬性，更不會有非主屬性對鍵的傳遞依賴、部分依賴了，因此，STJ關系滿足第三范式。但仍然存在問題：上例分解為：ST（S，T）、TJ（T，J）第三十四頁，共七十九頁，編輯于2023年，星期四七、多值依賴例：學校中某一門課程由多個教員講授，他們使用相同的一套參考書。每個教員可以講授多門課程，每種參考書可以供多門課程使用。如下表：

課程C教員T參考書B物理李勇普通物理學物理李勇光學原理物理李勇物理習題集物理王軍普通物理學物理王軍光學原理物理王軍物理習題集數(shù)學李勇數(shù)學分析數(shù)學李勇微分方程數(shù)學李勇高等代數(shù)數(shù)學張平數(shù)學分析數(shù)學張平微分方程數(shù)學張平高等代數(shù)┇┇┇第三十五頁，共七十九頁，編輯于2023年，星期四………課程C教員T參考書B

物理

數(shù)學

計算數(shù)學李勇王軍

李勇張平

張平周峰

普通物理學光學原理物理習題集

數(shù)學分析微分方程高等代數(shù)

數(shù)學分析

第三十六頁，共七十九頁，編輯于2023年，星期四Teaching∈BCNF:Teach具有唯一候選碼(C，T，B)，即全碼Teaching模式中存在的問題(1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲多少次

第三十七頁，共七十九頁，編輯于2023年，星期四

(2)插入操作復雜：當某一課程增加一名任課教師時，該課程有多少本參照書，就必須插入多少個元組例如物理課增加一名教師劉關，需要插入兩個元組：

（物理，劉關，普通物理學）（物理，劉關，光學原理）第三十八頁，共七十九頁，編輯于2023年，星期四(3)刪除操作復雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個元組(4)修改操作復雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個元組產(chǎn)生原因 存在多值依賴第三十九頁，共七十九頁，編輯于2023年，星期四定義9：關系模式R（U），X，Y，Z是U的子集，并且Z=U-X-Y。關系模式R(U)中多值依賴XY成立，當且僅當對R（U）的任一關系r，給定的一對（x，z)值，有一組Y的值，這組值僅僅決定于x值而與z值無關。若XY，而Z=即Z為空，則稱XY為平凡的多值依賴。第四十頁，共七十九頁，編輯于2023年，星期四多值依賴性質：⑴對稱性。若XY，則XZ，其中Z=U－Ｘ－Ｙ。⑵傳遞性。若XY，ＹＺ，則XＺ－Y。⑶函數(shù)依賴可看作是多值依賴的特殊情況。若XY，則XY。⑷若XY，XＺ，則XYＺ。⑸若XY，XＺ，則XYＺ。⑹若XY，XＺ，則XY－Ｚ，XＺ－Y。第四十一頁，共七十九頁，編輯于2023年，星期四多值依賴的對稱性

XiZi1Zi2…ZimYi1Yi2…Yin第四十二頁，共七十九頁，編輯于2023年，星期四多值依賴的對稱性

物理普通物理學光學原理物理習題集李勇王軍第四十三頁，共七十九頁，編輯于2023年，星期四多值依賴與函數(shù)依賴的區(qū)別(1)有效性多值依賴的有效性與屬性集的范圍有關若X→→Y在U上成立，則在W（XYWU）上一定成立；反之則不然，即X→→Y在W（WU）上成立，在U上并不一定成立多值依賴的定義中不僅涉及屬性組X和Y，而且涉及U中其余屬性Z。一般地，在R（U）上若有X→→Y在W（WU）上成立，則稱X→→Y為R（U）的嵌入型多值依賴第四十四頁，共七十九頁，編輯于2023年，星期四多值依賴與函數(shù)依賴的區(qū)別只要在R（U）的任何一個關系r中，元組在X和Y上的值滿足定義5.l（函數(shù)依賴），則函數(shù)依賴X→Y在任何屬性集W（XYWU）上成立。第四十五頁，共七十九頁，編輯于2023年，星期四(2)

若函數(shù)依賴X→Y在R（U）上成立，則對于任何Y'Y均有X→Y'成立多值依賴X→→Y若在R(U)上成立，不能斷言對于任何Y'Y有X→→Y'成立多值依賴與函數(shù)依賴的區(qū)別第四十六頁，共七十九頁，編輯于2023年，星期四八、4NF定義10：關系模式R<U，F(xiàn)>1NF，如果對于R的每個非平凡多值依賴XY（YX），X都含有碼，則稱R<U，F(xiàn)>4NF。第四十七頁，共七十九頁，編輯于2023年，星期四關系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設計的工具。一個關系只要其分量都是不可分的數(shù)據(jù)項，它就是規(guī)范化的關系，但這只是最基本的規(guī)范化。規(guī)范化程度可以有多個不同的級別九、規(guī)范化小結第四十八頁，共七十九頁，編輯于2023年，星期四規(guī)范化程度過低的關系不一定能夠很好地描述現(xiàn)實世界，可能會存在插入異常、刪除異常、修改復雜、數(shù)據(jù)冗余等問題一個低一級范式的關系模式，通過模式分解可以轉換為若干個高一級范式的關系模式集合，這種過程就叫關系模式的規(guī)范化第四十九頁，共七十九頁，編輯于2023年，星期四1NF↓消除非主屬性對碼的部分函數(shù)依賴2NF↓消除非主屬性對碼的傳遞函數(shù)依賴3NF↓消除主屬性對碼的部分和傳遞函數(shù)依賴BCNF↓消除非平凡且非函數(shù)依賴的多值依賴4NF第五十頁，共七十九頁，編輯于2023年，星期四規(guī)范化的基本思想消除不合適的數(shù)據(jù)依賴，各關系模式達到某種程度的“分離”采用“一事一地”的模式設計原則讓一個關系描述一個概念、一個實體或者實體間的一種聯(lián)系。若多于一個概念就把它“分離”出去所謂規(guī)范化實質上是概念的單一化第五十一頁，共七十九頁，編輯于2023年，星期四不能說規(guī)范化程度越高的關系模式就越好在設計數(shù)據(jù)庫模式結構時，必須對現(xiàn)實世界的實際情況和用戶應用需求作進一步分析，確定一個合適的、能夠反映現(xiàn)實世界的模式上面的規(guī)范化步驟可以在其中任何一步終止第五十二頁，共七十九頁，編輯于2023年，星期四練習題設有關系模式：授課表（課程號，課程名，學分，授課教師號，教師名，授課時數(shù)），其語義為：一門課程可以由多名教師講授。指出此關系模式的候選碼，判斷此關系模式屬于第幾范式，若不是第三范式，將其分解為第三范式。第五十三頁，共七十九頁，編輯于2023年，星期四5.3數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊含 定義9.11對于滿足一組函數(shù)依賴F的關系模式R<U，F(xiàn)>，其任何一個關系r，若函數(shù)依賴X→Y都成立,則稱

F邏輯蘊含X→Y第五十四頁，共七十九頁，編輯于2023年，星期四Armstrong公理系統(tǒng)一套推理規(guī)則，是模式分解算法的理論基礎用途求給定關系模式的碼從一組函數(shù)依賴求得蘊含的函數(shù)依賴第五十五頁，共七十九頁，編輯于2023年，星期四1.Armstrong公理系統(tǒng)

關系模式R<U，F(xiàn)>來說有以下的推理規(guī)則：Al.自反律（Reflexivity）：若Y

X

U，則X→Y為F所蘊含。A2.增廣律（Augmentation）：若X→Y為F所蘊含，且Z

U，則XZ→YZ為F所蘊含。A3.傳遞律（Transitivity）：若X→Y及Y→Z為F所蘊含，則X→Z為F所蘊含。 注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F第五十六頁，共七十九頁，編輯于2023年，星期四定理5.lArmstrong推理規(guī)則是正確的（l）自反律:若Y

X

U，則X→Y為F所蘊含證:設Y

X

U

對R<U，F(xiàn)>的任一關系r中的任意兩個元組t，s：若t[X]=s[X]，由于Y

X，有t[y]=s[y]，所以X→Y成立.自反律得證第五十七頁，共七十九頁，編輯于2023年，星期四(2)增廣律:若X→Y為F所蘊含，且Z

U，則XZ→YZ為F所蘊含。證：設X→Y為F所蘊含，且Z

U。設R<U，F(xiàn)>的任一關系r中任意的兩個元組t，s；若t[XZ]=s[XZ]，則有t[X]=s[X]和t[Z]=s[Z]；由X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]，所以XZ→YZ為F所蘊含.增廣律得證。第五十八頁，共七十九頁，編輯于2023年，星期四(3)傳遞律：若X→Y及Y→Z為F所蘊含，則

X→Z為F所蘊含。證：設X→Y及Y→Z為F所蘊含。對R<U，F(xiàn)>的任一關系r中的任意兩個元組t，s。若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]，所以X→Z為F所蘊含.傳遞律得證。第五十九頁，共七十九頁，編輯于2023年，星期四2.導出規(guī)則1.根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推理規(guī)則：合并規(guī)則：由X→Y，X→Z，有X→YZ。（A2，A3）

偽傳遞規(guī)則：由X→Y，WY→Z，有XW→Z。（A2，A3）

分解規(guī)則：由X→Y及ZY，有X→Z。（A1，A3）第六十頁，共七十九頁，編輯于2023年，星期四導出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理5.1引理5.lX→A1A2…Ak成立的充分必要條件是X→Ai成立（i=l，2，…，k）。第六十一頁，共七十九頁，編輯于2023年，星期四3.函數(shù)依賴閉包定義5.l2在關系模式R<U，F(xiàn)>中為F所邏輯蘊含的函數(shù)依賴的全體叫作F的閉包，記為F+。定義5.13設F為屬性集U上的一組函數(shù)依賴，X

U，

XF+={A|X→A能由F根據(jù)Armstrong公理導出}，XF+稱為屬性集X關于函數(shù)依賴集F的閉包第六十二頁，共七十九頁，編輯于2023年，星期四F的閉包F={XY,YZ},F+計算是NP完全問題，XA1A2...An

F+={Xφ,Yφ,Zφ,XYφ,XZφ,YZφ,XYZφ,XX,YY,ZZ,XYX,XZX,YZY,XYZX,XY,YZ,XYY,XZY,YZZ,XYZY,XZ,YYZ,XYZ,XZZ,YZYZ,XYZZ,XXY,XYXY,XZXY,XYZXY,XXZ,XYYZ,XZXZ,XYZYZXYZ,XYXZ,XZXY,XYZXZ,XZYZ,XYXYZ,XZXYZ,XYZXYZ}第六十三頁，共七十九頁，編輯于2023年，星期四關于閉包的引理引理5.2設F為屬性集U上的一組函數(shù)依賴，X，Y

U，X→Y能由F根據(jù)Armstrong公理導出的充分必要條件是Y

XF+用途將判定X→Y是否能由F根據(jù)Armstrong公理導出的問題，就轉化為求出XF+，判定Y是否為XF+的子集的問題第六十四頁，共七十九頁，編輯于2023年，星期四求閉包的算法算法5.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)(V→WF∧VX（i）∧A

W)}；（3）X（i+1）=B∪X（i）

第六十五頁，共七十九頁，編輯于2023年，星期四（4）判斷X（i+1）=X

（i）嗎?（5）若相等或X（i）=U,則X（i）就是XF+,算法終止。（6）若否，則i=i+l，返回第（2）步。對于算法5.l，令ai=|X（i）|，{ai

}形成一個步長大于1的嚴格遞增的序列，序列的上界是|U|，因此該算法最多|U|-|X|次循環(huán)就會終止。第六十六頁，共七十九頁，編輯于2023年，星期四

U={A,B,C,D};F={AB,BCD};A+=AB.C+=C.(AC)+=ABCD.ExampleACB第六十七頁，共七十九頁，編輯于2023年，星期四

ExampleACDBU={A,B,C,D};AB,BCD.(AC)+=ABCD.第六十八頁，共七十九頁，編輯于2023年，星期四[例1]已知關系模式R<U，F(xiàn)>，其中U={A，B，C，D，E}；F={AB→C，B→D，C→E，EC→B，AC→B}。求（AB）F+。解設X（0）=AB；(1)計算X（1）:逐一的掃描F集合中各個函數(shù)依賴，找左部為A，B或AB的函數(shù)依賴。得到兩個：

AB→C，B→D。于是X（1）=AB∪CD=ABCD。第六十九頁，共七十九頁，編輯于2023年，星期四(2)因為X（0）≠X（1），所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到AB→C，B→D，C→E，AC→B，于是X（2）=X（1）∪BCDE=ABCDE。(3)因為X（2）=U，算法終止所以（AB）F+=ABCDE。第七十頁，共七十九頁，編輯于2023年，星期四4.Armstrong公理系統(tǒng)的有效性與完備性有效性：由F出發(fā)根據(jù)Armstrong公理推導出來的每一個函數(shù)依賴一定在F+中

/*Armstrong正確完備性：F+中的每一個函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導出來

/*Armstrong公理夠用，完全第七十一頁，共七十九頁，編輯于2023年，星期四5.函數(shù)依賴集等價