第4章關(guān)系數(shù)據(jù)庫規(guī)范化理論.ppt

1、An Introduction to Database System,安慶師范學(xué)院計(jì)算機(jī)與信息學(xué)院,數(shù)據(jù)庫系統(tǒng)概論 An Introduction to Database System 第四章 關(guān)系數(shù)據(jù)理論,An Introduction to Database System,第四章 關(guān)系數(shù)據(jù)理論,4.1 規(guī)范化問題的提出 4.2 函數(shù)依賴 4.3 范式 4.4 關(guān)系模式的規(guī)范化,An Introduction to Database System,例：描述教學(xué)管理的數(shù)據(jù)庫： 學(xué)生的學(xué)號(hào)（Sno）、所在系（Sdept） 系主任姓名（Mname）、課程名（Cname） 成績(jī)（Grade） 單一的

2、關(guān)系模式SCD： U Sno, Sdept, Mname, Cname, Grade ,4.1 規(guī)范化問題的提出,An Introduction to Database System,數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）,語義： 一個(gè)系有若干學(xué)生， 一個(gè)學(xué)生只屬于一個(gè)系； 一個(gè)系只有一名主任； 一個(gè)學(xué)生可以選修多門課程， 每門課程有若干學(xué)生選修； 每個(gè)學(xué)生所學(xué)的每門課程都有一個(gè)成績(jī)。,An Introduction to Database System,An Introduction to Database System,根據(jù)上述的語義規(guī)定，并分析以上關(guān)系中的數(shù)據(jù)，我們可以看出：(Sno,Cname

3、)屬性的組合能唯一標(biāo)識(shí)一個(gè)元組，所以(Sno,Cname)是該關(guān)系模式的主碼。在進(jìn)行數(shù)據(jù)庫的操作時(shí)，會(huì)出現(xiàn)以下幾方面的問題:,An Introduction to Database System,關(guān)系模式Student中存在的問題,1 數(shù)據(jù)冗余太大 浪費(fèi)大量的存儲(chǔ)空間 例：每一個(gè)系主任的姓名重復(fù)出現(xiàn) 2 插入異常（Insertion Anomalies） 該插的數(shù)據(jù)插不進(jìn)去 例，如果一個(gè)系剛成立，尚無學(xué)生，或有了學(xué)生但未選修課程，我們就無法把這個(gè)系及其系主任的信息存入數(shù)據(jù)庫。,An Introduction to Database System,3 修改異常（Update Anomalies）

4、 修改數(shù)據(jù)時(shí)，維護(hù)數(shù)據(jù)完整性代價(jià)大。 例：某系更換系主任后，系統(tǒng)必須修改與該系學(xué)生有關(guān)的每一個(gè)元組 4 刪除異常（Deletion Anomalies） 不該刪除的數(shù)據(jù)不得不刪 例，如果某個(gè)系的學(xué)生全部畢業(yè)了， 我們?cè)趧h除該系學(xué)生信息的同時(shí)，把這個(gè)系及其系主任的信息也丟掉了。,An Introduction to Database System,將單一的關(guān)系模式分解成三個(gè)關(guān)系模式： S（Sno,Sdept) SC(Sno,Cname,Grade) D(Sdept,Mname),An Introduction to Database System,在以上三個(gè)關(guān)系模式中，實(shí)現(xiàn)了信息的某種程度的分離

5、， S中存儲(chǔ)學(xué)生基本信息，與所選課程及系主任無關(guān)； D中存儲(chǔ)系的有關(guān)信息，與學(xué)生無關(guān)； SC中存儲(chǔ)學(xué)生選課的信息，而與系的有關(guān)信息無關(guān)。,An Introduction to Database System,與單一的Student關(guān)系模式相比： 數(shù)據(jù)的冗余度明顯降低 避免了插入異常 不會(huì)引起刪除異常 不會(huì)引起更新異常,An Introduction to Database System,規(guī)范化理論正是用來改造關(guān)系模式，通過分解關(guān)系模式將“不好”的關(guān)系模式轉(zhuǎn)化為“好”的關(guān)系模式，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。,An Introduction to Database Syste

