關系數(shù)據(jù)庫的規(guī)范化設計

1、第四章關系數(shù)據(jù)庫的規(guī)范化設計第四章關系數(shù)據(jù)庫的規(guī)范化設計4.1 問題的提出4.2 規(guī)范化4.3 數(shù)據(jù)依賴的公理系統(tǒng)4.4 模式的分解4.5 小結(jié)前言前言 關系數(shù)據(jù)庫的規(guī)范化設計是指面對一個關系數(shù)據(jù)庫的規(guī)范化設計是指面對一個現(xiàn)實問題，如何選擇一個比較好的關系模式現(xiàn)實問題，如何選擇一個比較好的關系模式集合。集合。 規(guī)范化設計理論主要包括三個方面的內(nèi)規(guī)范化設計理論主要包括三個方面的內(nèi)容：數(shù)據(jù)依賴、范式和模式設計方法。其中容：數(shù)據(jù)依賴、范式和模式設計方法。其中數(shù)據(jù)依賴起著核心的作用。數(shù)據(jù)依賴研究數(shù)數(shù)據(jù)依賴起著核心的作用。數(shù)據(jù)依賴研究數(shù)據(jù)之間的聯(lián)系，范式是關系模式的標準，模據(jù)之間的聯(lián)系，范式是關系模式的

2、標準，模式設計方法是自動化設計的基礎。式設計方法是自動化設計的基礎。 規(guī)范化設計理論對關系數(shù)據(jù)庫結(jié)構(gòu)的設規(guī)范化設計理論對關系數(shù)據(jù)庫結(jié)構(gòu)的設計起著重要的作用。計起著重要的作用。4.1 問題的提出問題的提出關系數(shù)據(jù)庫邏輯設計n針對具體問題，如何構(gòu)造一個適合于它的數(shù)據(jù)模式n數(shù)據(jù)庫邏輯設計的工具關系數(shù)據(jù)庫的規(guī)范化理論一、概念回顧一、概念回顧n關系：描述實體、屬性、實體間的聯(lián)系。n從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個子集。n關系模式：用來定義關系。n關系數(shù)據(jù)庫：基于關系模型的數(shù)據(jù)庫，利用關系來描述現(xiàn)實世界。n從形式上看，它由一組關系組成。n關系數(shù)據(jù)庫的模式：定義這組關系的關系模式的全

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

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

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

6、：每一個系主任的姓名重復出現(xiàn) 更新異常n數(shù)據(jù)冗余 ，更新數(shù)據(jù)時，維護數(shù)據(jù)完整性代價大。例：某系更換系主任后，系統(tǒng)必須修改與該系學生有關的每一個元組關系模式關系模式Student中存在的問題中存在的問題 插入異常n該插的數(shù)據(jù)插不進去 例，如果一個系剛成立，尚無學生，我們就無法把這個系及其系主任的信息存入數(shù)據(jù)庫。 刪除異常n不該刪除的數(shù)據(jù)不得不刪例，如果某個系的學生全部畢業(yè)了， 我們在刪除該系學生信息的同時，把這個系及其系主任的信息也丟掉了。數(shù)據(jù)依賴對關系模式的影響（續(xù)）數(shù)據(jù)依賴對關系模式的影響（續(xù)）結(jié)論：結(jié)論：Student關系模式不是一個好的模式?！昂谩钡哪Ｊ剑翰粫l(fā)生插入異常、刪除異常、更新

7、異常，數(shù)據(jù)冗余應盡可能少。原因：由存在于模式中的某些數(shù)據(jù)依賴引起的解決方法：通過分解關系模式來消除其中不合適 的數(shù)據(jù)依賴。4.2 規(guī)范化規(guī)范化 規(guī)范化理論正是用來改造關系模式，通過分解關系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。4.2.1 函數(shù)依賴函數(shù)依賴一、函數(shù)依賴二、平凡函數(shù)依賴與非平凡函數(shù)依賴三、完全函數(shù)依賴與部分函數(shù)依賴四、傳遞函數(shù)依賴一、函數(shù)依賴一、函數(shù)依賴（簡記為（簡記為FD）定義4.1 (函數(shù)依賴的直觀定義函數(shù)依賴的直觀定義) 如果有一個關系模式R(A1,A2,An)，X和Y為A1,A2,An的子集，那么對于關系R中的任意一個X值，都只有

