《數(shù)據(jù)庫(kù)原理》課件第7章 關(guān)系數(shù)據(jù)庫(kù)規(guī)范化理論

2024/9/6ftt@1優(yōu)秀的數(shù)據(jù)庫(kù)設(shè)計(jì)是應(yīng)用成功的基石

第7章關(guān)系數(shù)據(jù)庫(kù)規(guī)范化理論2024/9/6ftt@2問題的提出關(guān)系數(shù)據(jù)庫(kù)關(guān)系數(shù)據(jù)模型靜態(tài)的數(shù)據(jù)結(jié)構(gòu)描述動(dòng)態(tài)的數(shù)據(jù)操作集合數(shù)據(jù)完整性約束關(guān)系數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)針對(duì)一個(gè)具體問題，應(yīng)如何構(gòu)造一個(gè)適合于它的數(shù)據(jù)模式，即應(yīng)該構(gòu)造幾個(gè)關(guān)系，每個(gè)關(guān)系由哪些屬性組成等。數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工具──關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論2024/9/6ftt@3關(guān)系模式的設(shè)計(jì)問題例1.考慮為管理職工的工資信息而設(shè)計(jì)一個(gè)關(guān)系模式職工級(jí)別工資趙明4500錢廣5600孫志6700李開5600周祥67002024/9/6ftt@4存在問題：信息的不可表示問題插入異常：如果沒有職工具有8級(jí)工資，則8級(jí)工資的工資數(shù)額就難以插入刪除異常：如果僅有職工趙明具有4級(jí)工資，如果將趙明刪除，則有關(guān)4級(jí)工資的工資數(shù)額信息也隨之刪除了信息的冗余問題數(shù)據(jù)冗余：職工很多，工資級(jí)別有限，每一級(jí)別的工資數(shù)額反復(fù)存儲(chǔ)多次更新異常：如果將5級(jí)工資的工資數(shù)額調(diào)為620，則需要找到每個(gè)具有5級(jí)工資的職工，逐一修改麻煩!麻煩!!好煩!!!唉，剪不斷，理還亂2024/9/6ftt@5解決之道：關(guān)系模式分解級(jí)別工資450056006700分解!分解!!再分解!!!哇，原來(lái)生活可以如此簡(jiǎn)單2024/9/6ftt@6分解改進(jìn)后，好處：數(shù)據(jù)量減少。設(shè)有n個(gè)職工，m個(gè)工資級(jí)別，n>>m，則分解前原模式有3n個(gè)數(shù)據(jù)，改進(jìn)后新模式共有2n+2m個(gè)數(shù)據(jù)，顯然后者的數(shù)據(jù)量要少得多。表達(dá)能力強(qiáng)。分解前原表中無(wú)法進(jìn)入的信息（如9級(jí)工資），在改進(jìn)后的兩個(gè)模式中則可加入；當(dāng)刪除職工C時(shí)，也不會(huì)丟失7級(jí)工資信息。修改方便。改進(jìn)后，修改某一級(jí)別工資時(shí)只要修改一處。當(dāng)然，改進(jìn)后的關(guān)系模式也存在另外一個(gè)問題，當(dāng)查詢某個(gè)職工的工資時(shí)，需要將兩個(gè)關(guān)系連接后進(jìn)行查詢，而關(guān)系的連接代價(jià)是很大的。2024/9/6ftt@7主要內(nèi)容關(guān)系模式的冗余和異常問題數(shù)據(jù)依賴*數(shù)據(jù)依賴的公理系統(tǒng)（了解）碼與閉包算法求碼關(guān)系模式的規(guī)范化函數(shù)依賴與關(guān)系模式的范式：1NF，2NF，3NF，BCNF*多值依賴與4NF（了解）*模式的分解（了解）無(wú)損連接性分解保持函數(shù)依賴分解2024/9/6ftt@8數(shù)據(jù)依賴內(nèi)容提要關(guān)系模式中的數(shù)據(jù)依賴概念回顧關(guān)系模式的形式化定義什么是數(shù)據(jù)依賴關(guān)系模式的簡(jiǎn)化定義數(shù)據(jù)依賴對(duì)關(guān)系模式有什么影響數(shù)據(jù)依賴的形式化定義2024/9/6ftt@9概念回顧關(guān)系：描述實(shí)體及其屬性、實(shí)體間的聯(lián)系。從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個(gè)子集。關(guān)系模式：用來(lái)定義關(guān)系。關(guān)系數(shù)據(jù)庫(kù)：基于關(guān)系模型的數(shù)據(jù)庫(kù)，利用關(guān)系來(lái)描述現(xiàn)實(shí)世界。從形式上看，它由一組關(guān)系組成。關(guān)系數(shù)據(jù)庫(kù)的模式：定義這組關(guān)系的關(guān)系模式的全體。2024/9/6ftt@10關(guān)系模式的形式化定義關(guān)系模式由五部分組成，即它是一個(gè)五元組：

