第四章關(guān)系系統(tǒng)的查詢優(yōu)化第一頁，共五十二頁，編輯于2023年，星期五第四章關(guān)系系統(tǒng)的查詢優(yōu)化4.1關(guān)系系統(tǒng)4.2查詢優(yōu)化處理數(shù)據(jù)庫系統(tǒng)原理第二頁，共五十二頁，編輯于2023年，星期五

第四章關(guān)系系統(tǒng)的查詢優(yōu)化學(xué)習(xí)要求

了解關(guān)系系統(tǒng)的基本概念及分類標(biāo)準(zhǔn)，初步了解查詢處理的基本步驟，理解查詢優(yōu)化的意義，掌握關(guān)系代數(shù)優(yōu)化的算法及相應(yīng)的等價(jià)變換。學(xué)習(xí)重點(diǎn)

利用關(guān)系優(yōu)化規(guī)則對(duì)關(guān)系語法樹進(jìn)行優(yōu)化。

數(shù)據(jù)庫系統(tǒng)原理第三頁，共五十二頁，編輯于2023年，星期五第四章關(guān)系系統(tǒng)的查詢優(yōu)化

4.1關(guān)系系統(tǒng)4.2查詢優(yōu)化處理數(shù)據(jù)庫系統(tǒng)原理第四頁，共五十二頁，編輯于2023年，星期五第一節(jié)關(guān)系系統(tǒng)關(guān)系模型關(guān)系數(shù)據(jù)結(jié)構(gòu)域及域上定義的關(guān)系關(guān)系操作關(guān)系代數(shù)：并、交、差、廣義笛卡爾積、選擇、投影、連接、除等關(guān)系完整性實(shí)體完整性、參照完整性、用戶自己定義的完整性關(guān)系系統(tǒng)的查詢優(yōu)化第五頁，共五十二頁，編輯于2023年，星期五關(guān)系系統(tǒng)(續(xù))關(guān)系系統(tǒng)的定義能夠在一定程度上支持關(guān)系模型的數(shù)據(jù)庫管理系統(tǒng)是關(guān)系系統(tǒng)。定義4.1

一個(gè)系統(tǒng)是關(guān)系系統(tǒng)當(dāng)且僅當(dāng)它：支持關(guān)系數(shù)據(jù)庫（即關(guān)系數(shù)據(jù)結(jié)構(gòu)）。從用戶觀點(diǎn)看，數(shù)據(jù)庫是由表構(gòu)成的，并且系統(tǒng)中只有表這種結(jié)構(gòu)。支持選擇、投影和（自然）連接運(yùn)算。對(duì)這些運(yùn)算不要求用戶定義任何物理存取路徑。關(guān)系系統(tǒng)的查詢優(yōu)化第六頁，共五十二頁，編輯于2023年，星期五二、關(guān)系系統(tǒng)的分類分類依據(jù)─依據(jù)關(guān)系系統(tǒng)支持關(guān)系模型的程度不同。分類S：結(jié)構(gòu)I：完整性M：數(shù)據(jù)操縱關(guān)系系統(tǒng)的查詢優(yōu)化第七頁，共五十二頁，編輯于2023年，星期五數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操縱數(shù)據(jù)完整性表式結(jié)構(gòu)表××最小關(guān)系系統(tǒng)表選擇、投影、連接×關(guān)系完備的系統(tǒng)表全部×全關(guān)系系統(tǒng)全部全部完全支持關(guān)系系統(tǒng)的分類（續(xù)）關(guān)系系統(tǒng)的查詢優(yōu)化第八頁，共五十二頁，編輯于2023年，星期五第二節(jié)關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系系統(tǒng)的查詢處理查詢優(yōu)化概述查詢優(yōu)化問題的提出關(guān)系代數(shù)的優(yōu)化規(guī)則關(guān)系代數(shù)的優(yōu)化算法查詢優(yōu)化的一般步驟關(guān)系系統(tǒng)的查詢優(yōu)化第九頁，共五十二頁，編輯于2023年，星期五一、關(guān)系系統(tǒng)的查詢處理1、查詢處理步驟關(guān)系系統(tǒng)的查詢優(yōu)化查詢語句轉(zhuǎn)化成關(guān)系代數(shù)表達(dá)式第十頁，共五十二頁，編輯于2023年，星期五關(guān)系系統(tǒng)的查詢處理（續(xù)）2、實(shí)現(xiàn)查詢操作的算法示例例4.1選擇操作的實(shí)現(xiàn)Select*FromStudentWhere<條件表達(dá)式>;<條件表達(dá)式>的幾種情況：C1:Sno=‘95001’C2:Sage<20C3:Sdept=‘CS’AndSage>20①簡(jiǎn)單的全表掃描方法對(duì)查詢的基本表順序掃描，逐一檢查每個(gè)元組是否滿足選擇條件，把滿足條件的元組作為結(jié)果輸出。關(guān)系系統(tǒng)的查詢優(yōu)化第十一頁，共五十二頁，編輯于2023年，星期五

