1、第6章 關(guān)系數(shù)據(jù)庫理論,6.1 關(guān)系數(shù)據(jù)模式的規(guī)范化理論 6.1.1 關(guān)系模式規(guī)范化的必要性 6.1.2 函數(shù)依賴及其關(guān)系的范式 6.1.3 多值依賴及關(guān)系的第四范式 6.2 關(guān)系模式的分解算法 6.2.1 關(guān)系模式分解的算法基礎(chǔ) 6.2.3 判定分解服從規(guī)范的方法 6.2.4 關(guān)系模式的分解方法 6.3 關(guān)系系統(tǒng)及查詢優(yōu)化技術(shù),概念回顧,概念模型與數(shù)據(jù)模型: 關(guān)系模型： 關(guān)系： 關(guān)系模式： 關(guān)系數(shù)據(jù)庫：,第6章 關(guān)系數(shù)據(jù)庫理論,關(guān)系數(shù)據(jù)庫的理論是以數(shù)學(xué)理論為基礎(chǔ)的，包括： 1、數(shù)據(jù)庫設(shè)計理論： 關(guān)系規(guī)范化理論 關(guān)系模式分解理論 2、數(shù)據(jù)操作理論： 關(guān)系數(shù)據(jù)的查詢理論(8個關(guān)系運算) 關(guān)系數(shù)據(jù)

2、的查詢優(yōu)化理論,6.1 關(guān)系數(shù)據(jù)模式的規(guī)范化理論,6.1.1關(guān)系模式規(guī)范化的必要性 數(shù)據(jù)庫的設(shè)計核心是數(shù)據(jù)模型的設(shè)計，數(shù)據(jù)模型最基本內(nèi)容就是數(shù)據(jù)結(jié)構(gòu)，關(guān)系數(shù)據(jù)模型的數(shù)據(jù)結(jié)構(gòu)是通過各關(guān)系模式來描述的，只有每個關(guān)系模式設(shè)計規(guī)范，才可能讓整個關(guān)系模型合理，建立起來的數(shù)據(jù)庫才合理、科學(xué)。什么樣的關(guān)系模式才比較規(guī)范的呢？首先它就要必須滿足一些基本要求：,1、關(guān)系模式應(yīng)滿足的基本要求 1）元組的每個分量必須是不可分的數(shù)據(jù)項。 2）數(shù)據(jù)庫中的數(shù)據(jù)冗余應(yīng)盡可能少。 3）關(guān)系數(shù)據(jù)庫不能因為數(shù)據(jù)更新操作而引起數(shù)據(jù)不一致問題。 4）當(dāng)執(zhí)行數(shù)據(jù)插入操作時，數(shù)據(jù)庫中的數(shù)據(jù)不能產(chǎn)生插入異?，F(xiàn)象。 5）數(shù)據(jù)庫中的數(shù)據(jù)不能在

3、執(zhí)行刪除操作時產(chǎn)生刪除異常問題。 6） 數(shù)據(jù)庫設(shè)計應(yīng)考慮查詢要求，數(shù)據(jù)組織應(yīng)合理。,2. 關(guān)系不規(guī)范可能出現(xiàn)的問題,分析下面關(guān)系存在的問題:,冗余,（1）數(shù)據(jù)冗余大：,（2）更新異常：,（3） 插入異常：,（4） 刪除異常：,上述關(guān)系模式是不合理的，或者說是不很規(guī)范的，不符合關(guān)系數(shù)據(jù)模式的規(guī)范化基本要求。,如某系換了系主任,如成立新系，但還沒招生,某系所有學(xué)生已畢業(yè)，但還沒招新生,上述關(guān)系雖然結(jié)構(gòu)較簡單，包含所需信息，但存在數(shù)據(jù)冗余大、 插入異常、 刪除異常、 更新異常等問題。 （1）數(shù)據(jù)冗余大：很顯然 （2） 插入異常：如成立新系，但還沒招生，但沒法錄入系相關(guān)信息（主碼為學(xué)號、課程號）。 （

4、3） 刪除異常：某系所有學(xué)生已畢業(yè)，但還沒招新生，該系相關(guān)信息刪除。 （4） 更新異常：如某系換了系主任，則該系所有學(xué)生記錄都要更改，遺漏一個將出現(xiàn)數(shù)據(jù)不一致 上述關(guān)系模式是不合理的，或者說是不很規(guī)范的，不符合關(guān)系數(shù)據(jù)模式的規(guī)范化理論要求。,3. 模式分解是關(guān)系規(guī)范化的主要方法 可以將一個不規(guī)范或較低規(guī)范的關(guān)系模式通過模式分解的方法轉(zhuǎn)換成若干較為規(guī)范的關(guān)系模式的集合，這種過程叫關(guān)系模式的規(guī)范化。 上述的關(guān)系模式: 教學(xué)(學(xué)號，姓名，年齡，性別，系名，系主任，課程名， 成績). 可以按“一事一地”的原則分解成“學(xué)生”、“教學(xué)系”和“選課”三個關(guān)系，其關(guān)系模式為： 學(xué)生(學(xué)號，姓名，年齡，性別，系

5、名稱)； 教學(xué)系(系名，系主任)； 選課(學(xué)號，課程名，成績).,教學(xué)(學(xué)號，姓名，年齡，性別，系名，系主任，課程名， 成績).,可以按“一事一地”的原則分解成“學(xué)生”、“教學(xué)系”和“選課”：,教學(xué)系：,學(xué)生：,選課：,1、關(guān)系模式的簡化表示法 對關(guān)系的描述稱為關(guān)系模式，關(guān)系模式的完整表示是一個五元組： RU，D，Dom，F(xiàn). 其中： R為關(guān)系名； U為關(guān)系的屬性集合； D為屬性集U中屬性的數(shù)據(jù)域（類型）； Dom為屬性到域的映射（長度） F為屬性集U的數(shù)據(jù)依賴集。,6.1.2 函數(shù)依賴及其關(guān)系的范式,如選課關(guān)系：,R：選課,U：學(xué)號、課程名、成績,D：字符型、整型,Dom： 學(xué)號：字符型，長