R(U,D,DOM,F)R：關(guān)系名U：組成該關(guān)系的屬性名集合D：屬性組U中屬性所來(lái)自的域DOM：屬性向域的映象集合F：屬性間數(shù)據(jù)的依賴關(guān)系集合。即限定了組成關(guān)系的各個(gè)元組必須滿足的完整性約束條件。2024/9/6ftt@11什么是數(shù)據(jù)依賴1.完整性約束的表現(xiàn)形式限定屬性取值范圍：例如學(xué)生成績(jī)必須在0-100之間定義屬性值間的相互關(guān)連（主要體現(xiàn)于值的相等與否），這就是數(shù)據(jù)依賴，它是數(shù)據(jù)庫(kù)模式設(shè)計(jì)的關(guān)鍵。2024/9/6ftt@12什么是數(shù)據(jù)依賴（續(xù)）2.數(shù)據(jù)依賴是通過(guò)一個(gè)關(guān)系中屬性間值的相等與否體現(xiàn)出來(lái)的數(shù)據(jù)間的相互關(guān)系是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象是數(shù)據(jù)內(nèi)在的性質(zhì)是語(yǔ)義的體現(xiàn)2024/9/6ftt@13什么是數(shù)據(jù)依賴（續(xù)）3.數(shù)據(jù)依賴的主要類型函數(shù)依賴（FunctionalDependency，F(xiàn)D）多值依賴（了解）（MultivaluedDependency，MVD）連接依賴（了解）2024/9/6ftt@14關(guān)系模式的簡(jiǎn)化表示在關(guān)系模式R(U,D,DOM,F)中，影響數(shù)據(jù)庫(kù)模式設(shè)計(jì)的主要是U和F，D和DOM對(duì)其影響不大，為了方便討論，我們將關(guān)系模式簡(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)系。2024/9/6ftt@15數(shù)據(jù)依賴對(duì)關(guān)系模式的影響例2.建立一個(gè)描述學(xué)校的數(shù)據(jù)庫(kù)。涉及的對(duì)象包括： 學(xué)生的學(xué)號(hào)（Sno），所在系（Sdept），系主任姓名（Mname），課程名（Cname），成績(jī)（Grade）假設(shè)學(xué)校的數(shù)據(jù)庫(kù)模式由一個(gè)單一的關(guān)系模式Student構(gòu)成，則該關(guān)系模式的屬性集合為：

U＝｛Sno,Sdept,Mname,Cname,Grade｝2024/9/6ftt@16數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）現(xiàn)實(shí)世界的已知事實(shí)：一個(gè)系有若干學(xué)生，但一個(gè)學(xué)生只屬于一個(gè)系；一個(gè)系只有一名主任；一個(gè)學(xué)生可以選修多門課程，每門課程有若干學(xué)生選修；每個(gè)學(xué)生所學(xué)的每門課程都有一個(gè)成績(jī)。由此可得到屬性組U上的一組函數(shù)依賴F：

F＝｛Sno→Sdept,Sdept→Mname,(Sno,Cname)→Grade｝2024/9/6ftt@17數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）

SnoCnameSdeptMnameGrade函數(shù)依賴圖2024/9/6ftt@18數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）關(guān)系模式Student<U,F>中存在的問題：⒈數(shù)據(jù)冗余太大浪費(fèi)大量的存儲(chǔ)空間

例：每一個(gè)系主任的姓名重復(fù)出現(xiàn)，重復(fù)次數(shù)與該系所有學(xué)生的所有課程成績(jī)出現(xiàn)次數(shù)相同。⒉更新異常（UpdateAnomalies）數(shù)據(jù)冗余，更新數(shù)據(jù)時(shí)，維護(hù)數(shù)據(jù)完整性代價(jià)大。

例：某系更換系主任后，系統(tǒng)必須修改與該系學(xué)生有關(guān)的每一個(gè)元組。2024/9/6ftt@19數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）⒊插入異常（InsertionAnomalies）該插的數(shù)據(jù)插不進(jìn)去

例：如果一個(gè)系剛成立，尚無(wú)學(xué)生，我們就無(wú)法把這個(gè)系及其系主任的信息存入數(shù)據(jù)庫(kù)。⒋刪除異常（DeletionAnomalies）不該刪除的數(shù)據(jù)不得不刪

