第7章關系數據庫理論

7.1關系數據模式的標準化理論

7.1.1關系模式標準化的必要性7.1.2函數依賴及其關系的范式7.3關系系統及其查詢優化技術7.3.1關系系統的定義和分類7.3.2關系系統的查詢優化理論與技術.前面已經講述了關系數據庫、關系模型的根本概念以及關系數據庫的標準語言。如何使用關系模型設計關系數據庫，如何選擇一個比較好的關系模式的集合，每個關系又應該由哪些屬性組成。這屬于數據庫設計的問題，確切地講是數據庫邏輯設計的問題。.本章講述關系數據庫標準化理論和數據庫操作理論。要求了解標準化理論的研究動機及其在數據庫設計中的作用，掌握函數依賴的有關概念，第一范式、第二范式、第三范式及BC范式重點掌握并能夠靈活運用關系模式標準化的方法掌握關系數據操作理論——關系數據查詢和優化理論規那么.7.1關系數據模式的標準化理論標準化理論的主要內容：關系數據庫的標準化理論最早是由關系數據庫的創始人E.F.Codd提出的，后經許多專家學者對關系數據庫理論作了深入的研究和開展，形成了一整套有關關系數據庫設計的理論。范式〔NormalForm〕是指標準化的關系模式。由滿足最根本標準化的關系模式叫第一范式，第一范式的關系模式再滿足另外一些約束條件就產生了第二范式、第三范式、BC范式等等。一個低一級的關系范式通過模式分解可以轉換成假設干高一級范式的關系模式的集合，這種過程叫關系模式的標準化。.范式的概念最早由E.F.Codd提出。從1971年起，Codd相繼提出了關系的三級標準化形式，即第一范式〔1NF〕、第二范式〔2NF〕、第三范式〔3NF〕。1974年，Codd和Boyce以共同提出了一個新的范式的概念，即Boyce-Codd范式，簡稱BC范式。1976年Fagin提出了第四范式，后來又有人定義了第五范式。至此在關系數據庫標準中建立了一個范式系列：1NF,2NF,3NF,BCNF,4NF,5NF,一級比一級有更嚴格的要求。各個范式之間的聯系可以表示為：5NF4NFBCNF3NF2NF1NF如下圖。.4NF5NFBCNF3NF2NF1NF規范與非規范關系.如何設計一個適合的關系數據庫系統，關鍵是關系數據庫模式的設計，一個好的關系數據庫模式應該包括多少關系模式，而每一個關系模式又應該包括哪些屬性，又如何將這些相互關聯的關系模式組建一個適合的關系模型，這些工作決定了到整個系統運行的效率，也是系統成敗的關鍵所在，所以必須在關系數據庫的標準化理論的指導下逐步完成。.7.1.1關系模式標準化的必要性1.關系模式應滿足的根本要求

1)元組的每個分量必須是不可分的數據項。

2)數據庫中的數據冗余應盡可能少。

3)關系數據庫不能因為數據更新操作而引起數據不一致問題。

4)當執行數據插入操作時，數據庫中的數據不能產生插入異?，F象。

5)數據庫中的數據不能在執行刪除操作時產生刪除異常問題。

6)數據庫設計應考慮查詢要求，數據組織應合理。

.2.關系標準化可能出現的問題數據冗余大.插入異常。刪除異常。更新異常。學號姓名年齡性別系名系主任課程名成績98001李華20男計算機系王民程序設計8898001李華20男計算機系王民數據結構7498001李華20男計算機系王民數據庫8298001李華20男計算機系王民電路6598002張平21女計算機系王民程序設計9298002張平21女計算機系王民數據結構8298002張平21女計算機系王民數據庫7898002張平21女計算機系王民電路8398003陳兵20男數學系趙敏高等數學7298003陳兵20男數學系趙敏數據結構9498003陳兵20男數學系趙敏數據庫8398003陳兵20男數學系趙敏離散數學87.3.模式分解是關系標準化的主要方法

上述的關系模式:教學(學號，姓名，年齡，性別，系名，系主任，課程名，成績).p216異常情況分析?？梢园础耙皇乱坏亘暤脑敲捶纸獬伞皩W生〞、“教學系〞和“選課〞三個關系，其關系模式為：

學生(學號，姓名，年齡，性別，系名稱)；

教學系(系名，系主任)；

選課(學號，課程名，成績)..經過上述分析，我們說分解后的關系模式是一個好的關系數據庫模式。從而得出結論，一個好的關系模式應該具備以下四個條件：1.盡可能少的數據冗余。2.沒有插入異常。3.沒有刪除異常。4.沒有更新異常。

