數(shù)據(jù)庫系統(tǒng)原理(機(jī)械工業(yè)出版社)第七章答案

1、n教學(xué)目標(biāo)：教學(xué)目標(biāo)：使學(xué)生了解關(guān)系模式規(guī)范化的必要性，使學(xué)生了解關(guān)系模式規(guī)范化的必要性，理解函數(shù)依賴、多值依賴及其關(guān)系范式定義，掌理解函數(shù)依賴、多值依賴及其關(guān)系范式定義，掌握關(guān)系范式判斷方法。握關(guān)系范式判斷方法。n教學(xué)重點(diǎn)：教學(xué)重點(diǎn)：關(guān)系模式規(guī)范化，函數(shù)依賴、多值依關(guān)系模式規(guī)范化，函數(shù)依賴、多值依賴、賴、1-4NF的定義，關(guān)系范式判斷方法。的定義，關(guān)系范式判斷方法。 n教學(xué)難點(diǎn)：教學(xué)難點(diǎn)：1-4NF的定義，關(guān)系范式判斷方法，關(guān)的定義，關(guān)系范式判斷方法，關(guān)系模式的分解。系模式的分解。 7.1 關(guān)系數(shù)據(jù)模式的規(guī)范化理論關(guān)系數(shù)據(jù)模式的規(guī)范化理論7.2 關(guān)系模式的分解算法關(guān)系模式的分解算法7.1 關(guān)

2、系數(shù)據(jù)模式的規(guī)范化理論范式（范式（Normal Form）是指規(guī)范化的關(guān)系模式。由）是指規(guī)范化的關(guān)系模式。由滿足最基本規(guī)范化的關(guān)系模式叫第一范式，第一范滿足最基本規(guī)范化的關(guān)系模式叫第一范式，第一范式的關(guān)系模式再滿足另外一些約束條件就產(chǎn)生了第式的關(guān)系模式再滿足另外一些約束條件就產(chǎn)生了第二范式、第三范式、二范式、第三范式、BC范式等等。一個(gè)低一級的范式等等。一個(gè)低一級的關(guān)系范式通過模式分解可以轉(zhuǎn)換成若干高一級范式關(guān)系范式通過模式分解可以轉(zhuǎn)換成若干高一級范式的關(guān)系模式的集合，這種過程叫關(guān)系模式的規(guī)范化。的關(guān)系模式的集合，這種過程叫關(guān)系模式的規(guī)范化。 7.1.1 關(guān)系模式規(guī)范化的必要性關(guān)系模式規(guī)范化的

3、必要性1. 關(guān)系模式應(yīng)滿足的基本要求1) 元組的每個(gè)分量必須是不可分的數(shù)據(jù)項(xiàng)。元組的每個(gè)分量必須是不可分的數(shù)據(jù)項(xiàng)。2) 數(shù)據(jù)冗余應(yīng)盡可能少。數(shù)據(jù)冗余應(yīng)盡可能少。3) 不能因?yàn)閿?shù)據(jù)更新操作而引起數(shù)據(jù)不一致問題。不能因?yàn)閿?shù)據(jù)更新操作而引起數(shù)據(jù)不一致問題。4) 當(dāng)執(zhí)行數(shù)據(jù)插入操作時(shí)，數(shù)據(jù)不能產(chǎn)生插入異常當(dāng)執(zhí)行數(shù)據(jù)插入操作時(shí)，數(shù)據(jù)不能產(chǎn)生插入異?，F(xiàn)象?，F(xiàn)象。5) 數(shù)據(jù)不能在執(zhí)行刪除操作時(shí)產(chǎn)生刪除異常問題。數(shù)據(jù)不能在執(zhí)行刪除操作時(shí)產(chǎn)生刪除異常問題。6) 數(shù)據(jù)庫設(shè)計(jì)應(yīng)考慮查詢要求，數(shù)據(jù)組織應(yīng)合理。數(shù)據(jù)庫設(shè)計(jì)應(yīng)考慮查詢要求，數(shù)據(jù)組織應(yīng)合理。數(shù)據(jù)冗余大數(shù)據(jù)冗余大, , 插入異常插入異常, , 刪除異常刪除異常

4、, , 更新異常。更新異常。 學(xué)號學(xué)號姓名姓名年齡年齡性別性別系名系名系主任系主任課程名課程名成績成績98001李華李華20男男計(jì)算機(jī)系計(jì)算機(jī)系王民王民程序設(shè)計(jì)程序設(shè)計(jì)8898001李華李華20男男計(jì)算機(jī)系計(jì)算機(jī)系王民王民數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)7498001李華李華20男男計(jì)算機(jī)系計(jì)算機(jī)系王民王民數(shù)據(jù)庫數(shù)據(jù)庫8298001李華李華20男男計(jì)算機(jī)系計(jì)算機(jī)系王民王民電路電路6598002張平張平21女女計(jì)算機(jī)系計(jì)算機(jī)系王民王民程序設(shè)計(jì)程序設(shè)計(jì)9298002張平張平21女女計(jì)算機(jī)系計(jì)算機(jī)系王民王民數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)8298002張平張平21女女計(jì)算機(jī)系計(jì)算機(jī)系王民王民數(shù)據(jù)庫數(shù)據(jù)庫7898002張平張平21女