選擇操作的實(shí)現(xiàn)示例（續(xù)）②索引掃描方法

通過索引先找到滿足條件的元組主碼或元組指針，再通過元組指針直接在查詢的基本表中找到元組。

【C1例】Sno=’95001’，并且在Sno上有索引，則可以使用索引得到Sno為’95001’元組的指針，然后通過元組指針在Student表中檢索到該學(xué)生。

【C2例】Sage>20，并且Sage上有B+樹索引，則可以使用B+樹索引找到Sage=20的索引項(xiàng)，以此為入口點(diǎn)在B+樹的順序集上得到Sage>20的所有元組指針，然后通過這些元組指針到Student表中檢索到所有年齡大于20的學(xué)生。關(guān)系系統(tǒng)的查詢優(yōu)化第十二頁，共五十二頁，編輯于2023年，星期五Sage>20的一組元組指針【C3例】Sdept=‘CS’AndSage>20，如果Sdept和Sage上都有索引，則：

另一種算法：關(guān)系系統(tǒng)的查詢優(yōu)化

選擇操作的實(shí)現(xiàn)示例（續(xù)）Sdept=‘CS’的一組元組指針Sdept=‘CS’的一組元組指針Sdept=‘CS’的一組元組指針Sage>20的一組元組指針指針交集滿足條件的學(xué)生信息Student表Student表Sage>20的一組元組指針滿足條件的學(xué)生信息滿足Sdept=‘CS’條件的元組信息第十三頁，共五十二頁，編輯于2023年，星期五實(shí)現(xiàn)查詢操作的算法示例（續(xù)）例4.2連接操作的實(shí)現(xiàn)

Select*FromStudent,SCWhereStudent.Sno=SC.Sno①嵌套循環(huán)方法

關(guān)系系統(tǒng)的查詢優(yōu)化學(xué)號(hào)Sno姓名Sname性別Ssex年齡Sage所在系Sdept95002950019500395004李勇劉晨王敏張立男女女男20191819CSISMAISStudent學(xué)號(hào)Sno課程號(hào)Cno成績(jī)Grade9500195002950019500295002123239290888580SC對(duì)Student中的每一個(gè)元組，檢查SC中的每一個(gè)元組，若在連接屬性上相等，則連接輸出，直到Student中的元組處理完為止。第十四頁，共五十二頁，編輯于2023年，星期五連接操作的實(shí)現(xiàn)（續(xù)）②排序-合并方法學(xué)號(hào)Sno姓名Sname性別Ssex年齡Sage所在系Sdept95001950029500395004李勇劉晨王敏張立男女女男20191819CSISMAISStudent學(xué)號(hào)Sno課程號(hào)Cno成績(jī)Grade9500195001950019500295002123239285889080SC關(guān)系系統(tǒng)的查詢優(yōu)化取Student表中第一個(gè)Sno，依次掃描SC表中具有相同Sno的元組，把他們連接起來；當(dāng)掃描到Sno不相同的第一個(gè)SC元組時(shí)，返回Student表掃描它的下一個(gè)元組，再掃描SC表中具有相同Sno的元組，把它們連接起來。第十五頁，共五十二頁，編輯于2023年，星期五二、查詢優(yōu)化概述

查詢優(yōu)化是從眾多可供選擇的執(zhí)行策略和操作算法中，選擇一個(gè)高效執(zhí)行的查詢處理策略。