6、度5 課程名：字符型，長度20 成績：整型,F：（學(xué)號，課程名）成績，,數(shù)據(jù)依賴一般是指同一個關(guān)系中屬性間的相互依賴和相互制約，包括函數(shù)依賴、多值依賴和連接依賴。 數(shù)據(jù)依賴是關(guān)系模式規(guī)范化理論的基礎(chǔ)，其中： 函數(shù)依賴是1NF、2NF、3NF、BCNF的理論基礎(chǔ) 多值依賴是4NF的理論基礎(chǔ) 連接依賴是5NF的理論基礎(chǔ) 一般我們主要關(guān)心的是R、U、F，為簡化問題，一般關(guān)系模式可以用三元組來為： RU，F(xiàn),2、函數(shù)依賴的概念 1) 定義：設(shè)RU是屬性集U上的關(guān)系模式，X、Y是U的子集。若對于RU的任意一個可能的關(guān)系r，r中不可能存在兩個元組在X上的屬性值相等，而Y上的屬性值不等（X上值相同，則Y上值

7、必相同），則稱X函數(shù)確定Y函數(shù)，或Y函數(shù)依賴于X函數(shù)，記作XY。,如教學(xué)：,教學(xué)關(guān)系模式：RU，F(xiàn)： R= U= F=,教學(xué),學(xué)號，姓名，年齡，性別，系名，系主任，課程名，成績,學(xué)號姓名，學(xué)號年齡，學(xué)號性別，學(xué)號系名，系名系主任，(學(xué)號，課程名)成績,相關(guān)概念： XY，但Y X，則稱XY是非平凡的函數(shù)依賴。若不特別聲明，總是討論非平凡的函數(shù)依賴。 XY，但YX，則稱XY是平凡的函數(shù)依賴。 若XY，則X叫做決定因素（Determinant），Y叫做依賴因素（Dependent）。 若XY，YX，則記作XY。 若Y不函數(shù)依賴于X，則記作X Y。,(學(xué)號，課程名)成績,(學(xué)號，姓名)學(xué)號,2)完全函

8、數(shù)依賴 定義：在RU中，如果XY，并且對于X的任何一個真子集X，都有X Y，則稱Y對X完全函數(shù)依賴，記作：XY；若XY，但Y不完全函數(shù)依賴于X，則稱Y對X部分函數(shù)依賴，記作： XY。,P,F,部分：(學(xué)號，姓名)年齡、(學(xué)號，課程名)姓名,F,P,F,F,完全：學(xué)號姓名、學(xué)號年齡、(學(xué)號，課程名) 成績,P,結(jié)論： 決定因素是屬性組時才有部分依賴 如：學(xué)號姓名，學(xué)號年齡都是完全函數(shù)依賴 在規(guī)范程度不高的關(guān)系中其它屬性未必完全函數(shù)依賴于碼。,F,F,3)傳遞函數(shù)依賴 定義：在RU中，如果XY，(Y X)，Y X，YZ，則稱Z對X傳遞函數(shù)依賴。傳遞函數(shù)依賴記作X Z。 例如，在教學(xué)模式中： 因為：

9、學(xué)號系名，系名系主任； 所以：學(xué)號 系主任。,傳遞,傳遞,3、范式： 規(guī)范化的關(guān)系模式稱為范式（Normal Form）。由滿足最基本規(guī)范化條件的關(guān)系模式叫第一范式，第一范式的關(guān)系模式再滿足另外一些約束條件就產(chǎn)生了第二范式、第三范式、BC范式等，分別記為：1NF、2NF、3NF、BCNF、4NF、5NF。一個可用的關(guān)系最低要滿足3NF。,（1） 1NF的定義 定義：如果關(guān)系模式R，其所有的屬性均為簡單屬性，即每個屬性都是不可再分的，則稱R屬于第一范式，記作R1NF。 第一范式是最基本的范式，不滿足第一范式條件就不能稱為規(guī)范化關(guān)系，但僅滿足第一范式的條件還不夠，如教學(xué)關(guān)系： 教學(xué)(學(xué)號,姓名,年

10、齡,性別,系名,系主任,課程名,成績) 仍存在數(shù)據(jù)冗余度大、插入、刪除和更新可能產(chǎn)生異常的現(xiàn)象，需進(jìn)一步規(guī)范：,（2）. 2NF的定義 （1）定義： 若R1NF，且每一個非主屬性完全依賴于碼，則R2NF。,姓名,年齡,性別,系名,系主任,成績,學(xué)號,姓名,年齡,性別,系名,系主任,課程名,成績.,屬性集=,主碼=,(學(xué)號,課程名).,非主屬性=,例在教學(xué)模式中：,F=,顯然，教學(xué)模式不服從2NF，即：教學(xué)2NF。,非主屬性對碼的函數(shù)依賴：,（2）關(guān)系模式分解，轉(zhuǎn)化為第二范式： 學(xué)生_系(學(xué)號，姓名，年齡，性別，系名，系主任) 選課(學(xué)號,課程名，成績),顯然，學(xué)生_系2NF，選課2NF 。,學(xué)

11、生_系關(guān)系仍然存在冗余度大，更新、插入、刪除異常等問題,（3）. 3NF的定義 (1)定義:關(guān)系模式RU，F(xiàn)中若不存在這樣的碼X、屬性組Y及非主屬性Z(Z Y)使得XY、Y X、YZ成立，則稱RU，F(xiàn)3NF。 (2)含義: 每一個非主屬性不部分函數(shù)依賴于碼，所若R3NF,必有R2NF 證明:反證法 每一個非主屬性不傳遞函數(shù)依賴于碼(由定義知)。 換句話說：關(guān)系模式RU，F(xiàn)1NF ， 若XY且Y X （Y是非主屬性）時，X必含有碼，則稱RU，F(xiàn)3NF。 即非主屬性完全直接地依賴碼。,考查學(xué)生_系關(guān)系： 學(xué)生_系(學(xué)號,姓名,年齡,性別,系名,系主任) 碼= 主屬性= 非主屬性= 由于存在：學(xué)號系

12、名，系名系主任。 則： 學(xué)號 系主任。所以學(xué)生_系3NF。,傳遞,學(xué)號,學(xué)號,姓名，年齡，性別，系名，系主任,如果學(xué)生_系關(guān)系分解為： 學(xué)生(學(xué)號，姓名，年齡，性別，系名)； 教學(xué)系(系名，系主任) 選課(學(xué)號，課程名，成績) 顯然分解后的各子模式均屬于3NF。 結(jié)論：3NF是一個可用關(guān)系模應(yīng)滿足的最低范式,（4）. BCNF的定義 (1)定義:關(guān)系模式RU，F(xiàn)1NF。若XY且Y X時X必含有碼，則RU，F(xiàn)BCNF。 也就是說，關(guān)系模式RU，F(xiàn)中，若每一個決定因素都包含碼，則RU，F(xiàn)BCNF。由BCNF的定義可以得到結(jié)論。,3NF另一種定義：關(guān)系模式RU，F(xiàn) 1NF ，若XY且Y X （Y是非