5、女計(jì)算機(jī)系計(jì)算機(jī)系王民王民電路電路8398003陳兵陳兵20男男數(shù)學(xué)系數(shù)學(xué)系趙敏趙敏高等數(shù)學(xué)高等數(shù)學(xué)7298003陳兵陳兵20男男數(shù)學(xué)系數(shù)學(xué)系趙敏趙敏數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)9498003陳兵陳兵20男男數(shù)學(xué)系數(shù)學(xué)系趙敏趙敏數(shù)據(jù)庫數(shù)據(jù)庫8398003陳兵陳兵20男男數(shù)學(xué)系數(shù)學(xué)系趙敏趙敏離散數(shù)學(xué)離散數(shù)學(xué)873. 模式分解是關(guān)系規(guī)范化的主要方法模式分解是關(guān)系規(guī)范化的主要方法上述的關(guān)系模式上述的關(guān)系模式: : 教學(xué)教學(xué)( (學(xué)號，姓名，年齡，性別，系名，系主任，學(xué)號，姓名，年齡，性別，系名，系主任，課程名，成績課程名，成績).). 可以按可以按“一事一地一事一地”的原則分解成的原則分解成“學(xué)生學(xué)生”、“教教

6、學(xué)系學(xué)系”和和“選課選課”三個(gè)關(guān)系，其關(guān)系模式為：三個(gè)關(guān)系，其關(guān)系模式為： 學(xué)生學(xué)生( (學(xué)號，姓名，年齡，性別，系名稱學(xué)號，姓名，年齡，性別，系名稱) )； 教學(xué)系教學(xué)系( (系名，系主任系名，系主任) )； 選課選課( (學(xué)號，課程名，成績學(xué)號，課程名，成績).).7.1.2 函數(shù)依賴及其關(guān)系的范式函數(shù)依賴及其關(guān)系的范式1. 關(guān)系模式的簡化表示法關(guān)系模式的簡化表示法關(guān)系模式的完整表示是一個(gè)五元組：關(guān)系模式的完整表示是一個(gè)五元組： RU，D，Dom，F(xiàn).其中：其中：R為關(guān)系名；為關(guān)系名；U為關(guān)系的屬性集合；為關(guān)系的屬性集合；D為屬性集為屬性集U中中屬性的數(shù)據(jù)域；屬性的數(shù)據(jù)域；Dom為屬性到域

7、的映射；為屬性到域的映射；F為屬性集為屬性集U的的數(shù)據(jù)依賴集。數(shù)據(jù)依賴集。關(guān)系模式可以用三元組來為：關(guān)系模式可以用三元組來為： RU，F(xiàn).2. 函數(shù)依賴的概念函數(shù)依賴的概念1) 設(shè)設(shè)RU是屬性集是屬性集U上的關(guān)系模式，上的關(guān)系模式，X、Y是是U的子集。若對于的子集。若對于RU的任意一個(gè)可能的關(guān)系的任意一個(gè)可能的關(guān)系r，r中不可能存在兩個(gè)元組在中不可能存在兩個(gè)元組在X上上的屬性值相等，而的屬性值相等，而Y上的屬性值不等，則稱上的屬性值不等，則稱X函數(shù)確定函數(shù)確定Y函數(shù)，或函數(shù)，或Y函數(shù)依賴于函數(shù)依賴于X函數(shù)，記作函數(shù)，記作XY。例如，對于教學(xué)關(guān)系模式：教學(xué)例如，對于教學(xué)關(guān)系模式：教學(xué)U，F(xiàn)；U=

8、學(xué)號，姓名，年齡，性別，系名，系主任，課程名，成績學(xué)號，姓名，年齡，性別，系名，系主任，課程名，成績；F=學(xué)號學(xué)號姓名，學(xué)號姓名，學(xué)號年齡，學(xué)號年齡，學(xué)號性別，學(xué)號性別，學(xué)號系名，系名系名，系名系主系主任，任，(學(xué)號，課程名學(xué)號，課程名)成績成績. XY，但，但Y X，則稱，則稱XY是非平凡的函數(shù)依賴。若不特別是非平凡的函數(shù)依賴。若不特別聲明，總是討論非平凡的函數(shù)依賴。聲明，總是討論非平凡的函數(shù)依賴。 XY，但，但Y X，則稱，則稱XY是平凡的函數(shù)依賴。是平凡的函數(shù)依賴。 若若XY，則，則X叫做決定因素（叫做決定因素（Determinant），），Y叫做依賴叫做依賴因素（因素（Dependen