8、一個Y值與之對應，則稱X函數(shù)決定Y，或Y函數(shù)依賴于X，并用XY表示。 X稱為這個函數(shù)依賴的稱為這個函數(shù)依賴的決定屬性集決定屬性集。函數(shù)依賴（例）函數(shù)依賴（例）n例：對倉庫關系 倉庫(倉庫號,城市,面積)有函數(shù)依賴：倉庫號城市（城市函數(shù)依賴于倉庫號）倉庫號面積（面積函數(shù)依賴于倉庫號） 函數(shù)依賴的定義（準確定義）函數(shù)依賴的定義（準確定義）n定義4.1 設有關系模式R（U），X和Y是屬性集U的子集，函數(shù)依賴是形為XY的一個命題，只要r是R的當前關系，對r中任意兩個元組t和s，都有tX=sX蘊涵tY=sY，那么稱FD XY在關系模式R（U）中成立。 函數(shù)依賴的定義（例）函數(shù)依賴的定義（例）n例4.2

9、R關系A A1 1A A2 2 A A3 3A A4 4A Aa ac ce ed d3 38 8b bc cf ftyj jk kl lm md dt t8 89 97 7f fsy6 6txsxstr說明：說明： 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)有同名

10、人存在， 則拒絕裝入該元組。函數(shù)依賴（例）函數(shù)依賴（例）例: Student(Sno, Sname, Ssex, Sage, Sdept) 假設不允許重名，則有函數(shù)依賴:F=Sno Ssex， Sno Sage , Sno Sdept， Sno Sname, Sname Ssex， Sname SageSname Sdept Ssex Sage若XY，并且YX, 則記為XY。 若Y不函數(shù)依賴于X, 則記為XY。二、平凡函數(shù)依賴與非平凡函數(shù)依賴二、平凡函數(shù)依賴與非平凡函數(shù)依賴在關系模式R(U)中，對于U的子集X和Y，如果XY，但Y X，則稱XY是非平凡的函數(shù)依賴若XY，但Y X, 則稱XY是平凡

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

12、稱Y部分函數(shù)依賴于X，記作X P Y。 完全函數(shù)依賴與部分函數(shù)依賴（完全函數(shù)依賴與部分函數(shù)依賴（例例）例: 在關系SC(Sno, Cno, Grade)中， 由于：Sno Grade，Cno Grade， 因此：(Sno, Cno) Grade 完全函數(shù)依賴而：(Sno, Sdept) P Mname 是部分函數(shù)依賴 四、傳遞函數(shù)依賴四、傳遞函數(shù)依賴定義4.3 在關系模式R(U)中，如果XY，YZ，且Y X，YX，則稱Z傳遞函數(shù)依賴于X。注: 如果YX， 即XY，則Z直接依賴于X。例: 在關系Std(Sno, Sdept, Mname)中，有：Sno Sdept，Sdept Mname Mna

13、me傳遞函數(shù)依賴于Sno4.2.2 碼碼定義定義4.4 設K為關系模式R中的屬性或?qū)傩越M合。若K U，則K稱R的一個侯選碼。 若關系模式R有多個候選碼，則選定其中的一個做為主碼。n主屬性與非主屬性nALL KEY定義定義4.54.5 關系模式 R 中屬性或?qū)傩越MX 并非R 的碼，但 X 是另一個關系模式的碼，則稱 X 是R 的外部碼也稱外碼。主碼又和外部碼一起提供了表示關系間聯(lián)系的手段主碼又和外部碼一起提供了表示關系間聯(lián)系的手段。4.2.3 關系模式的關系模式的范式（范式（NF）n范式是符合某一種級別的關系模式的集合。n關系數(shù)據(jù)庫中的關系必須滿足一定的要求。滿足不同程度要求的為不同范式。n范式

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

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

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

17、rade） SL（Sno， Sdept， Sloc）例例:函數(shù)依賴圖：SnoCnoGradeSCSLSnoSdeptSloc第第2范式范式n2NF的定義定義4.6 若關系模式R1NF，并且每一個非主屬性都完全函數(shù)依賴于R的碼，則R2NF。例：SLC(Sno, Sdept, Sloc, Cno, Grade) 1NF SLC(Sno, Sdept, Sloc, Cno, Grade) 2NF SC（Sno， Cno， Grade） 2NF SL（Sno， Sdept， Sloc） 2NF2NFn采用投影分解法將一個1NF的關系分解為多個2NF的關系，可以在一定程度上減輕原1NF關系中存在的插入異