例：如果某個(gè)系的學(xué)生全部畢業(yè)了，我們?cè)趧h除該系學(xué)生信息的同時(shí)，把這個(gè)系及其系主任的信息也丟掉了。2024/9/6ftt@20數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）結(jié)論：Student關(guān)系模式不是一個(gè)好的模式。一個(gè)“好”的模式應(yīng)當(dāng)不會(huì)發(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應(yīng)盡可能少。原因：由存在于模式中的某些數(shù)據(jù)依賴引起的。解決方法：通過(guò)分解關(guān)系模式來(lái)消除其中不合適的數(shù)據(jù)依賴。2024/9/6ftt@21如何設(shè)計(jì)一個(gè)合理的關(guān)系數(shù)據(jù)庫(kù)模式？與實(shí)際問題相結(jié)合例3.設(shè)計(jì)一個(gè)關(guān)系數(shù)據(jù)模型以存放學(xué)生各門課考試成績(jī)方案一：Grade關(guān)系（sno，sname，cno，cname，grade）方案二：Grade關(guān)系（sno，sname，cno，grade）

Course關(guān)系（cno，cname）方案三：Grade關(guān)系（sno，cnograde）

Student關(guān)系（sno，sname）

Course關(guān)系（cno，cname）規(guī)范化理論2024/9/6ftt@22例4.設(shè)計(jì)教學(xué)管理關(guān)系數(shù)據(jù)庫(kù)模型2024/9/6ftt@23方案一：SCT（sno,cno,tno,sname,grade,cname,tname）

問題分析關(guān)系SCT冗余度高修改困難插入問題刪除問題產(chǎn)生問題的原因

屬性間約束關(guān)系（即數(shù)據(jù)間的依賴關(guān)系）太強(qiáng)2024/9/6ftt@24方案二：分解成5個(gè)關(guān)系模式

students（sno，sname）、courses（cno，cname）

enrolls（sno，cno，grade）

teachers（tno,tname）、teaching（tno，cno）

CnoTnoC1T1C1T4C2T2C3T3C4T4CoursesStudentsEnrollsTeachersTeachCourses2024/9/6ftt@25什么是關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)理論？關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)的核心：關(guān)系模式設(shè)計(jì)關(guān)系模式的設(shè)計(jì)：

按照一定的原則從數(shù)量眾多而又相互關(guān)聯(lián)的數(shù)據(jù)中，構(gòu)造出一組既能較好地反映現(xiàn)實(shí)世界，而又有良好的操作性能的關(guān)系模式。關(guān)系模式優(yōu)劣，如何評(píng)價(jià)，如何改進(jìn)？

——本章所要解決的問題2024/9/6ftt@26什么是關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)理論？（續(xù)）規(guī)范化理論正是用來(lái)改造關(guān)系模式，通過(guò)分解關(guān)系模式來(lái)消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。數(shù)據(jù)庫(kù)語(yǔ)義學(xué)的重要內(nèi)容它借助近代代數(shù)工具，提出了一整套嚴(yán)密的理論和實(shí)用算法，把抽象的數(shù)學(xué)理論和具體的實(shí)際問題結(jié)合起來(lái)解決如何設(shè)計(jì)好一個(gè)關(guān)系數(shù)據(jù)模式問題是關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)的指南理論的基礎(chǔ)：數(shù)據(jù)的依賴（數(shù)據(jù)的相關(guān)性）2024/9/6ftt@27數(shù)據(jù)依賴相關(guān)概念函數(shù)依賴（FunctionalDependency）平凡函數(shù)依賴與非平凡函數(shù)依賴完全函數(shù)依賴與部分函數(shù)依賴傳遞函數(shù)依賴碼2024/9/6ftt@28函數(shù)依賴數(shù)據(jù)依賴的一種，它反映屬性或?qū)傩越M之間相依存，互相制約的關(guān)系，即反映現(xiàn)實(shí)世界的約束關(guān)系。定義： 設(shè)R（U）是屬性U上的一個(gè)關(guān)系模式，X和Y均為U={A1，A2，…，An}的子集，r為R的任一關(guān)系，如果對(duì)于r中的任意兩個(gè)元組u，v，只要有u[X]=v[X]，就有u[Y]=v[Y]，則稱X函數(shù)決定Y，或稱Y函數(shù)依賴于X，記為X→Y，稱X為決定因素。若X→Y，并且Y→X,則記為X←→Y。若Y不函數(shù)依賴于X,則記為X→Y。2024/9/6ftt@29函數(shù)依賴（續(xù)）函數(shù)依賴是語(yǔ)義范疇的概念。只能根據(jù)語(yǔ)義來(lái)確定函數(shù)依賴性的存在與否。例如“姓名→年齡”這個(gè)函數(shù)依賴只有在不允許有同名人的條件下成立。函數(shù)依賴反映屬性之間的一般規(guī)律，必須在關(guān)系模式下的任一個(gè)關(guān)系r中都滿足約束條件。數(shù)據(jù)庫(kù)設(shè)計(jì)者可以對(duì)現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定。例如規(guī)定不允許同名人出現(xiàn)，函數(shù)依賴“姓名→年齡”成立。所插入的元組必須滿足規(guī)定的函數(shù)依賴，若發(fā)現(xiàn)有同名人存在，則拒絕裝入該元組。2024/9/6ftt@30函數(shù)依賴（續(xù)）屬性間的聯(lián)系決定函數(shù)依賴關(guān)系。設(shè)X、Y均是U的子集，