9、t）。）。 若若XY，YX，則記作，則記作XY。 若若Y不函數(shù)依賴于不函數(shù)依賴于X，則記作，則記作X Y。完全函數(shù)依賴、傳遞函數(shù)依賴完全函數(shù)依賴、傳遞函數(shù)依賴 2) 在在RU中，如果中，如果XY，并且對于，并且對于X的任何一個(gè)真子集的任何一個(gè)真子集X，都有，都有X Y，則稱，則稱Y對對X完全函數(shù)依賴，記作：完全函數(shù)依賴，記作：XY；若若XY，但，但Y不完全函數(shù)依賴于不完全函數(shù)依賴于X，則稱，則稱Y對對X部分函數(shù)依部分函數(shù)依賴，記作：賴，記作： XY。例如，在教學(xué)關(guān)系模式：例如，在教學(xué)關(guān)系模式：(學(xué)號，課程名學(xué)號，課程名)成績，成績，(學(xué)號，學(xué)號，課程名課程名)姓名姓名3) 在在RU中，如果中，

10、如果XY，(YX)，Y X，YZ，則，則稱稱Z對對X傳遞函數(shù)依賴。傳遞函數(shù)依賴記作傳遞函數(shù)依賴。傳遞函數(shù)依賴記作X Z。傳遞例如，在教學(xué)模式中，因?yàn)椋簩W(xué)號傳遞例如，在教學(xué)模式中，因?yàn)椋簩W(xué)號系名，系名系名，系名系主系主任；所以：學(xué)號任；所以：學(xué)號 系主任。系主任。 PFFP傳遞傳遞3. 1NF 3. 1NF 的定義、的定義、 2NF 2NF 的定義的定義n如果關(guān)系模式如果關(guān)系模式R，其所有的屬性均為簡單屬性，即每個(gè)屬性都，其所有的屬性均為簡單屬性，即每個(gè)屬性都是不可再分的，則稱是不可再分的，則稱R屬于第一范式，記作屬于第一范式，記作R 1NF。n 若若R 1NF，且每一個(gè)非主屬性完全依賴于碼，則

11、，且每一個(gè)非主屬性完全依賴于碼，則R 2NF。在教學(xué)中：屬性集在教學(xué)中：屬性集=學(xué)號，姓名，年齡，系名，系主任，課程名，成績學(xué)號，姓名，年齡，系名，系主任，課程名，成績.函數(shù)依賴集函數(shù)依賴集=學(xué)號學(xué)號姓名，學(xué)號姓名，學(xué)號年齡，學(xué)號年齡，學(xué)號性別，學(xué)號性別，學(xué)號系名，系名， 系名系名系主任，系主任，(學(xué)號，課程名學(xué)號，課程名)成績成績.主碼主碼=(學(xué)號，課程名學(xué)號，課程名). 非主屬性非主屬性=(姓名，年齡，系名，系主任，成績姓名，年齡，系名，系主任，成績)。非主屬性對碼的函數(shù)依賴：非主屬性對碼的函數(shù)依賴： (學(xué)號，課程名學(xué)號，課程名)姓名，姓名，(學(xué)號，課程名學(xué)號，課程名)年年齡，齡，(學(xué)號，

12、課程號學(xué)號，課程號)性別性別 ， (學(xué)號，課程名學(xué)號，課程名)系名，系名，(學(xué)號，課程名學(xué)號，課程名)系系主任；主任；(學(xué)號，課程名學(xué)號，課程名)成績成績.顯然，教學(xué)模式不服從顯然，教學(xué)模式不服從2NF，即：教學(xué)，即：教學(xué) 2NF。PPPPPn關(guān)系模式關(guān)系模式RU，F(xiàn)中若不存在這樣的碼中若不存在這樣的碼X、屬性組、屬性組Y及非及非主屬性主屬性Z(ZY)使得使得XY、Y X、YZ成立，則稱成立，則稱RU，F(xiàn) 3NF?？梢宰C明，若可以證明，若R 3NF，則每一個(gè)非主屬性既不部分函數(shù)依，則每一個(gè)非主屬性既不部分函數(shù)依賴于碼，也不傳遞函數(shù)依賴于碼。賴于碼，也不傳遞函數(shù)依賴于碼。 考查學(xué)生考查學(xué)生_系關(guān)

13、系，由于存在：學(xué)號系關(guān)系，由于存在：學(xué)號系名，系名系名，系名系主任。系主任。則：則： 學(xué)號學(xué)號 系主任。所以系主任。所以學(xué)生學(xué)生_系系 3NF。如果分解為：如果分解為： 學(xué)生學(xué)生(學(xué)號，姓名，年齡，性別，系名學(xué)號，姓名，年齡，性別，系名)； 教學(xué)系教學(xué)系(系名，系主任系名，系主任).顯然分解后的各子模式均屬于顯然分解后的各子模式均屬于3NF。傳遞n關(guān)系模式關(guān)系模式RU，F(xiàn) 1NF。若。若XY且且YX時(shí)時(shí)X必含有碼，必含有碼，則則RU，F(xiàn) BCNF。也就是說，關(guān)系模式也就是說，關(guān)系模式RU，F(xiàn)中，若每一個(gè)決定因素都包中，若每一個(gè)決定因素都包含碼，則含碼，則RU，F(xiàn) BCNF。由。由BCNF的定義

