數(shù)據(jù)庫(kù)應(yīng)用與開發(fā)課件第3章

第3章關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)理論

主要內(nèi)容3.1數(shù)據(jù)庫(kù)設(shè)計(jì)中存在的問題3.2函數(shù)依賴3.3范式3.4范式之間的關(guān)系

學(xué)習(xí)目標(biāo)了解數(shù)據(jù)庫(kù)設(shè)計(jì)中存在的問題了解函數(shù)依賴的概念掌握范式的使用

導(dǎo)入案例

設(shè)計(jì)好的數(shù)據(jù)庫(kù)是否實(shí)用、高效，或者是否合理、正確？我們可以依據(jù)關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)理論進(jìn)行核查。一般情況下，按照將EER模型轉(zhuǎn)化為關(guān)系模式的理論方法進(jìn)行數(shù)據(jù)庫(kù)模式設(shè)計(jì)是不會(huì)出現(xiàn)太大問題的，那么關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)理論也可以驗(yàn)證或者解釋轉(zhuǎn)化原理的必要性和有效性。錯(cuò)誤的或者不合理的關(guān)系模式必然會(huì)在數(shù)據(jù)庫(kù)進(jìn)行增、刪、改、查操作時(shí)，發(fā)生種種異常。范式及范式之間的關(guān)系是關(guān)系模式進(jìn)行規(guī)約和轉(zhuǎn)化的理論基礎(chǔ)，是重點(diǎn)學(xué)習(xí)章節(jié)。

3.1數(shù)據(jù)庫(kù)設(shè)計(jì)中存在的問題數(shù)據(jù)庫(kù)設(shè)計(jì)是否有據(jù)可依，為什么一定要遵循一定的原則？隨意安排的一個(gè)關(guān)系模式到底容易出現(xiàn)哪些問題？

eg:設(shè)計(jì)學(xué)生關(guān)系模式S(SNO,SNAME,DEPT,HEAD,CNO,G)，如圖所示，這個(gè)關(guān)系模式是否能滿足基本的數(shù)據(jù)操作呢?學(xué)生關(guān)系

數(shù)據(jù)操作時(shí)發(fā)生異常插入異常：如果一個(gè)系剛成立沒有學(xué)生，或者有了學(xué)生但學(xué)生尚未選課，那么就無法將這個(gè)系及其負(fù)責(zé)人的信息插入數(shù)據(jù)庫(kù)。刪除異常：如果某個(gè)系的全部學(xué)生都畢業(yè)了，則刪除該系學(xué)生及其選修課程的同時(shí)，把這個(gè)系及其負(fù)責(zé)人的信息也丟掉了。數(shù)據(jù)冗余：學(xué)生及其所選課程很多，而系主任只有一個(gè)，但其卻要和學(xué)生及其所選課程出現(xiàn)的次數(shù)一樣多。更新異常：如果某個(gè)系要更換系主任，就必須修改這個(gè)系學(xué)生所選課程的每個(gè)元組，修改其中的系主任信息。若有疏忽，就會(huì)造成數(shù)據(jù)的不一致。

發(fā)生這些操作異常的原因是把多個(gè)實(shí)體型用一個(gè)關(guān)系模式表示，解決辦法是將現(xiàn)有關(guān)系模式進(jìn)行分解

分解后的關(guān)系

3.2函數(shù)依賴

一個(gè)實(shí)體型的諸屬性之間具有內(nèi)在的聯(lián)系。通過對(duì)這些聯(lián)系的分析，我們可以做到一個(gè)關(guān)系模式只表示一個(gè)實(shí)體型的信息，從而消除上述問題。在關(guān)系模型中，實(shí)體類型屬性間這種相互依賴又相互制約的關(guān)系稱為數(shù)據(jù)依賴。數(shù)據(jù)依賴是通過關(guān)系中屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間的相互關(guān)系，它是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象，是數(shù)據(jù)內(nèi)在的性質(zhì)，是語義的體現(xiàn)。其中最重要的是函數(shù)依賴。分析函數(shù)依賴關(guān)系可以改造性能較差的關(guān)系模式集合。

函數(shù)依賴（續(xù)I）

