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

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

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

3、體。二、關(guān)系模式的形式化定義二、關(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ù)依賴三、什么是數(shù)據(jù)依賴1. 完整性約束的表現(xiàn)形式n限定屬性取值范圍：例如學(xué)生成績必須在0-100之間n定義屬性值間的相互關(guān)連:（主要體現(xiàn)于值的相等與否）2. 數(shù)據(jù)依賴n數(shù)據(jù)依賴是通過一個(gè)關(guān)系中屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間的相互關(guān)系。它是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象，是數(shù)據(jù)內(nèi)在的性質(zhì)，是語義的體現(xiàn)。它是數(shù)據(jù)庫模式設(shè)計(jì)的關(guān)鍵3.

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

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

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

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

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

9、R關(guān)系A(chǔ)1A1 A2 A2 A3A3 A4A4A Aa ac ce ed d3 38 8b bc cf ftyj jk kl lm md dt t8 89 97 7f fsy6 6txsxstr說明：說明： 1.函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些關(guān)系 實(shí)例滿足的約束條件，而是指R的所有關(guān)系實(shí)例 均要滿足的約束條件。2. 函數(shù)依賴是語義范疇的概念。只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴。例如“姓名年齡”這個(gè)函數(shù)依賴只有在不允許有同名人的條件下成立3. 數(shù)據(jù)庫設(shè)計(jì)者可以對(duì)現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定。例如規(guī)定不允許同名人出現(xiàn)，函數(shù)依賴“姓名年齡”成立。所插入的元組必須滿足規(guī)定的函數(shù)依賴，若發(fā)現(xiàn)有同名人存在，

10、則拒絕裝入該元組。函數(shù)依賴（例）函數(shù)依賴（例）例: Student(Sno, Sname, Ssex, Sage, Sdept) 假設(shè)不允許重名，則有函數(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ù)依賴在關(guān)系模式R(U)中，對(duì)于U的子集X和Y，如果XY，但Y X，則稱XY是非平凡的函數(shù)依賴若XY，但Y X, 則稱XY是平凡的函數(shù)依賴

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

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

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

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

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不是一個(gè)好的關(guān)系模式不是一個(gè)好的關(guān)系模式(1) 插入異常假設(shè)Sno95102，SdeptIS，SlocN的學(xué)生還未選課，因課程號(hào)是主屬性，因此該學(xué)生的信息無法插入SLC。(2) 刪除異常 假定某個(gè)學(xué)生本來只選修了3號(hào)課程這一

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

