自考數(shù)據(jù)庫(kù)系統(tǒng)原理

1、1函數(shù)依賴：設(shè)有關(guān)系模式R（U），X和Y是屬性集U的子集，函數(shù)依賴（functional dependency，簡(jiǎn)記為FD）是形為XY的一個(gè)命題，只要r是R的當(dāng)前關(guān)系，對(duì)r中任意兩個(gè)元組t和s，都有tX=sX蘊(yùn)涵tY=sY，那么稱FD XY在關(guān)系模式R（U）中成立。這里tX表示元組t在屬性集X上的值，其余類同。XY讀作“X函數(shù)決定Y”，或“Y函數(shù)依賴于X”。FD是對(duì)關(guān)系模式R的一切可能的關(guān)系r定義的。對(duì)于當(dāng)前關(guān)系r的任意兩個(gè)元組，如果X值相同，則要求Y值也相同，即有一個(gè)X值就有一個(gè)Y值與之對(duì)應(yīng)，或者說(shuō)Y值由X值決定。因而這種依賴稱為函數(shù)依賴。2平凡的函數(shù)依賴:對(duì)于FD XY，如果YX，那么稱X

2、Y是一個(gè)“平凡的FD”，否則稱為“非平凡的FD”。正如名稱所示，平凡的FD并沒(méi)有實(shí)際意義，根據(jù)規(guī)則A1就可推出。人們感興趣的是非平凡的FD。只有非平凡的FD才和“真正的”完整性約束條件相關(guān)。從規(guī)則A4和A5，立即可得到下面的定理。定理3.3 如果A1An是關(guān)系模式R的屬性集，那么XA1An成立的充分必要條件是XAi（i=1，n）成立。3函數(shù)依賴集F的閉包F+（Closure）:設(shè)F是函數(shù)依賴集，被F邏輯蘊(yùn)涵的函數(shù)依賴全體構(gòu)成的集合，稱為函數(shù)依賴集F的閉包（Closure），記為F+。即F+= XY | F|=XY。4屬性集X的閉包X+:設(shè)F是屬性集U上的FD集，X是U的子集，那么（相對(duì)于F）屬

3、性集X的閉包用X+表示，它是一個(gè)從F集使用FD推理規(guī)則推出的所有滿足XA的屬性A的集合：X+=屬性A | F|=XA 5函數(shù)依賴的邏輯蘊(yùn)含:設(shè)F是在關(guān)系模式R上成立的函數(shù)依賴的集合，XY是一個(gè)函數(shù)依賴。如果對(duì)于R的每個(gè)滿足F的關(guān)系r也滿足XY，那么稱F邏輯蘊(yùn)涵XY，記為F|=XY。6函數(shù)依賴集的等價(jià):如果關(guān)系模式R（U）上的兩個(gè)函數(shù)依賴集F和G，有F+=G+，則稱F和G是等價(jià)的函數(shù)依賴集。7最小依賴集:如果函數(shù)依賴集G滿足下列三個(gè)條件，則稱為G是最小依賴集。（1）G中每個(gè)FD的右邊都是單屬性。（2）G中沒(méi)有冗余的F，即G中不存在這樣的函數(shù)依賴XY，使得GXY與G等價(jià)。（3）G中每個(gè)FD的左邊沒(méi)

4、有冗余的屬性，即G中不存在這樣的函數(shù)依賴XY，X有真子集W使得GXYWY與G等價(jià)。顯然，每個(gè)函數(shù)依賴集至少存在一個(gè)等價(jià)的最小依賴集，但并不一定惟一。8無(wú)損分解:設(shè)R是一個(gè)關(guān)系模式，F(xiàn)是R上的一個(gè)FD集。R分解成數(shù)據(jù)庫(kù)模式=R1，R2Rk。如果對(duì)R中滿足F的每一個(gè)關(guān)系r，都有r=那么稱分解相對(duì)于F是“無(wú)損連接分解”（Lossless Join Decomposition），簡(jiǎn)稱為“無(wú)損分解”，否則稱為“損失分解”（Lossy Decomposition）。9泛關(guān)系假設(shè):無(wú)損分解定義有一個(gè)先決條件，即r是R的一個(gè)關(guān)系。也就是先存在r（泛關(guān)系）的情況下，再去談?wù)摲纸?，這就是關(guān)系數(shù)據(jù)庫(kù)理論中著名的“泛

5、關(guān)系假設(shè)”（Univarsal Relation Assumption）。有泛關(guān)系假設(shè)時(shí)，r與（r）之間的聯(lián)系，可用圖3.3表示。從圖中可看出（r）有兩個(gè)性質(zhì)：（1）r（r）（2）設(shè)s=（r），則=riRrs=R1，R2Rk r1，r2，rk圖3.3 泛關(guān)系假設(shè)下關(guān)系模式分解的示意圖10Chase過(guò)程: “追蹤”（chase）過(guò)程，用于測(cè)試一個(gè)分解是否是無(wú)損分解。追蹤過(guò)程的算法（無(wú)損分解的測(cè)試）輸入：關(guān)系模式R=A1An，F(xiàn)是R上成立的函數(shù)依賴集，=R1，Rk是R的一個(gè)分解。輸出：判斷相對(duì)于F是否具有無(wú)損分解特征。方法：構(gòu)造一張k行n列的表格，每列對(duì)于一個(gè)屬性Aj（1jn），每行對(duì)于一個(gè)模式R