13、主屬性）時，X必含有碼，則稱RU，F(xiàn)3NF。,與3NF定義的比較：,兩種范式定義不同點：BCNF要求每一個非平凡的函數(shù)依賴中，決定因素X都要含有碼，依賴因素Y包括是主屬性和非主屬性兩情況 ，而3NF只要求依賴因素Y是非主屬性時，決定因素X都要含有碼。,BCNF和3NF的比較總結(jié)：,1) 3NF只強(qiáng)調(diào)非主屬性對碼的完全直接依賴，這樣就可能出現(xiàn)主屬性對碼的部分依賴和傳遞依賴。 2) BCNF不僅強(qiáng)調(diào)非主屬性對碼的完全的直接的依賴，而且強(qiáng)調(diào)主屬性對碼的完全的直接的依賴，它包括3NF，即RBCNF，則R一定屬于3NF。 所以BCNF比3NF的要求又進(jìn)了一步，通常認(rèn)為BCNF是修正的第三范式，有時也稱為

14、擴(kuò)充的第三范式。 因此BCNF要求任何屬性都必須完全的直接的依賴于碼， 任何屬性不能完全函數(shù)依賴于非碼的屬性組。,例如，關(guān)系模式STJ(S，T，J)中，S表示學(xué)生，T表示教師，J表示課程。語義為：每一教師只能講授一門課程，每門課程由若干教師講授；每個學(xué)生選修某門課程就對應(yīng)一個固定的教師。,由語義可以得到STJ模式的函數(shù)依賴為： F=(S，J)T， (S，T)J， TJ 顯然： 碼= 主屬性集= 非主屬性= 由于STJ模式中無非主屬性，所以它屬于3NF； 結(jié)論：無非主屬性的關(guān)系都屬于3NF 因為存在TJ，由于T不是碼，故STJBCNF。,(S，J)和(S ，T),S，T，J,（空集）,可將它分解

15、為：ST（S，T）和TJ(T，J)，它們都BCNF,其它結(jié)論： 一個二目的關(guān)系屬于BCNF 只有一個碼的3NF關(guān)系屬于BCNF (Armstrong公理的增廣律可證明) 全碼關(guān)系屬于BCNF,6.1.3 多值依賴及關(guān)系的第四范式,1. 研究多值依賴的必要性例: 學(xué)校中某一門課程由多個教師講授，他們使用相同的一套參考書。 關(guān)系模式Teaching(C, T, B),用二維表表示Teaching,Teaching模式中存在的問題 (1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲多少次. (2)插入操作復(fù)雜：當(dāng)某一課程增加一名任課教師時，該課程有多少本參照書，就必須插入多少個元組. 例如物理課增

16、加一名教師劉關(guān)，需要插入三個元組： （物理，劉關(guān)，普通物理學(xué)） （物理，劉關(guān)，光學(xué)原理） （物理，劉關(guān)，物理習(xí)題集） (3) 刪除操作復(fù)雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個元組 (4) 修改操作復(fù)雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個元組,關(guān)系分析： Teaching具有唯一碼(C，T，B)， 即全碼 TeachingBCNF 產(chǎn)生問題原因:存在多值依賴,2. 多值依賴的定義和性質(zhì),定義：設(shè)有關(guān)系模式RU，U是屬性集，X、Y是U的子集, Z=U-X-Y 。如果R的任一關(guān)系r，對于一個確定值(x,z)，都存在Y的一組值與之對應(yīng)，且Y的這組

17、值僅x相關(guān),與z不相關(guān)，此時稱Y多值依賴于X，或X多值決定Y，記為XY。例 Teaching（C, T, B） 對于C的每一個值，T有一組值與之對應(yīng)，而不論B取何值,多值依賴具有以下性質(zhì)：1) 多值依賴具有對稱性。即若XY，則XZ，其中Z=U-X-Y。 2) 函數(shù)依賴可以看作是多值依賴的特殊情況。即若XY，則XY。這是因為當(dāng)XY時，對X的每一個值x，Y有一個確定的值y與之對應(yīng)，所以XY。3) 在多值依賴中，若XY且Z=U-X-Y，則稱XY為非平凡的多值依賴，否則稱為平凡的多值依賴。,3.多值依賴與函數(shù)依賴的區(qū)別 (1) 有效性:多值依賴的有效性與屬性集的范圍有關(guān) 函數(shù)依賴XY 的有效性只取決于

18、X，Y ，與其它屬性無關(guān)。 多值依賴的定義中不僅涉及屬性組 X和 Y，而且涉及U中其余屬性Z。 (2) 多值依賴沒有自反律 若函數(shù)依賴XY在R（U）上成立，則對于任何Y Y均有XY 成立 多值依賴XY若在R(U)上成立，不能斷言對于任何Y Y有XY 成立,4.第四范式（4NF） 定義:關(guān)系模式R(U，F(xiàn))1NF，如果對于R的每個非平凡多值依賴XY（Y X），X都含有碼，則R4NF。 如果R 4NF， 則R BCNF 允許是函數(shù)依賴（非平凡多值含碼就時函數(shù)依賴，函數(shù)依賴是多值依賴特例） 不允許有非平凡且非函數(shù)依賴的多值依賴 允許平凡多值依賴（ XY且Z=U-X-Y ）,例： Teaching(C

19、,T,B) 4NF 存在非平凡的多值依賴CT，且C不是碼 用分解法把Teaching分解為如下兩個關(guān)系模式： CT(C, T) 4NF CB(C, B) 4NF CT， CB是平凡多值依賴 若只考慮函數(shù)依賴，BCNF是最高范式，若考慮多值依賴，4NF是最高范式，或考慮連接依賴，5NF是最高范式.,6.1.4 連接依賴（JD）5NF,1、關(guān)系分解的無損連接,設(shè)U是關(guān)系模式R的屬性域，R1，R2R為R分解后的子關(guān)系，若滿足RR1 R2 R，則稱該分解具有無損連接性。,關(guān)系規(guī)范化主要手段是分解，分解后的子關(guān)系可通過自然連接進(jìn)行合并，連接依賴就是關(guān)于分解和自然連接的理論，第五范式就是關(guān)于消除子關(guān)系插入

