功能上與關(guān)系代數(shù)等價-課件

數(shù)據(jù)庫技術(shù)中國科學(xué)技術(shù)大學(xué)網(wǎng)絡(luò)學(xué)院闞衛(wèi)華第四章關(guān)系系統(tǒng)及其查詢優(yōu)化數(shù)據(jù)庫技術(shù)中國科學(xué)技術(shù)大學(xué)網(wǎng)絡(luò)學(xué)院闞衛(wèi)華第四章關(guān)系系統(tǒng)第四章

關(guān)系系統(tǒng)及其查詢優(yōu)化4.1關(guān)系系統(tǒng)4.2關(guān)系系統(tǒng)的查詢優(yōu)化4.3小結(jié)注：這一章包括兩個方面的內(nèi)容：一是關(guān)系系統(tǒng)(關(guān)系數(shù)據(jù)庫系統(tǒng)的簡稱)，二是關(guān)系系統(tǒng)的查詢優(yōu)化。主要討論關(guān)系系統(tǒng)的定義和分類；討論關(guān)系系統(tǒng)中查詢優(yōu)化的概念、查詢優(yōu)化的基本原理和技術(shù)。10/7/20232第四章關(guān)系系統(tǒng)及其查詢優(yōu)化4.1關(guān)系系統(tǒng)注：這一章包括4.1關(guān)系系統(tǒng)能夠在一定程度上支持關(guān)系模型的數(shù)據(jù)庫管理系統(tǒng)是關(guān)系系統(tǒng)。關(guān)系模型中并非每一部分都是同等重要的。不苛求一個實際的關(guān)系系統(tǒng)必須完全支持關(guān)系模型；也不苛求完全支持關(guān)系模型的才能稱為關(guān)系系統(tǒng)。10/7/202334.1關(guān)系系統(tǒng)能夠在一定程度上支持關(guān)系模型的數(shù)據(jù)庫管理系統(tǒng)是關(guān)系系統(tǒng)與關(guān)系模型關(guān)系系統(tǒng)與關(guān)系模型是兩個密切相關(guān)而又不同的概念。關(guān)系數(shù)據(jù)結(jié)構(gòu)域及域上定義的關(guān)系。關(guān)系操作并、交、差、廣義笛卡爾積、選擇、投影、連接、除等。關(guān)系完整性實體完整性、參照完整性、用戶自己定義的完整性。10/7/20234關(guān)系系統(tǒng)與關(guān)系模型關(guān)系系統(tǒng)與關(guān)系模型是兩個密切相關(guān)而又不同的4.4.1關(guān)系系統(tǒng)的定義

一個數(shù)據(jù)庫管理系統(tǒng)可定義為關(guān)系系統(tǒng)，當(dāng)且僅當(dāng)它至少支持(對關(guān)系系統(tǒng)的最低要求)：1.支持關(guān)系數(shù)據(jù)庫（即關(guān)系數(shù)據(jù)結(jié)構(gòu)）。

從用戶觀點看，數(shù)據(jù)庫由表構(gòu)成，并且系統(tǒng)中只有表這一種結(jié)構(gòu)。

2.支持選擇、投影和（自然）連接運算，對這些運算不必要求用戶定義任何物理存取路徑。

10/7/202354.4.1關(guān)系系統(tǒng)的定義一個數(shù)據(jù)庫管理系統(tǒng)關(guān)系系統(tǒng)的定義（續(xù)）不支持關(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)；原因：降低或喪失了數(shù)據(jù)的物理獨立性。選擇、投影、連接運算是最有用的運算，能解決絕大部分的實際問題。10/7/20236關(guān)系系統(tǒng)的定義（續(xù)）不支持關(guān)系數(shù)據(jù)結(jié)構(gòu)的系統(tǒng)顯然不能稱為4.1.2關(guān)系系統(tǒng)的分類分類依據(jù)：支持關(guān)系模型的程度分類⒈表式系統(tǒng)：支持關(guān)系數(shù)據(jù)結(jié)構(gòu)(即表)

這類系統(tǒng)不支持集合級的操作。表式系統(tǒng)不能算關(guān)系系統(tǒng)[倒排表系統(tǒng)屬于這一類]。⒉(最小)關(guān)系系統(tǒng)

