數(shù)據(jù)庫原理與應用(第二版)Chapter4課件

1、第四章關系數(shù)據(jù)理論4.1 關系數(shù)據(jù)庫模式的設計問題1引言 數(shù)據(jù)庫設計的一個最基本的問題是如何建立一個好的數(shù)據(jù)庫模式，即給出一組數(shù)據(jù)，如何構造一個適合于它們的數(shù)據(jù)模式，使數(shù)據(jù)庫系統(tǒng)有較好的性能。 2關系模式的存儲異常問題 數(shù)據(jù)冗余量大 數(shù)據(jù)修改量大 插入異常 刪除異常 3 冗余和數(shù)據(jù)依賴數(shù)據(jù)依賴是指數(shù)據(jù)之間存在的各種聯(lián)系，譬如鍵就是一種依賴。數(shù)據(jù)冗余的產(chǎn)生和數(shù)據(jù)依賴有著密切的聯(lián)系。例如關系S中，為什么學生S2的班級會重復出現(xiàn)？就是因為S和CLS之間存在依賴關系，即每個學生只屬于一個班級，這種依賴稱為函數(shù)依賴。這個依賴勢必造成關系出現(xiàn)冗余現(xiàn)象。4.2 關系模式的函數(shù)依賴函數(shù)依賴的定義定義1：設有關

2、系模式R（），是R的屬性的集合，X、Y，對于R的任意關系實例r，r中的任意兩個元組t和s，如果tX=sX，則tY=sY，則稱Y函數(shù)依賴于X，或稱X函數(shù)地決定Y，記作XY。 定義2：設R是一個具有屬性集合的關系模式，如果XY ，并且對于X的任何一個真子集Z，ZY都不成立，則稱Y完全函數(shù)依賴于X，記作：X Y 。若XY，但Y不完全函數(shù)依賴于X，則稱Y部分函數(shù)依賴于X，記作：X Y。定義3：設R是一個具有屬性集合的關系模式，X，Y，Z是的子集，YX不成立，ZX、ZY和YX不空。如果XY，YZ則稱Z傳遞函數(shù)依賴于X，記作：X Z。例如對于關系：學生（學號，班級，班主任），有：學號班級，班級班主任，則學

3、號班主任，所以 學號 班主任。 2. 鍵 定義4 設R是一個具有屬性集合的關系模式，K是的子集。若K滿足下列兩個條件，則稱K是R的一個候選鍵。K不存在K的真子集Z，使得Z。候選鍵可以唯一地識別關系的元組。一個關系模式中可能具有多個候選鍵。我們可以指定一個候選鍵作為主鍵。 定義5 設X是關系模式R的屬性的子集。如果X是另一關系模式的候選鍵，則稱X是R的外部鍵。例如，在學生關系S（S，SN，CLS，MON，C，GR）中存在以下函數(shù)依賴：SSN，每個學生有唯一的一個學號；CLSMON，每個班最多只有一個班主任；SCLS，每個學生只屬于一個班級；（S，C）GR，一個學生選修一門課程有一個成績等級；可以

4、看出（S，C）是主鍵。 4.3 關系的規(guī)范化 在關系數(shù)據(jù)模式設計中，為了避免由依賴引起的數(shù)據(jù)冗余和更新異常等問題，必須進行關系模式的合理分解，即關系模式的規(guī)范化。 1. 關系模式的范式關系模式的設計原則：數(shù)據(jù)的冗余量盡量小；對關系進行插入、刪除等操作，不要出問題盡量能如實地反映現(xiàn)實世界的實際情況，而且又易懂。 關系數(shù)據(jù)庫中的關系滿足一定的要求。而把滿足不同程度要求的關系稱為不同的范式。滿足最低要求的關系叫第一范式，簡稱1NF。在第一范式中進一步滿足一定要求的為第二范式，簡稱2NF，其余以此類推。 關系規(guī)范化:就是一個低一級范式的關系模式通過投影運算，轉(zhuǎn)化為若干高一級范式的關系模式的集合，這種過