6、m,關(guān)系模式由五部分組成，即它是一個(gè)五元組： R(U, D, DOM, F) R： 關(guān)系名 U： 組成該關(guān)系的屬性名集合 D： 屬性組U中屬性所來自的域 DOM：屬性向域的映象集合 F： 屬性間數(shù)據(jù)的依賴關(guān)系集合,4.2 函數(shù)依賴,An Introduction to Database System,4.2.1 函數(shù)依賴,一、函數(shù)依賴 二、平凡函數(shù)依賴與非平凡函數(shù)依賴 三、完全函數(shù)依賴與部分函數(shù)依賴 四、傳遞函數(shù)依賴,An Introduction to Database System,關(guān)系模式中的各屬性之間相互依賴、相互制約的聯(lián)系稱為數(shù)據(jù)依賴。 數(shù)據(jù)依賴一般分為函數(shù)依賴、多值依賴和連接依賴。

7、 其中,函數(shù)依賴是最重要的數(shù)據(jù)依賴。,An Introduction to Database System,一、函數(shù)依賴,比如描述一個(gè)學(xué)生的關(guān)系，可以有學(xué)號(hào)（Sno)，姓名(Sname)，系名(Sdept)等幾個(gè)屬性。由于一個(gè)學(xué)號(hào)只對(duì)應(yīng)一個(gè)學(xué)生，一個(gè)學(xué)生只在一個(gè)系學(xué)習(xí)。因而當(dāng)“學(xué)號(hào)”值確定之后，姓名和該生所在系的值也就被唯一地確定了。就象自變量x確定之后，函數(shù)值f(x)也就唯一地確定一樣，稱Sno函數(shù)決定Sname和Sdept或者說Sname,Sdept函數(shù)依賴于Sno，記為： Sno Sname， Sno Sdept,An Introduction to Database System,說明

8、：,1. 函數(shù)依賴是語義范疇的概念。只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴。 例如“姓名年齡”這個(gè)函數(shù)依賴只有在不允許有同名人的條件下成立 2. 數(shù)據(jù)庫設(shè)計(jì)者可以對(duì)現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定。例如規(guī)定不允許同名人出現(xiàn)，函數(shù)依賴“姓名年齡”成立。所插入的元組必須滿足規(guī)定的函數(shù)依賴，若發(fā)現(xiàn)有同名人存在， 則拒絕裝入該元組。,An Introduction to Database System,函數(shù)依賴（續(xù)）,例: Student(Sno, Sname, Ssex, Sage, Sdept) 假設(shè)不允許重名，則有: Sno Ssex， Sno Sage , Sno Sdept， Sno Sname, Sname

9、 Ssex， Sname Sage Sname Sdept 但Ssex Sage 若XY，并且YX, 則記為XY。 若Y不函數(shù)依賴于X, 則記為XY。,An Introduction to Database System,二、平凡函數(shù)依賴與非平凡函數(shù)依賴,在關(guān)系模式R(U)中，對(duì)于U的子集X和Y， 如果XY，但Y X，則稱XY是非平凡的函數(shù)依賴 若XY，但Y X, 則稱XY是平凡的函數(shù)依賴 例：在關(guān)系SC(Sno, Cno, Grade)中， 非平凡函數(shù)依賴： (Sno, Cno) Grade 平凡函數(shù)依賴： (Sno, Cno) Sno (Sno, Cno) Cno,An Introduct

10、ion to Database System,平凡函數(shù)依賴與非平凡函數(shù)依賴（續(xù)）,對(duì)于任一關(guān)系模式，平凡函數(shù)依賴都是必然成立的，它不反映新的語義，因此若不特別聲明， 我們總是討論非平凡函數(shù)依賴。,An Introduction to Database System,三、完全函數(shù)依賴與部分函數(shù)依賴,在關(guān)系模式R(U)中，如果XY，并且對(duì)于X的任何一個(gè)真子集X，都有 X Y, 則稱Y完全函數(shù)依賴于X，記作X Y。 若XY，即Y不完全函數(shù)依賴于X，則稱Y部分函數(shù)依賴于X，記作X P Y。,An Introduction to Database System,完全函數(shù)依賴與部分函數(shù)依賴（續(xù)）,例: 在