函數(shù)依賴極為普遍地存在于現(xiàn)實(shí)生活中?？疾礻P(guān)系模式S(SNO,SNAME,DEPT,HEAD,CNO,G)，由于一個(gè)SNO只對(duì)應(yīng)一個(gè)學(xué)生，而一個(gè)學(xué)生只能在一個(gè)系中學(xué)習(xí)。因而當(dāng)SNO的值確定后，SNAME和DEPT也被唯一地確定了。就像自變量x確定后，相應(yīng)的f(x)也被確定了一樣。我們說SNO函數(shù)決定（SNAME，DEPT），而（SNAME，DEPT）函數(shù)依賴于SNO。

函數(shù)依賴（續(xù)II）定義函數(shù)依賴：設(shè)R(U)是屬性集U上的關(guān)系模式，X,YU，r是R(U)

上的任意一個(gè)關(guān)系，如果對(duì)任意兩個(gè)元組t,sr，若t[X]=s[X]，則t[Y]=s[Y]，那么稱“X函數(shù)決定Y”，或“Y函數(shù)依賴于X”，記作XY。稱X為決定因素或決定屬性集。 如 SNO

SNAME

（SNO，CNO）

G

函數(shù)依賴（續(xù)III）

函數(shù)依賴是不隨時(shí)間而變的。若關(guān)系R具有函數(shù)依賴XY，那么雖然關(guān)系R的值隨時(shí)間而變化，從而R[X，Y]也會(huì)發(fā)生變化，但R[X，Y]在任一特定時(shí)刻仍保持為一個(gè)函數(shù)。函數(shù)依賴與屬性間的聯(lián)系類型有關(guān)。當(dāng)X、Y之間是“1對(duì)1”聯(lián)系時(shí)，則存在函數(shù)依賴XY和YX。當(dāng)X、Y之間是“多對(duì)1”聯(lián)系時(shí)，則存在函數(shù)依賴XY。當(dāng)X、Y之間是“多對(duì)多”聯(lián)系時(shí)，則不存在函數(shù)依賴。

函數(shù)依賴（續(xù)IV）

函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些元組滿足的約束條件，而是指R的一切元組均要滿足的約束條件。函數(shù)依賴是現(xiàn)實(shí)世界中屬性間關(guān)系的客觀存在和數(shù)據(jù)庫(kù)設(shè)計(jì)者的人為強(qiáng)制相結(jié)合的產(chǎn)物。

函數(shù)依賴（續(xù)V）平凡函數(shù)依賴：如果XY，但YX，則稱其為非平凡的函數(shù)依賴，否則稱為平凡的函數(shù)依賴。如（SNO，SNAME）SNAME是平凡的函數(shù)依賴部分函數(shù)依賴：在R(U)中，如果XY，且對(duì)于任意X的真子集X′，都有X’Y

，則稱Y對(duì)X完全函數(shù)依賴，記作XY

，否則稱為Y對(duì)X部分函數(shù)依賴，記作XY

（SNO，CNO）G

（SNO，CNO）SNAME

函數(shù)依賴（續(xù)VI）傳遞函數(shù)依賴：在R(U)中，如果XY，Y

Z，且X不包含Y，Y

X，則稱Z對(duì)X傳遞函數(shù)依賴。 如：SNO

DEPT，DEPT

HEAD HEAD對(duì)SNO傳遞函數(shù)依賴。

函數(shù)依賴（續(xù)VII）檢驗(yàn)：A→C？C→A？A,B→D？ABCDa1b1c1d1a1b2c1d2a2b2c2d2a2b3c2d3a3b3c2d4

鍵定義超鍵：設(shè)K為R（U,F）的屬性或?qū)傩越M，若K

U，則稱K為R的超鍵。 如：SNOU，（SNO,SNAME）U候選鍵：設(shè)K為R（U,F）的屬性或?qū)傩越M，若K滿足以下條件，則稱K為R的一個(gè)候選鍵：K

U不存在K的真子集Z使得ZU成立。 或者：設(shè)K為R（U,F）的超鍵，若KU，則稱K為R的候選鍵。 如：SNOU