僅支持關(guān)系數(shù)據(jù)結(jié)構(gòu)和三種關(guān)系操作[選擇、投影、連接關(guān)系操作],許多微機關(guān)系數(shù)據(jù)庫系統(tǒng)[如FoxBASE,FoxPro等]就屬于這一類。

10/7/202374.1.2關(guān)系系統(tǒng)的分類分類依據(jù)：支持關(guān)系模型的程度10/關(guān)系系統(tǒng)的分類（續(xù)）

⒊關(guān)系完備的系統(tǒng)

支持關(guān)系數(shù)據(jù)結(jié)構(gòu)和所有的關(guān)系代數(shù)操作(功能上與關(guān)系代數(shù)等價)。20世紀90年代初的許多關(guān)系數(shù)據(jù)庫管理系統(tǒng)屬于這一類。⒋全關(guān)系系統(tǒng)

支持關(guān)系模型的所有特征。即不僅是關(guān)系上完備的而且支持數(shù)據(jù)結(jié)構(gòu)中域的概念，支持實體完整性和參照完整性。目前，大多數(shù)關(guān)系系統(tǒng)已不同程度上接近或達到了這個標準。10/7/20238關(guān)系系統(tǒng)的分類（續(xù)）⒊關(guān)系完備的系統(tǒng)10/6/20238關(guān)系系統(tǒng)的分類（續(xù)）

數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作完整性表式系統(tǒng)表

(最小)關(guān)系系統(tǒng)表選擇、投影、連接

關(guān)系完備的系統(tǒng)表

全關(guān)系系統(tǒng)

10/7/20239關(guān)系系統(tǒng)的分類（續(xù)）

數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作完整性表式系統(tǒng)表4.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化4.2.1關(guān)系系統(tǒng)及其查詢優(yōu)化4.2.2查詢優(yōu)化的必要性4.2.3查詢優(yōu)化的一般準則4.2.4關(guān)系代數(shù)等價變換規(guī)則4.2.5關(guān)系代數(shù)表達式的優(yōu)化算法4.2.6優(yōu)化的一般步驟10/7/2023104.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化4.2.1關(guān)系系統(tǒng)及其查詢4.2.1關(guān)系系統(tǒng)及其查詢優(yōu)化查詢優(yōu)化的必要性關(guān)系數(shù)據(jù)庫系統(tǒng)和非過程化的SQL語言能夠取得巨大成功，關(guān)鍵是得益于查詢優(yōu)化技術(shù)的發(fā)展。關(guān)系查詢優(yōu)化極大地影響了RDBMS的性能。

查詢優(yōu)化的可能性關(guān)系數(shù)據(jù)語言的級別很高，使DBMS可以從關(guān)系表達式中分析查詢語義。

