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

數(shù)據(jù)庫(kù)技術(shù)中國(guó)科學(xué)技術(shù)大學(xué)網(wǎng)絡(luò)學(xué)院闞衛(wèi)華第四章關(guān)系系統(tǒng)及其查詢優(yōu)化數(shù)據(jù)庫(kù)技術(shù)中國(guó)科學(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é)注：這一章包括兩個(gè)方面的內(nèi)容：一是關(guān)系系統(tǒng)(關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的簡(jiǎn)稱)，二是關(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ù)庫(kù)管理系統(tǒng)是關(guān)系系統(tǒng)。關(guān)系模型中并非每一部分都是同等重要的。不苛求一個(gè)實(shí)際的關(guān)系系統(tǒng)必須完全支持關(guān)系模型；也不苛求完全支持關(guān)系模型的才能稱為關(guān)系系統(tǒng)。10/7/202334.1關(guān)系系統(tǒng)能夠在一定程度上支持關(guān)系模型的數(shù)據(jù)庫(kù)管理系統(tǒng)是關(guān)系系統(tǒng)與關(guān)系模型關(guān)系系統(tǒng)與關(guān)系模型是兩個(gè)密切相關(guān)而又不同的概念。關(guān)系數(shù)據(jù)結(jié)構(gòu)域及域上定義的關(guān)系。關(guān)系操作并、交、差、廣義笛卡爾積、選擇、投影、連接、除等。關(guān)系完整性實(shí)體完整性、參照完整性、用戶自己定義的完整性。10/7/20234關(guān)系系統(tǒng)與關(guān)系模型關(guān)系系統(tǒng)與關(guān)系模型是兩個(gè)密切相關(guān)而又不同的4.4.1關(guān)系系統(tǒng)的定義

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

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

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

10/7/202354.4.1關(guān)系系統(tǒng)的定義一個(gè)數(shù)據(jù)庫(kù)管理系統(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)，但沒(méi)有選擇、投影和連接運(yùn)算功能的系統(tǒng)仍不能算作關(guān)系系統(tǒng)。原因：不能提高用戶的生產(chǎn)率。支持選擇、投影和連接運(yùn)算，但要求定義物理存取路徑，這種系統(tǒng)也不能算作真正的關(guān)系系統(tǒng)；原因：降低或喪失了數(shù)據(jù)的物理獨(dú)立性。選擇、投影、連接運(yùn)算是最有用的運(yùn)算，能解決絕大部分的實(shí)際問(wèn)題。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)不支持集合級(jí)的操作。表式系統(tǒng)不能算關(guān)系系統(tǒng)[倒排表系統(tǒng)屬于這一類]。⒉(最小)關(guān)系系統(tǒng)

僅支持關(guān)系數(shù)據(jù)結(jié)構(gòu)和三種關(guān)系操作[選擇、投影、連接關(guān)系操作],許多微機(jī)關(guān)系數(shù)據(jù)庫(kù)系統(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ù)等價(jià))。20世紀(jì)90年代初的許多關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)屬于這一類。⒋全關(guān)系系統(tǒng)

支持關(guān)系模型的所有特征。即不僅是關(guān)系上完備的而且支持?jǐn)?shù)據(jù)結(jié)構(gòu)中域的概念，支持實(shí)體完整性和參照完整性。目前，大多數(shù)關(guān)系系統(tǒng)已不同程度上接近或達(dá)到了這個(gè)標(biāo)準(zhǔn)。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ù)庫(kù)系統(tǒng)的查詢優(yōu)化4.2.1關(guān)系系統(tǒng)及其查詢優(yōu)化4.2.2查詢優(yōu)化的必要性4.2.3查詢優(yōu)化的一般準(zhǔn)則4.2.4關(guān)系代數(shù)等價(jià)變換規(guī)則4.2.5關(guān)系代數(shù)表達(dá)式的優(yōu)化算法4.2.6優(yōu)化的一般步驟10/7/2023104.2關(guān)系數(shù)據(jù)庫(kù)系統(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ù)庫(kù)系統(tǒng)和非過(guò)程化的SQL語(yǔ)言能夠取得巨大成功，關(guān)鍵是得益于查詢優(yōu)化技術(shù)的發(fā)展。關(guān)系查詢優(yōu)化極大地影響了RDBMS的性能。

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

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

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

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