20、和刪除異常的理論,2、連接依賴的定義：,設(shè)U是關(guān)系模式R的屬性域，x1，x2x為U的子集，滿足U x1 x2x，Ri(xi)是R分解的一個子關(guān)系，如果R= RR1 R2 R對于R的每個關(guān)系r都成立，那么稱R在該分解上具有n目的連接依賴。,因為R1分解為：,SP,PJ,JS,R1,R2=SP PJ JS 所以插入前該分解具有無損連接性,例：設(shè)R（SPJ）有一個分解（SP，PJ，JS）,如果R的關(guān)系中已有兩個元組（S1，P1，J2）和（S1，P2，J1）,現(xiàn)在要插入一個元組（S2，P1，J1）：,SP,PJ,JS,R2=SP PJ JS 所以插入后該分解不具有無損連接性,插入后正確結(jié)果R2,如果關(guān)

21、系模式R的每個JD均由R的候選鍵隱含，那么稱R是5NF。 含義：指子關(guān)系的自然連接的公共屬性中含有碼。,3、5NF的定義：, JD是現(xiàn)實世界中屬性間的一種抽象，是語義的體現(xiàn)。但較之FD，MVD不直觀，很難斷定是一個模式是否是5NF。, 但R5NF，則R4NF。, 現(xiàn)在還沒有完備的推理規(guī)則。, JD只有在關(guān)系的連接運算時才反映出來。,說明：,小結(jié)： 關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計的工具。 一個關(guān)系只要其分量都是不可分的數(shù)據(jù)項，它就是規(guī)范化的關(guān)系，但這只是最基本的規(guī)范化。 規(guī)范化程度可以有多個不同的級別，一個低一級范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個高一級范式的關(guān)系模式集合 關(guān)系模

22、式規(guī)范化的基本步驟 1NF 2NF 3NF BCNF 4NF 5NF,消除決定屬性集非碼的非平凡函數(shù)依賴,消除非主屬性對碼的部分函數(shù)依賴,消除非主屬性對碼的傳遞函數(shù)依賴,消除主屬性對碼的部分和傳遞函數(shù)依賴FD,消除非平凡且非函數(shù)依賴的多值依賴MD,取消不是由候選碼所蘊涵的連接依賴JD,6.2 關(guān)系模式的分解算法6.2.1 關(guān)系模式分解的算法基礎(chǔ),1. 函數(shù)依賴的邏輯蘊含設(shè)F是模式RU的函數(shù)依賴集，X和Y是屬性集U的子集。如果從F中的函數(shù)依賴能推出XY，則稱F邏輯蘊含XY，或稱XY是F的邏輯蘊含。,如：F=A B，B C,那么：A B、B C、A C為F所邏輯蘊含,2. Armstrong公理系

23、統(tǒng)(1) Armstrong公理系統(tǒng) 設(shè)U為屬性集，F(xiàn)是U上的函數(shù)依賴集，于是有關(guān)系模式RU，F(xiàn)。對RU，F(xiàn)來說，有以下的推理規(guī)則。 1) 自反律：若YXU，則XY為F所蘊含(平凡)。 2) 增廣律：若XY為F所蘊含，且ZU，則XZYZ為F所蘊含。 3) 傳遞律：若XY及YZ為F所蘊含，則XZ為F所蘊含。,(2) Armstrong公理的三個推理 1) 合并規(guī)則：由XY，XZ，有XYZ。 2) 偽傳遞規(guī)則：由XY，WYZ，有XWZ。 3) 分解規(guī)則：由XY及ZY，有XZ。 根據(jù)合并規(guī)則和分解規(guī)則，可得XA1 A2Ak成立的充分必要條件是XAi成立（i=l，2，k）,證明： XY， X X Y

24、（增廣律） Xz， XyYz（增廣律） XYz（傳遞律）,證明： XY， XWYW（增廣律） YWz， XWz（傳遞律）,(3) Armstrong公理的有效性和完備性 1)有效性:由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個函數(shù)依賴一定為F所蘊含的,即是正確的。 2)完備性：F所邏輯蘊含的每一個函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來. 建立公理系統(tǒng)體系目的：從已知的函數(shù)依賴推導(dǎo)出未知的函數(shù)依賴,3. 函數(shù)依賴集閉包F+和屬性集閉包XF+ (1)函數(shù)依賴集閉包F+和屬性集閉包XF+的定義 F+定義：在關(guān)系模式RU，F(xiàn)中，為F所邏輯蘊含的函數(shù)依賴的全體叫做F的閉包，記

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

26、)=ABCD XF(2)=ABCDE XF(3)= XF(2)=ABCDE (AB)F+=ABCDE=A，B，C，D，E,求XF+提供了判斷X Y是否為F所蘊含的方法，若Y XF+，則為F所蘊含 求XF+提供了判斷碼的方法,【例6-2】已知關(guān)系RU，F(xiàn)，其中U=A，B，C，D，E，F(xiàn)=AB，BCE，EDAB，求(ABC)F+。 設(shè)X=ABC XF(0)=ABC XF(1)=ABCE XF(2)=ABCE XF(2)= XF(1)=ABCE (ABC)F+=ABCE=A，B，C，E,4. 函數(shù)依賴集等價,如：F=A B，B C G=A B，B C, A C,因此：F與G等價,因為：A B、B C

27、 所以：A C,1)定義:設(shè)F和G 兩個函數(shù)依賴集,如果G+=F+，就說函數(shù)依賴集F與G等價（F覆蓋G，G覆蓋F）。,2)定理:F+ = G+ 的充分必要條件是 : F G+ (G覆蓋F)，G F+(F覆蓋G) 3)判斷F+ = G+ 的方法是根據(jù)2),具體做法: 判定F G+，只須逐一對F中的函數(shù)依賴XY，考察 Y 是否屬于XG+ 就行了(Y XG+, XY G+ ),若全是,則F G+ 判定G F+，只須逐一對G中的函數(shù)依賴XY，考察 Y 是否屬于XF+ 就行了(Y XF+, XY F+ ),若全是,則F G+,【例6-3】判斷 F=ABC，BAC，CA與G=AB，BC，CA是否等價,（1

28、）判定F G+,因為：（A）G+=ABC，所以：ABCG+ 因為：（B）G+=ABC，所以： BACG+ 顯然：CAG+ 因此： F G+,（2）判定G F+,因為：（A）F+=ABC，所以：ABF+ 因為：（B）F+=ABC，所以： BCF+ 顯然：CAF+ 因此： G F+,（3）結(jié)論：F+ = G+,5. 函數(shù)依賴集的最小化,(1) 最小函數(shù)依賴集的定義 如果函數(shù)依賴集F滿足下列條件，則稱F為一個極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。1) F中任一函數(shù)依賴的右部僅含有一個屬性(右邊無多余的屬性)。2) F中不存在這樣的函數(shù)依賴XA，使得F與F-XA等價(無多余的函數(shù)依賴) 。3)