18、常、刪除異常、數(shù)據(jù)冗余度大、修改復雜等問題。n將一個1NF關系分解為多個2NF的關系，并不能完全消除關系模式中的各種異常情況和數(shù)據(jù)冗余。 4.2.5 第第3范式范式例：2NF關系模式SL(Sno, Sdept, Sloc)中n函數(shù)依賴： SnoSdept SdeptSloc SnoSlocSloc傳遞函數(shù)依賴于Sno，即SL中存在非主屬性對碼的傳遞函數(shù)依賴。 3NF函數(shù)依賴圖：SLSnoSdeptSloc 3NFn解決方法解決方法 采用投影分解法，把SL分解為兩個關系模式，以消除傳遞函數(shù)依賴： SD（Sno， Sdept） DL（Sdept， Sloc）SD的碼為Sno， DL的碼為Sdept

19、。 3NFSD的碼為Sno， DL的碼為Sdept。SnoSdeptSDSdeptSlocDL 3NFn3NF的定義定義4.8 關系模式R 是2NF，且每個非主屬性都不傳遞函數(shù)依賴于候選關鍵字，則稱R 3NF。例， SL(Sno, Sdept, Sloc) 2NF SL(Sno, Sdept, Sloc) 3NF SD（Sno， Sdept） 3NF DL（Sdept， Sloc） 3NF 3NF說明說明n若R3NF，則R的每一個非主屬性既不部分函數(shù)依賴于候選碼也不傳遞函數(shù)依賴于候選碼。n如果R3NF，則R也是2NF。n采用投影分解法將一個2NF的關系分解為多個3NF的關系，可以在一定程度上解

20、決原2NF關系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復雜等問題。n將一個2NF關系分解為多個3NF的關系后，并不能完全消除關系模式中的各種異常情況和數(shù)據(jù)冗余。 4.2.6 BC范式（范式（BCNF）n定義4.9 設關系模式R1NF，如果對于R的每個函數(shù)依賴XY，若Y不屬于X，則X必含有候選碼，那么RBCNF。若RBCNF n每一個決定屬性集（因素）都包含（候選）碼nR中的所有屬性（主，非主屬性）都完全函數(shù)依賴于碼n若R3NF 則 R不一定BCNF例：例： 在關系模式STST（S S，T T，J J）中，S表示學生，T表示教師，J J表示課程。n每一教師只教一門課。每門課由若干教師教，某

21、一學生選定某門課，就確定了一個固定的教師。某個學生選修某個教師的課就確定了所選課的名稱 ： (S， J J)T，(S，T) J J ，T J J例：例： SJTSTJSTJBCNFSTJ J 3NF n(S， J J)和(S，T)都可以作為候選碼 nS、T、 J J都是主屬性STJ J BCNFnT J J ，T是決定屬性集，T不是候選碼BCNF解決方法：將STJ分解為二個關系模式： SJ(S，J) BCNF， TJ(T，J) BCNF 沒有任何屬性對碼的部分函數(shù)依賴和傳遞函數(shù)依賴SJSTTJTJBCNF的關系模式所具有的性質(zhì)的關系模式所具有的性質(zhì) 所有非主屬性都完全函數(shù)依賴于每個候選碼 所有

22、主屬性都完全函數(shù)依賴于每個不包含它的候選碼 沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性4.2.7 關系模式的關系模式的規(guī)范化規(guī)范化n關系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設計的工具。n一個關系只要其分量都是不可分的數(shù)據(jù)項，它就是規(guī)范化的關系，但這只是最基本的規(guī)范化。n規(guī)范化程度可以有多個不同的級別規(guī)范化規(guī)范化n規(guī)范化程度過低的關系不一定能夠很好地描述現(xiàn)實世界，可能會存在插入異常、刪除異常、修改復雜、數(shù)據(jù)冗余等問題n一個低一級范式的關系模式，通過模式分解可以轉(zhuǎn)換為若干個高一級范式的關系模式集合，這種過程就叫關系模式的規(guī)范化規(guī)范化（續(xù)）規(guī)范化（續(xù)）n關系模式規(guī)范化的基本步驟 1NF 消除非主屬性對碼

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

24、模式n上面的規(guī)范化步驟可以在其中任何一步終止4.3 數(shù)據(jù)依賴的公理系統(tǒng)數(shù)據(jù)依賴的公理系統(tǒng)n一套推理規(guī)則，是模式分解算法的理論基礎n用途n求給定關系模式的碼n從一組函數(shù)依賴求得蘊含的函數(shù)依賴數(shù)據(jù)依賴的公理系統(tǒng)數(shù)據(jù)依賴的公理系統(tǒng)n邏輯蘊含 有時需要根據(jù)給定的一組函數(shù)依賴來判斷另外一些函數(shù)依賴是否成立，這就是函數(shù)依賴邏輯蘊涵所要研究的內(nèi)容。 比如有關系模式R(U,F)，U=A,B,C，F(xiàn)=AB,B C，問A C是否也成立？邏輯蘊含邏輯蘊含n定義定義4.10： 設F是在關系模式R上成立的函數(shù)依賴的集合，XY是一個函數(shù)依賴。如果對于R的每個滿足F的關系r也滿足XY，那么稱F邏輯蘊涵XY，記為F XY。1