11、關(guān)系SC(Sno, Cno, Grade)中， 由于：Sno Grade，Cno Grade， 因此：(Sno, Cno) Grade,An Introduction to Database System,四、傳遞函數(shù)依賴,在關(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傳遞函數(shù)依賴于Sno,An Introduction to Database System,4.2.2 碼,設(shè)K為關(guān)系模式R中的屬

12、性或?qū)傩越M合。若 K U，則K稱為R的一個(gè)侯選碼（Candidate Key）。若關(guān)系模式R有多個(gè)候選碼，則選定其中的一個(gè)做為主碼（Primary key）。 主屬性與非主屬性 ALL KEY,An Introduction to Database System,外部碼,關(guān)系模式 R 中屬性或?qū)傩越MX 并非 R的碼，但 X 是另一個(gè)關(guān)系模式的碼，則稱 X 是R 的外部碼（Foreign key）簡(jiǎn)稱外碼。,An Introduction to Database System,4.3 范式,關(guān)系模式必須滿足一定的要求。滿足不同程度要求的為不同范式。 范式的種類： 第一范式(1NF) 第二范式(2

13、NF) 第三范式(3NF) BC范式(BCNF) 第四范式(4NF) 第五范式(5NF),An Introduction to Database System,各種范式之間存在聯(lián)系： 某一關(guān)系模式R為第n范式，可簡(jiǎn)記為RnNF。,An Introduction to Database System,An Introduction to Database System,4.3.1 1NF,1NF的定義 如果關(guān)系模式R的每個(gè)屬性都是不可再分的，則稱R為第一范式，簡(jiǎn)稱1NF，記作R1NF。 但是滿足第一范式的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式。,An Introduction to Database

14、 System,4.3.2 2NF,例: 關(guān)系模式 SLC(Sno, Sdept, Sloc, Cno, Grade) Sloc為學(xué)生住處，假設(shè)每個(gè)系的學(xué)生住在同一個(gè)地方。 函數(shù)依賴包括： (Sno, Cno) f Grade Sno Sdept (Sno, Cno) P Sdept Sno Sloc (Sno, Cno) P Sloc Sdept Sloc,An Introduction to Database System,SLC的碼為(Sno, Cno) SLC滿足第一范式。 非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno, Cno),An Introduction to Data

15、base System,SLC不是一個(gè)好的關(guān)系模式,(1) 數(shù)據(jù)冗余度大 如果一個(gè)學(xué)生選修了10門課程，那么他的Sdept和Sloc值就要重復(fù)存儲(chǔ)了10次。 (2) 插入異常 假設(shè)Sno 95102 ，Sdept IS ，Sloc N的學(xué)生還未選課，因課程號(hào)是主屬性，因此該學(xué)生的信息無法插入SLC。,An Introduction to Database System,SLC不是一個(gè)好的關(guān)系模式,(3) 刪除異常 假定某個(gè)學(xué)生本來只選修了3號(hào)課程這一門課?，F(xiàn)在因身體不適，他連3號(hào)課程也不選修了。因課程號(hào)是主屬性，此操作將導(dǎo)致該學(xué)生信息也要?jiǎng)h除。 (4) 修改復(fù)雜 例如學(xué)生轉(zhuǎn)系，在修改此學(xué)生元組

16、的Sdept值的同時(shí)，還可能需要修改住處（Sloc）。如果這個(gè)學(xué)生選修了K門課，則必須無遺漏地修改K個(gè)元組中全部Sdept、Sloc信息。,An Introduction to Database System,2NF,原因 Sdept、 Sloc部分函數(shù)依賴于碼。 解決方法 SLC分解為兩個(gè)關(guān)系模式，以消除這些部分函數(shù)依賴 SC（Sno， Cno， Grade） SL（Sno， Sdept， Sloc）,An Introduction to Database System,2NF,函數(shù)依賴圖：,An Introduction to Database System,2NF,2NF的定義 若關(guān)系模

17、式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） 2NF,An Introduction to Database System,采用投影分解法將一個(gè)1NF的關(guān)系分解為多個(gè)2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。 將一個(gè)1NF關(guān)系分解為多個(gè)2NF的關(guān)系，并不能完全消除關(guān)系模

18、式中的各種異常情況和數(shù)據(jù)冗余。,An Introduction to Database System,4.3.3 3NF,例：2NF關(guān)系模式SL(Sno, Sdept, Sloc)中 函數(shù)依賴： SnoSdept SdeptSloc SnoSloc Sloc傳遞函數(shù)依賴于Sno，即SL中存在非主屬性對(duì)碼的傳遞函數(shù)依賴。,An Introduction to Database System,函數(shù)依賴圖：,An Introduction to Database System,解決方法 采用投影分解法，把SL分解為兩個(gè)關(guān)系模式，以消除傳遞函數(shù)依賴： SD（Sno， Sdept） DL（Sdept，