29、F中不存在這樣的函數(shù)依賴XA，X有真子集Z使得F-XAZ A與F等價(左邊無多余的屬性) 。,(2) 最小函數(shù)依賴集的求法 逐一檢查F中各函數(shù)依賴XY，若Y=A1A2Ak，k2，則用XAj|j=1，2，k來取代XY (保證右邊無多余的屬性) 。 逐一檢查F中各函數(shù)依賴XA，令G=F-XA，若AXG+，則從F中去掉此函數(shù)依賴(保證無多余的函數(shù)依賴) 。 逐一取出F中各函數(shù)依賴XA，設(shè)X=B1B2Bm，逐一檢查Bi（i=1，2，m），如果A(X-Bi)F+，則以X-Bi取代X。,【例6-4】設(shè)F=ABC，BAC，CA，對F進(jìn)行極小化處理。 解：1) 根據(jù)分解規(guī)則把F中的函數(shù)依賴轉(zhuǎn)換成右部都是單屬性

30、的函數(shù)依賴集合，分解后的函數(shù)依賴集仍用F表示。 F=AB，AC，BA，BC，CA2) 去掉F中冗余的函數(shù)依賴。判斷AB。設(shè)：G1= AC,BA,BC,CA 得：AG1+=AC BAG1+ AB不冗余判斷AC。設(shè)：G2= AB,BA,BC,CA 得：AG2+=ABC CAG2+ AC冗余,判斷BA。設(shè)：G3= AB，BC，CA，得：BG3+=BCA ABG3+ BA冗余判斷BC。設(shè)：G4= AB，CA，得：BG4+=B CBG4+ BC不冗余判斷CA。設(shè)：G5= AB，BC ， 得：CG5+=C ACG5+ CA不冗余 Fm= AB，BC，CA (3) 去掉各函數(shù)依賴左部冗余的屬性: 左邊都是單

31、屬性,無多余的屬性.,【例6-5】求F=ABC，AB，BA的最小函數(shù)依賴集Fm。 (1)右邊已全是單屬性,無需再分解 (2)去掉F中冗余的函數(shù)依賴。判斷ABC是否冗余。設(shè)：G1= AB，BA，得：(AB)G1+=AB C (AB)G1+ ABC不冗余判斷AB是否冗余。設(shè)：G2= ABC，BA，得：AG2+=A BABG2+ AB不冗余判斷BA是否冗余。設(shè)：G3= ABC，AB ，得：BG3+=B ABG3+ BA不冗余經(jīng)過檢驗后的函數(shù)依賴集仍然為F=ABC，AB，BA。,(3) 去掉各函數(shù)依賴左部冗余的屬性。本題只需考慮ABC的情況。方法1：在決定因素中去掉B，若CAF+，則以AC代替ABC。

32、求得：AF+=ABC CAF+ 以AC代替ABC故：Fm=AC，AB，BA方法2：在決定因素中去掉A，若CBF+，則以BC代替ABC。求得：BF+=ABC CBF+ 以BC代替ABC故：Fm=BC，AB，BA,6.2.3 判定分解服從規(guī)范的方法 定義: 設(shè)= R1，R2，Rn， U=U1U2Un，且不存在 Ui Uj，則稱是關(guān)系模式R的一個分解, m(r) Ri(r)， m(r)是r在中各關(guān)系的投影的連接。 判定分解服從規(guī)范考慮兩個因素： 具有無損連接性 保持函數(shù)依賴 1. 關(guān)系分解的無損連接性 （1）定義： R1，R2 Rk是R上的一個分解，若對于R的任一關(guān)系r，均有r m(r)成立，則具有

33、無損連接性 。,例6.6 設(shè)有關(guān)系模式R(ABC)，分解成 =AB,AC (1) (a)是R上的一個關(guān)系r，(b)和(c)是r在模式AB和AC上的投影r1和r2。,顯示對于此關(guān)系r,有r m(r),a,b :AB(r),c:AC(r),d:m(r),顯示對于此關(guān)系r,有r m(r)，,（2）同樣的模式分解，對于另外一個關(guān)系r：,a,不具有無損連接性 。,b =AB(r),c =AC(r),2、判斷分解具有無損連接性的方法： （1）一般方法： 構(gòu)造一張k行n列的表格，每列對應(yīng)一個屬性Aj(1jn)，每行對應(yīng)一個模式Ri (1ik)。如果Aj在Ri中，那么在表格的第i行第j列處填上符號aj，否則填

34、上bij。 把表格看成模式R的一個關(guān)系，反復(fù)檢查F中每個FD在表格中是否成立，若不成立，則修改表格中的值。修改方法如下：對于F中一個FD XY，如果表格中有兩行在X值上相等,在Y值上不相等,那么把這兩行在Y值上也改成相等的值。 *如果Y值中有一個是aj，那么另一個也改成aj； * 如果沒有aj，那么用其中一個bij替換另一個值（盡量把下標(biāo)i改成較小的數(shù)）。 一直到表格不能修改為止。（這個過程稱為chase過程） 若修改的最后一張表格中有一行是全a，即a1a2an，那么稱相對于F是無損分解，否則稱損失分解。,例6.7:設(shè)關(guān)系模式R(ABCD)，R分解成= AB, BC, CD.如果R上成立的函數(shù)

35、依賴集F1= BA,CD，那么相對于F1是否為無損分解？,(a) 初始表格,(b) 修改后的表格,b21,a2,a2,a3,a3,b24,a1,a4,a1,a4,（2）判斷分解成兩個關(guān)系且具有無損連接的方法： 定理：RU，F(xiàn)的一個分解= R1U1，F(xiàn)1，R2U2，F(xiàn)2具有無損連接性的充分必要條件是： U1U2U1-U2F+. 或 U1U2U2-U1F+.,初始化,例如： 設(shè)R=ABC， R1=AB，R2=AC， 則 U1U2=A， U1-U2=B，U2-U1=C,U1U2U1-U2 (AB),U1U2U2-U1 (AC),3. 判斷分解保持函數(shù)依賴的方法 （1）定義： 設(shè)F是屬性集U上的FD集