按照優(yōu)化的層次可以分為代數(shù)優(yōu)化和物理優(yōu)化。代數(shù)優(yōu)化：是指關(guān)系代數(shù)表達(dá)式的優(yōu)化，按照一定的規(guī)則，改變代數(shù)表達(dá)式中操作的次序和組合，使查詢執(zhí)行效率更高。物理優(yōu)化：則是指存取路徑和底層操作算法的選擇。關(guān)系系統(tǒng)的查詢優(yōu)化第十六頁，共五十二頁，編輯于2023年，星期五查詢優(yōu)化概述（續(xù)）目前RDBMS通過某種代價(jià)模型計(jì)算出各種查詢執(zhí)行策略的執(zhí)行代價(jià)，然后選取代價(jià)最小的執(zhí)行方案。查詢的執(zhí)行開銷主要包括集中式數(shù)據(jù)庫磁盤存取塊數(shù)（I/O代價(jià)）處理機(jī)時(shí)間（CPU代價(jià)）查詢的內(nèi)存開銷分布式數(shù)據(jù)庫I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)+通信代價(jià)查詢優(yōu)化的總目標(biāo)選擇有效策略，求得給定關(guān)系表達(dá)式的值，使得查詢代價(jià)最小。關(guān)系系統(tǒng)的查詢優(yōu)化第十七頁，共五十二頁，編輯于2023年，星期五三、查詢優(yōu)化問題的提出例4.3：求選修了2號(hào)課程的學(xué)生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.SnoANDSC.Cno='2';系統(tǒng)可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式來完成這一查詢。

關(guān)系系統(tǒng)的查詢優(yōu)化第十八頁，共五十二頁，編輯于2023年，星期五查詢優(yōu)化問題的提出（續(xù)）假設(shè)1外存：

Student表中有1000條學(xué)生記錄

SC表中有10000條選課記錄 其中選修2號(hào)課程的選課記錄為50條假設(shè)2內(nèi)存： 一個(gè)內(nèi)存塊可以裝10個(gè)Student元組或100個(gè)SC元組 一個(gè)內(nèi)存塊可以裝10個(gè)Student和SC的連接結(jié)果元組 內(nèi)存中一次可以存放5塊Student元組、1塊SC元組和若干塊連接結(jié)果元組假設(shè)3讀寫速度：20塊/秒假設(shè)4連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法關(guān)系系統(tǒng)的查詢優(yōu)化第十九頁，共五十二頁，編輯于2023年，星期五1、第一種方法關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化問題的提出（續(xù)）

內(nèi)存塊100Student表SC表…………內(nèi)存塊1內(nèi)存塊2內(nèi)存塊3內(nèi)存塊4內(nèi)存塊5一般連接的方法：內(nèi)存塊1內(nèi)存塊2內(nèi)存塊100讀Student表100塊，讀SC表20遍，每遍100塊。第二十頁，共五十二頁，編輯于2023年，星期五①計(jì)算廣義笛卡爾集Student×SC讀取總塊數(shù)=讀Student表塊數(shù)+讀SC表遍數(shù)*每遍塊數(shù)

=1000/10+(1000/(10×5))×(10000/100)=100+20×100=2100讀數(shù)據(jù)時(shí)間=2100/20=105秒中間結(jié)果大?。ㄟB接后的元組數(shù)）=1000*10000=107

(1千萬條元組)寫中間結(jié)果時(shí)間=10000000/10/20=50000秒②選擇操作讀數(shù)據(jù)時(shí)間=50000秒

③投影操作

總時(shí)間=105＋50000＋50000秒=100105秒=27.8小時(shí)關(guān)系系統(tǒng)的查詢優(yōu)化第一種方法（續(xù)）第二十一頁，共五十二頁，編輯于2023年，星期五2、第二種方法①計(jì)算自然連接

讀取總塊數(shù)=2100塊

讀數(shù)據(jù)時(shí)間=2100/20=105秒 中間結(jié)果大小=10000（減少1000倍） 寫中間結(jié)果時(shí)間=10000/10/20=50秒

②選擇操作

讀取中間文件塊，執(zhí)行選擇運(yùn)算，花費(fèi)時(shí)間50秒

③投影操作

把第二步的結(jié)果投影輸出

總時(shí)間＝(105＋50＋50)秒＝205秒=3.4分

關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化問題的提出（續(xù)）第二十二頁，共五十二頁，編輯于2023年，星期五3、第三種方法Q3=πSname(Student

SC.Cno=‘2’(SC))①選擇操作