14、可以得到結(jié)的定義可以得到結(jié)論，一個(gè)滿足論，一個(gè)滿足BCNF的關(guān)系模式有：的關(guān)系模式有：1) 所有非主屬性對每一個(gè)碼都是完全函數(shù)依賴。所有非主屬性對每一個(gè)碼都是完全函數(shù)依賴。2) 所有的主屬性對每一個(gè)不包含它的碼，也是完全依賴。所有的主屬性對每一個(gè)不包含它的碼，也是完全依賴。3) 沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。 1) BCNF不僅強(qiáng)調(diào)其他屬性對碼的完全的直接不僅強(qiáng)調(diào)其他屬性對碼的完全的直接的依賴，而且強(qiáng)調(diào)主屬性對碼的完全的直接的依賴，而且強(qiáng)調(diào)主屬性對碼的完全的直接的依賴，它包括的依賴，它包括3NF，即，即R BCNF，則，則R一定一定

15、屬于屬于3NF。2) 3NF只強(qiáng)調(diào)非主屬性對碼的完全直接依賴，只強(qiáng)調(diào)非主屬性對碼的完全直接依賴，這樣就可能出現(xiàn)主屬性對碼的部分依賴和傳這樣就可能出現(xiàn)主屬性對碼的部分依賴和傳遞依賴。遞依賴。例如，關(guān)系模式例如，關(guān)系模式STJ(S，T，J)中，中，S表示學(xué)生，表示學(xué)生，T表示表示教師，教師，J表示課程。語義為：每一教師只能講授一門表示課程。語義為：每一教師只能講授一門課程，每門課程由若干教師講授；每個(gè)學(xué)生選修某課程，每門課程由若干教師講授；每個(gè)學(xué)生選修某門課程就對應(yīng)一個(gè)固定的教師。由語義可以得到門課程就對應(yīng)一個(gè)固定的教師。由語義可以得到STJ模式的函數(shù)依賴為：模式的函數(shù)依賴為： F=(S，J)T，

16、TJ顯然：顯然：(S，J)和和(T，S)都是關(guān)系的碼；關(guān)系的主屬性都是關(guān)系的碼；關(guān)系的主屬性集為集為S，T，J，非主屬性為，非主屬性為 （空集）。（空集）。由于由于STJ模式中無非主屬性，所以它屬于模式中無非主屬性，所以它屬于3NF；但因；但因?yàn)榇嬖跒榇嬖赥J，由于，由于T不是碼，故不是碼，故STJ BCNF。7.1.3 多值依賴及關(guān)系的第多值依賴及關(guān)系的第4范式范式1. 研究多值依賴的必要性研究多值依賴的必要性例如，給定一個(gè)關(guān)系模式例如，給定一個(gè)關(guān)系模式JPW(產(chǎn)品，零件，工序產(chǎn)品，零件，工序)，其中每種產(chǎn)品由多，其中每種產(chǎn)品由多種零件構(gòu)成，每個(gè)零件在裝配時(shí)需要多道工序。設(shè)產(chǎn)品電視機(jī)需要的零

17、種零件構(gòu)成，每個(gè)零件在裝配時(shí)需要多道工序。設(shè)產(chǎn)品電視機(jī)需要的零件和工序如圖所示。件和工序如圖所示。 顯像管顯像管電視機(jī)電視機(jī)開關(guān)開關(guān)電源電源焊接焊接調(diào)試調(diào)試測試測試裝配裝配調(diào)試調(diào)試焊接焊接調(diào)試調(diào)試2. 多值依賴的定義和性質(zhì)多值依賴的定義和性質(zhì)n設(shè)有關(guān)系模式設(shè)有關(guān)系模式RU，U是屬性集，是屬性集，X、Y是是U的子集。如果的子集。如果R的任一關(guān)系，對于的任一關(guān)系，對于X的一個(gè)確定值，都存在的一個(gè)確定值，都存在Y的一組值與之的一組值與之對應(yīng)，且對應(yīng)，且Y的這組值又與的這組值又與Z=U-X-Y中的屬性值不相關(guān)，此時(shí)中的屬性值不相關(guān)，此時(shí)稱稱Y多值依賴于多值依賴于X，或，或X多值決定多值決定Y，記為，記