36、，Z是U的子集，F(xiàn)在Z上的投影用Z（F）表示，定義為： Z（F）= XY | XYF+，且XY Z 例：設(shè)：F= AB，BC ，C D，Z=ABD 求Z（F） 求得：Z（F）,=AB，BD,（2）定義：設(shè)U，F(xiàn)的分解=R1U1，F(xiàn)1，R2U2，F(xiàn)2，RkUK，F(xiàn)K，若F+=(Fi)+，則稱分解保持函數(shù)依賴。 （3）判斷一個分解是否保持FD，其方法是： 1）逐個求Fi= Ri (F) 2）求G= Fi= Ri (F) 3）判斷是否有: F+=G+ 判定G F+：顯然，不需判斷 判定F G+：,逐步驗證F中每個FD是否被G邏輯蘊涵,【例6-8】關(guān)系模式R=CITY，ST，ZIP，其中CITY為城市

37、，ST為街道，ZIP為郵政編碼，F(xiàn)=(CITY，ST)ZIP，ZIPCITY。如果將R分解成R1和R2，R1=ST，ZIP，R2=CITY，ZIP，檢查分解是否具有無損連接和保持函數(shù)依賴。 解：1) 檢查無損連接性。 求得：R1R2=ZIP；R2-R1=CITY. (ZIPCITY)F+. 分解具有無損連接性 2) 檢查分解是否保持函數(shù)依賴 求得：F1=R1(F)=；F2=R2(F)= ZIPCITY. G=R1(F)R2(F)= ZIPCITY (CITY，ST)ZIP （ ZIPCITY ）+ 該分解不保持函數(shù)依賴。,【例6-9】設(shè)關(guān)系模式R(WNO,WS,WG)的屬性分別表示職工的工號、

38、工資級別和工資數(shù)目。如果規(guī)定每個職工只有一個工資級別，并且一個工資級別只有一個工資數(shù)目，則R上的FD有：F= WNOWS，WSWG 如果R分解成 =R1,R2，其中R1=WNO,WS，R2=WNO, WG，則這個分解是無損連接分解嗎？是否保持FD嗎？ 解：1) 檢查無損連接性。 求得：R1R2=WNO；R1-R2=WS. (WNOWS)F+. 分解具有無損連接性 2) 檢查分解是否保持函數(shù)依賴 求得：F1=R1(F)= WNOWS ； F2=R2(F)= WNOWG. G=F1F2=WNOWS， WNOWG WSWG G + 該分解不保持函數(shù)依賴。,【例6-10】設(shè)關(guān)系模式R（ABC），= A

39、B，AC 是R的一個分解。試分析分別在F1= AB ，F(xiàn)2= AC，BC ，F(xiàn)3= BA ，F(xiàn)4= CB，BA 情況下，是否具有無損分解和保持FD的分解特性。 相對于F1= AB ，分解是無損分解且保持FD的分解。 相對于F2= AC，BC ，分解是無損分解，但不保持FD。因為BC丟失了。 相對于F3= BA ，分解是損失分解但保持FD集的分解。 相對于F4= CB，BA ，分解是損失分解且不保持FD集的分解(丟失了CB) 因此是一關(guān)系模式分解是否為無損分解和是否保持函數(shù)依賴與具體的函數(shù)依賴集有關(guān),無損連接反映了模式分解的數(shù)據(jù)等價原則。 依賴等價保證了分解后的模式與原有的模式在數(shù)據(jù)語義上的一致

40、性。,6.2.4 關(guān)系模式的分解方法,1. 將關(guān)系模式轉(zhuǎn)化為3NF的保持函數(shù)依賴的分解1) 對RU，F(xiàn)中的F進(jìn)行極小化處理。處理后的函數(shù)依賴集仍用F表示。2) 找出不再在F中出現(xiàn)的屬性，把這樣的屬性構(gòu)成一個關(guān)系模式，并把這些屬性從U中去掉。3) 如果F中有一個函數(shù)依賴涉及R的全部屬性（碼含有n-1屬性），則R不能再分解(已是3NF)。4) 如果F中含有XA，則分解應(yīng)包含模式XA，如果XA1，XA2，XAn均屬于F，則分解應(yīng)包含模式XA1A2An（保證非主屬性Ai對碼X的直接依賴,且保證函數(shù)依賴沒有丟失）。,【例6-11】設(shè)關(guān)系模式RU，F(xiàn)， U=C，T，H，R，S，G，X，Y，Z， F=CT，

41、CSG，HRC，HSR，THR，CX， 將R分解為3NF，且保持函數(shù)依賴。 解：該函數(shù)依賴集已經(jīng)是最小化的，則分解為： R1=YZ，F(xiàn)1= R2= CTX ，F(xiàn)2= CT，CX R3= CSG ，F(xiàn)3= CSG R4= HRC ，F(xiàn)4= HRC R5= HSR ，F(xiàn)5= HSR R6= THR ，F(xiàn)6= THR =YZ，CTX，CSG，HRC，HSR，THR.,2. 將關(guān)系轉(zhuǎn)化為3NF、且既具有無損連接性又能保持函數(shù)依賴的分解 對于給定的關(guān)系模式RU，F(xiàn)，將其轉(zhuǎn)換為3NF，且既具有無損連接性又能保持函數(shù)依賴的分解算法為：1) RU，F(xiàn)先進(jìn)行保持函數(shù)依賴的分解，結(jié)果為= R1U1，F(xiàn)1，R2U2

42、，F(xiàn)2，RkUk，F(xiàn)k。2) X設(shè)是RU，F(xiàn)的碼，若有某個Ui，X Ui，令=，否則令=R*X，F(xiàn)x ，就是所求的分解。,【例6-12】有關(guān)系模式RU，F(xiàn)，U=C，T，H，R，S，G，F(xiàn)=CT，CSG，HRC，HSR，THR，將R分解為3NF，且既具有無損連接性又能保持函數(shù)依賴。解： (1)它的一個保持函數(shù)依賴的3NF為： =CT，CSG，HRC，HSR，THR. (2)求得關(guān)系模式R的碼為HS HSHSR = CT，CSG，HRC，HSR，THR為滿足要求的分解。,3. 將關(guān)系模式轉(zhuǎn)換為BCNF的無損連接的分解,1) 令= RU，F(xiàn)。 2) 檢查中各關(guān)系模式是否均屬于BCNF。若是，則算法終