讀SC表總塊數(shù)=10000/100=100塊 讀數(shù)據(jù)時(shí)間=100/20=5秒

中間結(jié)果大小=50條（滿足條件的元組只有50個(gè)），不必使用中間文件。②自然連接操作 讀Student表總塊數(shù)=1000/10=100塊（只需讀一遍該表） 讀數(shù)據(jù)時(shí)間=100/20=5秒

③投影操作

把連接結(jié)果投影輸出。

總時(shí)間＝5＋5秒＝10秒關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化問題的提出（續(xù)）第二十三頁，共五十二頁，編輯于2023年，星期五四、關(guān)系代數(shù)的優(yōu)化規(guī)則關(guān)系代數(shù)優(yōu)化策略是通過對(duì)關(guān)系代數(shù)表達(dá)式的等價(jià)變換來提高查詢效率。關(guān)系代數(shù)表達(dá)式等價(jià)指把相同的關(guān)系代入兩個(gè)關(guān)系代數(shù)表達(dá)式所得到的結(jié)果是相同的。兩個(gè)關(guān)系表達(dá)式E1和E2是等價(jià)的，記為E1≡E2。關(guān)系系統(tǒng)的查詢優(yōu)化第二十四頁，共五十二頁，編輯于2023年，星期五關(guān)系代數(shù)的優(yōu)化規(guī)則（續(xù)）1、常用的等價(jià)變換規(guī)則設(shè)E1、E2是關(guān)系代數(shù)表達(dá)式，F(xiàn)是條件表達(dá)式。（1）連接、笛卡爾積交換律E1×E2≡E2×E1

E1E2≡E2E1E1E2≡E2E1（2）連接、笛卡爾積的結(jié)合律(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)

關(guān)系系統(tǒng)的查詢優(yōu)化FFF1F1F2F2第二十五頁，共五十二頁，編輯于2023年，星期五常用的等價(jià)變換規(guī)則（續(xù)）（3）投影的級(jí)聯(lián)（串接定律）假設(shè)：

1)E是關(guān)系代數(shù)表達(dá)式

2)Ai(i=1，2，…，n),Bj(j=l，2，…，m)是屬性名

3){A1,A2,…,An}是{Bl，B2，…，Bm}的子集。則：（4）選擇的級(jí)聯(lián)（串接定律）選擇的串接律說明選擇條件可以合并。關(guān)系系統(tǒng)的查詢優(yōu)化第二十六頁，共五十二頁，編輯于2023年，星期五關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）（5）選擇與投影的交換律假設(shè):選擇條件F只涉及屬性A1，…，An假設(shè):F中有不屬于A1,…,An的屬性B1,…,Bm

關(guān)系系統(tǒng)的查詢優(yōu)化第二十七頁，共五十二頁，編輯于2023年，星期五關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）（6）選擇與笛卡爾積的交換律假設(shè)：F中涉及的屬性都是E1中的屬性，則

假設(shè)：F=F1∧F2，并且F1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性，則由上面的等價(jià)變換規(guī)則1，4，6可推出 假設(shè)：F=F1∧F2，F(xiàn)1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性，則

關(guān)系系統(tǒng)的查詢優(yōu)化F

(

E1×E2)≡F1∧F2(E1×E2)≡F2

(F1

(E1×E2))

≡F2

(F1

(E1)×E2)F

(

E1×E2)≡F1∧F2(E1×E2)≡F1

(F2

(E1×E2))

≡F1

(F2

(E2)×E1)

≡F1

(E1)×F2

(E2)

第二十八頁，共五十二頁，編輯于2023年，星期五關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）（7）選擇與并的分配律 假設(shè)：E=E1∪E2，E1，E2有相同的屬性名

（8）選擇與差運(yùn)算的分配律 假設(shè)：E1與E2有相同的屬性名（9）選擇對(duì)自然連接的分配律

假設(shè)：F只涉及E1和E2的公共屬性

F(E1

E2)≡F(E1)F(E2)

關(guān)系系統(tǒng)的查詢優(yōu)化第二十九頁，共五十二頁，編輯于2023年，星期五關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）（10）投影與笛卡爾積的分配律 假設(shè)：E1和E2是兩個(gè)關(guān)系表達(dá)式，A1，…，An是E1的屬性，B1，…，Bm是E2的屬性，則（11）投影與并的分配 假設(shè)：E1和E2

