第六章__關(guān)系數(shù)據(jù)理論(1)

1、第六章 關(guān)系數(shù)據(jù)理論習(xí)題1理解并給出下列術(shù)語的定義：函數(shù)依賴、部分函數(shù)依賴、完全函數(shù)依賴、傳遞依賴、候選碼、主碼、外碼、全碼（All-key）、1NF、2NF、3NF、BCNF、多值依賴、4NF。2聯(lián)立一個關(guān)于系、學(xué)生、班級、學(xué)會等諸信息的關(guān)系數(shù)據(jù)庫。描述學(xué)生的屬性有：學(xué)號、姓名、出生年月、系名、班號、宿舍區(qū)。描述班級的屬性有：班號、專業(yè)名、系名、人數(shù)、入校年份。描述系的屬性有：系名、系號、辦公室地點、人數(shù)。描述學(xué)會的屬性有：學(xué)會名、成立年份、地點、人數(shù)。有關(guān)語義如下：一個系有若干學(xué)生，每個專業(yè)每年只招一個班，每個班有若干學(xué)生。一個系的學(xué)生住在同一宿舍區(qū)。每個學(xué)生可參加若干學(xué)會，每個學(xué)會有若干

2、學(xué)生。學(xué)生參加某學(xué)會有一個入會年份。請給出關(guān)系模式，寫出每個關(guān)系模式的極小函數(shù)依賴集，指出是否存在傳遞函數(shù)依賴，對于函數(shù)依賴左部是多屬性的情況討論函數(shù)依賴是完全函數(shù)依賴，還是部分函數(shù)依賴。指出各關(guān)系的候選碼、外部碼，有沒有全碼存在？3試由Armstrong公理系統(tǒng)推導(dǎo)下面三條推理規(guī)則：（1）合并規(guī)則：若，則有（2）偽傳遞規(guī)則：由，有（3）分解規(guī)則：，有4關(guān)于多值依賴的另一種定義試：給定一個關(guān)系模式R（X，Y，Z），其中X，Y，Z可以是屬性或?qū)傩越M合。設(shè)，在R中的像集偽：定義 R（X，Y，Z）當(dāng)且僅當(dāng)對于每一組（，）都成立，則Y對X多值依賴，記作。這里，允許Z為空集，在Z為空集時，稱為平凡的多值

3、依賴。請證明這里的定義和概論5。2。7節(jié)中定義5。9是等價的。5試舉出3個多值依賴的實例。*6試證明書上給出的關(guān)于FD和MVD公理系統(tǒng)的A4，A6和A8。*7設(shè)關(guān)系模式為R（U，F(xiàn)），X，Y為屬性集，X，。證明：（1）（2）（3）若則（4）*8設(shè)關(guān)系模式R（U，F(xiàn)），若，則稱X相對于F是飽和的。定義飽和集，試證明。9圖6.12表示一個公司各部門的層次結(jié)構(gòu)。圖6.12 某公司各部門的層次結(jié)構(gòu)對每個部門，數(shù)據(jù)庫中包含部門號（唯一的）D、預(yù)算費（BUDGET）以及此部門領(lǐng)導(dǎo)人員的職工號E（唯一的）信息。對每一個部門，還存有關(guān)于此部門的全部職工、生產(chǎn)與科研項目以及辦公室的信息。職工信息包括：職工號、他

4、所參與的生產(chǎn)與科研項目號（J）、他所在辦公室的電話號碼（PHONE）。生產(chǎn)科研項目包括：項目號（唯一的）、預(yù)算費。辦公室信息包含辦公室房間號（唯一的）、面積。對每個職工，數(shù)據(jù)庫中有他曾擔(dān)任過的職務(wù)以及擔(dān)任某一職務(wù)時的工資歷史。對每個辦公室包含此辦公室中全部電話號碼的信息。請給出你認為合理的數(shù)據(jù)依賴，把這個層次結(jié)構(gòu)轉(zhuǎn)換稱一組規(guī)范化的關(guān)系。提示：此題可分步完成，第一步先轉(zhuǎn)換成一組1NF的關(guān)系，然后逐步轉(zhuǎn)換為2NF，3NF，BCNF。10在一個訂貨系統(tǒng)的數(shù)據(jù)庫中，存有顧客、貨物和訂貨單的信息。每個顧客包含顧客號CUST（唯一的）、收貨地址ADDRESS、訂貨日期DATE、訂貨細則LINE（每個訂貨單