6、i（1ik）。如果Aj在Ri中，那么在表格的第i行第j列處填上符號(hào)aj，否則填上bij。把表格看成模式R的一個(gè)關(guān)系，反復(fù)檢查F中每個(gè)FD在表格中是否成立，若不成立，則修改表格中的值。修改反復(fù)如下：對(duì)于F中一個(gè)FD XY，如果表格中有兩行在X值上相對(duì)，在Y值上不相等，那么把這兩行在Y值上也改成相等的值。如果Y值中有一個(gè)是aj，那么另一個(gè)也改成aj；如果沒(méi)有aj，那么用其一個(gè)bij替換另一個(gè)值（盡量把下標(biāo)ij改成較小的數(shù)）。一直到表格不能修改為止。（這個(gè)過(guò)程稱為Chase過(guò)程）若修改的最后一張表格中有一行是全a，即a1a2an，那么稱相對(duì)于F是無(wú)損分解，否則稱損失分解。11保持函數(shù)依賴:分解的另一

7、個(gè)特征是在分解的過(guò)程中能否函數(shù)依賴集，如果不能保持FD，那么數(shù)據(jù)的語(yǔ)義就會(huì)出現(xiàn)混亂。設(shè)F是屬性集U上的FD集，Z是U的子集，F(xiàn)在Z上的投影用表示，定義為設(shè)=R1，Rk是R的一個(gè)分解，F(xiàn)是R上的FD集，如果有，那么稱分解保持函數(shù)依賴集F。121NF如果關(guān)系模式R的每個(gè)關(guān)系r的屬性值都是不可分的原子值，那么稱R是第一范式（First Normal Form，簡(jiǎn)記為1NF）的模式。132NF如果關(guān)系模式R是1NF，且每個(gè)非主屬性完全函數(shù)依賴于候選鍵，那么稱R是第二范式（2NF）的模式。143NF如果關(guān)系模式R是1NF，且每個(gè)非主屬性都不傳遞依賴于R的候選鍵，那么稱R是第三范式（3NF）的模式。15B

8、CNF如果關(guān)系模式R是1NF，且每個(gè)屬性都不傳遞依賴于R的候選鍵，那么稱R是BCNF。16MVD設(shè)U是關(guān)系模式R的屬性集，X，Y是U的子集，Z=U-X-Y，小寫(xiě)的xyz表示屬性集XYZ的值。對(duì)于R的關(guān)系r，在r中存在元組（x，y1，z1）和（x，y2，z2）時(shí)，就也存在元組（x，y2，z1）和（x，y1，z2），那么稱多值依賴（Multivalued Dependency，簡(jiǎn)記為MVD）XY在模式R上成立。17平凡的MVD對(duì)于屬性集U上的MVD XY，如果YX或XY=U，那么稱XY是一個(gè)平凡的MVD，否則稱XY是一個(gè)非平凡的MVD。184NF設(shè)D是關(guān)系模式R上成立的FD和MVD集合。如果D中每

9、個(gè)非平凡的MVD XY的左部X都是R的超鍵，那么稱R是4NF的模式。3.2試解釋下面兩個(gè)“數(shù)據(jù)冗余”概念：一、文件系統(tǒng)中不可避免的“數(shù)據(jù)冗余”在數(shù)據(jù)管理中，數(shù)據(jù)冗余一直是影響系統(tǒng)性能的大問(wèn)題。數(shù)據(jù)冗余是指同一個(gè)數(shù)據(jù)在系統(tǒng)中多次重復(fù)出現(xiàn)。在文件系統(tǒng)中，由于文件之間沒(méi)有聯(lián)系，引起一個(gè)數(shù)據(jù)在多個(gè)文件中出現(xiàn)。二、關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)中應(yīng)該盡量避免的“數(shù)據(jù)冗余”數(shù)據(jù)庫(kù)系統(tǒng)克服了文件系統(tǒng)的這種缺陷，但對(duì)于數(shù)據(jù)冗余問(wèn)題仍然應(yīng)加以關(guān)注。如果一個(gè)關(guān)系模式設(shè)計(jì)的不好，仍然會(huì)出現(xiàn)像文件系統(tǒng)一樣的數(shù)據(jù)冗余、異常、不一致等問(wèn)題。3.3關(guān)系模式的非形式化設(shè)計(jì)準(zhǔn)則有哪幾條？這些準(zhǔn)則對(duì)數(shù)據(jù)庫(kù)設(shè)計(jì)有什么幫助？在討論關(guān)系模式質(zhì)量時(shí)，有

10、四個(gè)非形式化的衡量準(zhǔn)則。準(zhǔn)則3.1 關(guān)系模式的設(shè)計(jì)應(yīng)盡可能只包含直接聯(lián)系的屬性，不要包含有間接聯(lián)系的屬性。也就是，每個(gè)關(guān)系模式應(yīng)只對(duì)應(yīng)于一個(gè)實(shí)體類型或一個(gè)聯(lián)系類型。準(zhǔn)則3.2 關(guān)系模式的設(shè)計(jì)應(yīng)盡可能使得相應(yīng)關(guān)系中不出現(xiàn)插入、刪除和修改等操作異常現(xiàn)象。如果出現(xiàn)任何異常，則要清楚地加以說(shuō)明，并確保更新數(shù)據(jù)庫(kù)的正確操作。設(shè)計(jì)成表準(zhǔn)則3.3 關(guān)系模式的設(shè)計(jì)應(yīng)盡可能使得相應(yīng)關(guān)系之中避免放置經(jīng)常為空的屬性。準(zhǔn)則3.4 關(guān)系模式的設(shè)計(jì)應(yīng)盡可能使得關(guān)系的等值連接在主鍵和外鍵的屬性上進(jìn)行，并且保證連接以后不會(huì)生成額外的元組。3.4對(duì)函數(shù)依賴XY的定義加以擴(kuò)充，X和Y可以為空屬性集，用表示，那么X，Y，的含義是什