鍵（續(xù)I）主鍵：若R(U,F)有多個(gè)候選鍵，則可以從中選定一個(gè)作為R的主鍵。主鍵是唯一確定一個(gè)實(shí)體的最少屬性的集合。如： S關(guān)系模式中的SNO SC關(guān)系模式中的（SNO，CNO）鍵屬性：包含在任何一個(gè)候選鍵中的屬性，稱作鍵屬性。非鍵屬性：不包含在任何一個(gè)候選鍵中的屬性，稱作非鍵屬性。全鍵：關(guān)系模式的鍵由整個(gè)屬性組構(gòu)成。

關(guān)系模式S(SNO,SNAME,DEPT,HEAD,CNO,G)

主鍵：（SNO，CNO）

【例3.3】指出關(guān)系模式S(SNO,SNAME,DEPT,HEAD,CNO,G)中的函數(shù)依賴：

函數(shù)依賴： （SNO，CNO） G SNO

SNAME，（SNO，CNO）SNAME SNO

DEPT，（SNO，CNO） DEPT DEPT

HEAD，（SNO，CNO）HEAD

3.3范式定義范式是對(duì)關(guān)系的不同數(shù)據(jù)依賴程度的要求。如果一個(gè)關(guān)系滿足某個(gè)范式所指定的約束集，則稱它屬于某個(gè)特定的范式。范式（簡(jiǎn)稱NF）從低級(jí)到高級(jí)依次可分為：

1NF、2NF、3NF、

BCNF、4NF、5NF

乃至更高。

。1NF2NF3NF4NFBCNF5NF

規(guī)范化

一個(gè)低一級(jí)范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個(gè)高級(jí)范式的關(guān)系模式的集合，這一過程稱作規(guī)范化。

1NF定義

關(guān)系中每一分量必須是原子的，不可再分。即不能以集合、序列等作為屬性值。SNOTNOS1{T1，T2，T3}SNOTNO1TNO2TNO3S1T1T2T3不滿足1NF的關(guān)系模式滿足1NF的關(guān)系模式

規(guī)范化分解關(guān)系。

2NF定義若R

1NF，且每個(gè)非鍵屬性完全依賴于鍵，則稱R2NF

將1NF的關(guān)系模式規(guī)范化為2NF的關(guān)系模式，其方法是消除1NF的關(guān)系模式中非鍵屬性對(duì)鍵的部分依賴。思考：如果關(guān)系R的全體屬性都是R的鍵屬性，或者R的所有候選鍵都只含一個(gè)屬性，那么，R是否屬于第二范式？關(guān)系模式S(SNO,SNAME,DEPT,HEAD,CNO,G)

2NF（續(xù)I）不良特性插入異常：如果學(xué)生沒有選課，關(guān)于他的個(gè)人信息及所在系的信息就無法插入。刪除異常：如果刪除學(xué)生的選課信息，則有關(guān)他的個(gè)人信息及所在系的信息也隨之刪除了。更新異常：如果學(xué)生轉(zhuǎn)系，若他選修了k門課，則需要修改k次。數(shù)據(jù)冗余：如果一個(gè)學(xué)生選修了k門課，則有關(guān)他的所在系的信息重復(fù)

2NF（續(xù)II）原因：S2NF，因?yàn)椋⊿NO，CNO） SNAME（SNO，CNO）DEPT規(guī)范化將S分解為：

SC(SNO,CNO,G)2NF S_SD(SNO,SNAME,DEPT,HEAD)2NFS_SD(SNO,SNAME,DEPT,HEAD)

3NF不良特性插入異常：如果系中沒有學(xué)生，則有關(guān)系的信息就無法插入。刪除異常：如果學(xué)生全部畢業(yè)了，則在刪除學(xué)生信息的同時(shí)有關(guān)系的信息也隨之刪除了。更新異常：如果學(xué)生轉(zhuǎn)系，不但要修改DEPT，還要修改HEAD，如果換系主任，則該系每個(gè)學(xué)生元組都要做相應(yīng)修改。數(shù)據(jù)冗余：每個(gè)學(xué)生都存儲(chǔ)了所在系的系主任的信息。

3NF（續(xù)I）定義在關(guān)系模式R(U)中，如果X→Y，Y→Z，并且X不包含Y，Y