.將結構復雜的關系分解成結構簡單的關系，從而把不好的關系數據庫模式轉變為好的關系數據庫模式，這就是關系的標準化。標準化又可以根據不同的要求而分成假設干級別。我們要設計的關系模式中的各屬性是相互依賴、相互制約的，這樣才構成了一個結構嚴謹的整體。因此在設計關模式時，必須從語義上分析這些依賴關系。數據庫模式的好壞和關系中各屬性間的依賴關系有關，因此，我們先討論屬性間的依賴關系，然后再討論關系標準化理論。.7.1.2函數依賴及其關系的范式關系模式中的各屬性之間相互依賴、相互制約的聯系稱為數據依賴。數據依賴一般分為函數依賴、多值依賴和連接依賴。其中,函數依賴是最重要的數據依賴。函數依賴〔FunctionalDependency〕是關系模式中屬性之間的一種一一對應的邏輯依賴關系。.例如在關系模式Student中，SNO與SN、AGE、DEPT之間都有一種依賴關系。由于一個SNO只對應一個學生，而一個學生只能屬于一個系，所以當SNO的值確定之后，SN，AGE，DEPT的值也隨之被唯一確實定了。我們說SNO決定函數〔SN，AGE，DEPT〕，或者說〔SN，AGE，DEPT〕函數依賴于SNO。.1.關系模式的簡化表示法

關系模式的完整表示是一個五元組：

R〈U，D，Dom，F〉.

其中：R為關系名；U為關系的屬性集合；D為屬性集U中屬性的數據域；Dom為屬性到域的映射；F為屬性集U的數據依賴集。

關系模式可以用三元組來為：

R〈U，F〉.

.2.函數依賴的概念1)設R〈U〉是屬性集U上的關系模式，X、Y是U的子集。假設對于R〈U〉的任意一個可能的關系r，r中不可能存在兩個元組在X上的屬性值相等，而Y上的屬性值不等，那么稱X函數確定Y函數，或Y函數依賴于X函數，記作X→Y。

例如，對于教學關系模式：教學〈U，F〉；

U={學號，姓名，年齡，性別，系名，系主任，課程名，成績}；

F={學號→姓名，學號→年齡，學號→性別，學號→系名，系名→系主任，(學號，課程名)→成績}.

.相關概念及表示 ①X→Y，但YX，那么稱X→Y是非平凡的函數依賴。假設不特別聲明，總是討論非平凡的函數依賴。

②X→Y，但YX，那么稱X→Y是平凡的函數依賴。

③假設X→Y，那么X叫做決定因素〔Determinant〕，Y叫做依賴因素〔Dependent〕。

④假設X→Y，Y→X，那么記作X?Y。

⑤假設Y不函數依賴于X，那么記作XY。. 2)在R〈U〉中，如果X→Y，并且對于X的任何一個真子集X‘，都有X‘Y，那么稱Y對X完全函數依賴，記作：X→Y；假設X→Y，但Y不完全函數依賴于X，那么稱Y對X局部函數依賴，記作：X→Y。

例如，在教學關系模式：(學號，課程名)→成績，(學號，課程名)→姓名

3)在R〈U〉中，如果X→Y，(YX)，YX，Y→Z，那么稱Z對X傳遞函數依賴。傳遞函數依賴記作X→Z。

例如，在教學模式中，因為：學號→系名，系名→系主任；所以：學號→系主任。PFFP傳遞傳遞.

3.1NF的定義如果關系模式R，其所有的屬性均為簡單屬性，即每個屬性都是不可再分的，那么稱R屬于第一范式，記作R1NF。

4.2NF的定義假設R1NF，且每一個非主屬性完全依賴于碼，那么R2NF。

〔即消除非主屬性碼對碼的局部依賴〕.在教學模式中：屬性集={學號，姓名，年齡，性別，系名，系主任，課程名，成績}.

函數依賴集={學號→姓名，學號→年齡，學號→性別，學號→系名，系名→系主任，(學號，課程名)→成績}.

主碼=(學號，課程名).非主屬性=(姓名，年齡，系名，系主任，成績)。

非主屬性對碼的函數依賴：{(學號，課程名)→姓名，(學號，課程名)→年齡，(學號，課程名)→性別，(學號，課程名)→系名，(學號，課程名)→系主任；(學號，課程名)→成績}.教學模式不服從2NF，將教學模式分解為：學生－系〔學號，姓名，年齡，性別，系名，系主任〕選課〔學號，課程名，成績〕pppppF.5.3NF的定義關系模式R〈U，F〉中假設不存在這樣的碼X、屬性組Y及非主屬性Z(ZY)使得X→Y、YX、Y→Z成立，那么稱R〈U，F〉3NF。