11、么？解：根據(jù)函數(shù)依賴的定義，以上三個(gè)表達(dá)式的含義為：1. 一個(gè)關(guān)系模式R（U）中，X，Y是U的子集，r是R的任一具體關(guān)系，如果對(duì)r的任意兩個(gè)元組t1、t2，由t1X=t2X必有t1=t2。即X表示空屬性函數(shù)依賴于X。這是任何關(guān)系中都存在的。2. Y表示Y函數(shù)依賴于空屬性。由此可知該關(guān)系中所有元組中Y屬性的值均相同。3. 表示空屬性函數(shù)依賴于空屬性。這也是任何關(guān)系中都存在的。3.5用A1、A2和A3三條推理規(guī)則來(lái)證明3.2.3節(jié)中的定理3.2（推理規(guī)則A4A8）試證明A1（自反性）：若YXU，則XY在R上成立。證：設(shè)t1和t2是關(guān)系R中的任意兩個(gè)元組。如t1【X】=t2【X】，因YX，則有t1【

12、Y】=t2【Y】，故XY在R上成立。試證明A2（增廣性）：若XY在R上成立，且ZU，則XZYZ在R上成立。證：設(shè)t1和t2是關(guān)系R中的任意兩個(gè)元組。如果t1【XZ】=t2【XZ】，則有如t1【X】=t2【X】，t1【Z】=t2【Z】。已知XY，因此可得t1【Y】=t2【Y】，由上可知如t1【YZ】=t2【YZ】，故XZYZ成立。試證明A3（傳遞性）：若XY和若YZ在R上成立，則XZ在R上成立。證：設(shè)t1和t2是關(guān)系R中的任意兩個(gè)元組。根據(jù)傳遞函數(shù)依賴條件可知：如t1【X】=t2【X】，則t1【Y】=t2【Y】，如t1【Y】=t2【Y】，則t1【Z】=t2【Z】，由上可得：如t1【X】=t2【X

13、】，則t1【Z】=t2【Z】，即XZ在R上成立。試證明A4（合并性）：XY，XZ |=XYZ。證：根據(jù)A2增廣性，在XY的函數(shù)依賴表達(dá)式左部和右部分別并上X，得 XX Y。在XZ的函數(shù)依賴表達(dá)式左部和右部分別并上Y，得 XYYZ。根據(jù)A3傳遞性，由XX Y和XYYZ得XYZ。試證明A5（分解性）XY，ZY |=XZ。證：根據(jù)A 1自反性，因?yàn)閆Y所以YZ成立。已知XY又知，YZ，根據(jù)A3，得XZ。試證明A6（偽傳遞性）XY，WYZ |=WXZ。證：根據(jù)A2增廣性，在XY的函數(shù)依賴表達(dá)式左部和右部分別并上W，得WXWY。根據(jù)A3傳遞性，由WXWY 和WYZ得WXZ。試證明A7（復(fù)合性）XY，WZ

