1、第四章第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化關(guān)系系統(tǒng)及其查詢優(yōu)化本章包括兩個(gè)內(nèi)容，一是關(guān)系系統(tǒng)的本章包括兩個(gè)內(nèi)容，一是關(guān)系系統(tǒng)的定義和分定義和分類類；二是關(guān)系系統(tǒng)的；二是關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化。關(guān)系模型的三個(gè)關(guān)系模型的三個(gè)基本要素基本要素：關(guān)系數(shù)據(jù)結(jié)構(gòu)關(guān)系數(shù)據(jù)結(jié)構(gòu)、關(guān)關(guān)系系統(tǒng)的完整性系系統(tǒng)的完整性和和關(guān)系操作關(guān)系操作。關(guān)系系統(tǒng)和關(guān)系模型兩個(gè)概念密切相關(guān)，實(shí)際關(guān)系系統(tǒng)和關(guān)系模型兩個(gè)概念密切相關(guān)，實(shí)際的關(guān)系數(shù)據(jù)庫系統(tǒng)的關(guān)系數(shù)據(jù)庫系統(tǒng)并不苛求完全支持并不苛求完全支持關(guān)系模型，因關(guān)系模型，因此有一個(gè)關(guān)系系統(tǒng)的此有一個(gè)關(guān)系系統(tǒng)的最小要求以及分類的定義最小要求以及分類的定義。第一節(jié)第一節(jié) 關(guān)系系統(tǒng)關(guān)系系統(tǒng)1 1

2、）支持關(guān)系數(shù)據(jù)庫（關(guān)系數(shù)據(jù)結(jié)構(gòu)）支持關(guān)系數(shù)據(jù)庫（關(guān)系數(shù)據(jù)結(jié)構(gòu)）一一 定義定義2 2）支持選擇、投影和連接運(yùn)算，對這）支持選擇、投影和連接運(yùn)算，對這些運(yùn)算不要求定義任何物理存取路徑些運(yùn)算不要求定義任何物理存取路徑3）由于）由于選擇、投影和連接運(yùn)算是最有用的運(yùn)算功選擇、投影和連接運(yùn)算是最有用的運(yùn)算功能能，能解決大部分的實(shí)際問題，因此在關(guān)系系統(tǒng)，能解決大部分的實(shí)際問題，因此在關(guān)系系統(tǒng)的最小要求中的最小要求中要求能支持這三種運(yùn)算要求能支持這三種運(yùn)算。1）支持關(guān)系數(shù)據(jù)庫：從用戶觀點(diǎn)看，）支持關(guān)系數(shù)據(jù)庫：從用戶觀點(diǎn)看，數(shù)據(jù)庫由表數(shù)據(jù)庫由表組成，且只有表這一種結(jié)構(gòu)組成，且只有表這一種結(jié)構(gòu)。2）一個(gè)系統(tǒng)僅支持

3、關(guān)系數(shù)據(jù)庫而）一個(gè)系統(tǒng)僅支持關(guān)系數(shù)據(jù)庫而沒有運(yùn)算功能，沒有運(yùn)算功能，不能稱為關(guān)系系統(tǒng)不能稱為關(guān)系系統(tǒng)。一個(gè)系統(tǒng)雖然支持這三種運(yùn)。一個(gè)系統(tǒng)雖然支持這三種運(yùn)算，但要求定義物理存取路徑就算，但要求定義物理存取路徑就喪失了物理獨(dú)立喪失了物理獨(dú)立性，也不能稱為關(guān)系系統(tǒng)。性，也不能稱為關(guān)系系統(tǒng)。原因是：原因是：二二 分類分類在關(guān)系模型的三個(gè)在關(guān)系模型的三個(gè)基本要素中基本要素中：用：用S(Structure)表示表示關(guān)系數(shù)據(jù)結(jié)構(gòu)、關(guān)系數(shù)據(jù)結(jié)構(gòu)、用用I(Integrity)表示表示關(guān)系系統(tǒng)的關(guān)系系統(tǒng)的完整性和完整性和用用M(Manipulation)M(Manipulation)表示表示關(guān)系操作關(guān)系操作。則。

