數(shù)據(jù)庫(kù)6-關(guān)系數(shù)據(jù)理論

AnIntroductiontoDatabaseSystem數(shù)據(jù)庫(kù)系統(tǒng)概論AnIntroductiontoDatabaseSystem第六章關(guān)系數(shù)據(jù)理論6.1函數(shù)依賴用形式化方法研究一個(gè)關(guān)系中各屬性之間的語(yǔ)義關(guān)系。函數(shù)依賴的定義：

若關(guān)系R的任意兩個(gè)元組在屬性A1、A2、…、An上一致(即有相同分量值)，則這兩個(gè)元組在屬性B上也一致，則稱屬性A1A2…An函數(shù)決定B，或稱屬性B函數(shù)依賴于A1A2…An。記為：A1A2…An→BAnIntroductiontoDatabaseSystemtuAB若t和u在A上一致,則在B上也一致函數(shù)依賴的定義關(guān)系：學(xué)生(學(xué)號(hào),姓名,性別)中為何學(xué)號(hào)→姓名成立？在一個(gè)關(guān)系中，不存在（鍵值）完全相同的元組。如果不存在兩個(gè)元組具有相同學(xué)號(hào)，即每個(gè)元組各表示一個(gè)學(xué)生，則學(xué)號(hào)→姓名成立。關(guān)系：學(xué)生(學(xué)號(hào),姓名,課號(hào),成績(jī))中學(xué)號(hào)→姓名？如果兩個(gè)元組具有相同學(xué)號(hào)，則兩個(gè)元組指同一個(gè)學(xué)生，故具有相同姓名。但是：學(xué)號(hào)→成績(jī)？如果兩個(gè)元組學(xué)號(hào)相同，但課程號(hào)不同，其成績(jī)亦可能不同。只有在學(xué)號(hào)，課號(hào)都確定的情況下，成績(jī)才被確定，因此：學(xué)號(hào)，課號(hào)→成績(jī)函數(shù)依賴的定義(續(xù))AnIntroductiontoDatabaseSystem函數(shù)依賴的定義(續(xù))[例1]建立一個(gè)描述學(xué)校教務(wù)的數(shù)據(jù)庫(kù)： 學(xué)生的學(xué)號(hào)（Sno）、所在系（Sdept） 系主任姓名（Mname）、課程名（Cname） 成績(jī)（Grade）單一的關(guān)系模式：Student<U、F>U＝｛Sno,Sdept,Mname,Cname,Grade｝AnIntroductiontoDatabaseSystem函數(shù)依賴的定義(續(xù))

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

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

SnoCnameSdeptMnameGradeExampleMovies(title,year,length,filmType,studioname,starName)ReasonableFD’stoassert:titleyear→lengthtitleyear→filmTypetitleyear→studioNameBut titleyear→starNametitleyearlengthfilmtypestudioNamestarNameStarWarsStarWarsStarWarsMightyDucksWayne’sWorldWayne’sWorld1977197719771991199219921241241241049595colorcolorcolorcolorcolorcolorFoxFoxFoxDisneyParamountParamountCarrieFisherMarkHamillHarrisonFordEmilioEstevezDanaCarveyMikeMeyers6.2函數(shù)依賴規(guī)則什么是函數(shù)依賴規(guī)則？為何需要它？在一個(gè)給定關(guān)系上，已知一組函數(shù)依賴作為前提條件。根據(jù)一組函數(shù)依賴規(guī)則，就可推斷另一些函數(shù)依賴。這種計(jì)算和驗(yàn)證可有效減少冗余，得到良好的關(guān)系設(shè)計(jì)。函數(shù)依賴規(guī)則重要的函數(shù)依賴規(guī)則：分解／合并(Splitting/combining)規(guī)則平凡依賴(TrivialDependance)規(guī)則

傳遞(Transitivy)規(guī)則

Armstrong公理

分解/合并規(guī)則分解／合并規(guī)則(Splitting/CombiningRule)：A1A2…An→B1B2…Bm等價(jià)于

A1A2…An→B1A1A2…An→B2…A1A2…An

→Bm注意：函數(shù)依賴的左面不能分解合并。分解/合并規(guī)則（續(xù)）