14、 |=WXYZ。證：根據(jù)A2增廣性，在XY的函數(shù)依賴表達(dá)式左部和右部分別并上W，的WXWY。在WZ的函數(shù)依賴表達(dá)式左部和右部分別并上Y，的WYZY。根據(jù)A3傳遞性，由WXWY和WYZY得WXYZ。試證明A8（復(fù)合性）XY，WZ|=X(WY)YZ。證：根據(jù)A2增廣性，在XY兩邊用（WY）擴(kuò)充，得到X(WY)Y(WY），而Y(WY)=WY，因此有X(WY)WY。從已知WZ，根據(jù)A2兩邊用Y擴(kuò)充，得到WYYZ。在根據(jù)A3，從X(WY)WY和WYYZ可得到X(WY)YZ3.6設(shè)關(guān)系模式R有n個(gè)屬性，在模式R上可能成立的函數(shù)依賴有多少個(gè)？其中平凡的FD有多少個(gè)？非平凡的FD有多少個(gè)？（要考慮所有可能的情

15、況,數(shù)學(xué)排列組合問(wèn)題。對(duì)于數(shù)據(jù)庫(kù)本身而言，本題沒(méi)多大意義）解：這個(gè)問(wèn)題是排列組合問(wèn)題。FD形為XY，從n個(gè)屬性值中選擇屬性組成X共有：種方法；同理，組成Y也有種方法。因此組成XY形成應(yīng)該有種方法。即可能成立的FD有個(gè)。平凡的FD要求YX，組合XY形式的選擇有：即平凡的FD有。因而非平凡的FD有個(gè)。3.7已知關(guān)系模式R（ABC），F(xiàn)是R上成立的FD集，F(xiàn)=AB，BC，試寫(xiě)出F的閉包F+（有43個(gè)）。 A AB AC ABC B BC CAA ABA ACA ABCA BB BCB CCAB ABB ACB ABCB BC BCCAC ABC ACC ABCC BBC BCBCAAB ABAB A

16、CAB ABCABAAC ABAC ACAC ABCACABC ABBC ACBC ABCBCAABC ABABC ACABC ABCABC解：1 先求屬性集ABC的子集、A、AB、AC、ABC、B、BC、C2 求以上子集的閉包根據(jù)F=AB，BC，得：+=A+=ABC A有： + + + =23=8個(gè)B+=BC B有： + + =22=4個(gè)C+=C C有： + =21=2個(gè)(AB)+=ABC AB有：8個(gè)(AC)+=ABC AC有：8個(gè)(BC)+=BC AB有：4個(gè)(ABC)+=ABC ABC有：8個(gè)共43個(gè)。 3 求函數(shù)依賴根據(jù)屬性集的閉包，得：根據(jù)：+=得：根據(jù)：A+=ABC得：A、AA、

17、AB、AC、AAB、AAC、ABC、AABC根據(jù)：B+=BC得：B、BB、BC、BBC根據(jù)：C+=C得：C、CC根據(jù)：AB+=ABC得：AB、ABA、ABB、ABC、ABAB、ABAC、ABBC、ABABC根據(jù)：AC+=ABC得：AC、ACA、ACB、ACC、ACAB、ACAC、ACBC、ACABC根據(jù)：BC+=BC得：BC、BCB、BCC、BCBC根據(jù)：ABC+=ABC得：ABC、ABCA、ABCB、ABCC、ABCAB、ABCAC、ABCBC、ABCABC3.8設(shè)關(guān)系模式R（ABCD），F(xiàn)是R上成立的FD集，F(xiàn)=AB，CB，則相對(duì)于F，試寫(xiě)出關(guān)系模式R的關(guān)鍵碼。并說(shuō)明理由。解：由于A、C屬

18、性是L類屬性，則A、C必為 R 的任一候選碼的成員。由于D屬性是N類屬性，則D必為 R 的任一候選碼的成員。到此，初步確定的關(guān)鍵碼為ACD。下一步根據(jù)F求出ACD的閉包，得ACD+=ABCD。因?yàn)锳CD+包含了R的全部屬性，ACD是 R 的唯一關(guān)鍵鍵碼。3.9設(shè)關(guān)系模式R（ABCDE），F(xiàn)是R上成立的FD集，F(xiàn)=ABC，CDE，DEB，判斷AB是R的候選鍵嗎？ABD呢？請(qǐng)做出解釋。解：屬性AB如果是候選鍵，那么AB的閉包必須包含R的全部屬性。根據(jù)F得AB+=ABC。AB+沒(méi)有包含R的全部屬性，故AB不是R的候選鍵。屬性ABC如果是候選鍵，那么ABC的閉包必須包含R的全部屬性。根據(jù)F得ABD+=

19、ABCDE。ABD+包含R的全部屬性，故ABD是R的候選鍵。3.10設(shè)關(guān)系模式R（ABCD）上FD集為F，并且F=ABC，CD，DA 試從F求出所有非平凡的FD。 試求R的所有候選鍵 試求R的所有不是候選鍵的超鍵。解：要想求出、和，就必須先求出屬性集的所有子集及其子集的閉包。1、求屬性集ABCD的子集。在屬性集ABCD中找出由一個(gè)屬性組成的子集。A、B、C、D共4個(gè)。在屬性集ABCD中找出由兩個(gè)屬性組成的子集。共6個(gè)。ABCDAABACADBBCBDCCDD在屬性集ABCD中找出由三個(gè)屬性組成的子集。共4個(gè)ABCDABABCABDACABCACDADABDACDBCABCBCDBDABDBCD

20、CDACDBCD在屬性集ABCD中找出由四個(gè)屬性組成的子集。ABCD 一個(gè)。屬性集ABCD的子集：共15個(gè)。ABC DABBCCDACBDADBCDABCABDACDABCD2、所有子集的閉包（參照F=ABC，CD，DA）。A+ =AB+ =BC+ =ACDD+=DAAB+ =ABCDBC+ =BCDACD+=CDAAC+ =ACDBD+ =BDACAD+ =ADBCD+=BCDAABC+ =ABCDABD+ =ABDCACD+ =ACDABCD+=ABCD求屬性的閉包有兩種算法（一是根據(jù)推理規(guī)則，而是根據(jù)閉包的算法）3、求出所有的函數(shù)依賴 1）根據(jù) A+=A AA 平凡的函數(shù)依賴（1），非平

21、凡的函數(shù)依賴（0） 2）根據(jù) B+=B BB 平凡的函數(shù)依賴（1），非平凡的函數(shù)依賴（0） 3）根據(jù) C+=ACD CA CAC CAD CACD CC CCD CD 平凡的函數(shù)依賴（1），非平凡的函數(shù)依賴（6） 4）根據(jù) D+=AD DA DD DDA 平凡的函數(shù)依賴（1），非平凡的函數(shù)依賴（2） 5）根據(jù) AB+=ABCD ABA ABAB ABAC ABADABABC ABABD ABACD ABABCD ABB ABBC ABBD ABBCD ABC ABCD ABD 平凡的函數(shù)依賴（3），非平凡的函數(shù)依賴（12） 6）根據(jù) BC+=ABCD BCA BCAB BCAC BCAD BC

22、ABC BCABD BCACD BCABCD BCB BCBC BCBD BCBCD BCC BCCD BCD 平凡的函數(shù)依賴（3），非平凡的函數(shù)依賴（12） 7）根據(jù) CD+=ACD CDA CDAC CDAD CDACD CDC CDCD CDD 平凡的函數(shù)依賴（3），非平凡的函數(shù)依賴（4） 8）根據(jù) AC+=ACD ACA ACAC ACAD ACACD ACC ACCD ACD 平凡的函數(shù)依賴（3），非平凡的函數(shù)依賴（4） 9）根據(jù) BD+=ABCD BDA BDAB BDAC BDAD BDABC BDABD BDACD BDABCD BDB BDBC BDBD BDBCD BDC