5、程就叫關系的規(guī)范化。 各范式之間的關系1NF2NF3NF4NF5NF第一范式（1NF） 設R是一個關系模式。如果R的每一屬性的值都是不可分離的原子值，即每個屬性的值域是單值域，則R是第一范式，記作R1NF。符合1NF的工資關系編 號姓 名基本工資獎 金121015張三李四王五趙六200002800026000230003000500045004000(2) 第二范式如果關系模式R1NF，且R中每一非主屬性完全函數(shù)依賴于R的鍵，則R稱為第二范式，記作R2NF。 例如，4.1節(jié)給出的學生關系S中非主屬性CLS、MON都不是完全函數(shù)依賴于主鍵（S，C），而部分函數(shù)依賴于（S，C）。對1NF進行投影運

6、算，將其分解為兩個關系： SSS，SN，CLS，MON（S）SCS，C，GR（S），其中S為SS的主鍵，（S，C）為SC的主鍵。這樣，在這兩個關系中，非主屬性對主鍵都是完全函數(shù)依賴，所以關系SS和SC都為2NF。 (3) 第三范式如果關系模式R是2NF，且它的任何一個非主屬性都不傳遞函數(shù)依賴于任何候選鍵，則稱R為第三范式，記作R3NF。例如，訂單關系（訂單號，顧客名稱，商店貨號，定購數(shù)量，交貨日期）中的主鍵是訂單號，存在的函數(shù)依賴是：訂單號顧客名稱；訂單號商品貨號；訂單號定購數(shù)量；訂單號交貨日期，不再有別的函數(shù)依賴，此關系是2NF的，且所有非主屬性對主鍵沒有傳遞函數(shù)依賴，所以是3NF的。 (4

7、) BC范式（BCNF） 如果關系模式R1NF，且每個函數(shù)依賴XY中X必為候選鍵，則R是BCNF范式。從BCNF的定義可以明顯地得出一個滿足BCNF的關系模式如下結論：所有非主屬性對鍵是完全函數(shù)依賴。所有主屬性對不包含它的鍵是完全函數(shù)依賴。沒有屬性完全函數(shù)依賴于非鍵的任何屬性組例4-3 在關系模式SJP（S，J，P）中，S是學號，J是課號，P為名次。每一個學生每門課程有一定的名次，每門課程中每一名次只有一個學生。由這些語義可得到下面的函數(shù)依賴：（S，J） P（J，P） S 顯然，（S，J）與（J，P）都是候選鍵。這兩個候選鍵各由兩個屬性組成，而且相交。這個關系模式中顯然沒有屬性對鍵傳遞或部分依

8、賴，所以SJP 3NF。 例44 關系模式SCT（S，C，T）中，S表示學號，C表示課程號，T表示教師。每一教師只教一門課。每門課由若干教師教授，某一學生選定某門課，就確定了一個固定的教師。于是有如下的函數(shù)依賴： （S，C）T（S，T）C TC 顯然，（S，C）和（S，T）都是候選鍵。SCT是3NF，因為沒有任何非主屬性對鍵的傳遞或部分函數(shù)依賴。但SCT不是BCNF，因為T是決定因素，而T不是候選鍵。 S#C#TS#TC#2關系規(guī)范化方法與實例 關系模式規(guī)范化遵循以下原則：關系模式進行無損連接分解。關系模式分解過程中數(shù)據(jù)不能丟失或增加，必須把全部關系模式中的所有數(shù)據(jù)無損地分解到各個子關系模式中

9、，以保證數(shù)據(jù)的完整性。合理選擇規(guī)范化程度。低級范式造成的冗余度很大，既浪費了存儲空間，又影響了數(shù)據(jù)的一致性，因此希望一個子模式的屬性越少越好，即取高級范式；若考慮查詢效率、低級范式比高級范式好，此時連接運算的代價較小，這是一對矛盾，所以應根據(jù)實際情況，合理選擇規(guī)范化程度。正確性與可實現(xiàn)性原則。4.4函數(shù)依賴的公理系統(tǒng) 定義6 設R是一個具有屬性集合的關系模式，F(xiàn)是R上的函數(shù)依賴集合。如果對于R的任意一個使F成立的關系實例r，函數(shù)依賴XY都成立，則稱F邏輯地蘊含XY。Armstrong公理系統(tǒng) 設R是一個關系模式，為R的屬性集合，F(xiàn)為上的一組函數(shù)依賴的集合。Armstrong公理系統(tǒng)包含如下三條