例如：關(guān)系Movies中，

titleyear→lengthfilmTypestudioName

等價(jià)于：

titleyear→length titleyear→fileType titleyear→studioName

但是，學(xué)號(hào)課號(hào)→成績(jī)不能分解為： 學(xué)號(hào)→成績(jī) 課號(hào)→成績(jī)AnIntroductiontoDatabaseSystem平凡函數(shù)依賴與非平凡函數(shù)依賴在關(guān)系模式R(U)中，對(duì)于U的子集X和Y，如果X→Y，但YX，則稱X→Y是非平凡的函數(shù)依賴若X→Y，但YX,則稱X→Y是平凡的函數(shù)依賴?yán)涸陉P(guān)系SC(Sno,Cno,Grade)中，非平凡函數(shù)依賴：(Sno,Cno)→

Grade

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

Sno(Sno,Cno)→CnoAnIntroductiontoDatabaseSystem平凡函數(shù)依賴與非平凡函數(shù)依賴（續(xù)）若X→Y，則X稱為這個(gè)函數(shù)依賴的決定屬性組，也稱為決定因素（Determinant）。若X→Y，Y→X，則記作X←→Y。若Y不函數(shù)依賴于X，則記作X→Y。AnIntroductiontoDatabaseSystem完全函數(shù)依賴與部分函數(shù)依賴定義

在R(U)中，如果X→Y，并且對(duì)于X的任何一個(gè)真子集X’，都有X’Y,則稱Y對(duì)X完全函數(shù)依賴，記作

XFY。若X→Y，但Y不完全函數(shù)依賴于X，則稱Y對(duì)X部分函數(shù)依賴，記作XPY。

AnIntroductiontoDatabaseSystem完全函數(shù)依賴與部分函數(shù)依賴（續(xù)）[例1]中(Sno,Cno)→Grade是完全函數(shù)依賴，

(Sno,Cno)→Sdept是部分函數(shù)依賴因?yàn)镾no→Sdept成立，且Sno是（Sno，Cno）的真子集

FPAnIntroductiontoDatabaseSystem傳遞函數(shù)依賴定義6.3

在R(U)中，如果X→Y，(YX),Y→XY→Z，則稱Z對(duì)X傳遞函數(shù)依賴。記為：X→Z

注:如果Y→X，即X←→Y，則Z直接依賴于X。例:在關(guān)系Std(Sno,Sdept,Mname)中，有：

Sno→Sdept，Sdept→MnameMname傳遞函數(shù)依賴于Sno傳遞AnIntroductiontoDatabaseSystem碼定義：

設(shè)K為R<U,F>中的屬性或?qū)傩越M合。若K

U，則K稱為R的侯選碼（CandidateKey）。若候選碼多于一個(gè)，則選定其中的一個(gè)做為主碼（PrimaryKey）。FAnIntroductiontoDatabaseSystem碼（續(xù)）主屬性與非主屬性包含在任何一個(gè)候選碼中的屬性，稱為主屬性（Primeattribute）不包含在任何碼中的屬性稱為非主屬性（Nonprimeattribute）或非碼屬性（Non-keyattribute）全碼整個(gè)屬性組是碼，稱為全碼（All-key）AnIntroductiontoDatabaseSystem碼（續(xù)）[例2]

關(guān)系模式S(Sno,Sdept,Sage)，單個(gè)屬性Sno是碼，

SC（Sno，Cno，Grade）中，（Sno，Cno）是碼[例3]

關(guān)系模式R（P，W，A）

P：演奏者W：作品A：聽眾一個(gè)演奏者可以演奏多個(gè)作品某一作品可被多個(gè)演奏者演奏聽眾可以欣賞不同演奏者的不同作品碼為(P，W，A)，即All-KeyAnIntroductiontoDatabaseSystem外部碼定義6.5

關(guān)系模式R中屬性或?qū)傩越MX并非R的碼，但X是另一個(gè)關(guān)系模式的碼，則稱X是R的外部碼（Foreignkey）也稱外碼如在SC（Sno，Cno，Grade）中，Sno不是碼，但Sno是關(guān)系模式S（Sno，Sdept，Sage）的碼，則Sno是關(guān)系模式SC的外部碼