19、Sloc） SD的碼為Sno， DL的碼為Sdept。,An Introduction to Database System,SD的碼為Sno， DL的碼為Sdept。,An Introduction to Database System,3NF的定義 定義4.8 關(guān)系模式R 中若不存在這樣的碼X、屬性組Y及非主屬性Z（Z Y）, 使得XY，Y X，YZ，成立，則稱R 3NF。 例， SL(Sno, Sdept, Sloc) 2NF SL(Sno, Sdept, Sloc) 3NF SD（Sno， Sdept） 3NF DL（Sdept， Sloc） 3NF,An Introduction t

20、o Database System,若R3NF，則R的每一個(gè)非主屬性既不部分函數(shù)依賴于候選碼也不傳遞函數(shù)依賴于候選碼。 如果R3NF，則R也是2NF。 采用投影分解法將一個(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ù)冗余。,An Introduction to Database System,4.3.4 BCNF,定義4.9 設(shè)關(guān)系模式R1NF，如果對(duì)于R的每個(gè)函數(shù)依賴XY，若Y X，則X必含有候選碼，那么RBCNF。 若RB

21、CNF 每一個(gè)決定屬性集（因素）都包含（候選）碼 R中的所有屬性（主，非主屬性）都完全函數(shù)依賴于碼,An Introduction to Database System,BCNF,例：在關(guān)系模式STJ（S，T，J）中，S表示學(xué)生，T表示教師，J表示課程。 每一教師只教一門課。每門課由若干教師教，某一學(xué)生選定某門課，就確定了一個(gè)固定的教師。某個(gè)學(xué)生選修某個(gè)教師的課就確定了所選課的名稱 ： (S，J)T，(S，T)J，TJ,An Introduction to Database System,An Introduction to Database System,BCNF,STJ3NF (S，J)和

22、(S，T)都可以作為候選碼 S、T、J都是主屬性 STJBCNF TJ，T是決定屬性集，T不是候選碼,An Introduction to Database System,BCNF,解決方法：將STJ分解為二個(gè)關(guān)系模式： SJ(S，T) BCNF， TJ(T，J) BCNF 沒有任何屬性對(duì)碼的部分函數(shù)依賴和傳遞函數(shù)依賴,An Introduction to Database System,4.4 規(guī)范化,關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計(jì)的工具。 一個(gè)關(guān)系只要其分量都是不可分的數(shù)據(jù)項(xiàng)，它就是規(guī)范化的關(guān)系，但這只是最基本的規(guī)范化。 規(guī)范化程度可以有多個(gè)不同的級(jí)別,An Introductio

23、n to Database System,規(guī)范化（續(xù)）,規(guī)范化程度過低的關(guān)系不一定能夠很好地描述現(xiàn)實(shí)世界，可能會(huì)存在插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題 一個(gè)低一級(jí)范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式集合，這種過程就叫關(guān)系模式的規(guī)范化,An Introduction to Database System,規(guī)范化（續(xù)）,關(guān)系模式規(guī)范化的基本步驟 1NF 消除非主屬性對(duì)碼的部分函數(shù)依賴 消除決定因素 2NF 非碼的非平 消除非主屬性對(duì)碼的傳遞函數(shù)依賴 凡函數(shù)依賴 3NF 消除主屬性對(duì)碼的部分和傳遞函數(shù)依賴 BCNF,An Introduction to Data