10、推理規(guī)則：（1）自反律 若Y X ，則F蘊含XY（2）增廣律 若XY為F所蘊含，且Z ，則XZYZ為F所蘊含。（3）傳遞律 若XY和YZ為F所蘊含，則XZ為F所蘊含。 定理1 Armstrong推理規(guī)則是正確的。證明：（1）設YXU。對于R的任一關系實例r的任意兩個元組t和s，若tX=SX,由于YX，有tY=sY， 所以XY成立。自反律得證。（2）設XY為F所邏輯蘊含，ZU。對于R的任一關系實例r的任意兩個元組t和s，若tXZ=sXZ,則有tX=sX，tZ=sZ 。由XY，tY=sY。于是tYZ=sYZ從而XZYZ成立。增廣律得證。（3）設XY及YZ為F所邏輯蘊含，ZU。對于R的任一關系實例r

11、的任意兩個元組t和s，若tX=sX,由于XY，有tY=sY。又由YZ，有tZ=sZ。于是，XZ成立。 三條推理規(guī)則：（1）合并規(guī)則 如果XY，XZ成立，則XYZ成立。（2）偽傳遞規(guī)則 如果XY和WYZ成立，則XWZ成立。（3）分解規(guī)則 如果XY和Z Y成立，則XZ成立。 定理2 合并規(guī)則、偽傳遞規(guī)則和分解規(guī)則是正確的。證明：（1）由XY和增廣律，XXY。又由XZ和增廣律，XYYZ。由傳遞律，XYZ成立。合并規(guī)則得證。（2）由XY和增廣律，XWYW。又由YWZ和傳遞律，XWZ。偽傳遞規(guī)則得證。（3）由ZY和自反律，YZ。又由XY和傳遞律，XZ。分解規(guī)則得證。 引理1 XA1 A2 AK成立的充分

12、必要條件是對于1ik，XA1成立。引理1 設F是屬性集U上的一組函數(shù)依賴的集合。X、YU，XY能由F根據(jù)Armstrong公理導出的充分必要條件是YX+。定義7 設R是一個具有屬性集合U的關系模式，F(xiàn)是給定的函數(shù)依賴集合。由F邏輯蘊含的所有函數(shù)依賴稱為F的閉包，記作F+ 。定義8 設R是一個具有屬性集合U的關系模式，F(xiàn)是給定的函數(shù)依賴集合。XU。X+=A|XA能由F根據(jù)Armstrong公理導出稱為屬性集X關于函數(shù)依賴集F的閉包。 引理2 把判定XY是否能由F根據(jù)Armstrong公理導出的問題轉(zhuǎn)化為求出X+，判定Y是否為X+的子集合的問題。證明：（1）充分性 設YX+ ，并設Y=B1 B2

13、BK。根據(jù)屬性閉包的定義可知，XB1，XBK是根據(jù)Armstrong公理從F導出的。由合并規(guī)則，有XY。所以當YX+時，XY能根據(jù)Armstrong公理從F導出。（2）必要性 設XY能根據(jù)Armstrong公理從F導出的， Y=B1 B2 BK。根據(jù)分解規(guī)則有XB1，XBK，由X+ 的定義可知BKX+（I=1,2, k），所以YX+，證畢。算法1 計算X+。輸入：X，F(xiàn)輸出：X+方法： X（1）：=空集合；X（0）：=X； B= A|VW能由F根據(jù)Armstrong公理導出，VX(0)AW； X（1）：=BX（0）； IF X（1）X（0） THEN X（0）：=X（1）；GOTO 2； EL

14、SE X+=X（1）； ENDIF。例46已知R是一個具有屬性集合U的關系模式，F(xiàn)是給定的函數(shù)依賴集合。其中U=A，B，C，D，E，F(xiàn)=ABC，ACB，BD，CE，ECB，求（AB）+ 。解：由算法可知X（0）=A，B。ABC，BD，X（0）=X（1）=A，BC，D=A，B，C，D。又ABC，BD，CE，ACB，X（0）=X（1）=A，B，C，DC，D，E，B=A，B，C，D，E。這時，X（0）已經(jīng)包含U的全部屬性，所以（AB）+ =A，B，C，D，E。引理3 設G和F是兩個函數(shù)依賴的集合。F和G等價的充分必要條件是FG+且GF+。證明：（1）必要性 設G+F+ ，由于FF+ 和G+=F+，我