1.X和Y間聯(lián)系是1:1，則X→Y且Y→X，則記為X←→Y。

2.X和Y間聯(lián)系是M:1(M>1)，則記為X→Y。

3.X和Y間聯(lián)系是M:N(M,N>1)，則X、Y間不存在函數(shù)依賴，則記為X→Y。關(guān)系中函數(shù)依賴關(guān)系可以用函數(shù)依賴圖表示。例：關(guān)系模式SCT（sno,cno,tno,sname,grade,cname,tname）snamecnamesnocnogradetnotname因不允許學(xué)生有重名sno→snamesname→sno因課程名唯一cno←→cname(sno,cno)→grade(sno,cno)→tnotno→tname2024/9/6ftt@31平凡函數(shù)依賴與非平凡函數(shù)依賴定義：設(shè)X,Y均為某關(guān)系上的屬性集，且X→Y：若Y包含于X即Y

X，則稱X→Y為平凡函數(shù)依賴；若Y不包含于X即Y

X，則稱X→Y為非平凡函數(shù)依賴。XYW例：設(shè)關(guān)系X,Y,W為關(guān)系R中的三個(gè)屬性組，屬性關(guān)系如下圖所示，問X→Y,X→W,W→Y各屬上述何種函數(shù)依賴。X→Y為平凡函數(shù)依賴

X→W,W→Y為非平凡函數(shù)依賴2024/9/6ftt@32平凡函數(shù)依賴與非平凡函數(shù)依賴（續(xù)）例：在關(guān)系SC(Sno,Cno,Grade)中，非平凡函數(shù)依賴：(Sno,Cno)→

Grade

平凡函數(shù)依賴：(Sno,Cno)→

Sno(Sno,Cno)→Cno于任一關(guān)系模式，平凡函數(shù)依賴都是必然成立的，它不反映新的語(yǔ)義，因此若不特別聲明，我們總是討論非平凡函數(shù)依賴。2024/9/6ftt@33完全函數(shù)依賴與部分函數(shù)依賴定義：在R(U)中,如果X→Y,并且對(duì)于X的任何真子集X’都有X’→Y,則稱Y完全依賴于X,記作X→Y；否則，如果X→Y，且X中存在一個(gè)真子集X’，使得X’→Y成立，則Y部分依賴于X，記作X→Y。例：在關(guān)系SC(Sno,Cno,Grade)中，Sno→Grade，Cno→Grade，因此：(Sno,Cno)→

Grade但：(Sno,Cno)→Sno,(Sno,Cno)

→Cno平凡函數(shù)依賴必定是部分函數(shù)依賴非平凡函數(shù)依賴也可能是部分函數(shù)依賴ｆpｆpp2024/9/6ftt@34完全函數(shù)依賴與部分函數(shù)依賴（續(xù)）例：Student(Sno,Sname,Ssex,Sage,Sdept)

Snoｆ

Sname,SnoｆSsex,Snoｆ

Sage,

SnoｆSdept(Sno,Sname)PSdept,(Sno,Ssex)PSdept2024/9/6ftt@35傳遞函數(shù)依賴定義：在關(guān)系模式R(U)中，如果X→Y，Y→Z，且Y

X，Y→X，則稱Z傳遞函數(shù)依賴于X。注：如果Y→X，即X←→Y，則Z直接依賴于X。例：在關(guān)系Std(Sno,Sdept,Mname)中，