18、為XY。多值依賴具有以下性質(zhì)：多值依賴具有以下性質(zhì)：1) 多值依賴具有對稱性。即若多值依賴具有對稱性。即若XY，則，則XZ，其中，其中Z=U-X-Y。2) 函數(shù)依賴可以看作是多值依賴的特殊情況。即若函數(shù)依賴可以看作是多值依賴的特殊情況。即若XY，則則XY。這是因?yàn)楫?dāng)。這是因?yàn)楫?dāng)XY時(shí)，對時(shí)，對X的每一個(gè)值的每一個(gè)值x，Y有一有一個(gè)確定的值個(gè)確定的值y與之對應(yīng)，所以與之對應(yīng)，所以XY。3) 在多值依賴中，若在多值依賴中，若XY且且Z=U-X-Y，則稱，則稱XY為為非平凡的多值依賴，否則稱為平凡的多值依賴。非平凡的多值依賴，否則稱為平凡的多值依賴。7.2.1 關(guān)系模式分解的算法基礎(chǔ)1. 函數(shù)依賴的

19、邏輯蘊(yùn)含函數(shù)依賴的邏輯蘊(yùn)含設(shè)設(shè)F是是RU函數(shù)依賴集，函數(shù)依賴集，X和和Y是屬性集是屬性集U的子的子集。如果從集。如果從F中的函數(shù)依賴能推出中的函數(shù)依賴能推出XY，則稱，則稱F邏邏輯蘊(yùn)含輯蘊(yùn)含XY，或稱，或稱XY是是F的邏輯蘊(yùn)含。的邏輯蘊(yùn)含。(1) Armstrong公理系統(tǒng)公理系統(tǒng):設(shè)設(shè)U為屬性集，為屬性集，F(xiàn)是是U上的函數(shù)依賴集，上的函數(shù)依賴集，于是有關(guān)系模式于是有關(guān)系模式RU，F(xiàn)。 1) 自反律：若自反律：若Y X U，則，則XY為為F所蘊(yùn)含。所蘊(yùn)含。2) 增廣律：若增廣律：若XY為為F所蘊(yùn)含，且所蘊(yùn)含，且Z U，則，則XZYZ為為F所所蘊(yùn)含。蘊(yùn)含。3) 傳遞律：若傳遞律：若XY及及YZ為

20、為F所蘊(yùn)含，則所蘊(yùn)含，則XZ為為F所蘊(yùn)含。所蘊(yùn)含。(2) Armstrong公理的三個(gè)推理公理的三個(gè)推理1) 合并規(guī)則：由合并規(guī)則：由XY，XZ，有，有XYZ。2) 偽傳遞規(guī)則：由偽傳遞規(guī)則：由XY，WYZ，有，有XWZ。3) 分解規(guī)則：由分解規(guī)則：由XY及及Z Y，有，有XZ。 (1) 函數(shù)依賴集閉包函數(shù)依賴集閉包F+和屬性集閉包和屬性集閉包XF+的定義的定義定義：在關(guān)系模式定義：在關(guān)系模式RU，F(xiàn)中，為中，為F所邏輯蘊(yùn)含所邏輯蘊(yùn)含的函數(shù)依賴的全體叫做的函數(shù)依賴的全體叫做F的閉包，記作的閉包，記作F+。定義：設(shè)有關(guān)系模式定義：設(shè)有關(guān)系模式RU，F(xiàn)，X是是U的子集，稱的子集，稱所有從所有從F推

21、出的函數(shù)依賴集推出的函數(shù)依賴集XAi中中Ai的屬性集為的屬性集為X的屬性閉包，記作的屬性閉包，記作XF+。即：。即： XF+= Ai | AiU，XAiF+ 1) 選選X作為閉包作為閉包XF+的初值的初值XF(0)。2) XF(i+1)是由是由XF(i)并上集合并上集合A所組成，其中所組成，其中A為為F中中存在的函數(shù)依賴存在的函數(shù)依賴YZ，而，而A Z，Y XF(i)。3) 重復(fù)步驟重復(fù)步驟2)。一旦發(fā)現(xiàn)。一旦發(fā)現(xiàn)XF(i)= XF(i+1)，則，則XF(i)為所為所求求XF+。n【例例】已知關(guān)系已知關(guān)系RU，F(xiàn)，其中，其中U=A，B，C，D，E，F(xiàn)=ABC，BD，CE，ECB，ACB，求，求

22、(AB)F+。設(shè)設(shè)X=AB XF(0)=AB XF(1)=ABCD XF(2)=ABCDE XF(3)= XF(2)=ABCDE (AB)F+=ABCDE=A，B，C，D，E4. 函數(shù)依賴集的最小化(1) 最小函數(shù)依賴集的定義最小函數(shù)依賴集的定義1) F中任一函數(shù)依賴的右部僅含有一個(gè)屬性。中任一函數(shù)依賴的右部僅含有一個(gè)屬性。2) F中不存在這樣的函數(shù)依賴中不存在這樣的函數(shù)依賴XA，使得，使得F與與F-XA等價(jià)。等價(jià)。3) F中不存在這樣的函數(shù)依賴中不存在這樣的函數(shù)依賴XA，X有真子集有真子集Z使使得得 F-XAZ-A與與F等價(jià)。等價(jià)。 1) 逐一檢查逐一檢查F中各函數(shù)依賴中各函數(shù)依賴XY，若，