43、止。 3) 假設(shè)中RiUi，F(xiàn)i不屬于BCNF，那么必定有XAFi+，(AX)，且X非Ri的碼。對Ri進(jìn)行分解：=S1，S2，US1=XA（s1是屬于BCNF ，且保持無損連接），US2= Ui-A，以代替RiUi，F(xiàn)i，返回第2)步。 S1 S2=X，S1-S2=A，X A 每次分解都是無損分解，但不能保證保持函數(shù)依賴,【例】關(guān)系模式RU，F(xiàn)，U=CTHRSG，F(xiàn)= CT，HRC， HTR，CSG，HSR，把R分解成具有無損連接的BCNF。 解：令= CTHRSG 由于R的碼為HS，選擇CSG分解。 得出：=S1，S2. 其中：S1=CSG， F1= CSG； S2=CTHRS， F2= C

44、T，HRC，HTR，HSR S2不服從BCNF，需要繼續(xù)分解。 2) 對S2分解。S2的碼為HS，選擇CT分解。 得出：= S1，S3，S4. 其中：S3=CT， F3= CT； S4=CHRS， F4= HRC， HCR ，HSR， S4不服從BCNF，還需要繼續(xù)分解。,3) 對S4分解。碼為HS，選擇HRC分解： = S1，S3，S5，S6. 其中：S5=HRC， F5= HRC； S6=HRS， F6=HSR. 4) 最后的分解為：=CSG，CT，HRC，HRS. 可驗證此分解僅具有無損連接性，而不保持函數(shù)依賴。,【例】設(shè)關(guān)系模式R(U,F),U=學(xué)號,課程號,成績,教師名,教師所在系，

45、F=(學(xué)號,課程號) 成績,課程號教師名,教師名教師所在系,將其分解為具有無損連接的BCNF 解：令= 學(xué)號,課程號,成績,教師名,教師所在系 1) 由于R的碼為（學(xué)號,課程號 ），選擇教師名教師所在系分解。 得出：=S1，S2. 其中：S1=教師名,教師所在系 ， F1=教師名教師所在系； S2= 學(xué)號,課程號,成績,教師名 ， F2=(學(xué)號,課程號) 成績,課程號教師名. S2不服從BCNF，需要繼續(xù)分解。2) 對S2分解。S2的碼為（學(xué)號,課程號 ） ，選擇課程號教師名分解。 得出：= S1，S3，S4. 其中：S3= 課程號，教師名 ， F3=課程號教師名； S4= 學(xué)號,課程號,成績

46、， F4=(學(xué)號,課程號) 成績. S1，S3，S4服從BCNF，無需繼續(xù)分解。3) 最后的分解為： =（教師名,教師所在系）,（課程號,教師名）,（學(xué)號,課程號,成績） 可驗證此分解不僅具有無損連接性，而且還保持函數(shù)依賴。,3個結(jié)論 若分解保持函數(shù)依賴，分解一定可以達(dá)到3NF,但不一定能達(dá)到BCNF 若分解具有無損連接性，分解一定可以達(dá)到BCNF 若分解既保持依賴又具有無損連接性，分解一定可以達(dá)到3NF,但不一定能夠達(dá)到BCNF,6.3關(guān)系系統(tǒng)與查詢優(yōu)化技術(shù),6.3.1關(guān)系系統(tǒng)的定義與分類: 1.關(guān)系系統(tǒng)的定義: 能夠在一定程度上支持關(guān)系模型的數(shù)據(jù)庫管理系統(tǒng)是關(guān)系系統(tǒng)。 由于關(guān)系模型中并非每

47、一部分(數(shù)據(jù)結(jié)構(gòu)、操作與完整性約束）都是同等重要的，所以并不苛求一個實際的關(guān)系系統(tǒng)必須完全支持關(guān)系模型。一個數(shù)據(jù)庫管理系統(tǒng)可定義為關(guān)系系統(tǒng)，當(dāng)且僅當(dāng)它至少支持： （1）支持關(guān)系數(shù)據(jù)庫（即關(guān)系數(shù)據(jù)結(jié)構(gòu)）， 系統(tǒng)中只有表這種結(jié)構(gòu) （2） 支持選擇、投影和（自然）連接運算 對這些運算不要求用戶定義任何物理存取路徑。 上面兩條是對關(guān)系系統(tǒng)的最低要求。,說明： 不支持關(guān)系數(shù)據(jù)結(jié)構(gòu)的系統(tǒng)顯然不能稱為關(guān)系系統(tǒng)。 僅支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，但沒有選擇、投影和連接運算功能的系統(tǒng)仍不能算作關(guān)系系統(tǒng)。 原因：不能提高用戶的生產(chǎn)率 支持選擇、投影和連接運算，但要求定義物理存取路徑，這種系統(tǒng)也不能算作真正的關(guān)系系統(tǒng) 原因：就

48、降低或喪失了數(shù)據(jù)的物理獨立性 選擇、投影、連接運算是最有用的運算，它能解決大多數(shù)實際問題，所以一關(guān)系系統(tǒng)不一定要求支持關(guān)系代數(shù)的全部運算。,2 關(guān)系系統(tǒng)的分類 分類依據(jù)：支持關(guān)系模型的程度 表式系統(tǒng)：支持關(guān)系數(shù)據(jù)結(jié)構(gòu)(即表)，不支持集合級的操作，不能算是關(guān)系系統(tǒng)。 (最小)關(guān)系系統(tǒng)：支持：關(guān)系數(shù)據(jù)結(jié)構(gòu)，支持關(guān)系的選擇、投影、連接關(guān)系操作 關(guān)系完備的系統(tǒng)：支持：關(guān)系數(shù)據(jù)結(jié)構(gòu)，支持所有的關(guān)系代數(shù)操作。 全關(guān)系系統(tǒng)：支持：關(guān)系模型的所有特征（關(guān)系數(shù)據(jù)結(jié)構(gòu)、關(guān)系操作和三個完整性）， 特別是:數(shù)據(jù)結(jié)構(gòu)中域的概念。 現(xiàn)在的關(guān)系系統(tǒng)一般接近于全關(guān)系系統(tǒng)。,6.3.2 關(guān)系系統(tǒng)的查詢優(yōu)化,1 查詢優(yōu)化概述 (

49、1)查詢優(yōu)化的必要性: 查詢優(yōu)化極大地影響RDBMS的性能。 (2)查詢優(yōu)化的可能性 關(guān)系數(shù)據(jù)語言的級別很高，使DBMS可以從關(guān)系表達(dá)式中分析查詢語義。 (3)由DBMS進(jìn)行查詢優(yōu)化的好處 用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率 系統(tǒng)可以比用戶程序的優(yōu)化做得更好,因為: 1) 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息，而用戶程序則難以獲得這些信息,2)如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了，系統(tǒng)可以自動對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計劃。 在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實際應(yīng)用中往往是不太可能的。 3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃，而程序員一般只能考慮有限的幾種可能性。 4)優(yōu)