23、BDCD BDD 平凡的函數(shù)依賴（3），非平凡的函數(shù)依賴（12）10）根據(jù) AD+=AD ADA ADAD ADD 平凡的函數(shù)依賴（3），非平凡的函數(shù)依賴（0）11）根據(jù) BCD+=ABCD BCDA BCDAB BCDAC BCDAD BCDABC BCDABD BCDACD BCDABCD BCDB BCDBC BCDBD BCDBCD BCDC BCDCD BCDD 平凡的函數(shù)依賴（7），非平凡的函數(shù)依賴（8）12）根據(jù) ABC+=ABCD ABCA ABCAB ABCAC ABCAD ABCABC ABCABD ABCACD ABCABCD ABCB ABCBC ABCBD ABCBC

24、D ABCC ABCCD ABCD 平凡的函數(shù)依賴（7），非平凡的函數(shù)依賴（8）13）根據(jù) ABD+=ABCD ABDA ABDAB ABDAC ABDAD ABDABC ABDABD ABDACD ABDABCD ABDB ABDBC ABDBD ABDBCD ABDC ABDCD ABDD 平凡的函數(shù)依賴（7），非平凡的函數(shù)依賴（8）14）根據(jù) ACD+=ACD ACDA ACDAC ACDAD ACDACD ACDCACDCD ACDD 平凡的函數(shù)依賴（7），非平凡的函數(shù)依賴（0）15）根據(jù) ABCD+=ABCD ABCDA ABCDAB ABCDAC ABCDAD ABCDABC AB

25、CDABD ABCDACD ABCDABCD ABCDB ABCDBC ABCDBD ABCDBCD ABCDC ABCDCD ABCDD 平凡的函數(shù)依賴（15），非平凡的函數(shù)依賴（0） 從已知的F可求出非平凡的FD有76個(gè)。譬如，左邊是C的FD有6個(gè)：CA，CD，CAD，CAC，CCD，CACD。 左邊是D的FD有2個(gè)：DA，DAD。 左邊是AB的FD有12個(gè)：ABC, ABD, ABCD, ABAC,。感興趣的讀者可以自行把這76個(gè)FD寫(xiě)齊。 1）根據(jù) A+=A平凡的函數(shù)依賴（ 1），非平凡的函數(shù)依賴（ 0） 2）根據(jù) B+=B平凡的函數(shù)依賴（ 1），非平凡的函數(shù)依賴（ 0） 3）根據(jù) C

26、+=ACD平凡的函數(shù)依賴（ 1），非平凡的函數(shù)依賴（ 6） 4）根據(jù) D+=AD平凡的函數(shù)依賴（ 1），非平凡的函數(shù)依賴（ 2） 5）根據(jù) AB+=ABCD平凡的函數(shù)依賴（ 3），非平凡的函數(shù)依賴（12） 6）根據(jù) BC+=ABCD平凡的函數(shù)依賴（ 3），非平凡的函數(shù)依賴（12） 7）根據(jù) CD+=ACD平凡的函數(shù)依賴（ 3），非平凡的函數(shù)依賴（ 4） 8）根據(jù) AC+=ACD平凡的函數(shù)依賴（ 3），非平凡的函數(shù)依賴（ 4） 9）根據(jù) BD+=ABCD平凡的函數(shù)依賴（ 3），非平凡的函數(shù)依賴（12）10）根據(jù) AD+=AD平凡的函數(shù)依賴（ 3），非平凡的函數(shù)依賴（ 0）11）根據(jù) BCD+=A

27、BCD平凡的函數(shù)依賴（ 7），非平凡的函數(shù)依賴（ 8）12）根據(jù) ABC+=ABCD平凡的函數(shù)依賴（ 7），非平凡的函數(shù)依賴（ 8）13）根據(jù) ABD+=ABCD平凡的函數(shù)依賴（ 7），非平凡的函數(shù)依賴（ 8）14）根據(jù) ACD+=ACD平凡的函數(shù)依賴（ 7），非平凡的函數(shù)依賴（ 0）15）根據(jù) ABCD+=ABCD平凡的函數(shù)依賴（15），非平凡的函數(shù)依賴（ 0） -共計(jì) （65） 共計(jì)（76） 候選鍵是能函數(shù)決定所有屬性的不含多余屬性的屬性集。根據(jù)這個(gè)概念可求出R 的候選鍵有三個(gè)：AB、BC和BD。 R的所有不是候選鍵的超鍵有四個(gè)：ABC、ABD、BCD和ABCD。3.11如果下列推理規(guī)則成

28、立，則用推理規(guī)則A1A8證明之；否則舉出一個(gè)關(guān)系實(shí)例說(shuō)明規(guī)則不成立。WY，XZ|=WXYXY,XW,WYZ|=XZXYZ，YW|=XWZXZ，YZ|=XYXY，XYZ|=XZXY，ZW|=XZYWXYZ，ZX|=ZYXY，YZ|=XYZXYZ，ZW|=XW解：WY，XZ|=WXY根據(jù)推理規(guī)則A2（增廣性）在FD WY兩邊同時(shí)并上X，得 WXXY。已知WY,又因WWX，故WXY成立。XY,XW,WYZ|=XZ根據(jù)FD的分解/合并規(guī)則，XY,XW可合并成XYW，再根據(jù)推理規(guī)則A3（傳遞性），XYW，WYZ可得XZXYZ，YW|=XWZ根據(jù)推理規(guī)則A2（增廣性）在FD YW兩邊同時(shí)并上X，得YXXW