X，則稱Z對(duì)X傳遞函數(shù)依賴。關(guān)系模式R（U,F）中，若不存在這樣的鍵X，屬性組Y及非鍵屬性Z(ZY)，使得下式成立，X

Y,Y

Z,Y

X

則稱R3NF。將2NF的關(guān)系模式規(guī)范化為3NF的關(guān)系模式，其方法是消除2NF的關(guān)系模式中非鍵屬性對(duì)鍵的傳遞依賴。

3NF（續(xù)II）原因：S_SD

3NF，因?yàn)镾NODEPT，DEPTHEAD規(guī)范化將S_SD分解為：STUDENT(SNO,SNAME,DEPT)DEPT(DEPT,HEAD)

BCNF示例

STJ(S,T,J)，S表示學(xué)生，T表示教師，J表示課程。每位老師只教授一門課,每門課由若干教師教，某一學(xué)生選定某門課就確定了一個(gè)固定的教師，因此具有以下函數(shù)依賴：

TJ，（S，J）

T（S，T），（S，J）為候選鍵。

BCNF（續(xù)I）不良特性插入異常：如果沒有學(xué)生選修某位老師的任課，則該老師擔(dān)任課程的信息就無法插入。刪除異常：刪除學(xué)生選課信息，會(huì)刪除掉老師的任課信息。更新異常：如果老師所教授的課程有所改動(dòng)，則所有選修該老師課程的學(xué)生元組都要做改動(dòng)。數(shù)據(jù)冗余：每位學(xué)生都存儲(chǔ)了有關(guān)老師所教授的課程的信息。

BCNF（續(xù)II）定義若關(guān)系模式R（U,F）

1NF，如果對(duì)于R的每個(gè)函數(shù)依賴X

Y，且Y

X時(shí)，X必含有鍵，則R（U,F）

BCNF。

由BCNF的定義可以看到，每個(gè)BCNF的關(guān)系模式都具有如下三個(gè)性質(zhì)：所有非鍵屬性都完全函數(shù)依賴于每個(gè)候選鍵。所有鍵屬性都完全函數(shù)依賴于每個(gè)不包含它的候選鍵。沒有任何屬性完全函數(shù)依賴于非鍵的任何一組屬性。即如果關(guān)系模式R的每一個(gè)決定因素都包含鍵，則R屬于BCNF范式。（不存在非鍵決定因素！）

BCNF（續(xù)III）原因： 鍵屬性對(duì)鍵的不良依賴。如STJBCNF，因?yàn)門J，而T不含有鍵。改造：將STJ分解為（S，T），（T，J）。

考慮兩個(gè)關(guān)系：關(guān)系模式S(S#,SNAME,SADD,SAGE)限制SNAME唯一;

分析：鍵為S#和SNAME，且除此而外無其它決定因素，是3NF范式和BCNF范式。關(guān)系模式SS(S#,SNAME,C#,G)限制SNAME唯一;

分析：鍵為（S#,C#）和（SNAME,C#），非主屬性G不傳遞任何候選鍵，所以SS是3NF范式，但它不是BCNF范式。因?yàn)镾#SNAME，S#不是SS的候選鍵。

小結(jié)：

一個(gè)關(guān)系數(shù)據(jù)庫(kù)模式中的關(guān)系都屬于BCNF，則在函數(shù)依賴的范疇內(nèi)，已實(shí)現(xiàn)了徹底的分離，消除了插入、刪除和修改的異常。3NF的”不徹底”性表現(xiàn)在當(dāng)關(guān)系模式具有多個(gè)候選鍵，且這些候選鍵具有公共屬性時(shí)，可能存在主屬性對(duì)鍵的部分依賴和傳遞依賴。 當(dāng)然，關(guān)系模式的屬性之間除了函數(shù)依賴外，還存在多值依賴關(guān)系。BCNF（續(xù)IV）

多值依賴

關(guān)系模式TEACH（C#，P#，B#），一門課程由多個(gè)教師擔(dān)任，一門課程使用相同的一套參考書。它的鍵是（C#，P#，B#），所以屬于BCNF。C#P#B#物理張明普通物理學(xué)物理張明光學(xué)原理物理張平普通物理學(xué)物理張平光學(xué)原理化學(xué)張明無機(jī)化學(xué)化學(xué)張明有機(jī)化學(xué)化學(xué)王微無機(jī)化學(xué)化學(xué)王微有機(jī)化學(xué)C#P#B#物理{張明,張平}{普通物理學(xué),光學(xué)原理}化學(xué){張明,王微}{無機(jī)化學(xué),有機(jī)化學(xué)}

多值依賴（續(xù)I）不良特性插入異常：當(dāng)某門課程增加一名教師時(shí)，該門課程有多少本參考書就必須插入多少個(gè)元組；同樣當(dāng)某門課程需要增加一本參考書時(shí)，它有多少個(gè)教師就必須插入多少個(gè)元組。刪除異常：當(dāng)刪除一門課程的某個(gè)教師或者某本參考書時(shí)，需要?jiǎng)h除多個(gè)元組。更新異常：當(dāng)一門課程的教師或參考書作出改變時(shí)，需要修改多個(gè)元組。數(shù)據(jù)冗余：同一門課的教師與參考書的信息被反復(fù)存儲(chǔ)多次。