可以證明，假設R3NF，那么每一個非主屬性既不局部函數依賴于碼，也不傳遞函數依賴于碼?！布聪侵鲗傩詫Υa的局部和傳遞函數依賴〕

.考查學生_系關系，由于存在：學號→系名，系名→系主任。那么：學號→系主任。所以學生_系3NF。

如果分解為：

學生(學號，姓名，年齡，性別，系名)；

教學系(系名，系主任).

顯然分解后的各子模式均屬于3NF。傳遞.6.BCNF的定義關系模式R〈U，F〉1NF。假設X→Y且YX時X必含有碼，那么R〈U，F〉BCNF。〔即消除主屬性對碼的局部和傳遞函數依賴〕

也就是說，關系模式R〈U，F〉中，假設每一個決定因素都包含碼，那么R〈U，F〉BCNF。由BCNF的定義可以得到結論，一個滿足BCNF的關系模式有：

1)所有非主屬性對每一個碼都是完全函數依賴。

2)所有的主屬性對每一個不包含它的碼，也是完全依賴。

3)沒有任何屬性完全函數依賴于非碼的任何一組屬性。.7.BCNF和3NF的比較1)BCNF不僅強調其他屬性對碼的完全的直接的依賴，而且強調主屬性對碼的完全的直接的依賴，它包括3NF，即RBCNF，那么R一定屬于3NF。

2)3NF只強調非主屬性對碼的完全直接依賴，這樣就可能出現主屬性對碼的局部依賴和傳遞依賴。

.例如，關系模式STJ(S，T，J)中，S表示學生，T表示教師，J表示課程。語義為：每一教師只能講授一門課程，每門課程由假設干教師講授；每個學生選修某門課程就對應一個固定的教師。由語義可以得到STJ模式的函數依賴為：

F={(S，J)→T，T→J}

顯然：(S，J)和(T，S)都是關系的碼；關系的主屬性集為{S，T，J}，非主屬性為〔空集〕。

由于STJ模式中無非主屬性，所以它屬于3NF；但因為存在T→J，由于T不是碼，故STJBCNF。分解為〔S，T〕和

〔T，J〕兩個模式。.7.1.5關系模式的標準化到目前為止，標準化理論已經提出了六類范式〔有關4NF和5NF的內容不再詳細介紹〕。各范式級別是在分析函數依賴條件下對關系模式別離程度的一種測度，范式級別可以逐級升高。一個低一級范式的關系模式，通過模式分解轉化為假設干個高一級范式的關系模式的集合，這種分解過程叫作關系模式的標準化〔Normalization〕。.關系模式標準化的目的和原那么一個關系只要其分量都是不可分的數據項，就可稱作標準化的關系，但這只是最根本的標準化。這樣的關系模式是合法的。但人們發現有些關系模式存在插入、刪除、修改異常、數據冗余等弊病。標準化的目的就是使結構合理，消除存儲異常，使數據冗余盡量小，便于插入、刪除和更新。標準化的根本原那么就是遵從概念單一化“一事一地〞的原那么，即一個關系只描述一個實體或者實體間的聯系。假設多于一個實體，就把它“別離〞出來。因此，所謂標準化，實質上是概念的單一化，即一個關系表示一個實體。