有：Sno→Sdept，Sdept→Mname，Mname傳遞函數(shù)依賴于Sno。2024/9/6ftt@36碼的求解碼的定義數(shù)據(jù)依賴的公理系統(tǒng)閉包算法侯選碼的求解理論和算法函數(shù)依賴集等價(jià)最小函數(shù)依賴集2024/9/6ftt@37碼的定義定義：設(shè)K為關(guān)系模式R<U,F>中的屬性或?qū)傩越M合。若KU，則K稱為R的一個(gè)侯選碼（CandidateKey）。若關(guān)系模式R有多個(gè)候選碼，則選定其中的一個(gè)做為主碼（Primarykey）。主屬性：包含在每一個(gè)候選碼中的屬性，稱作主屬性。碼是關(guān)系模式中一個(gè)重要概念。候選碼能夠唯一地標(biāo)別關(guān)系的元組，是關(guān)系模式中一組最重要的屬性。主碼又和外部碼一起提供了一個(gè)表示關(guān)系間聯(lián)系的手段。f2024/9/6ftt@38數(shù)據(jù)依賴的公理系統(tǒng)一套推理規(guī)則，是模式分解算法的理論基礎(chǔ)用途求給定關(guān)系模式的碼討論如何推導(dǎo)函數(shù)依賴，即從已知的函數(shù)依賴集中推導(dǎo)出其他隱含的函數(shù)依賴。2024/9/6ftt@39Armstrong公理系統(tǒng)Armstrong公理系統(tǒng)

設(shè)有關(guān)系模式R(U,F)，X、Y、Z、W

U，則對(duì)R(U,F)有：A1（自反律）：若Y

X，則X→Y；A2（增廣律）：若X→Y，則XZ→YZ；A3（傳遞律）：若X→Y，Y→Z，則X→Z。定理Armstrong公理是正確的。即如果函數(shù)依賴F成立，則由F根據(jù)Armstrong公理所推導(dǎo)的函數(shù)依賴總是成立的。由Armstrong公理系統(tǒng)，可以得到以下三個(gè)推論：合成規(guī)則：若X→Y，X→Z，則X→YZ；分解規(guī)則：若X→Y，Z

Y，則X→Z；偽傳遞規(guī)則：若X→Y，WY→Z，則XW→Z。引理X→A1A2…Ak成立的充分必要條件是X→Ai成立（i=1,2,…,k）。2024/9/6ftt@40函數(shù)依賴的閉包定義

設(shè)關(guān)系模式R(U,F)，U為R的屬性集合，F(xiàn)為其函數(shù)依賴集，則稱所有用Armstrong公理從F推出的函數(shù)依賴X→R中Ai的屬性集合，為X的屬性閉包，記作X+，讀作X關(guān)于函數(shù)依賴集F的閉包。引理

設(shè)關(guān)系模式R(U,F)，U為R的屬性集合，F(xiàn)為其函數(shù)依賴集，X、Y

U，則從F推出X→Y的充要條件是Y

X+。用途將判定X→Y是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，就轉(zhuǎn)化為求出XF+

，判定Y是否為XF+的子集的問題。2024/9/6ftt@41求解閉包的算法算法求屬性集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)(V→W

F∧V

X（i）∧A

W)}；(3)X（i+1）=B∪X（i）；(4)判斷X（i+1）=X

（i）嗎?(5)若相等或X（i）=U,則X（i）就是XF+,算法終止。(6)若否，則i=i+l，返回第(2)步。2024/9/6ftt@42求解閉包的算法（續(xù)）算法偽代碼表示：（輸出結(jié)果XF+存儲(chǔ)在變量result中）result:=X;WHILE(result發(fā)生變化)DOFOREACH函數(shù)依賴Y→ZINFDOBEGINIFY

resultTHENresult:=result∪Z;END2024/9/6ftt@43求解閉包示例例1.已知U={A,B,C,D};A→B,BC→D.A+=AB.C+=C.(AC)+=ABCD.ACDB2024/9/6ftt@44求解閉包示例（續(xù)）例2.已知關(guān)系模式R<U，F(xiàn)>，其中U={A，B，C，D，E}；F={AB→C，B→D，C→E，EC→B，AC→B}。求（AB）F+

。(1)設(shè)X（0）=AB；(2)計(jì)算X（1）:逐一的掃描F集合中各個(gè)函數(shù)依賴，找左部為A，B或AB的函數(shù)依賴。得到兩個(gè)：AB→C，B→D。于是X（1）=AB∪CD=ABCD。(3)因?yàn)閄（0）≠X（1），所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到AB→C，B→D，C→E，AC→B，于是X（2）=X（1）∪BCDE=ABCDE。(4)因?yàn)閄（2）=U，算法終止所以（AB）F+=ABCDE。2024/9/6ftt@45閉包求解與碼利用閉包算法，能夠正確判斷一個(gè)新的函數(shù)依賴能否從給定的函數(shù)依賴F集合中推導(dǎo)出來(lái)。通過(guò)閉包算法，可以從關(guān)系R(U,F)中給定的函數(shù)依賴集合F推導(dǎo)出所有的函數(shù)依賴。還可以得出結(jié)論：關(guān)系R(U,F)中，其中某個(gè)給定屬性集K