有相同的屬性名，則

關(guān)系系統(tǒng)的查詢優(yōu)化第三十頁，共五十二頁，編輯于2023年，星期五關(guān)系代數(shù)等價(jià)變換規(guī)則小結(jié)1-2:連接、笛卡爾積的交換律、結(jié)合律3：投影運(yùn)算的合并或分解4：選擇運(yùn)算的合并或分解5-6：選擇運(yùn)算與其他運(yùn)算的交換律7-9：選擇運(yùn)算與其他運(yùn)算的分配律10-11：投影運(yùn)算與其他運(yùn)算的分配律關(guān)系系統(tǒng)的查詢優(yōu)化第三十一頁，共五十二頁，編輯于2023年，星期五2、關(guān)系代數(shù)的優(yōu)化規(guī)則（1）選擇運(yùn)算應(yīng)盡可能先做。目的：減少中間結(jié)果大?。?）投影運(yùn)算和選擇運(yùn)算同時(shí)做。目的：避免重復(fù)掃描關(guān)系（3）將投影運(yùn)算與其前面或后面的雙目運(yùn)算結(jié)合。目的：減少掃描關(guān)系的遍數(shù)。關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）第三十二頁，共五十二頁，編輯于2023年，星期五查詢優(yōu)化的一般準(zhǔn)則（續(xù)）（4）把某些選擇同在它前面執(zhí)行的笛卡兒積結(jié)合起來成為一個(gè)連接運(yùn)算。例：Student.Sno=SC.Sno

(Student×SC)

StudentSC

例4.3中：關(guān)系系統(tǒng)的查詢優(yōu)化第三十三頁，共五十二頁，編輯于2023年，星期五（5）提取公共子表達(dá)式。一個(gè)關(guān)系表達(dá)式如果包含多個(gè)相同的子表達(dá)式，那么只需計(jì)算一次公共表達(dá)式，把所得的中間結(jié)果存起來，以后每遇到這種子表達(dá)式，只需檢索中間結(jié)果而無須重新計(jì)算。關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化的一般準(zhǔn)則（續(xù)）第三十四頁，共五十二頁，編輯于2023年，星期五五、關(guān)系代數(shù)的優(yōu)化算法1、查詢樹在查詢優(yōu)化過程中，查詢語句被轉(zhuǎn)換為更適合處理的內(nèi)部表示，通常這種內(nèi)部表示表現(xiàn)為查詢樹的形式，它的構(gòu)造方法如下:（1）每一個(gè)葉節(jié)點(diǎn)對(duì)應(yīng)于查詢中的基本關(guān)系;（2）非葉節(jié)點(diǎn)是關(guān)系代數(shù)運(yùn)算產(chǎn)生的中間關(guān)系;（3）樹的根節(jié)點(diǎn)代表查詢結(jié)果;（4）運(yùn)算按照從葉到根的順序執(zhí)行。關(guān)系系統(tǒng)的查詢優(yōu)化第三十五頁，共五十二頁，編輯于2023年，星期五查詢樹（續(xù)）例4.3中的關(guān)系代數(shù)表達(dá)式：轉(zhuǎn)化為查詢樹：關(guān)系系統(tǒng)的查詢優(yōu)化第三十六頁，共五十二頁，編輯于2023年，星期五關(guān)系代數(shù)的優(yōu)化算法（續(xù)）2、關(guān)系表達(dá)式的優(yōu)化算法輸入：一個(gè)關(guān)系表達(dá)式的查詢樹。輸出：優(yōu)化的查詢樹。方法：1．分解選擇運(yùn)算。2．通過交換選擇運(yùn)算，將其盡可能移到葉端。3．通過交換投影運(yùn)算，將其盡可能移到葉端。4．合并串接的選擇和投影，以便能同時(shí)執(zhí)行或在一次掃描中完成。5．對(duì)內(nèi)結(jié)點(diǎn)分組。6．生成程序。關(guān)系系統(tǒng)的查詢優(yōu)化第三十七頁，共五十二頁，編輯于2023年，星期五關(guān)系代數(shù)的優(yōu)化算法(續(xù))（1）分解選擇運(yùn)算。