17、 SL（Sno， Sdept， Sloc）例例:函數(shù)依賴圖：SnoCnoGradeSCSLSnoSdeptSloc第第2范式范式n2NF的定義定義4.6 若關(guān)系模式R1NF，并且每一個(gè)非主屬性都完全函數(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采用投影分解法將一個(gè)1NF的關(guān)系分解為多個(gè)2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的插入異常、刪除異

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

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

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

21、某門課，就確定了一個(gè)固定的教師。某個(gè)學(xué)生選修某個(gè)教師的課就確定了所選課的名稱 ： (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分解為二個(gè)關(guān)系模式： SJ(S，J) BCNF， TJ(T，J) BCNF 沒有任何屬性對(duì)碼的部分函數(shù)依賴和傳遞函數(shù)依賴SJSTTJTJBCNF的關(guān)系模式所具有的性質(zhì)的關(guān)系模式所具有的性質(zhì) 所有非主屬性都完全函數(shù)依賴于每個(gè)候選碼 所有主屬性都完

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

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

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

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

26、定理定理4.l(2)增廣律: 若XY 為F 所蘊(yùn)含，且Z U，則XZYZ 為F 所蘊(yùn)含。 證：設(shè)XY 為F 所蘊(yùn)含，且Z U。 設(shè)R 的任一關(guān)系r 中任意的兩個(gè)元組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 所蘊(yùn)含.增廣律得證。定理定理4.l(3) 傳遞律：若XY 及YZ 為F 所蘊(yùn)含，則 XZ為 F 所蘊(yùn)含。證：設(shè)XY及YZ為F所蘊(yùn)含。對(duì)R 的任一關(guān)系 r中的任意兩個(gè)元組 t，s。若t X=s X，由于XY，有 t Y=s Y；再由YZ，有t Z=s Z，所以XZ 為F 所蘊(yùn)含.傳遞律得證。2.

27、導(dǎo)出規(guī)則導(dǎo)出規(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）導(dǎo)出規(guī)則導(dǎo)出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理5.1 引理5.l XA1 A2Ak成立的充分必要條件是XAi 成立（i=l，2，k）。3. 函數(shù)依賴閉包函數(shù)依賴閉包定義4.l2 在關(guān)系模式R中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作 F 的閉包，記為F +。定義4.13 設(shè)F 為屬性集U上的一組函數(shù)依賴，X U， XF+ = A|XA能由F 根據(jù)

28、Armstrong公理導(dǎo)出， XF+稱為屬性集X 關(guān)于函數(shù)依賴集F 的閉包F的閉包的閉包 F=X Y,Y Z, F +計(jì)算是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 XY,

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

30、+1）=BX（i） 算法算法4.l（4）判斷X（i+1）= X （i）嗎?（5）若相等或X（i）=U , 則X（i）就是XF+ , 算法終止。（6）若否，則 i=i+l，返回第（2）步。對(duì)于算法4.l， 令ai =|X（i）|，ai 形成一個(gè)步長大于1的嚴(yán)格遞增的序列，序列的上界是 | U |，因此該算法最多 |U| - |X| 次循環(huán)就會(huì)終止。函數(shù)依賴閉包函數(shù)依賴閉包例1 已知關(guān)系模式R，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，ACB。求（AB）F+ 。解 設(shè)X（0）=AB；(1)計(jì)算X（1）: 逐一的掃描F 集合中各個(gè)函數(shù)依賴，找左部為A，B或AB的函數(shù)依賴。得到兩個(gè)：

31、 ABC，BD。 于是X（1）=ABCD=ABCD。函數(shù)依賴閉包函數(shù)依賴閉包(2)因?yàn)閄（0） X（1） ，所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到ABC，BD， CE，ACB， 于是X（2）=X（1）BCDE=ABCDE。(3)因?yàn)閄（2）=U，算法終止所以（AB）F+ =ABCDE。4. FD推理規(guī)則的完備性推理規(guī)則的完備性n推理規(guī)則的正確性是指“從FD集F使用推理規(guī)則集推出的FD必定在F+中”，n完備性是指“F+中的FD都能從F集使用推理規(guī)則集導(dǎo)出”。也就是正確性保證了推出的所有FD是正確的，完備性保證了可以推出所有被蘊(yùn)涵的FD。這就保證了推導(dǎo)的有效性和可靠性。n定理4.5 F

32、D推理規(guī)則A1，A2，A3是完備的。 5. 函數(shù)依賴集等價(jià)函數(shù)依賴集等價(jià)定義4.14 如果G +=F +，就說函數(shù)依賴集F 覆蓋G（F是G的覆蓋，或G是F 的覆蓋），或F 與G 等價(jià)。函數(shù)依賴集等價(jià)的充要條件函數(shù)依賴集等價(jià)的充要條件引理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ù)依賴集等價(jià)函數(shù)依賴集等價(jià)n要判定F G +，只須逐一對(duì)

33、F中的函數(shù)依賴XY，考察 Y 是否屬于XG+ 就行了。因此引理4.3 給出了判斷兩個(gè)函數(shù)依賴集等價(jià)的可行算法。 6. 最小依賴集最小依賴集 定義4.15 如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。 (1) F中任一函數(shù)依賴的右部僅含有一個(gè)屬性。 (2) F中不存在這樣的函數(shù)依賴XA，使得F與F-XA等價(jià)。 (3) F中不存在這樣的函數(shù)依賴XA， X有真 子集Z使得F-XAZA與F等價(jià)。 例:例例1 設(shè)設(shè)F是關(guān)系模式是關(guān)系模式R（ABC）的）的FD集，集，F(xiàn)= ABC，BC，AB，ABC ，試求，試求Fmin。 先把先把F中的中的FD寫成右邊是單屬性形

34、式：寫成右邊是單屬性形式：F= AB，AC，BC，AB，ABC 顯然多了一個(gè)顯然多了一個(gè)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 對(duì)于4.l節(jié)中的關(guān)系模式S，其中： U= SNO，SDEPT，MN，CNAME，G ， F= SNOSDEPT，SDEPTMN， （SNO，CNAME）G 設(shè)F=SN

35、OSDEPT，SNOMN， SDEPTMN，(SNO，CNAME)G， (SNO，SDEPT)SDEPTF是最小覆蓋，而F 不是。因?yàn)椋篎 -SNOMN與F 等價(jià) F -(SNO，SDEPT)SDEPT也與F 等價(jià) F -(SNO，SDEPT)SDEPT SNOSDEPT也與F 等價(jià)4.4 模式的分解模式的分解n把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系模式的方法并不是唯一的n只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義關(guān)系模式分解的標(biāo)準(zhǔn)關(guān)系模式分解的標(biāo)準(zhǔn)三種模式分解的等價(jià)定義 分解具有無損連接性 分解要保持函數(shù)依賴 分解既要保持函數(shù)依賴，又要具有無損連接性模式的分解（續(xù)）模

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

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

38、分解（續(xù)）2. SL分解為下面二個(gè)關(guān)系模式： NL(Sno, Sloc) DL(Sdept, Sloc)分解后的關(guān)系為： 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比原來的SL關(guān)

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