多值依賴（續(xù)II）定義描述型：設(shè)R(U)是屬性集U上的一個(gè)關(guān)系模式，X、Y、Z是U的子集，并且Z=U–X–Y，關(guān)系模式R(U)中多值依賴X

Y成立，當(dāng)且僅當(dāng)在R(U)的任一關(guān)系r里，對(duì)給定的Ｘ屬性值，都有一組Y的值與之對(duì)應(yīng)，而與其它屬性Ｚ值無關(guān)。如在關(guān)系模式TEACH中，對(duì)(物理,普通物理學(xué))有一組P#值(張明,張平)，對(duì)(物理,光學(xué)原理)也有一組P#值(張明,張平)，這組值僅取決于C#的取值，而與B#的取值無關(guān)。因此，P#多值依賴于C#，記作C#

P#，同樣有C#

B#。

多值依賴（續(xù)III）形式化：在R(U)的任一關(guān)系r中，如果存在元組t，s使得t[x]=s[x]，那么就必然存在元組w，v∈r，（w，v可以與s，t相同），使得：w[X]=s[X]=v[X]=t[X]w[Y]=t[Y]，v[Y]=s[Y]w[Z]=s[Z]，v[Z]=t[Z]

則稱Y多值依賴與X，記作X

Y。 若(C#,P#,B#)滿足C#

P#，含有元組t=(物理,張明,普通物理學(xué))，s=(物理,張平,光學(xué)原理)，則也一定含有元組w=(物理,張明,光學(xué)原理)，v=(物理,張平,普通物理學(xué))。

多值依賴（續(xù)IV）找出關(guān)系上所滿足的多值依賴。CB？若使BC成立，需加入哪些元組ABCa1b1c1a1b1c2a2b1c1a2b1c3ABCa1b1c1a2b1c1t1t2ABCa2b1c1a1b1c1ABCt2.At1.Bt2.Ct1.At2.Bt1.Ct3t4t3t4

多值依賴（續(xù)V）性質(zhì)多值依賴具有對(duì)稱性，即 若X

Y，則XZ，其中Z=U–X–Y。函數(shù)依賴是多值依賴的特例，即 若X

Y，則X

Y。若X

Y，U–X–Y=

，則稱XY為平凡的多值依賴。

多值依賴Vs函數(shù)依賴有效性范圍X

Y的有效性僅決定于X、Y屬性集上的值，它在任何屬性集W（XY

W

U）上都成立。 若X

Y在R(U)上成立，則對(duì)于任何Y′

Y，均有X

Y′成立。

多值依賴Vs函數(shù)依賴（續(xù)I）X

Y的有效性與屬性集范圍有關(guān)。

X

Y在屬性集W（XY

W

U）上成立，但在U上不一定成立。

X

Y在U上成立

X

Y在屬性集W（XY

W

U）上成立。 若在R(U)上，X

Y在屬性集W(XY

W

U)上成立，則稱X

Y為R(U)的嵌入式多值依賴。 若X

Y在R(U)上成立，則不能斷言對(duì)于Y′

Y，是否有X

Y′成立。

4NF定義關(guān)系模式R（U,F）

1NF，如果對(duì)于R到每個(gè)非平凡的多值依賴XY（YX），X都含有鍵，則稱R4NF。

4NF就是限制關(guān)系模式的屬性之間不允許有非平凡且非函數(shù)依賴的多值依賴。因?yàn)楦鶕?jù)定義，對(duì)于每一個(gè)非平凡的多值依賴X