24、base System,規(guī)范化的基本思想,消除不合適的數(shù)據(jù)依賴 各關(guān)系模式達(dá)到某種程度的“分離” 采用“一事一地”的模式設(shè)計(jì)原則 讓一個(gè)關(guān)系描述一個(gè)概念、一個(gè)實(shí)體型或者實(shí)體型間的一種聯(lián)系。若多于一個(gè)概念就把它“分離”出去,An Introduction to Database System,規(guī)范化（續(xù)）,不能說規(guī)范化程度越高的關(guān)系模式就越好 在設(shè)計(jì)數(shù)據(jù)庫模式結(jié)構(gòu)時(shí)，必須對(duì)現(xiàn)實(shí)世界的實(shí)際情況和用戶應(yīng)用需求作進(jìn)一步分析，確定一個(gè)合適的、能夠反映現(xiàn)實(shí)世界的模式 上面的規(guī)范化步驟可以在其中任何一步終止,An Introduction to Database System,判斷下列模式分別屬于哪個(gè)范式(

25、最高范式)并說明理由 1 R(A，B，C，(A，C)B，(A，B)C，BC) 2 R(S#，SD，SL，SN，S#SD，S#SN，S#SL，SDSL),習(xí)題：,An Introduction to Database System,設(shè)有關(guān)系STUDENT(S#,SNAME,SDEPT,MNAME,CNAME,GRADE)，S#,CNAME為候選碼，設(shè)關(guān)系中有如下函數(shù)依賴： （S#,CNAME）SNAME,SDEPT,MNAMES#SNAME,SDEPT,MNAME（S#,CNAME）GRADESDEPTMNAME,An Introduction to Database System,試求下列問題

26、：（1）關(guān)系STUDENT屬于第幾范式？（2）如果關(guān)系STUDENT不屬于BCNF，請(qǐng)將關(guān)系STUDENT逐步分解為BCNF。 要求：寫出達(dá)到每一級(jí)范式的分解過程，并指明消除什么類型的函數(shù)依賴。,An Introduction to Database System,4.5 Armstrong公理系統(tǒng),邏輯蘊(yùn)含 定義4.11 對(duì)于滿足一組函數(shù)依賴 F 的關(guān)系模式R ，其任何一個(gè)關(guān)系r，若函數(shù)依賴XY都成立, 則稱 F邏輯蘊(yùn)含X Y,An Introduction to Database System,Armstrong公理系統(tǒng),Armstrong公理系統(tǒng)是函數(shù)依賴的一個(gè)有效而完備的公理系統(tǒng) 可用

27、于從一組函數(shù)依賴F求得蘊(yùn)含(導(dǎo)出)的函數(shù)依賴 可用于求得關(guān)系模式的碼,An Introduction to Database System,1. Armstrong公理系統(tǒng),關(guān)系模式R 來說有以下的推理規(guī)則： Al.自反律（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)含。 注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F,An Introduction to Database

28、System,定理 4.l Armstrong推理規(guī)則是正確的,（l）自反律:若Y X U，則X Y為F所蘊(yùn)含 證: 設(shè)Y X U 對(duì)R 的任一關(guān)系r中的任意兩個(gè)元組t，s： 若tX=sX，由于Y X，有ty=sy， 所以XY成立. 自反律得證,An Introduction to Database System,定理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； 若tXZ=sXZ，則有tX=sX和tZ=sZ； 由XY，于是有tY=sY，所以tYZ=sYZ，所以XZYZ為F所蘊(yùn)含. 增廣

29、律得證。,An Introduction to Database System,定理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。 若tX=sX，由于XY，有 tY=sY； 再由YZ，有tZ=sZ，所以XZ為F所蘊(yùn)含. 傳遞律得證。,An Introduction to Database System,2. 導(dǎo)出規(guī)則,1.根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： 合并規(guī)則：由XY，XZ，有XYZ。 （A2， A3） 偽傳遞規(guī)則：由XY，WYZ，有XWZ。 （A2， A3）

30、分解規(guī)則：由XY及 ZY，有XZ。 （A1， A3）,An Introduction to Database System,導(dǎo)出規(guī)則,2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理4.1 引理4.l XA1 A2Ak成立的充分必要條件是XAi成立（i=l，2，k）。,An Introduction to Database System,3. 函數(shù)依賴閉包,定義4.l2 在關(guān)系模式R中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作 F的閉包，記為F+。,An Introduction to Database System,3. 函數(shù)依賴閉包,定義4.13 設(shè)F為屬性集U上的一組函數(shù)依賴，X U， XF+ = A|XA

31、能由F 根據(jù)Armstrong公理導(dǎo)出，XF+稱為屬性集X關(guān)于函數(shù)依賴集F 的閉包,An Introduction to Database System,求閉包的算法,算法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+1）=BX（i）,An Introduction to Database System,算法4.l,（4）判斷X（i+1）= X （i）嗎? （5）若相等或X（i）=U , 則X（i）就是XF+ ,