10/7/2023114.2.1關(guān)系系統(tǒng)及其查詢優(yōu)化查詢優(yōu)化的必要性10/6/由DBMS進行查詢優(yōu)化的好處用戶不必考慮如何最好地表達查詢以獲得較好的效率；系統(tǒng)可以比用戶程序的優(yōu)化做得更好：(1)優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息，例如關(guān)系中的元組數(shù)、關(guān)系中的每個屬性值的分布情況等。優(yōu)化器可以根據(jù)這些信息選擇有效地執(zhí)行計劃，而用戶程序則難以獲得這些信息。10/7/202312由DBMS進行查詢優(yōu)化的好處用戶不必考慮如何最好地表達查詢以由DBMS進行查詢優(yōu)化的好處（續(xù)）(2)如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了，系統(tǒng)可以自動對查詢進行重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計劃。在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實際應(yīng)用中往往是不太可能的。10/7/202313由DBMS進行查詢優(yōu)化的好處（續(xù)）(2)如果數(shù)據(jù)庫的物理統(tǒng)計由DBMS進行查詢優(yōu)化的好處（續(xù)）(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃，而程序員一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自動優(yōu)化相當(dāng)于使得所有人都擁有這些優(yōu)化技術(shù)。10/7/202314由DBMS進行查詢優(yōu)化的好處（續(xù)）(3)優(yōu)化器可以考慮數(shù)百關(guān)系數(shù)據(jù)庫查詢優(yōu)化的總目標查詢優(yōu)化的總目標選擇有效的策略，求得給定關(guān)系表達式的值。(一般地)實際系統(tǒng)的查詢優(yōu)化步驟：①將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語法樹。②根據(jù)一定的等價變換規(guī)則把語法樹轉(zhuǎn)換成標準（優(yōu)化）形式。10/7/202315關(guān)系數(shù)據(jù)庫查詢優(yōu)化的總目標查詢優(yōu)化的總目標10/6/2023實際系統(tǒng)的查詢優(yōu)化步驟（續(xù)）③選擇低層的操作算法。對于語法樹中的每一個操作：計算各種執(zhí)行算法的執(zhí)行代價；選擇代價小的執(zhí)行算法。④生成查詢計劃(查詢執(zhí)行方案)查詢計劃是由一系列內(nèi)部操作組成的。這些內(nèi)部操作按一定的次序構(gòu)成查詢的一個執(zhí)行方案。

注:對于語法樹中的每一個操作,需要根據(jù)存取路徑、數(shù)據(jù)的存儲分布、存儲數(shù)據(jù)的聚簇等信息來選擇具體的執(zhí)行算法.10/7/202316實際系統(tǒng)的查詢優(yōu)化步驟（續(xù)）③選擇低層的操作算法。注實際系統(tǒng)的查詢優(yōu)化步驟（續(xù)）

通常這樣的執(zhí)行方案有多個，需要對每個執(zhí)行計劃計算代價，從中選擇代價最小的一個。在集中式關(guān)系數(shù)據(jù)庫中，計算代價時主要考慮磁盤讀寫的I/O次數(shù)，也有一些系統(tǒng)還考慮了CPU的處理時間。上述“選擇低層的操作算法”與“生成查詢計劃”兩步,實際上沒有清晰的界限,有些系統(tǒng)是作為一個步驟來處理的;目前的商品化RDBMS大多采用基于代價的優(yōu)化算法。這種方法要求優(yōu)化器充分考慮系統(tǒng)中的各種參數(shù)(如緩沖區(qū)大小、表的大小、數(shù)據(jù)的分布、存取路徑等)，通過某種代價模型計算出各種查詢執(zhí)行方案的執(zhí)行代價，然后選取代價最小的執(zhí)行方案。10/7/202317實際系統(tǒng)的查詢優(yōu)化步驟（續(xù)）通常這樣的執(zhí)行方案有多個，代價模型集中式數(shù)據(jù)庫：單用戶系統(tǒng)總代價=I/O代價+CPU代價多用戶系統(tǒng)總代價=I/O代價+CPU代價+內(nèi)存代價分布式數(shù)據(jù)庫：總代價=I/O代價+CPU代價[+內(nèi)存代價]+通信代價10/7/202318代價模型集中式數(shù)據(jù)庫：10/6/2023184.2.2查詢優(yōu)化的必要性例(P.159)：求選修了課程Ｃ2的學(xué)生姓名.

用SQL語言表達: SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';10/7/2023194.2.2查詢優(yōu)化的必要性例(P.159)：求選修了課程查詢優(yōu)化的必要性（續(xù)）假設(shè)1：外存：學(xué)生_數(shù)據(jù)庫中有Student:1000條學(xué)生記錄,SC:10000條選課記錄,其中選修2號課程的選課記錄:50條。假設(shè)2：一個內(nèi)存塊裝:10個Student元組,或100個SC元組,內(nèi)存中一次可以存放:5塊Student元組,1塊SC元組和若干塊連接結(jié)果元組。假設(shè)3：讀寫速度：20塊/秒。假設(shè)4：連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法。

10/7/202320查詢優(yōu)化的必要性（續(xù)）假設(shè)1：外存：學(xué)生_數(shù)據(jù)庫中有執(zhí)行策略1Q1＝ПＳname(бStudent.Sno=SC.Sno∧SC.Cno='2'(Student×SC))

①Student×SC

讀取總塊數(shù)

=讀Student表塊數(shù)(100塊)+讀SC表遍數(shù)(20遍)*每遍塊數(shù)(100塊)

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

讀數(shù)據(jù)時間=2100/20=105秒。10/7/202321執(zhí)行策略1Q1＝ПＳname(бStudent.Sno=SC不同的執(zhí)行策略,考慮I/O時間

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

寫中間結(jié)果時間=10000000/10/20=50000秒

②б(執(zhí)行選擇運算)

讀數(shù)據(jù)時間=50000秒

③П將②的結(jié)果投影輸出(所有內(nèi)存處理時間均忽略不計)總時間

=(105＋50000＋50000)秒=100105秒≈27.8小時10/7/202322不同的執(zhí)行策略,考慮I/O時間10/6/202322查詢優(yōu)化的必要性（續(xù)）執(zhí)行策略2Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))