主碼與外部碼一起提供了表示關(guān)系間聯(lián)系的手段計(jì)算屬性的閉包屬性閉包的概念設(shè)S是關(guān)系R上的函數(shù)依賴集，A={A1,A2,…,An}是R上的屬性集，則屬性集A可函數(shù)決定的最大屬性集合（一定存在這樣的集合）稱做A的閉包，記做：A+

。這個(gè)集合如何計(jì)算？這種計(jì)算有何用途？屬性的閉包：

設(shè)S是關(guān)系R上的函數(shù)依賴集，A={A1,A2,…,An}是R上的屬性集，屬性集A在函數(shù)依賴集S下的閉包(closure)是這樣一個(gè)屬性集B，對(duì)于關(guān)系R的所有實(shí)例，函數(shù)依賴：A1A2…An→B均成立，即A1A2…An→B“邏輯蘊(yùn)含于”函數(shù)依賴集S。

屬性集{A1,A2,…,An}的閉包表示為{A1,A2,…,An}+。 顯然：{A1,A2,…,An}含于{A1,A2,…,An}+若A1A2…An→X，則X含于B計(jì)算屬性的閉包(續(xù))計(jì)算屬性的閉包(續(xù))計(jì)算屬性的閉包：

給定函數(shù)依賴集S，和屬性集A={A1,A2,…,An}，如何計(jì)算A+？設(shè)屬性集X是A的閉包，將X初始化為{A1,A2,…,An}，即為閉包的最小集合。遍歷S中的每個(gè)函數(shù)依賴，對(duì)于每個(gè)函數(shù)依賴式：B1B2…Bm→C。如果B1、B2、…、Bm都在X中，而C不在X中，則把C加入X中。重復(fù)第2步，直到遍歷完S中所有函數(shù)依賴，而沒(méi)有新屬性能加入到X中。最終屬性集X即為屬性集A在函數(shù)依賴集S下的閉包A+。

Y+newY+XAExampleR=(A,B,C,G,H,I)F={A

B

A

C

CG

H

CG

I

B

H}(AG)+1. result=AG2. result=ABCG (A

CandAB)3. result=ABCGH (CG

HandCGAGBC)4. result=ABCGHI (CG

IandCGAGBCH)IsAGacandidatekey?IsAGasuperkey?DoesAG

R?==Is(AG)+RIsanysubsetofAGasuperkey?DoesA

R?==Is(A)+RDoesG

R?==Is(G)+R6.2關(guān)系數(shù)據(jù)庫(kù)模式設(shè)計(jì)關(guān)系模式設(shè)計(jì)中出現(xiàn)冗余的原因：關(guān)系模式設(shè)計(jì)中可能出現(xiàn)各種冗余，即同一事實(shí)在多個(gè)元組中重復(fù)。造成冗余的原因通常是將同一個(gè)對(duì)象的單值和多值特征混合在同一個(gè)關(guān)系中。例如：學(xué)生關(guān)系學(xué)號(hào)

姓名家庭地址課號(hào)

成績(jī)

系號(hào)

系主任

S1S1S1S2S3S3S4S4

N1N1N1N2N3N3N4N4A1A1A1A2A3A3A4A4C1C2C3C2C1C3C1C2

AABBAABA

D1D1D1D1D2D2D2D2

M1M1M1M1M2M2M2M2

關(guān)系數(shù)據(jù)庫(kù)模式設(shè)計(jì)（續(xù)）“異常”指什么？