15、們有FG+。同理我們有GF+。 （2）充分性 設FG+且GF+。對于每個XYF+，能從F出發(fā)根據(jù)Armstrong公理導出。由于FG+ ，所以XY，能從G+出發(fā)根據(jù)Armstrong公理導出，即XY（G+）+= G+。于是F+G+ 。同理可證G+F+。最后，我們有G+=F+ 即F與G等價。證畢。 定義9 如果函數(shù)依賴集F滿足下列條件，則稱F是一個極小函數(shù)依賴集。 （1）F中任一函數(shù)依賴的右部僅含有一個屬性； （2）F中不存在這樣的函數(shù)依賴XA，使得F與F XA等價； （3）F中不存在這樣的函數(shù)依賴XA，X包括真子集Z，使得（F XA）ZA與F等價。例47 已知R是一個具有屬性集合U的關系模式，

16、F是給定的函數(shù)依賴集合。其中U=S#，SD，MN，CN，GR，F(xiàn)=S#SD，SDMN，（S#，CN）GR。F=S#SD，S#MN，（S#，CN）GR ，SDMN，（S#，SD）SD。根據(jù)定義可以驗證F是極小函數(shù)依賴集，而F不是，因為FS#MN與F等價，F(xiàn)（S#，SD）SD與F等價。 4.5 模式分解 定義10 關系模式 RU，F(xiàn)的一個分解是指=R1U1，F(xiàn)1，R2U2，F(xiàn)2， ，RnUn，F(xiàn)n其中U= Ui ，并且沒有Ui Uj，1i，jn，F(xiàn)i是F在Ui上的投影。nUi=1所謂“Fi是F在Ui上的投影”的確切定義是：定義11 函數(shù)依賴集合XY|XYF+XY Ui的一個覆蓋Fi叫做F在屬性Ui

17、上的投影。1 模式分解的三個定義具有“無損連接性”（Lossless join）。要“保持函數(shù)依賴”（Preserve dependency）。既要“保持函數(shù)依賴”，又要具有“無損連接性” 例4-8 已知關系模式RU，F(xiàn)，其中U=SNO，SDEPT，MN，F(xiàn)=SNOSDEPTMN。RU，F(xiàn)的元組語義是學生SNO正在SDEPT系學習，其系主任是MN。并且一個學生（SNO）只在一個系學生，一個系只有一名系主任。 由于R中存在傳遞函數(shù)依賴SNOMN，它會發(fā)生更新異常。例如，如果S4畢業(yè)，則D3系的系主任是王一的信息也就丟掉了。反過來，如果一個系D5尚無在校學生，那么這個系的系主任是趙某的信息也無法存

18、入。 對關系模式R作如下分解：1= R1SNO,R2SDEPT, ,R3MN,如果分解后的數(shù)據(jù)庫能夠恢復到原來的情況，不丟失信息的要求也就達到了。Ri向R的恢復是通過自然連接來實現(xiàn)的，這就產(chǎn)生了無損連接性的概念。顯然，本例的分解1所產(chǎn)生的諸關系自然連接的結果實際上是它們的笛卡爾積，元組增加了，信息丟失了。 對R又進行另一種分解：2= R1SNO,SDEPT,SNOSDEPT, R2SNO,MN,SNOMN可以證明2對R的分解是可恢復的，但是前面提到的插入和刪除異常仍然沒有解決，原因就在于原來在R中存在的函數(shù)依賴SDEPTMN在R1和R2中都不存在了。因此人們又要求分解具有“保持函數(shù)依賴”的特性