①(計算自然連接) 讀取總塊數(shù)=2100塊

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

寫中間結(jié)果時間=10000/10/20=50秒

②б(執(zhí)行選擇運算)

讀數(shù)據(jù)時間=50秒

③П

將②的結(jié)果投影輸出.總時間＝(105＋50＋50)秒＝205秒≈3.4分10/7/202323查詢優(yōu)化的必要性（續(xù)）執(zhí)行策略2Ｑ2＝ПＳname(бSC查詢優(yōu)化的必要性（續(xù)）執(zhí)行策略3

Ｑ3＝ПSname(StudentбSC.Cno='2'(SC))

①б(執(zhí)行選擇運算) 讀SC表總塊數(shù)=10000/100=100塊

讀數(shù)據(jù)時間=100/20=5秒

中間結(jié)果大小=50條不必寫入外存(不必使用中間文件)

②(把讀入的Student元組和內(nèi)存中的SC元組作連接) 讀Student表總塊數(shù)=1000/10=100塊

讀數(shù)據(jù)時間=100/20=5秒

③П

將連接的結(jié)果投影輸出.總時間＝(5＋5)秒＝10秒10/7/202324查詢優(yōu)化的必要性（續(xù)）執(zhí)行策略3Ｑ3＝查詢優(yōu)化的必要性（續(xù)）Ｑ3_1＝ПＳname(StudentбSC.Cno='2'(SC))假設(shè)SC表在Cno上有索引，Student表在Sno上有索引

①б 讀SC表索引(讀取SC.Cno=‘2’的那些元組

)=讀SC表總塊數(shù)=50/100<1塊 讀數(shù)據(jù)時間:幾秒

中間結(jié)果大小=50條不必寫入外存10/7/202325查詢優(yōu)化的必要性（續(xù)）Ｑ3_1＝ПＳname(Studen查詢優(yōu)化的必要性（續(xù)）② 讀Student表索引= 讀Student表總塊數(shù)=50/10=5塊 讀數(shù)據(jù)時間:幾秒③П總時間<10秒10/7/202326查詢優(yōu)化的必要性（續(xù)）②10/6/2023264.2.3查詢優(yōu)化的一般準則1.選擇運算應(yīng)盡可能先做

目的：減小中間關(guān)系(在優(yōu)化策略中，這是最重要的、最基本的一條。它常常可使執(zhí)行時間降低幾個數(shù)量級，因為選擇運算一般使計算的中間結(jié)果大大減小)2.在執(zhí)行連接操作前對關(guān)系適當(dāng)進行預(yù)處理在連接屬性上建立索引(索引連接方法)在連接屬性上對關(guān)系排序(排序合并連接方法)

10/7/2023274.2.3查詢優(yōu)化的一般準則1.選擇運算應(yīng)盡可能先做查詢優(yōu)化的一般準則(續(xù))3.投影運算和選擇運算同時做目的：避免重復(fù)掃描關(guān)系(如有若干投影運算和選擇運算,并且它們都是對同一個關(guān)系操作,則可以在掃描該關(guān)系的同時完成所有的這些運算,以避免重復(fù)掃描關(guān)系)4.將投影運算與其前面或后面的雙目運算結(jié)合目的：減少掃描關(guān)系的遍數(shù)10/7/202328查詢優(yōu)化的一般準則(續(xù))3.投影運算和選擇運算同時做10/6查詢優(yōu)化的一般準則（續(xù)）5.把某些選擇運算同在它前面要執(zhí)行的笛卡爾積連接運算結(jié)合起來,成為一個連接運算,連接運算(特別是等值連接運算)要比同樣關(guān)系上的笛卡爾積節(jié)省很多時間。例：бStudent.Sno=SC.Sno(Student×SC)

StudentSC6.提取公共子表達式。10/7/202329查詢優(yōu)化的一般準則（續(xù)）5.把某些選擇運算同在它前面要執(zhí)4.2.4關(guān)系代數(shù)等價變換規(guī)則關(guān)系代數(shù)表達式等價是指用相同的關(guān)系代替兩個表達式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的。上面的優(yōu)化策略大部分都涉及到代數(shù)表達式的變換。10/7/2023304.2.4關(guān)系代數(shù)等價變換規(guī)則10/6/202330常用的等價變換規(guī)則設(shè)E1、E2等是關(guān)系代數(shù)表達式，F(xiàn)是條件表達式. l.連接、笛卡爾積交換律 E1×E2≡E2×E1 E1E2≡E2E1

E1

FE2≡E2

FE1

10/7/202331常用的等價變換規(guī)則10/6/202331關(guān)系代數(shù)等價變換規(guī)則（續(xù)）2.連接、笛卡爾積的結(jié)合律(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)

F

F

F

F10/7/202332關(guān)系代數(shù)等價變換規(guī)則（續(xù)）2.連接、笛卡爾積的結(jié)合律10/關(guān)系代數(shù)等價變換規(guī)則（續(xù)）3.投影的串接定律

π

A1,A2,

,An(π

B1,B2,

,Bm(E))≡π

A1,A2,

,An(E)假設(shè)：1) E是關(guān)系代數(shù)表達式；2) Ai(i=1，2，…，n),Bj(j=l，2，…，m)是屬性名；3){A1,A2,…,An}構(gòu)成{Bl，B2，…，Bm}的子集。10/7/202333關(guān)系代數(shù)等價變換規(guī)則（續(xù)）3.投影的串接定律10/6/2關(guān)系代數(shù)等價變換規(guī)則（續(xù)）4.選擇的串接定律