29、。因?yàn)閄YZ，YXXW，Z和XW沒(méi)有包含或被包含的關(guān)系。故XYZ，YW|=XWZ不成立。例R（WXYZ），F(xiàn)=XYZ，YW，從以下函數(shù)依賴的圖形化表示可以看出，不成立。R（W X Y Z）XZ，YZ|=XY因?yàn)镕D XZ，YZ，X和Y沒(méi)有包含或被包含的關(guān)系。故上式不成立。XY，XYZ|=XZ根據(jù)推理規(guī)則A2（增廣性）在FD XY兩邊同時(shí)并上X，得XXXY。再根據(jù)推理規(guī)則A3（傳遞性），XXXY，XYZ，得XZXY，ZW|=XZYW根據(jù)推理規(guī)則A2（增廣性）在FD XY兩邊同時(shí)并上Z，得XZYZ。根據(jù)推理規(guī)則A2（增廣性）在FD ZW兩邊同時(shí)并上Y，得YZYW。再根據(jù)推理規(guī)則A3（傳遞性），XZ

30、YZ，YZYW，得XZYWXYZ，ZX|=ZY因?yàn)镕D XZ，YZ，X和Y沒(méi)有包含或被包含的關(guān)系。故上式不成立。XY，YZ|=XYZ根據(jù)推理規(guī)則A3（傳遞性）XY，YZ，得XZ。根據(jù)FD的分解/合并規(guī)則，XY,XZ可合并成XYZ。XYZ，ZW|=XW根據(jù)推理規(guī)則A3（傳遞性）XYZ，ZW，得XYW。故上式不成立。3.12 考慮以下兩個(gè)FD集：F=AC，ACD，EAD，EH和G=ACD，EAH。試檢查它們是否等價(jià)（應(yīng)說(shuō)出理由）。對(duì)F：A+=ACD，C+=C，D+=D，E+=EADCH=ACDEH，H+=H，AC+=ACD（AC+=A+C+ABC）。對(duì)G：A+=ACD，C+=C，D+=D，E+=E

31、AHCD=ACDEH，H+=H，AC+=ACD（AC+=A+C+ABC）。故F與G等價(jià)。理由：F和G相等，意味著F中每一個(gè)FD都可以從G推導(dǎo)出來(lái)，并且G中每一個(gè)FD也都可以從F推導(dǎo)出來(lái)。同例：R(ABCDE)，F(xiàn)1=AB,ABC,DAC,DE與F2=ABC,DAE等價(jià)？對(duì)F1：A+ABC，B+B，C+C，D+ABCDE，E+E，(AB)+ABC（AB+=A+B+=ABC）。對(duì)F2：A+ABC，B+B，C+C，D+ABCDE，E+E，(AB)+ABC（AB+=A+B+=ABC）。故F1與F2等價(jià)。3.13設(shè)關(guān)系模式R（ABCD）上FD集為F，并且F=AB，BC 試寫(xiě)出屬性集BD的閉包（BD）+。

32、 試寫(xiě)出所有左部是B的函數(shù)依賴（即形為“B？”）解： 有兩種解法1）用推理規(guī)則 從已知的F，F(xiàn)D BC，根據(jù)A2（增廣性），在兩邊同并上BD得BBDCBD 優(yōu)化后，可推出BDBCD，所以(BD)+=BCD。2）用屬性集的算法 1初始化，設(shè)X為所求屬性集的閉包，X(0)=BD。 2計(jì)算X(1)，在F中掃描各個(gè)FD，找左部為BD或BD子集的FD，找到一個(gè)FD BC左邊屬性在X(0)中，而右邊屬性不在X(0)中，就把C和X(0)加到X(1) 中。然后再F中做上標(biāo)記。因X(1)<U，算法繼續(xù)。 X(1)= X(0)C=BDC=BCD F=AB，BC 3計(jì)算X(2)，在F中掃描沒(méi)做處理標(biāo)記的FD，

33、找左部為BCD或BCD子集的FD， 沒(méi)找到，X(1)= X(0)。算法終止。 由算法得：(BD)+= X(1)=BCD 首先計(jì)算B的閉包1 初始化，設(shè)X為所求屬性B的閉包，X(0)=B。2 計(jì)算X(1),在F中掃描各個(gè)FD，找左邊為B的FD，找到一個(gè)FD BC左邊屬性在X(0)中，右邊屬性不在X(0)中，就把C和X(0)加到X(1) 中。然后再F中做上標(biāo)記。因X(1)<U，算法繼續(xù)。 X(1)= X(0)C=BC=BC F=AB，BC3 計(jì)算X(2)，在F中掃描沒(méi)做處理標(biāo)記的FD，找左部為BC或BC子集的FD，沒(méi)找到，X(1)= X(0)。算法終止。有算法得：(B)+= X(1)=BC由

34、于B+BC=BC，因此左部是B的FD有四個(gè)：B，BB，BC，BBC。3.14設(shè)關(guān)系模式R（ABCDE）上FD集為F，并且F=ABC，CDE，BD，EA。 試求R的候選鍵。 試求B+的值。解： R的候選鍵有A、E、CD和BC最有把握的求法是：1） 求出關(guān)系屬性集的所有子集。2） 求所有子集的閉包。3） 在所有子集的閉包中查找那些包含所有屬性集的閉包，那些不含多余屬性的屬性集閉包就是我們要找的候選鍵。1）求屬性集ABCDE的子集。 在屬性集ABCDE中找出由一個(gè)屬性組成的子集。A、B、C、D、E，共5個(gè)。 在屬性集ABCDE中找出由兩個(gè)屬性組成的子集。共10個(gè)。ABCDEAABACADAEBBCB