Y，X都含有候選鍵，于是就有X

Y，所以4NF所允許的非平凡的多值依賴實(shí)際上是函數(shù)依賴。

4NF（續(xù)I）如關(guān)系模式CPB，C#P#，C#B#，鍵為(C#,P#,B#)，所以CPB4NF。 如果一門課Ci有m個(gè)教師，n本參考書，則關(guān)系中分量為Ci的元組共有m×n個(gè)，數(shù)據(jù)冗余非常大。改造 將CPB分解為CP（C#，P#），CB（C#，B#），在分解后的關(guān)系中分量為Ci的元組共有m+n個(gè)。C#P#物理張明物理張平化學(xué)張明……C#B#物理普通物理學(xué)物理光學(xué)原理化學(xué)無機(jī)化學(xué)……

范式之間的關(guān)系3NF2NF

反證：若R

3NF，但R2NF，則按2NF定義，一定有非鍵屬性部分依賴于鍵， 設(shè)X為R的鍵，則存在X的真子集X′，以及非鍵屬性Z（Z

X′），使得X′Z。 于是在R中存在鍵X，屬性組X′，以及非鍵屬性Z（Z

X′)，使得X

X′，X′Z，(X′

X),XZ成立，這與R3NF矛盾。所以R2NF。

范式之間的關(guān)系（續(xù)I）BCNF3NF

反證：若RBCNF，但R3NF，則按3NF定義，一定有非鍵屬性對(duì)鍵的傳遞依賴，于是存在：

R的鍵X，屬性組Y，以及非主屬性Z（Z

Y），使得XY，YZ，YX成立。 由YZ，按BCNF定義，Y含有鍵，于是YX成立，這與YX矛盾。所以R3NF。4NFBCNF

函數(shù)依賴的公理系統(tǒng)Armstrong公理設(shè)有關(guān)系模式R(U)，U是R的屬性集，X，Y，Z和W均是U的子集，F(xiàn)是R的函數(shù)依賴集。

推理規(guī)則如下：A1（自反律，Reflexivity） 如果Y

X

U，則X→Y；A2（增廣律，Augmentation）如果X→Y，則XZ→YZ；A3（傳遞律，Transitivity） 如果X→Y，

Y→Z，則X→Z。

公理的正確性【定理1】Armstrong公理是正確的。

公理的推論

從Armstrong公理可以得出如下的推論。1．合成規(guī)則（UnionRule）若X→Y與X→Z成立，則X→YZ成立。因?yàn)閄→Y，所以X→XY；又X→Z，于是XY→YZ，所以有X→YZ。

若X→Y與WY→Z成立，則XW→Z成立。因?yàn)閄→Y，于是XW→WY，所以有XW→Z。2．偽傳遞規(guī)則（PseudotransitivityRule）

若X→Y成立，且Z

Y，則X→Z成立。因?yàn)閆

Y，于是Y→Z，根據(jù)已知條件X→Y，所以X→Z成立。從合成規(guī)則和分解規(guī)則可得出一個(gè)重要的結(jié)論：如果A1，A2，…，An是關(guān)系模式R的屬性，則X→A1，A2，…，An的充分必要條件是X→Ai(i=1，2，…，n)均成立。3．分解規(guī)則（DecompositionRule）

模式分解無損連接設(shè)有關(guān)系模式R(U，F(xiàn))，分解成關(guān)系模式

={R1(U1，F(xiàn)1)，…，Rk(Uk，F(xiàn)k)}，其中，且Ui

Uj(i

j)，若對(duì)于關(guān)系R(U，F(xiàn))的任一關(guān)系r都有則稱

具有無損連接性，其中是關(guān)系r

在Ui上的投影，為自然連接。

R