用SQL語(yǔ)言表達(dá): 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ù)庫(kù)中有Student:1000條學(xué)生記錄,SC:10000條選課記錄,其中選修2號(hào)課程的選課記錄:50條。假設(shè)2：一個(gè)內(nèi)存塊裝:10個(gè)Student元組,或100個(gè)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ù)庫(kù)中有執(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ù)時(shí)間=2100/20=105秒。10/7/202321執(zhí)行策略1Q1＝ПＳname(бStudent.Sno=SC不同的執(zhí)行策略,考慮I/O時(shí)間

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

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

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

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

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

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

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

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

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

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

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

③П

將②的結(jié)果投影輸出.總時(shí)間＝(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í)行選擇運(yùn)算) 讀SC表總塊數(shù)=10000/100=100塊

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

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

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

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

③П

將連接的結(jié)果投影輸出.總時(shí)間＝(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ù)時(shí)間:幾秒

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

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

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

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

E1

FE2≡E2

FE1

10/7/202331常用的等價(jià)變換規(guī)則10/6/202331關(guān)系代數(shù)等價(jià)變換規(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ù)等價(jià)變換規(guī)則（續(xù)）2.連接、笛卡爾積的結(jié)合律10/關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）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}的子集。10/7/202333關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）3.投影的串接定律10/6/2關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）4.選擇的串接定律

бF1（б

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

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

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

E2)

10/7/202336關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）6.選擇與笛卡爾積的分配律10關(guān)系代數(shù)等價(jià)變換規(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ù)等價(jià)變換規(guī)則（續(xù)）(3)假設(shè)：F=F1關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）7.選擇與并的分配 假設(shè)：E=E1∪E2，E1，E2有相同的屬性名 бF(E1∪E2)≡бF(E1)∪бF(E2)

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

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

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ù)等價(jià)變換規(guī)則（續(xù)）9.投影與笛卡爾積的分配10關(guān)系代數(shù)等價(jià)變換規(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ù)等價(jià)變換規(guī)則（續(xù)）l0.投影與并的分配10/6/2＊小結(jié)1-2:連接、笛卡爾積的交換律、結(jié)合律3：合并或分解投影運(yùn)算4：合并或分解選擇運(yùn)算5-8：選擇運(yùn)算與其他運(yùn)算交換（分配）5，9，10：投影運(yùn)算與其他運(yùn)算交換（分配）10/7/202341＊小結(jié)1-2:連接、笛卡爾積的交換律、結(jié)合律10/6/4.2.5關(guān)系代數(shù)表達(dá)式的優(yōu)化算法算法：關(guān)系表達(dá)式的優(yōu)化輸入：一個(gè)關(guān)系表達(dá)式的語(yǔ)法樹(shù)。輸出：計(jì)算該表達(dá)式的程序。方法：（1）分解選擇運(yùn)算利用規(guī)則4把形如бF1∧F2∧…∧Fn(E)變換為бF1(бF2(…(бFn(E))…))10/7/2023424.2.5關(guān)系代數(shù)表達(dá)式的優(yōu)化算法算法：關(guān)系表達(dá)式的優(yōu)化1關(guān)系代數(shù)表達(dá)式的優(yōu)化算法(續(xù))（2）通過(guò)交換選擇運(yùn)算，將其盡可能移到葉端對(duì)每一個(gè)選擇，利用規(guī)則4～8盡可能把它移到樹(shù)的葉端。

（3）通過(guò)交換投影運(yùn)算，將其盡可能移到葉端

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

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

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

10/7/202346關(guān)系代數(shù)表達(dá)式的優(yōu)化算法(續(xù))（6）生成程序10/6/204.2.6優(yōu)化的一般步驟1．把查詢轉(zhuǎn)換成某種內(nèi)部表示(通常用的內(nèi)部表示是語(yǔ)法樹(shù))；2．代數(shù)優(yōu)化：把語(yǔ)法樹(shù)轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式（利用優(yōu)化算法，把原始的語(yǔ)法樹(shù)轉(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)化了的語(yǔ)法樹(shù)，計(jì)算關(guān)系表達(dá)式值的時(shí)候，要充分考慮索引、數(shù)據(jù)的存儲(chǔ)分布等存取路徑，利用它們進(jìn)一步改善查詢效率。這就要求優(yōu)化器去查找數(shù)據(jù)字典，獲得當(dāng)前數(shù)據(jù)庫(kù)狀態(tài)的信息）；4．生成查詢計(jì)劃，選擇代價(jià)最小的。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)語(yǔ)法樹(shù)結(jié)果project(Sname)

select(SC.Cno=

2

)

jo