異常anomaly，即不符合規(guī)范的設(shè)計(jì)，導(dǎo)致操作數(shù)據(jù)庫(kù)時(shí)，出現(xiàn)影響數(shù)據(jù)一致性的現(xiàn)象。關(guān)系設(shè)計(jì)中可能出現(xiàn)哪些異常？冗余。同一信息在多個(gè)元組中不必要的重復(fù)。浪費(fèi)空間，增加更新操作的復(fù)雜度，影響數(shù)據(jù)一致性。修改異常。修改某個(gè)元組的信息，而重復(fù)的信息可能未修改而破壞一致性?；虿迦霐?shù)據(jù)時(shí)，某些有用信息暫時(shí)無(wú)法插入。刪除異常。刪除某個(gè)對(duì)象時(shí)，必須刪除多個(gè)元組而不是一個(gè)元組，操作不當(dāng)有可能破壞數(shù)據(jù)一致性?；騽h除元組時(shí)，同時(shí)刪除了其它有用信息。插入異常AnIntroductiontoDatabaseSystem解決方法結(jié)論：學(xué)生關(guān)系模式不是一個(gè)好的模式?！昂谩钡哪Ｊ剑翰粫?huì)發(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應(yīng)盡可能少原因：由存在于模式中的某些數(shù)據(jù)依賴引起的解決方法：通過(guò)分解關(guān)系模式來(lái)消除其中不合適的數(shù)據(jù)依賴關(guān)系分解關(guān)系分解：

給定一個(gè)關(guān)系R{A1,A2,…,An}，將R分解為兩個(gè)關(guān)系S{B1,B2,…,Bm}和T{C1,C2,…,Ck}，使得：{A1,A2,…,An}={B1,B2,…,Bm}∪{C1,C2,…,Ck}S中的元組是R的所有元組在{B1,B2,…,Bm}上的投影；

T中的元組是R的所有元組在{C1,C2,…,Ck}上的投影。

投影：

R中的一個(gè)元組在屬性B1,B2,…,Bm上的分量，構(gòu)成S中的一個(gè)元組，且保持元組不重復(fù)。為何進(jìn)行分解： 為了避免異常，用幾個(gè)關(guān)系代替原有的關(guān)系，且保持?jǐn)?shù)據(jù)一致性。

關(guān)系分解（續(xù)）上例學(xué)生(學(xué)號(hào),姓名,家庭地址,課號(hào),成績(jī),系號(hào)，系主任)可分解為右面的學(xué)生、選修兩個(gè)關(guān)系。分解后的兩個(gè)關(guān)系減少了異常。這兩個(gè)關(guān)系應(yīng)可連接(join)得到原有的關(guān)系元組，且不改變?cè)姓Z(yǔ)義。學(xué)號(hào)姓名家庭地址系號(hào)系主任S1S2S3S4

N1N2N3N4A1A2A3A4D1D1D2D2M1M1M2M2學(xué)號(hào)課號(hào)成績(jī)S1S1S1S2S3S3S4S4

C1C2C3C2C1C3C1C2AABBAABAAnIntroductiontoDatabaseSystem6.3規(guī)范化范式是符合某一種級(jí)別的關(guān)系模式的集合關(guān)系數(shù)據(jù)庫(kù)中的關(guān)系必須滿足一定的要求。滿足不同程度要求的為不同范式范式的種類：

第一范式(1NF)

第二范式(2NF)

第三范式(3NF) BC范式(BCNF)

第四范式(4NF)

第五范式(5NF)AnIntroductiontoDatabaseSystem范式各種范式之間存在聯(lián)系：某一關(guān)系模式R為第n范式，可簡(jiǎn)記為R∈nNF。一個(gè)低一級(jí)范式的關(guān)系模式，通過(guò)模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式的集合，這種過(guò)程就叫規(guī)范化

AnIntroductiontoDatabaseSystem1NF1NF的定義 如果一個(gè)關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項(xiàng)，則R∈1NF第一范式是對(duì)關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫(kù)模式不能稱為關(guān)系數(shù)據(jù)庫(kù)但是滿足第一范式的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式AnIntroductiontoDatabaseSystem1NF（續(xù)）[例4]關(guān)系模式S-L-C(Sno,Sdept,Sloc,Cno,Grade)Sloc為學(xué)生住處，假設(shè)每個(gè)系的學(xué)生住在同一個(gè)地方函數(shù)依賴包括：