.關系模式標準化的步驟標準化就是對原關系進行投影，消除決定屬性不是候選碼的任何函數依賴。具體可以分為以下幾步：1．對1NF關系進行投影，消除原關系中非主屬性對碼的局部函數依賴，將1NF關系轉換成假設干個2NF關系。2．對2NF關系進行投影，消除原關系中非主屬性對碼的傳遞函數依賴，將2NF關系轉換成假設干個3NF關系。3．對3NF關系進行投影，消除原關系中主屬性對碼的局部函數依賴和傳遞函數依賴，也就是說使決定因素都包含一個候選碼。得到一組BCNF關系。.關系標準化的根本步驟如下圖。1NF2NF3NFBCNF消除決定屬性不是候選碼的非平凡的函數依賴消除非主屬性對碼的部分函數依賴消除非主屬性對碼的傳遞函數依賴消除主屬性對碼的部分和傳遞函數依賴標準化過程.一般情況下，我們說沒有異常弊病的數據庫設計是好的數據庫設計，一個不好的關系模式也總是可以通過分解轉換成好的關系模式的集合。但是在分解時要全面衡量，綜合考慮，視實際情況而定。對于那些只要求查詢而不要求插入、刪除等操作的系統，幾種異?，F象的存在并不影響數據庫的操作。這時便不宜過度分解，否那么當要對整體查詢時，需要更多的多表連接操作，這有可能得不償失。在實際應用中，最有價值的是3NF和BCNF，在進行關系模式的設計時，通常分解到3NF就足夠了。.7.3關系系統及其查詢優化技術7.3.1關系系統的定義和分類能夠在一定程度上支持關系模型的數據庫管理系統是關系系統。由于關系模型中并非每一局部都是同等重要的并不苛求一個實際的關系系統必須完全支持關系模型。.1.關系系統的定義一個數據庫管理系統可定義為關系系統，當且僅當它至少滿足：1.支持關系數據庫〔即關系數據結構〕從用戶角度看，系統中只有表這種結構2.支持選擇、投影和〔自然〕連接運算對這些運算不要求用戶定義任何物理存取路徑對關系系統的最低要求.不支持關系數據結構的系統顯然不能稱為關系系統僅支持關系數據結構，但沒有選擇、投影和連接運算功能的系統仍不能算作關系系統。原因：不能提高用戶的生產率支持選擇、投影和連接運算，但要求定義物理存取路徑，這種系統也不能算作真正的關系系統原因：就降低或喪失了數據的物理獨立性選擇、投影、連接運算是最有用的運算.2.關系系統的分類分類依據：支持關系模型的程度分類⒈表式系統：支持關系數據結構(即表),不支持集合級的操作。⒉(最小)關系系統支持：關系數據結構 選擇、投影、連接關系操作⒊關系完備的系統支持：關系數據結構 所有的關系代數操作 支持關系的實體完整性和參照完整性⒋全關系系統支持：關系模型的所有特征 特別是:數據結構中域的概念，支持實體完整性、參照完整性和所有用戶定義的完整性

.

數據結構數據操作完整性表式系統表

(最小)關系系統表選擇、投影、連接

關系完備的系統表

全關系系統

.1.一個實例例：求選修了課程Ｃ2的學生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';.假設1：外存： Student:1000條,SC:10000條,選修2號課程:50條假設2：一個內存塊裝元組:10個Student,或100個SC, 內存中一次可以存放:5塊Student元組,1塊SC元組和假設干塊連接結果元組假設3：讀寫速度：20塊/秒假設4：連接方法：基于數據塊的嵌套循環法

.執行策略1Ｑ1＝ПＳname(бStudent.Sno=SC.Sno

∧SC.Cno='2'

(Student×SC))

①Student×SC

讀取總塊數=讀Student表塊數+讀SC表遍數*每遍塊數

=1000/10+(1000/(10×5))×(10000/100)=100+20×100=2100

讀數據時間=2100/20=105秒.不同的執行策略,考慮I/O時間

中間結果大小=1000*10000=107(1千萬條元組)

寫中間結果時間

=10000000/10/20=50000秒

②б

讀數據時間

=50000秒

③П總時間=105＋50000＋50000秒=100105秒

=27.8小時.2.Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))

① 讀取總塊數=2100塊 讀數據時間=2100/20=105秒 中間結果大小=10000〔減少1000倍〕 寫中間結果時間=10000/10/20=50秒

②б 讀數據時間=50秒

③П

總時間＝105＋50＋50秒＝205秒=3.4分

執行策略2.3.Ｑ2＝ПSname(StudentбSC.Cno='2'(SC))

①б

讀SC表總塊數=10000/100=100塊

讀數據時間=100/20=5秒

中間結果大小=50條不必寫入外存

② 讀Student表總塊數=1000/10=100塊

讀數據時間=100/20=5秒

③П

總時間＝5＋5秒＝10秒執行策略3.執行策略44.Ｑ2＝ПＳname(StudentбSC.Cno='2'(SC))假設SC表在Cno上有索引，Student表在Sno上有索引

①б

讀SC表索引=

讀SC表總塊數=50/100<1塊 讀數據時間

中間結果大小=50條不必寫入外存② 讀Student表索引=

讀Student表總塊數=50/10=5塊 讀數據時間③П總時間<10秒.查詢優化的必要性查詢優化極大地影響RDBMS的性能。