32、算法終止。 （6）若否，則 i=i+l，返回第（2）步。,An Introduction to Database System,函數(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è)： ABC，BD。 于是X（1）=ABCD=ABCD。,An Introduction to Database System,函數(shù)依賴閉包,(2)因?yàn)閄（0） X（1） ，所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到

33、ABC，BD， CE，ACB， 于是X（2）=X（1）BCDE=ABCDE。 (3)因?yàn)閄（2）=U，算法終止 所以（AB）F+ =ABCDE。,An Introduction to Database System,An Introduction to Database System,假設(shè)關(guān)系模式為R(A,B,C,D), F=AB,B C,B D，求蘊(yùn)含于給定函數(shù)依賴的所有非平凡函數(shù)依賴。 求解方法：求所有屬性組合的閉包，從中找出新的非平凡依賴。如：,A+=ABCD,B+=BCD,C+=C, D+=D，則有新的非平凡依賴為A C, A D 2) 兩個(gè)屬性的排列組合，8種新的： AB C, AB

34、 D, AC B, AC D, AD B, AD C, BC D, BD C 3）三個(gè)屬性的排列組合，2種新的：ABC D, ABD C 4）ABCD+=ABCD，無,An Introduction to Database System,4. 函數(shù)依賴集等價(jià),定義4.14 如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。,An Introduction to Database System,6. 最小依賴集,定義4.15 如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。 (1) F中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。

35、(2) F中不存在這樣的函數(shù)依賴XA，使得F與 F-XA等價(jià)。 (3) F中不存在這樣的函數(shù)依賴XA， X有真 子集Z使得F-XAZA與F等價(jià)。,An Introduction to Database System,最小依賴集,例2 對(duì)于4.l節(jié)中的關(guān)系模式S，其中： U= SNO，SDEPT，MN，CNAME，G ， F= SNOSDEPT，SDEPTMN， （SNO，CNAME）G 設(shè)F=SNOSDEPT，SNOMN， SDEPTMN，(SNO，CNAME)G， (SNO，SDEPT)SDEPT F是最小覆蓋，而F 不是。 因?yàn)椋篎 -SNOMN與F 等價(jià) F -(SNO，SDEPT)SD

36、EPT也與F 等價(jià) F -(SNO，SDEPT)SDEPT SNOSDEPT也與F 等價(jià),An Introduction to Database System,7. 極小化過程,定理4.3 每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小 函數(shù)依賴集Fm。此Fm稱為F的最小依賴集 證:構(gòu)造性證明，依據(jù)定義分三步對(duì)F進(jìn)行“極小化處理”，找出F的一個(gè)最小依賴集。 (1)逐一檢查F中各函數(shù)依賴FDi：XY， 若Y=A1A2 Ak，k 2， 則用 XAj |j=1，2， k 來取代XY。,An Introduction to Database System,極小化過程,(2)逐一檢查F中各函數(shù)依賴FDi：XA， 令

37、G=F-XA， 若AXG+， 則從F中去掉此函數(shù)依賴。,An Introduction to Database System,極小化過程,(3)逐一取出F中各函數(shù)依賴FDi：XA， 設(shè)X=B1B2Bm， 逐一考查Bi （i=l，2，m）， 若A （X-Bi ）F+ ， 則以X-Bi 取代X。,An Introduction to Database System,極小化過程,由定義，最后剩下的F就一定是極小依賴集。 因?yàn)閷?duì)F的每一次“改造”都保證了改造前后的兩個(gè)函數(shù)依賴集等價(jià)，因此剩下的F與原來的F等價(jià)。 定理4.3的證明過程 也是求F極小依賴集的過程,An Introduction to Da

38、tabase System,極小化過程,例3 F = AB，BA，BC， AC，CA Fm1、Fm2都是F的最小依賴集： Fm1= AB，BC，CA Fm2= AB，BA，AC，CA F的最小依賴集Fm不一定是唯一的它與對(duì)各函數(shù)依賴FDi 及XA中X各屬性的處置順序有關(guān),An Introduction to Database System,極小化過程,極小化過程( 定理4.3的證明 )也是檢驗(yàn)F是否為極小依賴集的一個(gè)算法 若改造后的F與原來的F相同，說明F本身就是一個(gè)最小依賴集,An Introduction to Database System,An Introduction to Database System,關(guān)系模式R(A，B，C，D)中，存在函數(shù)