бF1（б

F2（E））≡бF1∧F2(E)選擇的串接律說明：選擇條件可以合并；這樣一次就可檢查全部條件。10/7/202334關(guān)系代數(shù)等價變換規(guī)則（續(xù)）4.選擇的串接定律10/6/20關(guān)系代數(shù)等價變換規(guī)則（續(xù)）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)))10/7/202335關(guān)系代數(shù)等價變換規(guī)則（續(xù)）5.選擇與投影的交換律10/6/關(guān)系代數(shù)等價變換規(guī)則（續(xù)）6.選擇與笛卡爾積的分配律(1)假設(shè)：F中涉及的屬性都是E1中的屬性 бF(E1×E2)≡бF(E1)×E2

(2)假設(shè)：F=F1∧F2，并且F1只涉及E1中的屬性，

F2只涉及E2中的屬性， 則由上面的等價變換規(guī)則1，4，6(1)可推出： бF(E1×E2)≡бF1(E1)×бF2(

E2)

10/7/202336關(guān)系代數(shù)等價變換規(guī)則（續(xù)）6.選擇與笛卡爾積的分配律10關(guān)系代數(shù)等價變換規(guī)則（續(xù)）(3)假設(shè)：F=F1∧F2，

F1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性， бF(E1×E2)≡бF2(бF1(E1)×E2)它使部分選擇在笛卡爾積前先做。

10/7/202337關(guān)系代數(shù)等價變換規(guī)則（續(xù)）(3)假設(shè)：F=F1關(guān)系代數(shù)等價變換規(guī)則（續(xù)）7.選擇與并的分配 假設(shè)：E=E1∪E2，E1，E2有相同的屬性名 бF(E1∪E2)≡бF(E1)∪бF(E2)

8.選擇與差運算的分配 假設(shè)：E1與E2有相同的屬性名 бF(E1-E2)≡бF(E1)-бF(E2)10/7/202338關(guān)系代數(shù)等價變換規(guī)則（續(xù)）7.選擇與并的分配10/6/20關(guān)系代數(shù)等價變換規(guī)則（續(xù)）9.投影與笛卡爾積的分配

假設(shè)：E1和E2是兩個關(guān)系表達式，

A1，…，An是E1的屬性，