U，當(dāng)且僅當(dāng)K關(guān)于給定函數(shù)依賴集F的閉包K+是R的所有屬性集合U時(shí)，K即為關(guān)系R的超碼。當(dāng)且僅當(dāng)屬性集K中不存在任一真子集K’的閉包(K’)+也是R的所有屬性集合U時(shí)，即屬性集K是最小屬性集合構(gòu)成的超碼時(shí)

，K就是該關(guān)系R(U,F)的候選碼。2024/9/6ftt@46候選碼的求解理論和算法對(duì)于給定的關(guān)系R（A1A2…An）和函數(shù)依賴集F，可將其屬性分為4類：L類：僅出現(xiàn)在F函數(shù)依賴左部的屬性 R類：僅出現(xiàn)在F函數(shù)依賴右部的屬性N類：在F函數(shù)依賴的左右兩部均未出現(xiàn)的屬性LR類：在F函數(shù)依賴的左右兩部均出現(xiàn)的屬性定理：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，若X是R的L類屬性，則X必為R的任一侯選碼的成員。推論：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，若X是R的L類屬性，且X+包含了R的全部屬性，則X必為R的唯一侯選碼。2024/9/6ftt@47例：設(shè)有關(guān)系模式R(A,B,C,D)，其函數(shù)依賴集F={D->B,B->D,AD->B,AC->D}，求R的所有候選碼。解：考察F發(fā)現(xiàn)，A,C兩屬性是L類屬性，由以上的定理可知，AC必是R的候選碼成員，又因?yàn)锳C+=ABCD，所以AC是R的唯一侯選碼。2024/9/6ftt@48定理：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，若X是R的R類屬性，則X不是R的任何候選碼的成員。定理：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，若X是R的N類屬性，則X必為R的任一候選碼的成員。例：設(shè)有關(guān)系模式R（A,B,C,D,E,P），R的函數(shù)依賴集為F={A->D,E->D,D->B,BC->D,DC->A}，求R的所有候選碼。解：考察F發(fā)現(xiàn)，屬性E,C是L類屬性，故E,C必在R的任何候選碼中。又因?yàn)閷傩訮是N類屬性，所以P也在R的任何候選碼中。而CEP+=ABCDEP，所以CEP是R的唯一候選碼。推論：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，如果X是R的N類和L類組成的屬性集，且X+包含了R的全部屬性，則X是R的唯一候選碼。2024/9/6ftt@49示例關(guān)系模式S(S#,SN,SD,DMN,C#,G)函數(shù)依賴：

（S#，C#） GS#

SN，（S#，C#） SNS#SD，（S#，C#） SDSD

DMN 候選碼：（S#，C#）2024/9/6ftt@50函數(shù)依賴集等價(jià)定義如果G+=F+，就說(shuō)函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。2024/9/6ftt@51最小函數(shù)依賴集定義如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。(1)F中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。(2)F中不存在這樣的函數(shù)依賴X→A，使得F與F-{X→A}等價(jià)。(3)F中不存在這樣的函數(shù)依賴X→A，X有真子集Z使得F-{X→A}∪{Z→A}與F等價(jià)。2024/9/6ftt@52最小函數(shù)依賴集示例例.對(duì)于關(guān)系模式S<U，F(xiàn)>，其中：

U={SNO,SDEPT,DMN,CNAME,G}，

F={SNO→SDEPT，SDEPT→DMN，(SNO,CNAME)→G}設(shè)F’={SNO→SDEPT，SNO→DMN，SDEPT→DMN，

(SNO,CNAME)

→G，(SNO,SDEPT)→SDEPT}F是最小覆蓋，而F’不是。因?yàn)椋篎’—{SNO→MN}與F’等價(jià)；