23、若Y=A1A2Ak，k2，則用，則用XAj|j=1，2，k來取代來取代XY。2) 逐一檢查逐一檢查F中各函數(shù)依賴中各函數(shù)依賴XA，令，令G=F-XA，若若AXG+，則從，則從F中去掉此函數(shù)依賴。中去掉此函數(shù)依賴。3) 逐一取出逐一取出F中各函數(shù)依賴中各函數(shù)依賴XA，設(shè)，設(shè)X=B1B2Bm，逐一檢查逐一檢查Bi（i=1，2，m），如果），如果A(X-Bi)F+，則以則以X-Bi取代取代X?！纠吭O(shè)設(shè)F=ABC，BAC，CA，對，對F進(jìn)行極小化處理。進(jìn)行極小化處理。解：解：1) 把把F中的函數(shù)依賴轉(zhuǎn)換成右部都是單屬性的函數(shù)依賴，中的函數(shù)依賴轉(zhuǎn)換成右部都是單屬性的函數(shù)依賴，分解后的函數(shù)依賴集仍用分

24、解后的函數(shù)依賴集仍用F表示。表示。 F=AB，AC，BA，BC，CA2) 去掉去掉F中冗余的函數(shù)依賴。中冗余的函數(shù)依賴。判斷判斷AB。設(shè)：。設(shè)：G1= AC，BA，BC，CA，得：得：AG1+=AC B AG1+ AB不冗余不冗余判斷判斷AC。設(shè)：。設(shè)：G2= AB，BA，BC，CA，得：得：AG2+=ABC C AG2+ AC冗余冗余判斷判斷BA。設(shè)：。設(shè)：G3= AB，BC，CA，得：得：BG3+=BCA A BG3+ BA冗余冗余判斷判斷BC。設(shè)：。設(shè)：G4= AB，CA，得：得：BG4+=B C BG4+ BC不冗余不冗余判斷判斷CA。設(shè)：。設(shè)：G5= AB，BC ，得：得：CG5+=

25、C A CG5+ CA不冗余不冗余 Fm= AB，BC，CA【例例】求求F=ABC，AB，BA的最小函數(shù)依賴集的最小函數(shù)依賴集Fm。解：解：(1)去掉去掉F中冗余的函數(shù)依賴。中冗余的函數(shù)依賴。判斷判斷ABC是否冗余。是否冗余。 設(shè)：設(shè)：G1= AB，BA，得：，得：(AB)G1+=AB C (AB)G1+ ABC不冗余不冗余判斷判斷AB是否冗余。是否冗余。設(shè)：設(shè)：G2= ABC，BA，得：，得：AG2+=A B ABG2+ AB不冗余不冗余判斷判斷BA是否冗余。是否冗余。設(shè)：設(shè)：G3= ABC，AB ，得：，得：BG3+=B A BG3+ BA不冗余不冗余經(jīng)過檢驗(yàn)后的函數(shù)依賴集仍然為經(jīng)過檢驗(yàn)后

26、的函數(shù)依賴集仍然為 F=ABC，AB，BA?！纠壳笄驠=ABC，AB，BA的最小函數(shù)依賴集的最小函數(shù)依賴集Fm。解解 (2) 去掉各函數(shù)依賴左部冗余的屬性。去掉各函數(shù)依賴左部冗余的屬性。本題只需考慮本題只需考慮ABC的情況。的情況。方法方法1：在決定因素中去掉：在決定因素中去掉B，若，若C AF+，則以，則以AC代替代替ABC。求得：求得：AF+=ABC C AF+ 以以AC代替代替ABC故：故：Fm=AC，AB，BA方法方法2：在決定因素中去掉：在決定因素中去掉A，若，若C BF+，則以，則以BC代替代替ABC。求得：求得：BF+=ABC C BF+ 以以BC代替代替ABC故：故：Fm=

27、BC，AB，BA1. 關(guān)系分解的無損連接性關(guān)系分解的無損連接性 設(shè)關(guān)系模式設(shè)關(guān)系模式R，如果把它分解為兩個(gè)（或多個(gè)），如果把它分解為兩個(gè)（或多個(gè)）子模式子模式R1和和R2，相應(yīng)一個(gè)，相應(yīng)一個(gè)R關(guān)系中的數(shù)據(jù)就要被分關(guān)系中的數(shù)據(jù)就要被分成成R1 、R2兩個(gè)（或多個(gè)）子表。假如將這些子表自兩個(gè)（或多個(gè)）子表。假如將這些子表自然連接，即進(jìn)行然連接，即進(jìn)行R1 R2操作，得到的結(jié)果與原來關(guān)操作，得到的結(jié)果與原來關(guān)系中的數(shù)據(jù)一致，信息并沒有丟失，則稱該分解具系中的數(shù)據(jù)一致，信息并沒有丟失，則稱該分解具有無損連接性，否則如果有無損連接性，否則如果RR1 R2，則稱該分解不，則稱該分解不具有無損連接性。具有無