B1，…，Bm是E2的屬性πA1,A2,…,An,B1,B2,…,Bm（E1×E2)≡ πA1,A2,…,An（E1)×πB1,B2,…,Bm(E2)10/7/202339關(guān)系代數(shù)等價變換規(guī)則（續(xù)）9.投影與笛卡爾積的分配10關(guān)系代數(shù)等價變換規(guī)則（續(xù)）l0.投影與并的分配 假設(shè)：E1和E2有相同的屬性名 πA1,A2,…,An(E1∪E2)≡ πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)10/7/202340關(guān)系代數(shù)等價變換規(guī)則（續(xù)）l0.投影與并的分配10/6/2＊小結(jié)1-2:連接、笛卡爾積的交換律、結(jié)合律3：合并或分解投影運算4：合并或分解選擇運算5-8：選擇運算與其他運算交換（分配）5，9，10：投影運算與其他運算交換（分配）10/7/202341＊小結(jié)1-2:連接、笛卡爾積的交換律、結(jié)合律10/6/4.2.5關(guān)系代數(shù)表達式的優(yōu)化算法算法：關(guān)系表達式的優(yōu)化輸入：一個關(guān)系表達式的語法樹。輸出：計算該表達式的程序。方法：（1）分解選擇運算利用規(guī)則4把形如бF1∧F2∧…∧Fn(E)變換為бF1(бF2(…(бFn(E))…))10/7/2023424.2.5關(guān)系代數(shù)表達式的優(yōu)化算法算法：關(guān)系表達式的優(yōu)化1關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（2）通過交換選擇運算，將其盡可能移到葉端對每一個選擇，利用規(guī)則4～8盡可能把它移到樹的葉端。

（3）通過交換投影運算，將其盡可能移到葉端

對每一個投影利用規(guī)則3，9，l0，5中的一般形式盡可能把它移向樹的葉端。10/7/202343關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（2）通過交換選擇運算，將其關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（4）合并串接的選擇和投影，以便能同時執(zhí)行或在一次掃描中完成利用規(guī)則3～5把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。使多個選擇或投影能同時執(zhí)行，或在一次掃描中全部完成。盡管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。

10/7/202344關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（4）合并串接的選擇和投影，關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（5）對內(nèi)結(jié)點分組把上述得到的語法樹的內(nèi)節(jié)點分組。每一雙目運算(×，，∪，-)和它所有的直接祖先為一組(這些直接祖先是б，π運算)。如果其后代直到葉子全是單目運算，則也將它們并入該組，但當(dāng)雙目運算是笛卡爾積(×)，而且其后的選擇不能與它結(jié)合為等值連接時除外。把這些單目運算單獨分為一組。

10/7/202345關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（5）對內(nèi)結(jié)點分組10/6/關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（6）生成程序生成一個程序，每組結(jié)點的計算是程序中的一步。各步的順序是任意的，只要保證任何一組的計算不會在它的后代組之前計算。

10/7/202346關(guān)系代數(shù)表達式的優(yōu)化算法(續(xù))（6）生成程序10/6/204.2.6優(yōu)化的一般步驟1．把查詢轉(zhuǎn)換成某種內(nèi)部表示(通常用的內(nèi)部表示是語法樹)；2．代數(shù)優(yōu)化：把語法樹轉(zhuǎn)換成標準（優(yōu)化）形式（利用優(yōu)化算法，把原始的語法樹轉(zhuǎn)換成優(yōu)化形式）；10/7/2023474.2.6優(yōu)化的一般步驟1．把查詢轉(zhuǎn)換成某種內(nèi)部表示(通常優(yōu)化的一般步驟（續(xù)）3．物理優(yōu)化：選擇低層的存取路徑（根據(jù)第2步得到的優(yōu)化了的語法樹，計算關(guān)系表達式值的時候，要充分考慮索引、數(shù)據(jù)的存儲分布等存取路徑，利用它們進一步改善查詢效率。這就要求優(yōu)化器去查找數(shù)據(jù)字典，獲得當(dāng)前數(shù)據(jù)庫狀態(tài)的信息）；4．生成查詢計劃，選擇代價最小的。10/7/202348優(yōu)化的一般步驟（續(xù)）3．物理優(yōu)化：選擇低層的存取路徑（根據(jù)第優(yōu)化的一般步驟(續(xù))（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示例(P.159;P165)：求選修了課程Ｃ2的學(xué)生姓名 SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';10/7/202349優(yōu)化的一般步驟(續(xù))（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示10/6（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示(圖例4.3)語法樹結(jié)果project(Sname)

select(SC.Cno=

2

)

jo