(Sno,Cno)FGradeSno→Sdept(Sno,Cno)PSdeptSno→Sloc(Sno,Cno)PSlocSdept→SlocAnIntroductiontoDatabaseSystem1NF（續(xù)）S-L-C的碼為(Sno,Cno)S-L-C滿足第一范式。非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno,Cno)SnoCnoGradeSdeptSlocS-L-CAnIntroductiontoDatabaseSystemS-L-C不是一個(gè)好的關(guān)系模式（續(xù)）(1)插入異常(2)刪除異常(3)數(shù)據(jù)冗余度大(4)修改復(fù)雜AnIntroductiontoDatabaseSystemS-L-C不是一個(gè)好的關(guān)系模式（續(xù)）原因

Sdept、Sloc部分函數(shù)依賴于碼。解決方法

S-L-C分解為兩個(gè)關(guān)系模式，以消除這些部分函數(shù)依賴SC（Sno，Cno，Grade）

S-L（Sno，Sdept，Sloc）AnIntroductiontoDatabaseSystem1NF（續(xù)）函數(shù)依賴圖：SnoCnoGradeSCS-LSnoSdeptSloc關(guān)系模式SC的碼為（Sno，Cno）關(guān)系模式S-L的碼為Sno這樣非主屬性對(duì)碼都是完全函數(shù)依賴

AnIntroductiontoDatabaseSystem2NF2NF的定義

定義：

若R∈1NF，且每一個(gè)非主屬性完全函數(shù)依賴于碼，則R∈2NF。 例：S-L-C(Sno,Sdept,Sloc,Cno,Grade)∈1NFS-L-C(Sno,Sdept,Sloc,Cno,Grade)∈2NF SC（Sno，Cno，Grade）∈

2NF S-L（Sno，Sdept，Sloc）∈

2NF1NF分解為2NF范式的方法分解的原則： 把一個(gè)關(guān)系模式分解成一個(gè)由若干個(gè)關(guān)系模式構(gòu)成的集合，且這些關(guān)系模式應(yīng)滿足如下條件：每個(gè)關(guān)系模式都滿足2NF。分解后的元組能如實(shí)反映原有關(guān)系中的數(shù)據(jù)，即能由分解的關(guān)系準(zhǔn)確重構(gòu)原有關(guān)系。分解策略：消除違背2NF的函數(shù)依賴：找一個(gè)違背2NF的非平凡函數(shù)依賴A1A2…An→B1B2…Bm。

把關(guān)系R分解成兩個(gè)關(guān)系：

R1(A1,A2,…,An,B1,B2,…,Bm)。R2(A1,A2,…,An,所有其它屬性)。(即從R中刪除B1,B2,…,Bm列)R1,R2若不滿足2NF，則再分解。

1NF分解為2NF范式的方法

例如：R(學(xué)號(hào),姓名,家庭地址,課號(hào),成績(jī),系號(hào),系主任)不滿足2NF。

1R中違背2NF的非平凡函數(shù)依賴： 學(xué)號(hào)→姓名,家庭地址,系號(hào),系主任

2分解為：R1(學(xué)號(hào),姓名,家庭地址,系號(hào),系主任) R2(學(xué)號(hào),課號(hào),成績(jī))

AnIntroductiontoDatabaseSystem3NF3NF的定義

定義6.7

關(guān)系模式R<U，F(xiàn)>

中若不存在這樣的碼X、屬性組Y及非主屬性Z（ZY）,使得X→Y，Y→Z成立，

Y→X，則稱R<U，F(xiàn)>∈3NF。若R∈3NF，則每一個(gè)非主屬性既不部分依賴于碼也不傳遞依賴于碼。AnIntroductiontoDatabaseSystem3NF（續(xù)）例：2NF關(guān)系模式S-L(Sno,Sdept,Sloc)中函數(shù)依賴：

Sno→SdeptSdept→SnoSdept→Sloc

可得：

Sno→Sloc，即S-L中存在非主屬性對(duì)碼的傳遞函數(shù)依賴，S-L∈3NF傳遞AnIntroductiontoDatabaseSystem3NF（續(xù)）函數(shù)依賴圖：S-LSnoSdeptSlocAnIntroductiontoDatabaseSystem3NF（續(xù)）解決方法采用投影分解法，把S-L分解為兩個(gè)關(guān)系模式，以消除傳遞函數(shù)依賴：S-D（Sno，Sdept）