F’—{(SNO,SDEPT)→SDEPT}也與F’等價(jià)。2024/9/6ftt@53范式定義關(guān)系模式滿足的確定約束條件稱為范式，根據(jù)滿足約束條件的級(jí)別不同，范式由低到高分為1NF，2NF，3NF，BCNF，4NF，5NF等。不同的級(jí)別范式性質(zhì)不同。關(guān)系模式的規(guī)范化：把一個(gè)低一級(jí)的關(guān)系模式分解為高一級(jí)關(guān)系模式的過(guò)程。1NF2NF3NF4NFBCNF5NF各種范式之間存在聯(lián)系：2024/9/6ftt@54范式第一范式（1NF）部分函數(shù)依賴與第二范式（2NF）傳遞函數(shù)依賴與第三范式（3NF）主屬性的不良依賴與BC范式（BCNF）多值依賴與第四范式（4NF）（了解）2024/9/6ftt@55第一范式（1NF）1NF的定義：如果一個(gè)關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項(xiàng)，則R∈1NF。關(guān)系中每一分量不可再分，即屬性不能再分，是屬性項(xiàng)而不是屬性組。即不能以集合、序列等作為屬性值。第一范式是對(duì)關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫(kù)模式不能稱為關(guān)系數(shù)據(jù)庫(kù)。教工號(hào)教工名所在部門工資基本工資補(bǔ)貼工資005001王武管理學(xué)院

800.00500.00005002張三計(jì)算機(jī)學(xué)院

900.00600.002024/9/6ftt@561NF（續(xù)）例1：A1,A2,A3,…，Ak,…,An

Ak1Ak2例2：工資(工號(hào),姓名,工資(基本工資,年績(jī)津貼,煤電補(bǔ)貼))不滿足1NF的關(guān)系稱為非規(guī)范化關(guān)系。關(guān)系數(shù)據(jù)模型不能存儲(chǔ)上兩個(gè)例子（非規(guī)范化關(guān)系）,在關(guān)系數(shù)據(jù)庫(kù)中不允許非規(guī)范化關(guān)系的存在。轉(zhuǎn)化方法：

1)A1,A2,A3,…，Ak1，Ak2，…,An 2)工資(工號(hào),姓名,基本工資,津貼,獎(jiǎng)金)2024/9/6ftt@571NF（續(xù)）分量是否需要再分，與具體應(yīng)用有關(guān)。如果用到值的一部分，則需要進(jìn)一步分割。