35、DBECCDCEDDEE在屬性集ABCDE中找出由三個(gè)屬性組成的子集。共10個(gè)。ABCDEABABCABDABEACABCACDACEADABDACDADEAEABEACEADEBCABCBCDBCEBDABDBCDBDEBEABEBCEBDECDACDBCDCDECEACEBCECDEDEADEBDECDE在屬性集ABCDE中找出由四個(gè)屬性組成的子集。共5個(gè)。ABCDEABCABCDABCEABDABCDABDEABEABCEABDEACDABCDACDEACEABCEACDEADEABDEACDEBCDABCDBCDEBCEABCEBCDEBDEABDEBCDECDEACDEBCDE在屬性

36、集ABCDE中找出由五個(gè)屬性組成的子集。ABCDE，共1個(gè)。至此，共找出 5+10+10+5+1=31個(gè)子集。它們是：A、B、C、D、EAB、AC、AD、AE、BC、BD、BE、CD、CE、DEABC、ABD、ABE、ACD、ACE、ADE、BCD、BCE、BDE、CDEABCD、ABCE、ABDE、ACDE、BCDEABCDE2）求U=ABCDE所有子集的閉包（參照F=ABC，CDE，BD，EA）。ABC+=ABCDEABD+=ABDCE=ABCDEABE+=ABECD=ABCDEACD+=ACDBE=ABCDEACE+=ACEBD=ABCDEADE+=ADEBC=ABCDEBCD+=BCD

37、EA=ABCDEBCE+=BCEDA=ABCDEBDE+=BDEAC=ABCDECDE+=CDEAB=ABCDEABCD+=ABCDEABCE+=ABCED=ABCDEABDE+=ABDEC=ABCDEACDE+=ACDEB=ABCDEBCDE+=BCDEA=ABCDEABCDE+=ABCDEA+=ABCDEB+=BDC+=CD+=DE+=EABCD=ABCDEAB+=ABDAC+=ACBDE=ABCDEAD+=ADBCE=ABCDEAE+=AEBCD=ABCDEBC+=BCDEA=ABCDEBD+=BDBE+=BEDAC=ABCDECD+=CDEAB=ABCDECE+=CEABD=ABCDE

38、DE+=DEABC=ABCDE根據(jù)候選鍵的定義A+=ABCDE是候選鍵所有包含A的屬性子集，閉包內(nèi)容為ABCDE的都是超鍵。E+=ABCDE是候選鍵所有包含E的屬性子集，閉包內(nèi)容為ABCDE的都是超鍵。BC+=ABCDE是候選鍵所有包含BC的屬性子集，閉包內(nèi)容為ABCDE的都是超鍵。CD+=ABCDE是候選鍵所有包含CD的屬性子集，閉包內(nèi)容為ABCDE的都是超鍵。 B+=BD。1） 初始化，設(shè)X為所求屬性B的閉包，X(0)=B2） 計(jì)算X（1），在F中掃描各個(gè)FD，找左邊為B的FD。找到一個(gè)FD BD左邊屬性在X(0)中，而右邊屬性不在X(0)中，就把D和X(0)加的X(1)中，然后在F中做上

39、標(biāo)記。因X(1)<U，算法繼續(xù)。 X(1)= X(0)D=BD=BD3） 計(jì)算X（1），在F中掃描沒(méi)有做過(guò)處理標(biāo)記的FD，找左邊為BD或BD子集的FD，沒(méi)有找到，X(1)= X(0)。算法終止。有算法得：(B)+= X(1)=BD3.15 設(shè)有關(guān)系模式R（ABC），其關(guān)系r如圖3.1所示。 試判斷下列三個(gè)FD在關(guān)系r中是否成立？ABBCABA 根據(jù)關(guān)系r，你能斷定哪些FD在關(guān)系模式R上不成立？ABC123423533 圖3.1解： 在關(guān)系r中，AB成立，BCA不成立，BA不成立。 在關(guān)系r中，不成立的FD有:BA，CA，CB，CAB，BCA。3.16 什么是寄生元組？什么是懸掛元組？各是

40、怎么產(chǎn)生的？1寄生元組在泛關(guān)系模式R分解成數(shù)據(jù)庫(kù)模式=R，R時(shí)，泛關(guān)系r在的每一模式R（1in）上投影后再連接起來(lái)，比原來(lái)r中多出來(lái)的元組，稱為“寄生元組”（Spurious Tuple）。2懸掛元組如果談?wù)撃Ｊ椒纸鈺r(shí)，先不提泛關(guān)系r的存在性，而先說(shuō)存在一個(gè)數(shù)據(jù)庫(kù)實(shí)例r，r，再設(shè)ri=s，那么 ri(s)記為si就未必與ri相等了，原因就是這些ri中可能存有“懸掛元組”（Dangling Tuple）在無(wú)泛關(guān)系假設(shè)時(shí)，對(duì)兩個(gè)關(guān)系進(jìn)行自然連接中被丟失的元組稱為懸掛元組。3.17 設(shè)關(guān)系模式R（ABC）分解成=AB，BC，如果R上的FD集F=AB，那么這個(gè)分解是損失分解。試舉出R的一個(gè)關(guān)系r，不滿