D-L（Sdept，Sloc）S-D的碼為Sno，D-L的碼為Sdept。分解后的關(guān)系模式S-D與D-L中不再存在傳遞依賴AnIntroductiontoDatabaseSystem3NF（續(xù)）S-D的碼為Sno，D-L的碼為SdeptSnoSdeptS-DSdeptSlocD-LS-L(Sno,Sdept,Sloc)∈2NFS-L(Sno,Sdept,Sloc)∈3NFS-D(Sno，Sdept)∈3NFD-L(Sdept，Sloc)∈3NFAnIntroductiontoDatabaseSystem3NF（續(xù)）采用投影分解法將一個(gè)2NF的關(guān)系分解為多個(gè)3NF的關(guān)系，可以在一定程度上解決原2NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問(wèn)題。將一個(gè)2NF關(guān)系分解為多個(gè)3NF的關(guān)系后，仍然不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。AnIntroductiontoDatabaseSystemBC范式（BCNF）定義6.8

關(guān)系模式R<U，F(xiàn)>∈1NF，若X→Y且YX時(shí)X必含有碼，則R<U，F(xiàn)>∈BCNF。等價(jià)于：每一個(gè)決定屬性因素都包含碼AnIntroductiontoDatabaseSystemBCNF（續(xù)）若R∈BCNF所有非主屬性對(duì)每一個(gè)碼都是完全函數(shù)依賴所有的主屬性對(duì)每一個(gè)不包含它的碼，也是完全函數(shù)依賴沒(méi)有任何屬性完全函數(shù)依賴于非碼的任何一組屬性R∈BCNFR∈3NF充分不必要AnIntroductiontoDatabaseSystemBCNF（續(xù)）[例5]關(guān)系模式C（Cno，Cname，Pcno）C∈3NFC∈BCNF[例6]關(guān)系模式S（Sno，Sname，Sdept，Sage）假定S有兩個(gè)碼Sno，SnameS∈3NF。S∈BCNFAnIntroductiontoDatabaseSystemBCNF（續(xù)）［例7］關(guān)系模式SJP（S，J，P）函數(shù)依賴：（S，J）→P；(J，P）→S（S，J）與（J，P）都可以作為候選碼,屬性相交SJP∈3NF，SJP∈BCNFAnIntroductiontoDatabaseSystemBCNF（續(xù)）[例8]在關(guān)系模式STJ（S，T，J）中，S表示學(xué)生，T表示教師，J表示課程。函數(shù)依賴：

(S，J)→T，(S，T)→J，T→J(S，J)和(S，T)都是候選碼AnIntroductiontoDatabaseSystemBCNF（續(xù)）

JSJTSTSTJ中的函數(shù)依賴AnIntroductiontoDatabaseSystemBCNF（續(xù)）STJ∈3NF

沒(méi)有任何非主屬性對(duì)碼傳遞依賴或部分依賴

STJ∈BCNFT是決定因素，T不包含碼AnIntroductiontoDatabaseSystemBCNF（續(xù)）解決方法：將STJ分解為二個(gè)關(guān)系模式：

ST(S，T)∈BCNF，TJ(T，J)∈BCNF

沒(méi)有任何屬性對(duì)碼的部分函數(shù)依賴和傳遞函數(shù)依賴SJSTTJTJAnIntroductiontoDatabaseSystem3NF與BCNF的關(guān)系R∈BCNFR∈3NF如果R∈3NF，且R只有一個(gè)候選碼

R∈BCNFR∈3NF充分不必要充分必要思考(S#,C#,ORDER)，表示學(xué)生選修課程的名次，有函數(shù)依賴(S#，C#)ORDER，(C#，ORDER)S#，它屬于BCNF嗎？全碼屬于BCNF嗎？任何一個(gè)二目關(guān)系模式R（A，B）一定屬于BCNF嗎？一個(gè)全是主屬性的關(guān)系模式一定可以達(dá)到第幾范式？一個(gè)全碼的關(guān)系模式一定可以達(dá)到第幾范式？Exercise商品銷售業(yè)務(wù)管理系統(tǒng)的關(guān)系設(shè)計(jì)符合最高范式是什么？Customer(custid,name,prov,city,phone,unit)

Product(prodid,factory,type,spec,price,desc)