28、損連接性。2. 判斷分解成兩個(gè)關(guān)系具有無損連接性的方法判斷分解成兩個(gè)關(guān)系具有無損連接性的方法定理：定理：RU，F(xiàn)的一個(gè)分解的一個(gè)分解 = R1U1，F(xiàn)1，R2U2，F(xiàn)2具有無損連接性的充分必要條件是：具有無損連接性的充分必要條件是： U1U2U1-U2F+. 或或 U1U2U2-U1F+.3. 判斷分解保持函數(shù)依賴的方法判斷分解保持函數(shù)依賴的方法設(shè)設(shè)U，F(xiàn)的分解的分解 =R1U1，F(xiàn)1，R1U2，F(xiàn)2，RkUK，F(xiàn)K，若，若F+=(Fi)+，則稱分解，則稱分解 保持函數(shù)依賴保持函數(shù)依賴。 【例例】關(guān)系模式關(guān)系模式R=CITY，ST，ZIP，其中，其中CITY為城市，為城市，ST為街道，為街道，

29、ZIP為郵政編碼，為郵政編碼，F(xiàn)=(CITY，ST)ZIP，ZIPCITY。如果將。如果將R分解成分解成R1和和R2，R1=ST，ZIP，R2=CITY，ZIP，檢查分解是否具有無損連接和保持函數(shù)，檢查分解是否具有無損連接和保持函數(shù)依賴。依賴。解：解：1) 檢查無損連接性。檢查無損連接性。求得：求得：R1R2=ZIP；R2-R1=CITY. (ZIPCITY)F+. 分解具有無損連接性分解具有無損連接性2) 檢查分解是否保持函數(shù)依賴檢查分解是否保持函數(shù)依賴求得：求得：R1(F)=；R2(F)= ZIPCITY. R1(F)R2(F)= ZIPCITYF+. 該分解不保持函數(shù)依賴。該分解不保持函

30、數(shù)依賴。 7.2.4 關(guān)系模式的分解方法1. 將關(guān)系模式轉(zhuǎn)化為將關(guān)系模式轉(zhuǎn)化為3NF的保持函數(shù)依賴的分解的保持函數(shù)依賴的分解1) 對對RU，F(xiàn)中的中的F進(jìn)行極小化處理。處理后的函數(shù)依賴進(jìn)行極小化處理。處理后的函數(shù)依賴集仍用集仍用F表示。表示。2) 找出不再在找出不再在F中出現(xiàn)的屬性，把這樣的屬性構(gòu)成一個(gè)關(guān)系中出現(xiàn)的屬性，把這樣的屬性構(gòu)成一個(gè)關(guān)系模式，并把這些屬性從模式，并把這些屬性從U中去掉。中去掉。3) 若若F中有一個(gè)函數(shù)依賴涉及中有一個(gè)函數(shù)依賴涉及R全部屬性，則全部屬性，則R不能再分解。不能再分解。4) 如果如果F中含有中含有XA，則分解應(yīng)包含模式，則分解應(yīng)包含模式XA，如果，如果XA1，

31、XA2，XAn均屬于均屬于F，則分解應(yīng)包含模式，則分解應(yīng)包含模式XA1A2An?！纠吭O(shè)設(shè)RU，F(xiàn)，U=C，T，H，R，S，G，X，Y，Z，F(xiàn)=CT，CSG，HRC，HSR，THR，CX，將，將R分解為分解為3NF，且保持函數(shù)依賴。，且保持函數(shù)依賴。解：設(shè)該函數(shù)依賴集已經(jīng)是最小化的，則分解解：設(shè)該函數(shù)依賴集已經(jīng)是最小化的，則分解 為：為： =YZ，CTX，CSG，HRC，HSR，THR. 對于給定的關(guān)系模式對于給定的關(guān)系模式RU，F(xiàn)，將其轉(zhuǎn)換為，將其轉(zhuǎn)換為3NF，且既具有無損連接性又能保持函數(shù)依賴的分解算法且既具有無損連接性又能保持函數(shù)依賴的分解算法為：為：1) 設(shè)設(shè)X是是RU，F(xiàn)的碼，的碼

32、，RU，F(xiàn)先進(jìn)行保持先進(jìn)行保持函數(shù)依賴的分解，結(jié)果為函數(shù)依賴的分解，結(jié)果為 = R1U1，F(xiàn)1，R2U2，F(xiàn)2，RkUk，F(xiàn)k，令，令= R*X，F(xiàn)x。2) 若有某個(gè)若有某個(gè)Ui，X Ui，將，將R*X，F(xiàn)x從從中去掉，中去掉，就是所求的分解。就是所求的分解?！纠坑嘘P(guān)系模式有關(guān)系模式RU，F(xiàn)，U=C，T，H，R，S，G，F(xiàn)=CT，CSG，HRC，HSR，THR，將，將R分解為分解為3NF，且既具有無損連接性又，且既具有無損連接性又能保持函數(shù)依賴。能保持函數(shù)依賴。解：求得關(guān)系模式解：求得關(guān)系模式R的碼為的碼為HS，它的一個(gè)保持函數(shù)，它的一個(gè)保持函數(shù)依賴的依賴的3NF為：為： =CT，CSG，