25、. Armstrong公理系統(tǒng)公理系統(tǒng) 關系模式R 來說有以下的推理規(guī)則：nAl.自反律： 若Y X U，則X Y 為F 所蘊含。nA2.增廣律：若XY 為F 所蘊含，且Z U，則XZYZ 為F 所蘊含。nA3.傳遞律：若XY 及YZ 為F 所蘊含，則XZ 為F 所蘊含。注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F定理定理 4.l Armstrong推理規(guī)則是正確的推理規(guī)則是正確的（l）自反律:若Y X U，則X Y 為F 所蘊含證: 設Y X U 對R 的任一關系r 中的任意兩個元組t，s：若t X =s X ，由于Y X，有t y =s y ，所以XY 成立.

26、自反律得證定理定理4.l(2)增廣律: 若XY 為F 所蘊含，且Z U，則XZYZ 為F 所蘊含。 證：設XY 為F 所蘊含，且Z U。 設R 的任一關系r 中任意的兩個元組t，s；若t XZ=s XZ，則有t X=s X和t Z=s Z；由XY，于是有t Y=s Y，所以t YZ=s YZ，所以XZYZ 為F 所蘊含.增廣律得證。定理定理4.l(3) 傳遞律：若XY 及YZ 為F 所蘊含，則 XZ為 F 所蘊含。證：設XY及YZ為F所蘊含。對R 的任一關系 r中的任意兩個元組 t，s。若t X=s X，由于XY，有 t Y=s Y；再由YZ，有t Z=s Z，所以XZ 為F 所蘊含.傳遞律得

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

28、由F 根據(jù)Armstrong公理導出， XF+稱為屬性集X 關于函數(shù)依賴集F 的閉包F的閉包的閉包 F=X Y,Y Z, F +計算是NP完全問題，X A1A2.An F +=X , Y , Z , XY , XZ , YZ , XYZ , X X, Y Y, Z Z, XY X, XZ X, YZ Y, XYZ X,X Y, Y Z , XY Y, XZ Y, YZ Z, XYZ Y,X Z, Y YZ, XY Z, XZ Z, YZ YZ, XYZ Z,X XY, XY XY, XZ XY, XYZ XY, X XZ, XY YZ, XZ XZ, XYZ YZX YZ, XY XZ, XZ

29、 XY, XYZ XZ,X ZYZ, XY XYZ, XZ XYZ, XYZ XYZ 關于閉包的引理關于閉包的引理n引理4.2 設F 為屬性集U上的一組函數(shù)依賴，X，Y U，XY 能由F 根據(jù)Armstrong公理導出的充分必要條件是Y XF+n用途 將判定XY是否能由F 根據(jù)Armstrong公理導出的問題， 就轉(zhuǎn)化為求出XF+ ，判定Y是否為XF+的子集的問題求閉包的算法求閉包的算法算法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)；（