50、化器中包括了很多復(fù)雜的優(yōu)化技術(shù),（4）查詢優(yōu)化的總目標(biāo) 選擇有效策略，求得給定關(guān)系表達(dá)式的值 （5）代價模型 集中式數(shù)據(jù)庫 單用戶系統(tǒng) 總代價 = I/O代價 + CPU代價 多用戶系統(tǒng) 總代價 = I/O代價 + CPU代價 + 內(nèi)存代價 分布式數(shù)據(jù)庫 總代價 = I/O代價 + CPU代價+ 內(nèi)存代價 + 通信代價,2 查詢優(yōu)化的必要性,例：求選修了課程2的學(xué)生姓名 SELECT 學(xué)生.姓名 FROM 學(xué)生, 選課 WHERE 學(xué)生.學(xué)號=選課.學(xué)AND 選課.課程號=C2 假設(shè)1：外存： 學(xué)生:1000條,選課:10000條, 選修C2號課程:50條 假設(shè)2：一個內(nèi)存塊裝元組:10個學(xué)生

51、, 或100個選課, 內(nèi)存中一次可以存放: 5塊學(xué)生元組, 1塊選課元組和若干塊連接結(jié)果元組 假設(shè)3：讀寫速度：20塊/秒 假設(shè)4：連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法,執(zhí)行策略1,1 姓名(學(xué)生.學(xué)號=選課.學(xué)號 選課.課程號=C2 (學(xué)生選課) 學(xué)生選課 讀取總塊數(shù)= 讀學(xué)生表塊數(shù) + 讀選課表遍數(shù) *每遍塊數(shù) =1000/10+(1000/(105) (10000/100) =100+20100=2100 讀數(shù)據(jù)時間=2100/20=105秒,中間結(jié)果大小 = 1000*10000 = 107 (1千萬條元組) 寫中間結(jié)果時間 = 10000000/10/20 = 50000秒 讀數(shù)據(jù)時間

52、= 50000秒 總時間 =1055000050000秒 = 100105秒 = 27.8小時,執(zhí)行策略2,2 姓名(選課.課程號= C2 (學(xué)生 選課) 讀取總塊數(shù)= 2100塊 讀數(shù)據(jù)時間=2100/20=105秒 中間結(jié)果大小=10000 （減少1000倍） 寫中間結(jié)果時間=10000/10/20=50秒 讀數(shù)據(jù)時間=50秒 總時間1055050秒205秒=3.4分,執(zhí)行策略3,3. 3 姓名(學(xué)生 選課.課程號= C2 (選課) 讀選課表總塊數(shù)= 10000/100=100塊 讀數(shù)據(jù)時間=100/20=5秒 中間結(jié)果大小=50條 不必寫入外存 讀學(xué)生表總塊數(shù)= 1000/10=100塊

53、 讀數(shù)據(jù)時間=100/20=5秒 總時間55秒10秒,執(zhí)行策略4,4. 4 姓名(學(xué)生 選課.課程號=C2 (選課) 假設(shè)選課表在課程號上有索引，學(xué)生表在學(xué)號上有索引 讀選課表索引:少 讀選課表總塊數(shù)= 50/1001塊 讀數(shù)據(jù)時間=1/20 中間結(jié)果大小=50條 不必寫入外存, 讀學(xué)生表索引:少 讀學(xué)生表總塊數(shù)= 50/10=5塊 讀數(shù)據(jù)時間 =5/20 總時間10秒,3 查詢優(yōu)化的一般準(zhǔn)則,1）選擇運算應(yīng)盡可能先做 目的：減小中間關(guān)系,最重要、最基本的一條 2）在執(zhí)行連接操作前對關(guān)系適當(dāng)進(jìn)行預(yù)處理 按連接屬性排序 在連接屬性上建立索引 3）投影運算和選擇運算同時做：掃描關(guān)系同時，完成所有運

54、算。 目的：避免重復(fù)掃描關(guān)系 4）將投影運算與其前面或后面的雙目運算結(jié)合 目的：減少掃描關(guān)系的遍數(shù),5）某些選擇運算在其前面執(zhí)行的笛卡爾積 = 連接運算 例：學(xué)生.學(xué)號=選課.學(xué)號 (學(xué)生選課) 學(xué)生 選課 6）提取公共子表達(dá)式 公共表達(dá)式的結(jié)果不是一個很大的關(guān)系，且讀此關(guān)系的時間比計算機(jī)表達(dá)式的時間少，則可先提取公共表達(dá)式。,4 關(guān)系代數(shù)等價變換規(guī)則,設(shè)E1、E2等是關(guān)系代數(shù)表達(dá)式，F(xiàn)是條件表達(dá)式 （l） 連接、笛卡爾積交換律 E1 E2 E2E1 E1 E2E2 E1 E1 F E2E2 F E1 （2） 連接、笛卡爾積的結(jié)合律 (E1E2) E3 E1 (E2E3) (E1 E2) E3

55、 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) F F F F,（3） 投影的串接定律 A1,A2, ,An( B1,B2, ,Bm(E) A1,A2, ,An (E) 假設(shè)： 1)E是關(guān)系代數(shù)表達(dá)式 2)Ai(i=1，2，n), Bj(j=l，2，m)是屬性名 3)A1, A2, , An構(gòu)成Bl，B2，Bm的子集 （4） 選擇的串接定律 F1 （ F2（E） F1 F2(E) 選擇的串接律說明 選擇條件可以合并 這樣一次就可檢查全部條件。,（5） 選擇與投影的交換律 1)假設(shè): 選擇條件F只涉及屬性A1，An F (A1,A2, ,An(E) A1,A2, ,An(F(E) 2)假設(shè): F中有不屬于A1, ,An的屬性B1,Bm A1,A2, ,An ( F (E) A1,A2, ,An(F (A1,A2, ,An,B1,B2, ,Bm(E),（6） 選擇與笛卡爾積的交換律 1) 假設(shè)：F中涉及的屬性都是E1中的屬性 F (E1E2)F (E1)E2 2) 假設(shè)：F=F1F2，并且F1只涉及E1中的屬性，