5、有若干條），每條訂貨細則內(nèi)容為貨物號ITEM以及訂貨數(shù)量QTYORD。每種貨物包含貨物號ITEM（唯一的）、制造廠商PLANT、每個廠商的實際存貨量QTYOH、規(guī)定的最低存貨量DANGER和貨物描述DESCN。由于處理上的要求，每個訂貨單ORD的每一訂貨細則LINE中還應(yīng)有一個未發(fā)貨量QTYOUT（此值初始時為訂貨數(shù)量，隨著發(fā)貨將減為零）。為這些數(shù)據(jù)設(shè)計一個數(shù)據(jù)庫，如第9題那樣，首先給出合理的數(shù)據(jù)依賴。11設(shè)在第10題中實際上只有很少量的顧客（例如1），卻有多個發(fā)貨地址，由于這些少數(shù)的而又不能忽視的情形使得不能按一般的方式來處理問題。你能發(fā)現(xiàn)第10題答案中的問題嗎？能設(shè)法改進嗎？12下面的結(jié)論

6、哪些是正確的，哪些是錯誤的？對于錯誤的結(jié)論請給出理由或給出一個反例說明之。（1）任何一個二目關(guān)系都是屬于3NF的。（2）任何一個二目關(guān)系都是屬于BCNF的。（3）任何一個二目關(guān)系都是屬于4NF的。（4）當(dāng)且僅當(dāng)函數(shù)依賴AB在R上成立，關(guān)系R（A，B，C）等于其投影R1(A，B)和R2(A，C)的連接。（5）若R.AR.B，R.BR.C，則R.AR.C（6）若R.AR.B，R.AR.C，則R.AR.(B，C)（7）若R.BR.A，R.CR.A，則R.(B，C) R.A（8）若R.(B，C) R.A，則R.BR.A，R.CR.A參考答案1答：函數(shù)依賴：設(shè)R(U)是一個關(guān)系模式，U和R的屬性集合，X

7、和Y是U的子集。對于R(U)的任意一個可能的關(guān)系r，如果r中不存在兩個元組，它們在X上的屬性值相同，而在Y上的屬性值不同，則稱”X函數(shù)確定Y”或”Y函數(shù)依賴于X”，記作。答：完全函數(shù)依賴、部分函數(shù)依賴：在R(U)中，如果，并且對于X的任何一個真子集X，都有則稱Y對X完全函數(shù)依賴，記作：若X Y，但Y不完全函數(shù)依賴于X，則稱Y對X部分函數(shù)依賴，記作：傳遞依賴：在R(U)K ，如果，（）， ，則稱Z對X傳遞函數(shù)依賴。候選碼、主碼：設(shè)K為RU，F(xiàn)中的屬性或?qū)傩越M合，若則K為R的候選碼（Candidate key）。若候選碼多于一個，則選定其中的一個為主碼（Primary key）。答：外碼：關(guān)系模式

8、R中屬性或?qū)傩越MX并非R的碼，但X是另一個關(guān)系模式的碼，則稱X是R的外部碼（Foreign key），也稱外碼。全碼：整個屬性組是碼，稱為全碼（AII-Key）。答：INF：如果一個關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項，則RINF。答：2NF：若關(guān)系模式RINF，并且每一個非主屬性都完全函數(shù)依賴于R的碼，則R2NF。3NF：關(guān)系模式RU，F(xiàn)中若不存在這樣的碼X，屬性組Y及非主屬性Z（）使得()，成立，則稱RU，F(xiàn)3NFBCNF：關(guān)系模式RU，F(xiàn)3NF。若且時X必含有碼，則RU，F(xiàn)BCNF。答：多值依賴：設(shè)R(U)是屬性集U上的一個關(guān)系模式。X，Y，Z是U的子集，并且Z=U-X-Y。關(guān)系模