如果只是查詢出生日期，則它滿足1NF；如果查詢兩人生日是否相同，則只比較月、日，需要將生日分解，就不滿足1NF。如果比較兩人的生肖呢？姓名生日王軍68.7.10張立69.7.10李明80.3.28姓名年月日王軍687.10張立697.10李明803.282024/9/6ftt@58第二范式（2NF）關(guān)系模式S(S#,SN,SD,DMN,C#,G)不良特性插入異常：如果學(xué)生沒有選課，關(guān)于他的個(gè)人信息及所在系的信息就無(wú)法插入刪除異常：如果刪除學(xué)生的選課信息，則有關(guān)他的個(gè)人信息及所在系的信息也隨之刪除了更新異常：如果學(xué)生轉(zhuǎn)系，若他選修了k門課，則需要修改k次數(shù)據(jù)冗余：如果一個(gè)學(xué)生選修了k門課，則有關(guān)他的所在系的信息重復(fù)2024/9/6ftt@59S#C#GSDDMNSSNS的主碼是：（S#,C#）關(guān)系模式S(S#,SN,SD,DMN,C#,G)2024/9/6ftt@602NF（續(xù)）定義若R

1NF，且每個(gè)非主屬性完全依賴于碼，則稱R是第二范式，簡(jiǎn)記為2NF。

消除非主屬性對(duì)碼的部分依賴。若關(guān)系模型H包含的每一關(guān)系模式都是2NF的，則稱該關(guān)系模型是2NF的?！?NF∈1NF。2024/9/6ftt@612NF（續(xù)）如S(S#,SN,SD,DMN,C#,G)，S2NF，因?yàn)?/p>

改造非主屬性有兩種，一種完全依賴于碼，一種部分依賴于碼。將S分解為： SC(S#,C#,G) S_SD(S#,SN,SD,DMN)快速熱身關(guān)系模式R（A，B，C，D），碼為AB，給出它的一個(gè)函數(shù)依賴集，使得R屬于1NF而不屬于2NF。（S#，C#） SN（S#，C#）SD2024/9/6ftt@62例1：

SCT（SNO,CNO,CN,GRADE,TNAME,BDATE,SALARY）

F={（SNO,CNO）→GRADE,CNO→CN,CNO→TNAME,

TNAME→BDATE,TNAME→SALARY}非2NF存在問題：1.數(shù)據(jù)冗余；2.插入，刪除異常3.修改麻煩。原因：非主屬性部分依賴于侯選關(guān)鍵字，關(guān)鍵字是一個(gè)元組區(qū)別其它元組的依賴，同時(shí)也是一個(gè)元組賴以存在的依據(jù)。分解：SC(SNO,CNO,GRADE),

CT(CNO,CN,TNAME,BDATE,SALARY)例2：

R=(ABCD,{AB→C，C→D})

R為2NF2NF（續(xù)）2024/9/6ftt@63第三范式（3NF）S_SD(S#,SN,SD,DMN)不良特性插入異常：如果系中沒有學(xué)生，則有關(guān)系的信息就無(wú)法插入刪除異常：如果學(xué)生全部畢業(yè)了，則在刪除學(xué)生信息的同時(shí)有關(guān)系的信息也隨之刪除了更新異常：如果學(xué)生轉(zhuǎn)系，不但要修改SD，還要修改DMN，如果換系主任，則該系每個(gè)學(xué)生元組都要做相應(yīng)修改數(shù)據(jù)冗余：每個(gè)學(xué)生都存儲(chǔ)了所在系的系主任的信息2024/9/6ftt@643NF（續(xù)）S_SD(S#,SN,SD,DMN)

因?yàn)橛蠸#SD，SDDMN則S_SD

3NF，改造 將S分解為 STUDENT(S#,SN,SD) DEPT(SD,DMN)快速熱身 關(guān)系模式R（A，B，C，D），碼為AB，給出它的一個(gè)函數(shù)依賴集，使得R屬于2NF而不屬于3NF。S_SDS#SDDMN2024/9/6ftt@653NF（續(xù)）定義關(guān)系模式R<U,F>中，若不存在這樣的碼X，屬性組Y及非主屬性Z(ZY)，使得下式成立，X

Y,Y

Z,Y

X

則稱R是第三范式，簡(jiǎn)記為R3NF。消除非主屬性對(duì)碼的傳遞依賴。若關(guān)系模型R包含的每一關(guān)系模式都是3NF的，則稱該關(guān)系模型是3NF的。定理：一個(gè)3NF的關(guān)系(模式)必定是2NF的(3NF∈2NF∈1NF)。2024/9/6ftt@663NF（續(xù)）例1：

CT（CNO,TNAME,BDATE,SALARY）

存在問題：（1）不能存放不開課的教師

（2）教師信息和課程數(shù)一樣多原因：存在傳遞函數(shù)依賴

CT(CNO,TNAME,BDATE,SALARY）非3NF分解：

C(CNO,TNAME),

T(TNAME,BDATE,SALARY)

屬于3NF。

2024/9/6ftt@67BC范式（BCNF）例1.STC(S#,T#,C#)假設(shè)每一教師只教一門課。每門課由若干教師教，但某一學(xué)生選定某門課，就確定了一個(gè)固定的教師。可得函數(shù)依賴：T#

C#，(S#,C#)T#，(S#,T#)C#(S,C)和(S,T)都可以作為候選碼。S，T，C都是關(guān)系的主屬性。STC∈3NFT→C，即T也屬?zèng)Q定屬性集，可是T只是主屬性，它既不是候選碼，也不包含候選碼。SCTSTCSTC2024/9/6ftt@68BCNF（續(xù)）STC仍然不是一個(gè)理想的關(guān)系模式不良特性插入異常：如果沒有學(xué)生選修某位老師的任課，則該老師擔(dān)任課程的信息就無(wú)法插入刪除異常：刪除學(xué)生選課信息，會(huì)刪除掉老師的任課信息更新異常：如果老師所教授的課程有所改動(dòng)，則所有選修該老師課程的學(xué)生元組都要做改動(dòng)數(shù)據(jù)冗余：每位學(xué)生都存儲(chǔ)了有關(guān)老師所教課程的信息癥由主屬性對(duì)碼的不良依賴：主屬性C依賴于T，即主屬性C部分依賴于碼2024/9/6ftt@69BCNF（續(xù)）解決方法：采用投影分解法，將STC分解為兩個(gè)關(guān)系模式：ST(S,T)，碼：(S,T)TC(T,C)，碼：TSCTSTCSTCSTSTTCTC2024/9/6ftt@70BCNF（續(xù)）定義關(guān)系模式R<U,F>中，對(duì)于屬性組X、Y，若X

Y且YX時(shí)X必含有碼，則R<U,F>

BCNF

如STC(S#,T#,C#)，STCBCNF，因?yàn)門#C#，而T#不含有碼BCNF的關(guān)系模式所具有的性質(zhì)所有非主屬性都完全函數(shù)依賴于每個(gè)候選碼。所有主屬性都完全函數(shù)依賴于每個(gè)不包含它的候選碼。沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。2024/9/6ftt@71BCNF（續(xù)）3NF與BCNF的關(guān)系定理：BCNF滿足3NF(BCNF∈3NF∈2NF∈1NF)。如果R∈3NF，且R只有一個(gè)候選碼，則R必