利用規(guī)則4把形如F1∧F2∧…∧Fn(E)變換為

F1(F2(…(Fn(E))…))（2）通過交換選擇運(yùn)算，將其每個(gè)選擇盡可能移到葉端。對(duì)每一個(gè)選擇，利用規(guī)則4～9盡可能把它移到樹的葉端。（3）通過交換投影運(yùn)算，將其盡可能移到葉端。

對(duì)每一個(gè)投影利用規(guī)則3，5，l0，11中的一般形式盡可能把它移向樹的葉端。關(guān)系系統(tǒng)的查詢優(yōu)化第三十八頁，共五十二頁，編輯于2023年，星期五關(guān)系代數(shù)表達(dá)式的優(yōu)化算法(續(xù))（4）合并串接的選擇和投影，以便能同時(shí)執(zhí)行或在一次掃描中完成。利用規(guī)則3～5把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。使多個(gè)選擇或投影能同時(shí)執(zhí)行,或在一次掃描中全部完成。盡管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。關(guān)系系統(tǒng)的查詢優(yōu)化第三十九頁，共五十二頁，編輯于2023年，星期五關(guān)系代數(shù)表達(dá)式的優(yōu)化算法(續(xù))（5）對(duì)內(nèi)結(jié)點(diǎn)分組把上述得到的語法樹的內(nèi)節(jié)點(diǎn)分組。每一雙目運(yùn)算(×,,∪,-)和它所有的直接祖先（,π運(yùn)算）為一組。如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組，但當(dāng)雙目運(yùn)算是笛卡爾積(×)而且其后的選擇不能與它結(jié)合為等值連接時(shí)除外。把這些單目運(yùn)算單獨(dú)分為一組。關(guān)系系統(tǒng)的查詢優(yōu)化第四十頁，共五十二頁，編輯于2023年，星期五關(guān)系代數(shù)表達(dá)式的優(yōu)化算法(續(xù))（6）生成程序生成一個(gè)程序，每組結(jié)點(diǎn)的計(jì)算是程序中的一步。各步的順序是任意的，只要保證任何一組的計(jì)算不會(huì)在它的后代組之前計(jì)算。

關(guān)系系統(tǒng)的查詢優(yōu)化第四十一頁，共五十二頁，編輯于2023年，星期五例4.4給出例4.3中SQL語句的代數(shù)優(yōu)化算法。（1）把SQL語句轉(zhuǎn)換成查詢樹，對(duì)應(yīng)的關(guān)系表達(dá)式為：

關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)表達(dá)式的優(yōu)化算法(續(xù))第四十二頁，共五十二頁，編輯于2023年，星期五關(guān)系代數(shù)查詢樹關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)表達(dá)式的優(yōu)化算法(續(xù))πSname

Student.Sno=SC.Sno

∧SC.Cno=2

×

StudentSC第四十三頁，共五十二頁，編輯于2023年，星期五（2）對(duì)查詢樹進(jìn)行優(yōu)化①分解選擇運(yùn)算，對(duì)應(yīng)的關(guān)系代數(shù)表達(dá)式為:

Sname(σ

Student.Sno=SC.Sno(σ

SC.Cno=2

(Student×SC)));關(guān)系系統(tǒng)的查詢優(yōu)化關(guān)系代數(shù)表達(dá)式的優(yōu)化算法(續(xù))πSname

SC.Cno=2

×

StudentSC

Student.Sno=SC.Sno

優(yōu)化后的關(guān)系代數(shù)查詢樹：第四十四頁，共五十二頁，編輯于2023年，星期五對(duì)查詢樹進(jìn)行優(yōu)化（續(xù)）②將選擇運(yùn)算下移,對(duì)應(yīng)的關(guān)系代數(shù)表達(dá)式為:π

Sname(σ

Student.Sno=SC.Sno(Student×σ

SC.Cno='2'(SC)));關(guān)系系統(tǒng)的查詢優(yōu)化優(yōu)化后的關(guān)系代數(shù)查詢樹：πSname

×

StudentSCSC.Cno=2

Student.Sno=SC.Sno

第四十五頁，共五十二頁，編輯于2023年，星期五③將選擇/笛卡兒積變?yōu)樽匀贿B接，對(duì)應(yīng)