4、則關(guān)系系統(tǒng)的分類示意圖為：關(guān)系系統(tǒng)的分類示意圖為：SSSSMMMI(a)表式系統(tǒng)(b)(最小)關(guān)系系統(tǒng)(c)關(guān)系完備(d)全關(guān)系圖圖4.1 4.1 關(guān)系系統(tǒng)的分類示意圖關(guān)系系統(tǒng)的分類示意圖1 1 表式系統(tǒng)表式系統(tǒng)：僅支持關(guān)系：僅支持關(guān)系( (即表即表) )數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)S S，不，不支持集合級操作。如圖支持集合級操作。如圖4.1(a)4.1(a)所示。所示。2 2 （最小）關(guān)系系統(tǒng)（最小）關(guān)系系統(tǒng)：僅支持關(guān)系：僅支持關(guān)系( (即表即表) )數(shù)據(jù)結(jié)數(shù)據(jù)結(jié)構(gòu)構(gòu)S S和三種關(guān)系操作和三種關(guān)系操作M M。如。如FoxBASEFoxBASE，F(xiàn)oxProFoxPro。如。如圖圖4.1(b)4.1(b)

5、所示。所示。3 3 關(guān)系完備的系統(tǒng)關(guān)系完備的系統(tǒng)：支持關(guān)系數(shù)據(jù)結(jié)構(gòu)：支持關(guān)系數(shù)據(jù)結(jié)構(gòu)S S和所有和所有的關(guān)系代數(shù)操作的關(guān)系代數(shù)操作M M。如圖。如圖4.1(c)4.1(c)所示。所示。4 4 全關(guān)系系統(tǒng)全關(guān)系系統(tǒng)：支持關(guān)系模型的所有特征。即不：支持關(guān)系模型的所有特征。即不僅是關(guān)系上完備的，而且支持?jǐn)?shù)據(jù)結(jié)構(gòu)中域的概僅是關(guān)系上完備的，而且支持?jǐn)?shù)據(jù)結(jié)構(gòu)中域的概念，支持實(shí)體完整性和參照完整性。如圖念，支持實(shí)體完整性和參照完整性。如圖4.1(d)4.1(d)所示。所示。第二節(jié)第二節(jié) 查詢優(yōu)化查詢優(yōu)化在關(guān)系系統(tǒng)中，由于用戶無需指出數(shù)據(jù)操作中在關(guān)系系統(tǒng)中，由于用戶無需指出數(shù)據(jù)操作中的物理存取路徑，系統(tǒng)就的物

6、理存取路徑，系統(tǒng)就必須對用戶的操作進(jìn)行優(yōu)必須對用戶的操作進(jìn)行優(yōu)化處理化處理。查詢優(yōu)化的優(yōu)點(diǎn)查詢優(yōu)化的優(yōu)點(diǎn)不僅在于用戶不必考慮如何最不僅在于用戶不必考慮如何最好的表達(dá)查詢以獲得較好的效率，而且在于系統(tǒng)可好的表達(dá)查詢以獲得較好的效率，而且在于系統(tǒng)可以比用戶程序的優(yōu)化做得更好。這是因?yàn)椋阂员扔脩舫绦虻膬?yōu)化做得更好。這是因?yàn)椋? 1）優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，）優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，例如關(guān)系中的元組數(shù)、關(guān)系中每個(gè)屬性值的分布情例如關(guān)系中的元組數(shù)、關(guān)系中每個(gè)屬性值的分布情況等，優(yōu)化器可以根據(jù)這些信息況等，優(yōu)化器可以根據(jù)這些信息選擇有效的執(zhí)行計(jì)選擇有效的執(zhí)行計(jì)劃劃，而用戶程

7、序，而用戶程序 則難以獲得這些信息則難以獲得這些信息2 2）如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以）如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自自動(dòng)對查詢進(jìn)行重新優(yōu)化動(dòng)對查詢進(jìn)行重新優(yōu)化；3 3）優(yōu)化器可以考慮數(shù)百種）優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃不同的執(zhí)行計(jì)劃，而程序，而程序員一般只能考慮有限的幾種可能性員一般只能考慮有限的幾種可能性4 4）優(yōu)化器包括了很多）優(yōu)化器包括了很多復(fù)雜的優(yōu)化技術(shù)復(fù)雜的優(yōu)化技術(shù)。總之，優(yōu)化器充分考慮系統(tǒng)中的總之，優(yōu)化器充分考慮系統(tǒng)中的各種參數(shù)各種參數(shù)( (如如緩沖區(qū)大小、表的大小、數(shù)據(jù)緩沖區(qū)大小、表的大小、數(shù)據(jù) 的分布、存取路徑的分布、存取路徑等等) )，通過某