9、式R(U)中多值依賴成立，當(dāng)且僅當(dāng)對R（U）的任一關(guān)系r，給定的一對（x，z）值，有一組Y的值，這組值僅僅決定于X值而與Z值無關(guān)。4NF：關(guān)系模式RU， F1NF，如果對于R的每個非平凡多值依賴()，X都含有碼，則稱RU， F4NF。2答：關(guān)系模式：學(xué)生（學(xué)號，姓名，出生日期，系名，班號，宿舍區(qū)）學(xué)號姓名，學(xué)號出生日期，班號系名，系名宿舍區(qū) 存在傳遞依賴班級（班號，專業(yè)名，系名，人數(shù)，入校年份）班號專業(yè)名，專業(yè)名系名，班號人數(shù)，班號入校年份，（專業(yè)名，入校年份）班號 存在傳遞依賴系（系名，系號，系辦地點，人數(shù)）系號系名，系名系號，系號系辦地點，系號人數(shù)學(xué)會（學(xué)會名，成立年份，地點，人數(shù)）學(xué)會名

10、成立年份，學(xué)會名地點，學(xué)會名人數(shù)學(xué)生-學(xué)會（學(xué)號，學(xué)會名，入會年份）（學(xué)號，學(xué)會名）入會年份 各個關(guān)系模式的侯選關(guān)鍵字、外部關(guān)鍵字，以及有沒有全關(guān)鍵字.學(xué)生（學(xué)號，姓名，出生日期，系名，班號，宿舍區(qū)）班級（班號，專業(yè)名，系名，人數(shù)，入校年份） （專業(yè)名，入校年份）系（系名，系號，系辦地點，人數(shù)）學(xué)會（學(xué)會名，成立年份，地點，人數(shù)）學(xué)生-學(xué)會（學(xué)號，學(xué)會名，入會年份）沒有全關(guān)鍵字.說明：_ 表示候選關(guān)鍵字， 表示外部關(guān)鍵字。用下表等價表示：關(guān)系候選碼外部碼全碼學(xué)生學(xué)號班號，系號無班級班號，(專業(yè)號, 入校年份)系號無系系號和系名無無學(xué)會學(xué)會名無無學(xué)生學(xué)會(學(xué)號，學(xué)會名）學(xué)號，學(xué)會名無3證明：（1

11、）已知XZ，由增廣律知XYYZ，又因為XY，可得XXXYYZ，最后根據(jù)傳遞律得XYZ。（2）已知XY，根據(jù)增廣律得XWWY，因為WYZ，所以XWWYZ，通過傳遞律可知XWZ。（3）已知ZY，根據(jù)自反律知YZ，又因為XY，所以由傳遞律可得XZ。4證明：設(shè)YxzYxz對于每一組（x，z，z）都成立，現(xiàn)證其能推出定義 6.9得條件：設(shè)s，t是關(guān)系r中得兩個元組，sX=tX，由新定義得條件可知對于每一個z值，都對應(yīng)相同一組y值。這樣一來，對相同得x值，交換y值后所得的元組仍然屬于關(guān)系r，即定義6.9的條件成立；如果定義6.9的條件成立，則對相同的x值，交換y值后所得的元組仍然屬于關(guān)系r，由于任意性及其

12、對稱性，可知每個z值對應(yīng)相同的一組y值，所以Yxz=Yxz對于每一組（x，z，z）都成立。綜上可知，新定義和定義6.9的條件是等價的，所以新定義和定義6.9是等價的。5答：（1）關(guān)系模式MSC(M，S，C)中， M表示專業(yè)，S表示學(xué)生，C表示該專業(yè)的必修課。假設(shè)每個專業(yè)有多個學(xué)生，有一組必修課。設(shè)同專業(yè)內(nèi)所有學(xué)生選修的必修課相同，實例關(guān)系如下。按照語義對于M的每一值Mi，S有一完整的集合與之對應(yīng)而不問C取何值，所以MS。由于C與S的完全對稱性必然有MC成立。MSCM1S1C1M1S1C2M1S2C1M1S2C2（2）關(guān)系模式ISA(I，S，A)中，I表示學(xué)生興趣小組，S表示學(xué)生，A表示某興趣小

13、組的活動項目。假設(shè)每個興趣小組有多個學(xué)生，有若干活動項目。每個學(xué)生必須參加所在興趣小組的所有活動項目，每個活動項目要求該興趣小組的所有學(xué)生參加。按照語義IS，IA成立。（3）關(guān)系模式RDP(R，D，P)中，R表示醫(yī)院的病房，D表示責(zé)任醫(yī)務(wù)人員，P表示病人。假設(shè)每個病房住有多個病人，有多個責(zé)任醫(yī)務(wù)人員負責(zé)醫(yī)治和護理該病房的所有病人。按照語義有RD，RP成立。6證明：A4：若，則設(shè)ZU-X-Y已知，設(shè)r是R上的一個關(guān)系，s、tr，且tX=sX，則存在元組p、qr，使pX=tX，pZ=sZ，qY=sY，qZ=tZ。設(shè)tXW=sXW，我們以上構(gòu)造的元組p和q，是某部分屬性在s和t上翻轉(zhuǎn)而成，所以pW=

14、qW，可知pXW=qXW，同理pYV=tYV（由知tV=sV），qYV=sYV，pU-YV-YW=sU-YV-YW(因為)，qU-YV-YW=tU-YV-YW。所以，。A6：，則由容易證得。設(shè)R1U-X-Y，R2=U-Y-Z，R3=U-X-Z+Y。已知，設(shè)r是R上的任一關(guān)系s、tr，且tX=sX，則存在元組p、qr，使pX=qX=tX，而pY=tY，pR1=sR1，qY=sY，qR1=tR1。對元組t、p，已知tY=pY，tX=pX，由知：存在元組mr，使mZ-Y=pZ-Y。因為（Z-Y）R1，又pR1=sR1，所以，mZ-Y=sZ-Y。因為元組p和s在除屬性Y之外的屬性上值相等，所以mR2=

15、tR2，另外元組m由元組t和p交換某些屬性上的值而產(chǎn)生的，而t和p在屬性X上值相等，顯然mX=tX，所以mU-(Z-Y)=tU-(Z-Y)，即mR3=tR3。對元組s、q，同理可知sY=qY，存在元組n，使nZ-Y=tZ-Y，即nR3=sR3。綜上所述，對s、tr，tX=sX，存在元組m、nr，使mX=nX=tX，而mZ-Y=sZ-Y，mR3=tR3，nZ-Y=tZ-Y，nR3=sR3。A8：若，則。設(shè)r是R上的任一關(guān)系，對任意s、tr，若tX=sX，設(shè)R1=U-X-Y，則根據(jù)知：存在元組p、qr，使pX=qX=tX，而pY=tY，pR1=sR1，qY=sY，qR1=tR1。因為，所以sW=p

16、W，又，所以sZ=pZ；因為，且pY=tY，所以pZ=tZ；所以可得tZ=sZ，即。7證明：（1）因為，所以（根據(jù)的定義）。（2）下面求證。任意，（由任意知）存在，使能由F根據(jù)Armstrong公理導(dǎo)出，而從可知能由F根據(jù)Armstrong公理導(dǎo)出，根據(jù)公理中的傳遞律可知能由F根據(jù)Armstrong公理導(dǎo)出，所以，因此。所以。（3）對任意，可知能由F根據(jù)Armstrong公理導(dǎo)出，因為，由自反律可以得，由傳遞律得，所以。得證。（4）下面證明，即證U由F根據(jù)Armstrong公理推出得集合仍屬于U。自反律：，為F所蘊涵，顯然U由F據(jù)Armstrong公理的自反律推出的Y仍屬于U；增廣律：為F所蘊

17、涵，且，則為F所蘊涵，；傳遞律：和都為F所蘊涵，則為F所蘊涵，。8證明：（1）證。對任意，由已知條件的，因為，所以。（2）證。對任意，因為（見習(xí)題7），令，有所以即，得證。9答：（1）首先畫出一些重的函數(shù)依賴，所有這些函數(shù)依賴都是根據(jù)習(xí)題的文字說明和語義假設(shè)導(dǎo)出。語義假設(shè)如下：1）一個職工不能同時成為多個部門的領(lǐng)導(dǎo)人；2）一個職工不能同在在多個部門就職；3） 一個職工不能同時參加多個生產(chǎn)項目；4） 一個職工不能同時在兩個不同的辦公室辦公；5） 一個職工不能同時擁有兩部或兩部以上的電話； 6）一個生產(chǎn)項目不能同時分配給多個部門；7）一個辦公室不能同時分配給多個部門；8）部門號、職工號、

18、項目號、辦公室號及電話號碼是全局惟一的。（2）先按照圖5。12設(shè)計一組關(guān)系模式，它們都是屬于INF的。DEPT(DEPT，DBUDGET，MGR_EMP)PRIMARY KEY(DEPT)DEPT和MGR_EMP都是候選碼，把DEPT作為主碼。F=DEPTDBUDGET，DEPTMGR_EMP，MGR_EMPDEPTEMPI(EMP，DEPT，PROJ，OFF，PHONEPRIMARY KEY (EMP)F=EMPDEPT，EMPPROJ，EMPOFF，EMPPHONE，PHONEOFF，OFFDEPT，PROJDEPTJOB(EMP，JOBTITLE)PRIMARY KEY(EMP，JOBT

19、ITLE)F=EMP，JOBTITLEEMP，EMP，JOBTITLEJOBTITLESALHIST(EMP，JOBTITLE，DATE，SALARY)PRIMARY KEY (EMP，DATE)F=EMP，DATEJOBTITLE，EMP，DATESALARYPROJ(PROJ，DEPT，PBUDGET)PRIMARY KEY (PROJ)F=PROJDEPT，PROJPBUDGETOFFICE(OFF，DEPT，AREA) PRIMARY KEY (OFF)F=OFFDEPT，OFFAREAPHONE(PHONE，OFF) PRIMARY KEY (PHONE) F=PHQNEOFF(3)

20、現(xiàn)在來分析一下這7個關(guān)系模式，發(fā)現(xiàn)：SALHIST(EMP，DATE，JOBTITLE，SALARY)的屬性包含了JOB(EMP，JOBTLTLE)的屬性，所以JOB（EMP，JOBTITLE）可以消去。EMP1中OFF和DEPT都傳遞函數(shù)依賴于主碼（EMP）。OFF通過PHONE，DEPT通過PROJ或OFF(然后通過PHONE)傳遞依賴于EMP，所以可以把EMP1（EMP，DEPT，PROJ，OFF，PHONE）分解成下面4個3NF的關(guān)系模式： EMP(EMP，PROJ，PHONE) PRIMARY KEY (EMP) X(PHONE，OFF) PRIMARY KEY(PHONE) Y(P

21、ROJ，DEPT) PRIMARY KEY(PROJ) Z（OFF，DEPT） PRIMARY KEY(OFF)然而，X就是PHONE，Y是PROJ的投影，Z是OFFICE的投影，所以X、Y、Z都可以消去。 最后可以得到下面6個關(guān)系模式，所有這些關(guān)系模式都是屬于3NF的，進一步發(fā)現(xiàn)他們也是BCNF的。DEPT(DEPT，DBUDGET，MGR_EMP) PRIMARY KEY(MGR_EMP)EMP(EMP，PROJ，PHONE) PRIMARY KEY(EMP)SALHIST(EMP，DATE，JOBTITLE，SALARY) PRIMARY KEY (EMR)PROJ(PROJ，DEPT，

22、PBUDGET) PRIMARY KEY(PROJ)OFFICE(OFF，DEPT，AREA) PRIMARY KEY(OFF)PHONE(PHONE，OFF) PRIMARY KEY(PHONE)10答：其語義假設(shè)如下：（1）任何兩個顧客的收貨地址都不相同；（2）每一個訂單都有一個惟一的訂單號碼。（3）每個訂單的訂單細則在這個訂單里有一個惟一的編號。函數(shù)依賴圖如下：相應(yīng)的BCNF關(guān)系模式如下：CUST(CUST，BAL，CREDLIM，DISCOUNT) PRIMARY KEY(CUST)SHIPTO(ADDRESS，CUST) PRIMARY KEY(ADDRESS)ORDHEAD(ORD，ADDRESS，DATE) PRIMARY KEY(ORD)ORDLINE(ORD，LINE，ITEM，QTYORD，QTYOUT) PRIMARY KEY (ORD，LINE)ITEM(ITEM，DESCN) PRIMARY KEY(ITEM)IP(ITEM，PLANT，QTYOH，DANGER) PRIMARY KEY (ITEM，PLANT)11答：如果99的顧客只有一個收貨地址，則把地址放在與CUST不同的關(guān)系模式中，實際處理訂貨過程時的效率是很低的。因此我們可以對這個問題進行改進。對于每個顧客，指定一個合法收貨地址作為主地址，則對于99的顧客