查詢優化的可能性關系數據語言的級別很高，使DBMS可以從關系表達式中分析查詢語義。用戶不必考慮如何最好地表達查詢以獲得較好的效率系統可以比用戶程序的優化做得更好(1)優化器可以從數據字典中獲取許多統計信息，而用戶程序那么難以獲得這些信息(2)如果數據庫的物理統計信息改變了，系統可以自動對查詢重新優化以選擇相適應的執行方案。在非關系系統中必須重寫程序，而重寫程序在實際應用中往往是不太可能的。(3)優化器可以考慮數百種不同的執行方案，而程序員一般只能考慮有限的幾種可能性。(4)優化器中包括了很多復雜的優化技術查詢優化的總目標選擇有效策略，求得給定關系表達式的值

.2.查詢優化的一般準那么選擇運算應盡可能先做

目的：減小中間關系在執行連接操作前對關系適當進行預處理按連接屬性排序在連接屬性上建立索引

投影運算和選擇運算同時做目的：防止重復掃描關系將投影運算與其前面或后面的雙目運算結合目的：減少掃描關系的遍數某些選擇運算＋在其前面執行的笛卡爾積===>連接運算例：бStudent.Sno=SC.Sno(Student×SC)

StudentSC提取公共子表達式.3.關系代數等價變換規那么關系代數表達式等價指用相同的關系代替兩個表達式中相應的關系所得到的結果是相同的優化策略大局部都涉及到代數表達式的變換.

常用的等價變換規那么

設E1、E2等是關系代數表達式，F是條件表達式

l.連接、笛卡爾積交換律

E1×E2≡E2×E1 E1E2≡E2E1 E1FE2≡E2FE1

.

2.連接、笛卡爾積的結合律

(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)

F

F

F

F.3.投影的串接定律πA1,A2,,An(πB1,B2,,Bm(E))≡πA1,A2,,An(E)假設：1) E是關系代數表達式2) Ai(i=1，2，…，n),Bj(j=l，2，…，m)是屬性名3){A1,A2,…,An}構成{Bl，B2，…，Bm}的子集4.選擇的串接定律бF1〔бF2〔E〕〕≡бF1∧F2(E)選擇的串接律說明選擇條件可以合并這樣一次就可檢查全部條件。.5.選擇與投影的交換律(1)假設:選擇條件F只涉及屬性A1，…，AnбF(πA1,A2,

,An(E))≡πA1,A2,

,An(бF(E))

(2)假設:F中有不屬于A1,…,An的屬性B1,…,Bmπ

A1,A2,

,An

(

бF

(E))≡

πA1,A2,

,An(бF

(πA1,A2,

,An,B1,B2,

,Bm(E))).6.選擇與笛卡爾積的交換律(1)假設：F中涉及的屬性都是E1中的屬性 бF(E1×E2)≡бF(E1)×E2

(2)假設：F=F1∧F2，并且F1只涉及E1中的屬性，F2只涉及E2中的屬性 那么由上面的等價變換規那么1，4，6可推出： бF(E1×E2)≡бF1(E1)×бF2(E2)

(3)假設：F=F1∧F2，F1只涉及E1中的屬性，F2涉及E1和E2兩者的屬性 бF(E1×E2)≡бF2(бF1(E1)×E2)

它使局部選擇在笛卡爾積前先做.7.選擇與并的交換 假設：E=E1∪E2，E1，E2有相同的屬性名

бF(E1∪E2)≡бF(E1)∪бF(E2)

8.選擇與差運算的交換 假設：E1與E2有相同的屬性名

бF(E1-E2)≡бF(E1)-бF(E2).9.投影與笛卡爾積的交換 假設：E1和E2是兩個關系表達式，A1，…，An是E1的屬性，B1，…，Bm是E2的屬性πA1,A2,…,An,B1,B2,…,Bm〔E1×E2)≡ πA1,A2,…,An〔E1)×πB1,B2,…,Bm(E2)l0.投影與并的交換 假設：E1和E2有相同的屬性名 πA1,A2,…,An(E1∪E2)≡ πA1,A2,…,An(E1)∪πA1,A2,…,An(E2).4.關系代數表達式的優化算法

算法：關系表達式的優化輸入：一個關系表達式的語法樹。輸出：計算該表達式的程序。方法：〔1〕分解選擇運算利用規那么4把形如бF1∧F2∧…∧Fn(E)變換為бF1(бF2(…(бFn(E))…)).〔2〕通過交換選擇運算，將其盡可能移到葉端對每一個選擇，利用規那么4～8盡可能把它移到樹的葉端。

〔3〕通過交換投影運算，將其盡可能移到葉端 對每一個投影利用規那么3，9，l0，5中的一般形式