33、HRC，HSR，THR. HS HSR = = CT，CSG，HRC，HSR，THR為滿足要為滿足要求的分解。求的分解。 1) 令令 = RU，F(xiàn)。2) 檢查檢查 中各關(guān)系模式是否均屬于中各關(guān)系模式是否均屬于BCNF。若是，。若是，則算法終止。則算法終止。 3) 假設(shè)假設(shè) 中中RiUi，F(xiàn)i不屬于不屬于BCNF，那么必定，那么必定有有XA Fi+，(A X)，且，且X非非Ri的碼。對的碼。對Ri進(jìn)行分進(jìn)行分解：解：=S1，S2，US1=XA，US2= Ui-A，以，以代替代替RiUi，F(xiàn)i，返回第，返回第2)步。步?！纠筷P(guān)系模式關(guān)系模式RU，F(xiàn)，U=CTHRSG，F(xiàn)= CT，HRC， HT

34、R，CSG，HSR，把，把R分解成具有無損連接的分解成具有無損連接的BCNF。解：令解：令 = CTHRSG1) 由于由于R的碼為的碼為HS，選擇，選擇CSG分解。得出：分解。得出： =S1，S2.其中：其中：S1=CSG， F1= CSG； S2=CTHRS， F2= CT，HRC，HTR，HSR. S2不服從不服從BCNF，需要繼續(xù)分解。，需要繼續(xù)分解。2) 對對S2分解。分解。S2的碼為的碼為HS，選擇，選擇CT分解。得：分解。得： = S1，S3，S4.其中：其中：S3=CT， F3= CT； S4=CHRS， F4= HRC，HSR. S4不服從不服從BCNF，還需要繼續(xù)分解。，還需

35、要繼續(xù)分解。3) 對對S4分解。碼為分解。碼為HS，選擇，選擇HRC分解：分解： = S1，S3，S5，S6.其中：其中：S5=HRC， F5= HRC； S6=HRS， F6=HSR.4) 最后的分解為：最后的分解為： =CSG，CT，HRC，HRS. 習(xí)題習(xí)題77.2答：答： 正確。因?yàn)閷W(xué)號能夠多值決定課程號，且除了學(xué)號和課程號外還有成績屬性，它不是平凡的多值依賴。7.3設(shè)有關(guān)系模式R（A，B，C），數(shù)據(jù)依賴集F=ABC，CA，R屬于第幾范式？為什么？7.3答：答： BCNF。由于A多值依賴于C，而C不是碼，故不服從4NF。但在函數(shù)依賴式中，C依賴于碼AB，故該模式服從BCNF。7.4答：

36、答： 正確。正確。正確。正確。正確。正確。正確。不正確。例如，(學(xué)號，課程號)成績，則不存在：學(xué)號成績，課程號成績。7.7答： 把查詢轉(zhuǎn)換成語法樹表示。 把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式。 選擇低層的存取路徑。 生成查詢計(jì)劃，選擇代價(jià)最小的查詢計(jì)劃。7.8試述查詢優(yōu)化的一般準(zhǔn)則。7.8答： 選擇運(yùn)算盡可能先做。 在執(zhí)行連接前對關(guān)系適當(dāng)?shù)仡A(yù)處理，即在連接屬性上建立索引和對關(guān)系進(jìn)行排序。 把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行。 把投影同其前或其后的雙目運(yùn)算結(jié)合起來。 把某些選擇同在它前面要執(zhí)行的笛卡兒積結(jié)合起來成為一個(gè)連接運(yùn)算。 找出公共子表達(dá)式。7.13答： 是BCNF。二元關(guān)系中或?yàn)槿a，或?yàn)橐粋€(gè)單屬性

37、碼候選碼。是BCNF。關(guān)系模式中只有一個(gè)候選碼。不是BCNF。因?yàn)槟Ｊ街写嬖诤蜻x碼為AD、BCD和BE，顯然C對AD是部分依賴。7.22答：1）關(guān)系STUDENT是1NF。2） 消除部分函數(shù)依賴S#,CNAMESNAME,SDEPT,MNAME將關(guān)系分解為：R1(S#,SNAME,SDEPT,MNAME)；R2(S#,CNAME,GRADE). 由于在關(guān)系R1中，存在非主屬性對候選碼的傳遞函數(shù)依賴（S#SDEPT，SDEPT MNAME），所以以上關(guān)系模式還不是BCNF。進(jìn)一步分解R1為：R11 (S#,SNAME,SDEPT)；R12 (SDEPT,MNAME).R11，R12都是3NF。 對于關(guān)系模式：R2(S#,CNAME,GRADE)，F(xiàn)2=（S#,CNAME）GRADE;R1