8、種代價(jià)模型計(jì)算出各種查詢執(zhí)行方案，通過某種代價(jià)模型計(jì)算出各種查詢執(zhí)行方案的執(zhí)行代價(jià)，然后選取代價(jià)最小的執(zhí)行方案執(zhí)行用的執(zhí)行代價(jià)，然后選取代價(jià)最小的執(zhí)行方案執(zhí)行用戶的查詢請求。戶的查詢請求。實(shí)際系統(tǒng)對查詢優(yōu)化的實(shí)際系統(tǒng)對查詢優(yōu)化的具體實(shí)現(xiàn)不盡相同具體實(shí)現(xiàn)不盡相同，但，但一般來說，可以歸納為幾個(gè)步驟。一般來說，可以歸納為幾個(gè)步驟。下面通過實(shí)例對查詢優(yōu)化的一般準(zhǔn)則和步驟予下面通過實(shí)例對查詢優(yōu)化的一般準(zhǔn)則和步驟予以說明：以說明：SELECT SELECT Student.SnameStudent.SnameFROM FROM Student, SCStudent, SCWHERE WHERE Stud

9、ent.Sno = SC.SnoStudent.Sno = SC.Sno AND AND SC.Cno=2SC.Cno=2；例：在學(xué)生選課數(shù)據(jù)庫的關(guān)系表中，要查詢選例：在學(xué)生選課數(shù)據(jù)庫的關(guān)系表中，要查詢選修了修了2 2號課程的學(xué)生姓名。用號課程的學(xué)生姓名。用SQLSQL語言的查詢表達(dá)式語言的查詢表達(dá)式為：為：T2T2：SnameSname( ( SC.Cno=2SC.Cno=2(Student SC)(Student SC)T3T3：SnameSname(Student (Student SC.Cno=2SC.Cno=2(SC)(SC)下面用等價(jià)的關(guān)系代數(shù)表達(dá)式來實(shí)現(xiàn)上例中的查詢：下面用等價(jià)的

10、關(guān)系代數(shù)表達(dá)式來實(shí)現(xiàn)上例中的查詢：T1T1：SnameSname( ( Student.Sno=SC.SnoStudent.Sno=SC.Sno SC.Cno=2SC.Cno=2(Student(Student SC)SC)1 1 計(jì)算廣義笛卡兒積計(jì)算廣義笛卡兒積 2 2 作選擇運(yùn)算作選擇運(yùn)算 3 3 作投影作投影1 1 計(jì)算自然連接計(jì)算自然連接 2 2 作選擇運(yùn)算作選擇運(yùn)算 3 3 作投影作投影1 1 對對SCSC作選擇運(yùn)算作選擇運(yùn)算 2 2 作連接運(yùn)算作連接運(yùn)算 3 3作投影作投影一、查詢優(yōu)化的一般準(zhǔn)則一、查詢優(yōu)化的一般準(zhǔn)則 1 1 選擇運(yùn)算盡可能先做。選擇運(yùn)算盡可能先做。在優(yōu)化策略中這是

11、最基本也是最重要的一條。它使計(jì)算的中間結(jié)果大大變小，可使執(zhí)行時(shí)間降低幾個(gè)數(shù)量級。2 2 作連接運(yùn)算前對關(guān)系適當(dāng)?shù)念A(yù)處理。作連接運(yùn)算前對關(guān)系適當(dāng)?shù)念A(yù)處理。u在連接屬性上建立索引在連接屬性上建立索引u對關(guān)系排序?qū)﹃P(guān)系排序兩種預(yù)處理方式都減少了對表的掃描次數(shù)。4 把投影運(yùn)算同其前后的雙目運(yùn)算結(jié)合起來。把投影運(yùn)算同其前后的雙目運(yùn)算結(jié)合起來。3 3 把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行。把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行。掃描關(guān)系的同時(shí)完成所有的投影和選擇運(yùn)算，可避免重復(fù)掃描關(guān)系。5 5 把某些選擇同在它前面要執(zhí)行的笛卡兒積結(jié)合成為一把某些選擇同在它前面要執(zhí)行的笛卡兒積結(jié)合成為一個(gè)連接運(yùn)算。個(gè)連接運(yùn)算。6 找出公共子

12、表達(dá)式找出公共子表達(dá)式例：對例：對A、B、C、D四個(gè)表的查詢有如下表達(dá)式：四個(gè)表的查詢有如下表達(dá)式： SELECT * FROM A, B, C, D WHERE A.a =B.a AND B.b=C.b AND C.c=D.c可能存在的連接對：可能存在的連接對：ab, ac, ad, ba, bc, bd, ca, cd, cb, da, db, dc u找出連接兩個(gè)表的最佳方式（循環(huán)搜索，找出連接兩個(gè)表的最佳方式（循環(huán)搜索，hash法搜索，排序搜索）法搜索，排序搜索）u確定連接時(shí)是否使用索引確定連接時(shí)是否使用索引u計(jì)算連接的代價(jià)計(jì)算連接的代價(jià)對每一個(gè)連接對，查詢優(yōu)化器都將：對每一個(gè)連接對，

13、查詢優(yōu)化器都將：ababcabcdadcacdacbabdabdcacdbacbdadacbd 在該例中，還需計(jì)算三個(gè)表、四個(gè)表在該例中，還需計(jì)算三個(gè)表、四個(gè)表的連接對各自的連接代價(jià)。的連接對各自的連接代價(jià)。最后，從上述的連接中，剔除高代價(jià)最后，從上述的連接中，剔除高代價(jià)連接。連接。將查詢轉(zhuǎn)換成某種將查詢轉(zhuǎn)換成某種內(nèi)部表示內(nèi)部表示，通常是，通常是語法樹語法樹。 如下圖所示的兩種如下圖所示的兩種Project(Sname)Select(SC.Cno=2)Join(Student.Sno=SC.Sno)StudentSC結(jié)果結(jié)果SnameSC.Cno=2Student.Sno=SC.SnoStud

14、entSC結(jié)果結(jié)果圖4.2 語法樹圖4.3 用關(guān)系代數(shù)表示的語法樹二、查詢優(yōu)化的一般步驟：二、查詢優(yōu)化的一般步驟：根據(jù)一定的根據(jù)一定的等價(jià)變換規(guī)則等價(jià)變換規(guī)則把語法樹轉(zhuǎn)換成把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形式式。利用優(yōu)化算法，把原始的語法樹轉(zhuǎn)換成優(yōu)化的形式。利用轉(zhuǎn)換規(guī)則，可以把選擇SC.Cno=2移到葉端。得到如下圖示語法樹。有關(guān)轉(zhuǎn)換規(guī)則，將在下面的內(nèi)容講敘。SnameSC.Cno=2Student.Sno=SC.SnoStudentSC結(jié)果結(jié)果圖4.4 優(yōu)化后的語法樹代價(jià)計(jì)算公式為：代價(jià)計(jì)算公式為： 總代價(jià)總代價(jià)=I/O代價(jià)代價(jià)+CPU代價(jià)代價(jià)+內(nèi)存代價(jià)。內(nèi)存代價(jià)。選擇選擇低層的操作低層的操作算法。

15、算法。生成生成查詢計(jì)劃查詢計(jì)劃。根據(jù)上述優(yōu)化了的語法樹在計(jì)算關(guān)系表達(dá)式值時(shí)，要充分考慮索引、數(shù)據(jù)的存儲分布等存取路徑，進(jìn)一步改善查詢效率。優(yōu)化器可以通過查找數(shù)據(jù)字典，獲得數(shù)據(jù)庫狀態(tài)信息實(shí)現(xiàn)。如該例中，若SC表上建有Cno的索引，則利用這個(gè)索引，而不必去順序掃描SC表。查詢計(jì)劃是由一組內(nèi)部過程組成的，這組內(nèi)部過程實(shí)現(xiàn)按某條存取路徑計(jì)算關(guān)系表達(dá)式值。常有多個(gè)查詢計(jì)劃可供選擇。找出代價(jià)最佳的查詢計(jì)劃。關(guān)系代數(shù)關(guān)系代數(shù)等價(jià)轉(zhuǎn)換規(guī)則等價(jià)轉(zhuǎn)換規(guī)則：各種查詢語言，都可以轉(zhuǎn)換成等價(jià)的關(guān)系代數(shù)表達(dá)式。各種查詢語言，都可以轉(zhuǎn)換成等價(jià)的關(guān)系代數(shù)表達(dá)式。所謂所謂關(guān)系代數(shù)表達(dá)式的等價(jià)關(guān)系代數(shù)表達(dá)式的等價(jià)是指用相同的關(guān)系代替兩是指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同結(jié)果是相同的。的