30、3）X（i+1）=BX（i） 算法算法4.l（4）判斷X（i+1）= X （i）嗎?（5）若相等或X（i）=U , 則X（i）就是XF+ , 算法終止。（6）若否，則 i=i+l，返回第（2）步。對于算法4.l， 令ai =|X（i）|，ai 形成一個步長大于1的嚴格遞增的序列，序列的上界是 | U |，因此該算法最多 |U| - |X| 次循環(huán)就會終止。函數(shù)依賴閉包函數(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的函數(shù)依賴。

31、得到兩個： ABC，BD。 于是X（1）=ABCD=ABCD。函數(shù)依賴閉包函數(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。4. FD推理規(guī)則的完備性推理規(guī)則的完備性n推理規(guī)則的正確性是指“從FD集F使用推理規(guī)則集推出的FD必定在F+中”，n完備性是指“F+中的FD都能從F集使用推理規(guī)則集導出”。也就是正確性保證了推出的所有FD是正確的，完備性保證了可以推出所有被蘊涵的FD。這就保證了推導的有效性和可靠性。n定理

32、4.5 FD推理規(guī)則A1，A2，A3是完備的。 5. 函數(shù)依賴集等價函數(shù)依賴集等價定義4.14 如果G +=F +，就說函數(shù)依賴集F 覆蓋G（F是G的覆蓋，或G是F 的覆蓋），或F 與G 等價。函數(shù)依賴集等價的充要條件函數(shù)依賴集等價的充要條件引理4.3 F + = G + 的充分必要條件是 F G + ，和G F + 證: 必要性顯然，只證充分性。（1）若F G + ，則XF+ XG+ 。（2）任取XYF + 則有 Y XF+ XG+ 。 所以XY (G +）+= G +。即F + G +。（3）同理可證G + F + ，所以F + = G +。函數(shù)依賴集等價函數(shù)依賴集等價n要判定F G +，

33、只須逐一對F中的函數(shù)依賴XY，考察 Y 是否屬于XG+ 就行了。因此引理4.3 給出了判斷兩個函數(shù)依賴集等價的可行算法。 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等價。 例:例例1 設設F是關系模式是關系模式R（ABC）的）的FD集，集，F(xiàn)= ABC，BC，AB，ABC ，試求，試求Fmin。 先把先把F中的中的FD寫成右邊

34、是單屬性形式：寫成右邊是單屬性形式：F= AB，AC，BC，AB，ABC 顯然多了一個顯然多了一個AB，可刪去。得，可刪去。得F= AB，AC，BC，ABC F中中AC可從可從AB和和BC推出，因此推出，因此AC是冗余是冗余的，可刪去。得的，可刪去。得F= AB，BC，ABC F中中ABC可從可從AB和和BC推出，因此推出，因此ABC也可也可刪去。最后得刪去。最后得F= AB，BC ，即所求的，即所求的Fmin。 最小依賴集最小依賴集例2 對于4.l節(jié)中的關系模式S，其中： U= SNO，SDEPT，MN，CNAME，G ， F= SNOSDEPT，SDEPTMN， （SNO，CNAME）G

35、設F=SNOSDEPT，SNOMN， SDEPTMN，(SNO，CNAME)G， (SNO，SDEPT)SDEPTF是最小覆蓋，而F 不是。因為：F -SNOMN與F 等價 F -(SNO，SDEPT)SDEPT也與F 等價 F -(SNO，SDEPT)SDEPT SNOSDEPT也與F 等價4.4 模式的分解模式的分解n把低一級的關系模式分解為若干個高一級的關系模式的方法并不是唯一的n只有能夠保證分解后的關系模式與原關系模式等價，分解方法才有意義關系模式分解的標準關系模式分解的標準三種模式分解的等價定義 分解具有無損連接性 分解要保持函數(shù)依賴 分解既要保持函數(shù)依賴，又要具有無損連接性模式的分

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

37、001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B 模式的分解（續(xù)）模式的分解（續(xù)）1. SL分解為下面三個關系模式： SN(Sno) SD(Sdept) SO(Sloc)分解后的關系為：分解后的關系為： SN SD SO Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 PH 95005 模式的分解（續(xù)）模式的分解（續(xù)）分解后的數(shù)據(jù)庫丟失了許多信息 例如無法查詢95001學生所在系或所在宿舍。 如果分解后的關系可以通過自然連接恢復為原來的關系，那么這種分解就沒有丟失信息模式的分解（

38、續(xù)）模式的分解（續(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 模式的分解（續(xù)）模式的分解（續(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 模式的分解（續(xù)）模式的分解（續(xù)）NL DL比原

39、來的SL關系多了3個元組 無法知道95002、95004、95005 究竟是哪個系的學生 元組增加了，信息丟失了第三種分解方法第三種分解方法3. 將SL分解為下面二個關系模式： ND(Sno, Sdept) NL(Sno, Sloc) 分解后的關系為： 模式的分解（續(xù)）模式的分解（續(xù)）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 模式的分解（續(xù)）模式的分解（續(xù)） ND NL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 CS A 95005 PH B 與SL關系一樣，因此沒有丟失信息具有無損連接性的模式分解具有無損連接性的模式分解n關系模式R的一個分解 = R1，R2， ，Rn若R與R1、R2、Rn自然連接的結(jié)果相等，則稱關系模式R的這個分解具有無損連接性（Lossless join）n具有無損連接性的分解保證不丟失信息n無損連接性不一定能解決插入異常、刪除異常、修改復雜、數(shù)據(jù)冗余等問題模式的分解（續(xù)）模式的分解（續(xù)） 第三種分解方法具有無損連接性 問題: 這種分解方法沒有保持原關