41、足m（r）=r。解：這個(gè)反例r可以舉測(cè)試時(shí)的初始表格：ABC ABa1a2b13 BCb21a2a3AB和BC這兩行中，因?yàn)镕中只有 FD AB，所以，表格不能修改。又因表格不能修改，在表格中沒(méi)有一行全是a，故泛模式R（ABC）分解成=AB，BC是損失分解。設(shè)r是R上的一個(gè)關(guān)系，如下：a1a2b13b21a2a3r在模式AB和BC上的投影如下：AB（r）BC（r）ABBCa1a2a2b13b21a2a2a3模式AB和BC的連接，也就是在r上的投影如下，連接后比原來(lái)r的元組還要多。AB（r）BC（r）有四個(gè)元組：ABCa1a2b13a1a2a3b21a2b13b21a2a3即m（r）r。4.18

42、 試解釋數(shù)據(jù)庫(kù)“丟失信息”與“未丟失信息”兩個(gè)概念?！皝G失信息”與“丟失數(shù)據(jù)”有什么區(qū)別？答：數(shù)據(jù)庫(kù)中丟失信息是指rm（r），未丟失信息是指r=m（r）。丟失信息：“無(wú)損中的“損”是指信息的丟失，而不是指元組的丟失。”所以丟失信息是指不能辨別元組的真?zhèn)?。丟失數(shù)據(jù)：丟失數(shù)據(jù)是指丟失元組，是在無(wú)泛關(guān)系假設(shè)時(shí)，由數(shù)據(jù)庫(kù)模式中的子模式自然連接中被丟失的元組。3.19 設(shè)關(guān)系模式R（ABC），F(xiàn)是R上成立的FD集，F(xiàn)=AC，BC，試分別求F在模式AB和AC上的投影。答：分解后，F(xiàn)中FD AC，BC，在模式AB中沒(méi)有投影，在模式AC中只保留了一個(gè)FD AC。另一個(gè)FD BC丟失了。即不保持F。AB（F）=

43、（即不存在非平凡的FD）AC（F）=AC3.20 設(shè)關(guān)系模式R（ABC），F(xiàn)是R上成立的FD集，F(xiàn)=BC，CA，=AB，AC是R上的一個(gè)分解，那么分解是否保持是否無(wú)損分解和保持FD集F？并說(shuō)明理由。答： 已知F=BC，CA， 而AB（F）=，AC（F）=CA 顯然，這個(gè)分解丟失了FD BC 用測(cè)試過(guò)程可以知道，相對(duì)于F是損失分解。算法運(yùn)用（b）修改后表格ABCABa1a2b13ACa1b21a3（a）初始表格ABCABa1a2b13ACa1b21a3根據(jù)函數(shù)依賴集F中FD BC，B列中沒(méi)有相同的a值，故不能修改相應(yīng)C列的值。函數(shù)依賴集FD CA，C列中沒(méi)有相同的a值，故不能修改相應(yīng)A列的值。因

44、為在表格中沒(méi)有一行具有相同的數(shù)字a，故該分解為損失分解。3.21 設(shè)關(guān)系模式R（ABCD），F(xiàn)是R上成立的FD集，F(xiàn)=AB，BC，AD，DC，=AB，AC，BD是R的一個(gè)分解。 相對(duì)于F，是無(wú)損分解嗎？為什么？ 試求F在的每個(gè)模式上的投影。 保持F嗎？為什么？答： 用測(cè)試過(guò)程可以知道，相對(duì)于F是損失分解。 1）根據(jù)函數(shù)依賴集F中FD AB，A列中AB與AC行單元格具有相同的內(nèi)容a1值， B列AB單元的內(nèi)容是a2，故可把B列AC行單元格中的內(nèi)容改為a2。（a） 初始表格ABCDABa1a2b13b14ACa1b22a3b24BDb31a2b33a4（b） 修改1(AB)ABCDABa1a2b13

45、b14ACa1a2a3b24BDb31a2b33a4 2）根據(jù)函數(shù)依賴集F中FD BC，B列中AB與AC行單元格具有相同的內(nèi)容a2值， C列AC單元的內(nèi)容是a3，故可把C列AB行單元格中的內(nèi)容改為a3。 3）根據(jù)函數(shù)依賴集F中FD AD，A列中AB與AC行單元格具有相同的內(nèi)容a1值， D列AB與AC行單元格的內(nèi)容沒(méi)有一個(gè)是a值，故用其中一個(gè)下標(biāo)較小的單元格 內(nèi)容替代另外一個(gè)下標(biāo)較大的單元格內(nèi)容。（c） 修改3(AD)ABCDABa1a2a3b14ACa1a2a3b14BDb31a2a3a4（d） 修改2(BC)ABCDABa1a2a3b14ACa1a2a3b24BDb31a2a3a4 4）根據(jù)函數(shù)依賴集F中FD DC，D列中沒(méi)有相同的內(nèi)容a4，不能操作。再說(shuō)C列 都是a3，不用操作。追蹤過(guò)程完畢。（e） 修改4(DC)ABCDABa1a2a3b14ACa1a2a3b24BDb31a2a3a4得泛關(guān)系模式R（ABCD）在數(shù)據(jù)庫(kù)模式上的一個(gè)分解=AB，AC，BD是損失分解。 AB（F）=AB，AC（F）=AC，BD（F）=。AB，BC推理規(guī)則推出