19、。最后對R進行了以下分解：3= R1SNO，SDEPT,SNOSDEPT , R2 SDEPT,MN,SDEPTMN可以證明分解3既具有無損連接性，又保持函數(shù)依賴。它解決了更新異常，又沒有丟失原數(shù)據(jù)庫的信息，這是所希望的分解。引理4 設RU，F(xiàn)是一個關系模式，=R1U1，F(xiàn)1，RkUk，F(xiàn)k是RU，F(xiàn)的一個分解，r是RU，F(xiàn)的一個關系，ri=Ri(r)，則（1）r m(r)（2）若s=m(r)，則Ri(s)=ri（3）m(m(r)=m(r)證明：（1）證明r中的任何一個元組屬于m(r)。任取r中的一個元組t，tr，設ti=t.Ui（i=1，2，k）。對k進行歸納可以證明t1t2tk Ri(r)

20、，所以tm(r)。（2）由（1）得到r m(r)，已設s=m(r)，所以，r s， Ri(r) Ri(s)。現(xiàn)只需證明Ri(s) Ri(r)，就有Ri(s)= Ri(r)=ri。ki=1任取Si Ri(s) ，必有S中的一個元組v，使得v.Ui=Si。根據(jù)自然連接的定義v=t1t2tk ，對于其中每一個ti必存在r中的一個元組t，使得t.Ui=ti。由前面Ri(r)的定義即得ti Ri(r)。又因v=t1t2tk ，故v.UI =ti。又由上面證得：v.Ui =Si ，ti Ri(r)，故Si Ri(r)。即Ri(s) Ri(r)。故Ri(s)= Ri (r)。 （3）m(m(r)= Ri(m

21、 (r)= Ri(s)= Ri(r)= m(r)ki=1ki=1ki=1定義12 =R1U1，F(xiàn)1，RkUk，F(xiàn)k是RU，F(xiàn)的一個分解，若對RU，F(xiàn)的任何一個關系r均有r= m(r)成立，則稱分解具有無損連接性。簡稱為無損分解。直接根據(jù)定義12去鑒別一個分解的無損連接性是不可能的，算法2給出了一個判斷方法。算法2 判斷一個分解的無損連接性。=R1U1，F(xiàn)1，RkUk，F(xiàn)k是RU，F(xiàn)的一個分解，U=A1 ，A2 ，An，F(xiàn)=FD1 ，F(xiàn)D2 ，F(xiàn)Dp，不妨設F是一極小依賴集，記FDi為XiA1i 。（1）建立一張n列k行的表。每一列對應一個屬性，每一行對應分解中的一個關系模式。若屬性Aj屬于Ui

22、，則在j列i行交叉處填上aj ，否則填上bij ；（2）對每一個FDi做下列操作：找到Xi所對應的列中具有相同符號的那些行?？疾爝@些行中Li列的元素，若其中有ali；否則全部改為bmli；m是這些行的行號最小值。應當注意的是，若某個btli被更動，那么該表的li列中凡是btli的符號（不管它是開始找到的那些行）均作相應更改。如在某次更改之后，又一行成為a1，a2，an。則算法終止。具有無損連接性，否則不具有無損連接。對f中p個FD逐一進行一次這樣的處理，成為對F的一次掃描。（3）比較掃描前后，表有無變化。如有變化，則返回（2）步，否則算法終止。如果發(fā)生循環(huán)，那么前次掃描至少應使該表減少一個符號

23、，表中符號有限，因此循環(huán)必然終止。定理3 為無損連接分解的充分必要條件是算法2終止時，表中有一行為a1，a2，an。 例4-9 已知RU，F(xiàn)，U=A，B，C，D，E，F(xiàn)=ABC，CD，DE，R的一個分解為R1(A，B，C)，R2(C，D)，R3(D，E)。(1) 構造初始表：ABCDEa1b21b31 a2b22b32 a3a3b33 b14a4a4 b15b25a5 (2)對ABC，因各元組的第1、2列沒有相同的分量，所以表不改變。由CD可以把b14改成a4，再由DE可使b15、b25全改為a5。表中第1行成為a1、a2、a3、a4、a5，所以此分解具有無損連接性。 ABCDEa1b21b31 a2b22b32 a3a3b33 a4a4a4 a5a5a5 當關系模式R分解為兩個關系模式R1 ，R2時有下面的判斷準則。定理4 RU，F(xiàn)的一個分解=R1U1，F(xiàn)1，R2U2，F(xiàn)2具有無損連接性的充分必要條件是：U1U2U1-U2F+。 定義13 若F+=( Fi )+，則RU，F(xiàn)的分解=R1U1，F(xiàn)1，RkUk，F(xiàn)k保持函數(shù)依賴。 kUi=13 模式分解的算法 模式分解的幾個重要事實