信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系課件

信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系數(shù)據(jù)庫(kù)系統(tǒng)概論AnIntroductiontoDatabaseSystem第九章關(guān)系查詢處理和查詢優(yōu)化AnIntroductiontoDatabaseSystem信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系數(shù)據(jù)庫(kù)系統(tǒng)概論AnIntrodu1第九章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化9.3小結(jié)AnIntroductiontoDatabaseSystem第九章關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處29.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.1.1查詢處理步驟9.1.2實(shí)現(xiàn)查詢操作的算法示例AnIntroductiontoDatabaseSystem9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.1.1查詢處理步驟An39.1.1查詢處理步驟查詢分析詞法/語(yǔ)法/語(yǔ)義分析符號(hào)名轉(zhuǎn)換查詢檢查語(yǔ)義檢查安全性檢查完整性檢查查詢優(yōu)化代數(shù)優(yōu)化物理優(yōu)化查詢執(zhí)行查詢計(jì)劃生成代碼生成AnIntroductiontoDatabaseSystem9.1.1查詢處理步驟查詢分析AnIntroductio49.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.1.1查詢處理步驟9.1.2實(shí)現(xiàn)查詢操作的算法示例AnIntroductiontoDatabaseSystem9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.1.1查詢處理步驟An59.1.2實(shí)現(xiàn)查詢操作的算法示例一選擇操作的實(shí)現(xiàn)二連接操作的實(shí)現(xiàn)AnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例一選擇操作的實(shí)現(xiàn)AnI69.1.2實(shí)現(xiàn)查詢操作的算法示例一選擇操作的實(shí)現(xiàn)1、簡(jiǎn)單的全表掃描方法2、索引(或散列)掃描方法[例1]Select*fromstudent where<條件表達(dá)式>表達(dá)式情況:C1:無(wú)條件;C2:Sno=‘200215121’;C3:Sage>20;C4:Sdept=‘CS’ANDSage>20;AnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例一選擇操作的實(shí)現(xiàn)AnI79.1.2實(shí)現(xiàn)查詢操作的算法示例1、簡(jiǎn)單的全表掃描方法AnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例1、簡(jiǎn)單的全表掃描方法An89.1.2實(shí)現(xiàn)查詢操作的算法示例2、索引(或散列)掃描方法[例1-C2]Sno上有索引[例1-C3]Sage上有B+樹索引[例1-C4]Sdept和Sage上都有索引AnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例2、索引(或散列)掃描方法99.1.2實(shí)現(xiàn)查詢操作的算法示例二連接操作的實(shí)現(xiàn)1、嵌套循環(huán)方法(nestedloop)2、排序-合并方法(sort-mergejoin)3、索引連接(IndexJoin)方法4、HashJoin方法[例2]Select*fromstudent,sc wherestudent.sno=sc.sno;AnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例二連接操作的實(shí)現(xiàn)AnI109.1.2實(shí)現(xiàn)查詢操作的算法示例1、嵌套循環(huán)方法AnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例1、嵌套循環(huán)方法AnIn119.1.2實(shí)現(xiàn)查詢操作的算法示例2、排序合并方法20021512120021512220021512320021512420021512122002151213200215121120021512222002151223200215123520021512332002151231SNOSNOCNOAnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例2、排序合并方法20021129.1.2實(shí)現(xiàn)查詢操作的算法示例3、索引連接方法20021512320021512220021512120021512420021512122002151233200215123120021512122002151223200215121520021512232002151231SNOSNOCNO索引表AnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例3、索引連接方法20021139.1.2實(shí)現(xiàn)查詢操作的算法示例3、HashJoin方法20021512320021512220021512120021512412002151233200215122520021512132002151222200215121120021512332002151232200215121SNOSNOCNOAnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例3、HashJoin方法14第四章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化9.3小結(jié)AnIntroductiontoDatabaseSystem第四章關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處159.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化查詢優(yōu)化的必要性查詢優(yōu)化極大地影響RDBMS的性能。

查詢優(yōu)化的可能性關(guān)系數(shù)據(jù)語(yǔ)言的級(jí)別很高，使DBMS可以從關(guān)系表達(dá)式中分析查詢語(yǔ)義。AnIntroductiontoDatabaseSystem9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化查詢優(yōu)化的必要性AnIntr169.2.1查詢優(yōu)化概述關(guān)系系統(tǒng)的查詢優(yōu)化既是RDBMS的關(guān)鍵技術(shù)又是關(guān)系系統(tǒng)的優(yōu)點(diǎn)所在;大大減輕了用戶的負(fù)擔(dān)。AnIntroductiontoDatabaseSystem9.2.1查詢優(yōu)化概述關(guān)系系統(tǒng)的查詢優(yōu)化既是RDBMS的關(guān)179.2.1查詢優(yōu)化概述由DBMS進(jìn)行查詢優(yōu)化的好處用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率系統(tǒng)可以比用戶程序的優(yōu)化做得更好 (1)優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以獲得這些信息

AnIntroductiontoDatabaseSystem9.2.1查詢優(yōu)化概述由DBMS進(jìn)行查詢優(yōu)化的好處AnI18由DBMS進(jìn)行查詢優(yōu)化的好處(2)如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。 在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的。(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)AnIntroductiontoDatabaseSystem由DBMS進(jìn)行查詢優(yōu)化的好處(2)如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改199.2.1查詢優(yōu)化概述集中式數(shù)據(jù)庫(kù)查詢開銷：I/O+CPU+內(nèi)存分布式數(shù)據(jù)庫(kù)查詢開銷：I/O+CPU+內(nèi)存+通信代價(jià)查詢優(yōu)化的總目標(biāo)選擇有效策略，求得給定關(guān)系表達(dá)式的值，使得查詢代價(jià)較小AnIntroductiontoDatabaseSystem9.2.1查詢優(yōu)化概述集中式數(shù)據(jù)庫(kù)查詢開銷：AnIntr209.2.2一個(gè)實(shí)例例3：求選修了課程Ｃ2的學(xué)生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';AnIntroductiontoDatabaseSystem9.2.2一個(gè)實(shí)例例3：求選修了課程Ｃ2的學(xué)生姓名AnI219.2.2一個(gè)實(shí)例（續(xù)）假設(shè)1：外存： Student:1000條,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)法

AnIntroductiontoDatabaseSystem9.2.2一個(gè)實(shí)例（續(xù)）假設(shè)1：外存：AnIntrod229.2.2一個(gè)實(shí)例（續(xù)）三種策略：Ｑ1＝ПＳname(бStudent.Sno=SC.Sno∧SC.Cno='2'(Student×SC))

Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))Ｑ2＝ПSname(StudentбSC.Cno='2'(SC))

AnIntroductiontoDatabaseSystem9.2.2一個(gè)實(shí)例（續(xù)）三種策略：AnIntroduc23執(zhí)行策略1Ｑ1＝ПＳname(бStudent.Sno=SC.Sno

∧SC.Cno='2'

(Student×SC))

①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秒AnIntroductiontoDatabaseSystem執(zhí)行策略1Ｑ1＝ПＳname(бStudent.Sno=S24不同的執(zhí)行策略,考慮I/O時(shí)間

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

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

②б

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

③П總時(shí)間=105＋50000＋50000秒=100105秒=27.8小時(shí)AnIntroductiontoDatabaseSystem不同的執(zhí)行策略,考慮I/O時(shí)間

中間結(jié)果大小=1000259.2.2一個(gè)實(shí)例（續(xù)）策略2.Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))

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

②б

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

③П

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

AnIntroductiontoDatabaseSystem9.2.2一個(gè)實(shí)例（續(xù)）策略2.Ｑ2＝ПＳname(269.2.2一個(gè)實(shí)例（續(xù)）策略3.Ｑ3＝ПSname(StudentбSC.Cno='2'(SC))

①б 讀SC表總塊數(shù)=10000/100=100塊

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

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

② 讀Student表總塊數(shù)=1000/10=100塊

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

③П

總時(shí)間＝5＋5秒＝10秒AnIntroductiontoDatabaseSystem9.2.2一個(gè)實(shí)例（續(xù)）策略3.Ｑ3＝ПSname(S279.2.2一個(gè)實(shí)例（續(xù)）策略4.Ｑ2＝ПＳname(StudentбSC.Cno='2'(SC))假設(shè)SC表在Cno上有索引，Student表在Sno上有索引

①б 讀SC表索引= 讀SC表總塊數(shù)=50/100<1塊 讀數(shù)據(jù)時(shí)間

中間結(jié)果大小=50條不必寫入外存AnIntroductiontoDatabaseSystem9.2.2一個(gè)實(shí)例（續(xù)）策略4.Ｑ2＝ПＳname(S289.2.2一個(gè)實(shí)例（續(xù)）② 讀Student表索引= 讀Student表總塊數(shù)=50/10=5塊 讀數(shù)據(jù)時(shí)間③П總時(shí)間<10秒AnIntroductiontoDatabaseSystem9.2.2一個(gè)實(shí)例（續(xù)）②AnIntroduction29第九章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化9.3小結(jié)AnIntroductiontoDatabaseSystem第九章關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處309.3代數(shù)優(yōu)化9.3.1關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則9.3.2查詢樹的啟發(fā)式優(yōu)化AnIntroductiontoDatabaseSystem9.3代數(shù)優(yōu)化9.3.1關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則An319.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則關(guān)系代數(shù)表達(dá)式等價(jià)指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的上面的優(yōu)化策略大部分都涉及到代數(shù)表達(dá)式的變換AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則關(guān)系代數(shù)表達(dá)式等價(jià)AnI32

9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則設(shè)E1、E2等是關(guān)系代數(shù)表達(dá)式，F(xiàn)是條件表達(dá)式

l.連接、笛卡爾積交換律 E1×E2≡E2×E1 E1E2≡E2E1 E1FE2≡E2FE1

AnIntroductiontoDatabaseSystem

9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則AnIntroduct339.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則

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

F

F

F

FAnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則

AnIntroducti349.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則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}的子集AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則3.投影的串接定律AnI359.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則4.選擇的串接定律

бF1（б

F2（E））≡бF1∧F2(E)選擇的串接律說明選擇條件可以合并這樣一次就可檢查全部條件。AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則4.選擇的串接定律AnI369.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則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)))AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則5.選擇與投影的交換律An379.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則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可推出： бF(E1×E2)≡бF1(E1)×бF2(E2)

AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則6.選擇與笛卡爾積的交換律389.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則(3)假設(shè)：F=F1∧F2，

F1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性 бF(E1×E2)≡бF2(бF1(E1)×E2)

它使部分選擇在笛卡爾積前先做

AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則(3)假設(shè)：F=F1∧F399.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則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)AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則7.選擇與并的交換AnI409.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則9.選擇對(duì)自然連接的分配律 бF(E1E2)≡бF(E1)бF(E2)AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則9.選擇對(duì)自然連接的分配律419.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則10.投影與笛卡爾積的交換

假設(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)AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則10.投影與笛卡爾積的交換42關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）11.投影與并的交換

假設(shè)：E1和E2有相同的屬性名 πA1,A2,…,An(E1∪E2)≡ πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)AnIntroductiontoDatabaseSystem關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）11.投影與并的交換AnIn43小結(jié)1-2:連接、笛卡爾積的交換律、結(jié)合律3：合并或分解投影運(yùn)算4：合并或分解選擇運(yùn)算5-9：選擇運(yùn)算與其他運(yùn)算交換5，10，11：投影運(yùn)算與其他運(yùn)算交換AnIntroductiontoDatabaseSystem小結(jié)1-2:連接、笛卡爾積的交換律、結(jié)合律AnInt449.3代數(shù)優(yōu)化9.3.1關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則9.3.2查詢樹的啟發(fā)式優(yōu)化AnIntroductiontoDatabaseSystem9.3代數(shù)優(yōu)化9.3.1關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則An459.3.2查詢樹的啟發(fā)式優(yōu)化—典型啟發(fā)式規(guī)則：選擇運(yùn)算應(yīng)盡可能先做

目的：減小中間關(guān)系在執(zhí)行連接操作前對(duì)關(guān)系適當(dāng)進(jìn)行預(yù)處理按連接屬性排序在連接屬性上建立索引

投影運(yùn)算和選擇運(yùn)算同時(shí)做目的：避免重復(fù)掃描關(guān)系將投影運(yùn)算與其前面或后面的雙目運(yùn)算結(jié)合目的：減少掃描關(guān)系的遍數(shù)AnIntroductiontoDatabaseSystem9.3.2查詢樹的啟發(fā)式優(yōu)化—典型啟發(fā)式規(guī)則：選擇運(yùn)算應(yīng)盡469.3.2查詢樹的啟發(fā)式優(yōu)化—典型啟發(fā)式規(guī)則：某些選擇運(yùn)算＋在其前面執(zhí)行的笛卡爾積===>連接運(yùn)算例：бStudent.Sno=SC.Sno(Student×SC)

StudentSC提取公共子表達(dá)式AnIntroductiontoDatabaseSystem9.3.2查詢樹的啟發(fā)式優(yōu)化—典型啟發(fā)式規(guī)則：某些選擇運(yùn)算479.3.2查詢樹的啟發(fā)式優(yōu)化—算法算法：關(guān)系表達(dá)式的優(yōu)化輸入：一個(gè)關(guān)系表達(dá)式的語(yǔ)法樹。輸出：計(jì)算該表達(dá)式的程序。方法：（1）分解選擇運(yùn)算利用規(guī)則4把形如бF1∧F2∧…∧Fn(E)變換為бF1(бF2(…(бFn(E))…))AnIntroductiontoDatabaseSystem9.3.2查詢樹的啟發(fā)式優(yōu)化—算法算法：關(guān)系表達(dá)式的優(yōu)化A48關(guān)系代數(shù)表達(dá)式的優(yōu)化算法(續(xù))（2）通過交換選擇運(yùn)算，將其盡可能移到葉端對(duì)每一個(gè)選擇，利用規(guī)則4～9盡可能把它移到樹的葉端。

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

對(duì)每一個(gè)投影利用規(guī)則3，10，11，5中的一般形式盡可能把它移向樹的葉端。

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

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

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

AnIntroductiontoDatabaseSystem關(guān)系代數(shù)表達(dá)式的優(yōu)化算法(續(xù))（6）生成程序AnIntr52優(yōu)化的一般步驟1．把查詢轉(zhuǎn)換成某種內(nèi)部表示2．代數(shù)優(yōu)化：把語(yǔ)法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式3．物理優(yōu)化：選擇低層的存取路徑4．生成查詢計(jì)劃，選擇代價(jià)最小的AnIntroductiontoDatabaseSystem優(yōu)化的一般步驟1．把查詢轉(zhuǎn)換成某種內(nèi)部表示AnIntro53優(yōu)化的一般步驟(續(xù))（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示例：求選修了課程Ｃ2的學(xué)生姓名 SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';AnIntroductiontoDatabaseSystem優(yōu)化的一般步驟(續(xù))（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示AnI54（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示語(yǔ)法樹結(jié)果project(Sname)

select(SC.Cno=2)

join(Student.Sno=SC.Sno)

StudentSCAnIntroductiontoDatabaseSystem（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示語(yǔ)法樹結(jié)果project(S55關(guān)系代數(shù)語(yǔ)法樹πSname

SC.Cno=’2’

Student.Sno=SC.S

×

StudentSCAnIntroductiontoDatabaseSystem關(guān)系代數(shù)語(yǔ)法樹πSnameSC.Cno=’2’Stu56（2）代數(shù)優(yōu)化利用優(yōu)化算法把語(yǔ)法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式

πSname

Student.Sno=SC.Sno

SC.Cno=2

×

StudentSCAnIntroductiontoDatabaseSystem（2）代數(shù)優(yōu)化利用優(yōu)化算法把語(yǔ)法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式πS57第九章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化9.3小結(jié)AnIntroductiontoDatabaseSystem第九章關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處589.4物理優(yōu)化1、基于規(guī)則的啟發(fā)式優(yōu)化2、基于代價(jià)估算的優(yōu)化3、兩者結(jié)合的優(yōu)化方法AnIntroductiontoDatabaseSystem9.4物理優(yōu)化1、基于規(guī)則的啟發(fā)式優(yōu)化AnIntrodu599.4物理優(yōu)化9.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化9.4.2基于代價(jià)的優(yōu)化AnIntroductiontoDatabaseSystem9.4物理優(yōu)化9.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化609.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化一、選擇操作的啟發(fā)式規(guī)則二、連接操作的啟發(fā)式規(guī)則 P273AnIntroductiontoDatabaseSystem9.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化AnIntrod619.4物理優(yōu)化9.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化9.4.2基于代價(jià)的優(yōu)化AnIntroductiontoDatabaseSystem9.4物理優(yōu)化9.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化629.4.2基于代價(jià)的優(yōu)化統(tǒng)計(jì)信息表的元組數(shù)、元組長(zhǎng)度、占用的塊數(shù)等等屬性列不同值的個(gè)數(shù)、選擇率，最大最小值索引的層數(shù)、不同索引值的個(gè)數(shù)、索引葉結(jié)點(diǎn)數(shù)等代價(jià)估算示例全表掃描算法的代價(jià)估算公式索引掃描算法的代價(jià)估算公式嵌套循環(huán)連接算法的代價(jià)估算公式排序-合并連接算法的代價(jià)估算公式AnIntroductiontoDatabaseSystem9.4.2基于代價(jià)的優(yōu)化統(tǒng)計(jì)信息AnIntroducti63第九章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化9.3小結(jié)AnIntroductiontoDatabaseSystem第九章關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處649.3小結(jié)查詢處理是核心、優(yōu)化是關(guān)鍵查詢優(yōu)化的必要性代數(shù)優(yōu)化及其啟發(fā)式規(guī)則（查詢樹）物理優(yōu)化（存取路徑啟發(fā)式規(guī)則、代價(jià)優(yōu)化）AnIntroductiontoDatabaseSystem9.3小結(jié)查詢處理是核心、優(yōu)化是關(guān)鍵AnIntroduc65

下課了。。。休息一會(huì)兒。。。攀AnIntroductiontoDatabaseSystem下課了。。。休息一會(huì)兒。。。攀AnIntro66信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系數(shù)據(jù)庫(kù)系統(tǒng)概論AnIntroductiontoDatabaseSystem第九章關(guān)系查詢處理和查詢優(yōu)化AnIntroductiontoDatabaseSystem信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系數(shù)據(jù)庫(kù)系統(tǒng)概論AnIntrodu67第九章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化9.3小結(jié)AnIntroductiontoDatabaseSystem第九章關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處689.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.1.1查詢處理步驟9.1.2實(shí)現(xiàn)查詢操作的算法示例AnIntroductiontoDatabaseSystem9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.1.1查詢處理步驟An699.1.1查詢處理步驟查詢分析詞法/語(yǔ)法/語(yǔ)義分析符號(hào)名轉(zhuǎn)換查詢檢查語(yǔ)義檢查安全性檢查完整性檢查查詢優(yōu)化代數(shù)優(yōu)化物理優(yōu)化查詢執(zhí)行查詢計(jì)劃生成代碼生成AnIntroductiontoDatabaseSystem9.1.1查詢處理步驟查詢分析AnIntroductio709.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.1.1查詢處理步驟9.1.2實(shí)現(xiàn)查詢操作的算法示例AnIntroductiontoDatabaseSystem9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.1.1查詢處理步驟An719.1.2實(shí)現(xiàn)查詢操作的算法示例一選擇操作的實(shí)現(xiàn)二連接操作的實(shí)現(xiàn)AnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例一選擇操作的實(shí)現(xiàn)AnI729.1.2實(shí)現(xiàn)查詢操作的算法示例一選擇操作的實(shí)現(xiàn)1、簡(jiǎn)單的全表掃描方法2、索引(或散列)掃描方法[例1]Select*fromstudent where<條件表達(dá)式>表達(dá)式情況:C1:無(wú)條件;C2:Sno=‘200215121’;C3:Sage>20;C4:Sdept=‘CS’ANDSage>20;AnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例一選擇操作的實(shí)現(xiàn)AnI739.1.2實(shí)現(xiàn)查詢操作的算法示例1、簡(jiǎn)單的全表掃描方法AnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例1、簡(jiǎn)單的全表掃描方法An749.1.2實(shí)現(xiàn)查詢操作的算法示例2、索引(或散列)掃描方法[例1-C2]Sno上有索引[例1-C3]Sage上有B+樹索引[例1-C4]Sdept和Sage上都有索引AnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例2、索引(或散列)掃描方法759.1.2實(shí)現(xiàn)查詢操作的算法示例二連接操作的實(shí)現(xiàn)1、嵌套循環(huán)方法(nestedloop)2、排序-合并方法(sort-mergejoin)3、索引連接(IndexJoin)方法4、HashJoin方法[例2]Select*fromstudent,sc wherestudent.sno=sc.sno;AnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例二連接操作的實(shí)現(xiàn)AnI769.1.2實(shí)現(xiàn)查詢操作的算法示例1、嵌套循環(huán)方法AnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例1、嵌套循環(huán)方法AnIn779.1.2實(shí)現(xiàn)查詢操作的算法示例2、排序合并方法20021512120021512220021512320021512420021512122002151213200215121120021512222002151223200215123520021512332002151231SNOSNOCNOAnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例2、排序合并方法20021789.1.2實(shí)現(xiàn)查詢操作的算法示例3、索引連接方法20021512320021512220021512120021512420021512122002151233200215123120021512122002151223200215121520021512232002151231SNOSNOCNO索引表AnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例3、索引連接方法20021799.1.2實(shí)現(xiàn)查詢操作的算法示例3、HashJoin方法20021512320021512220021512120021512412002151233200215122520021512132002151222200215121120021512332002151232200215121SNOSNOCNOAnIntroductiontoDatabaseSystem9.1.2實(shí)現(xiàn)查詢操作的算法示例3、HashJoin方法80第四章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化9.3小結(jié)AnIntroductiontoDatabaseSystem第四章關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處819.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化查詢優(yōu)化的必要性查詢優(yōu)化極大地影響RDBMS的性能。

查詢優(yōu)化的可能性關(guān)系數(shù)據(jù)語(yǔ)言的級(jí)別很高，使DBMS可以從關(guān)系表達(dá)式中分析查詢語(yǔ)義。AnIntroductiontoDatabaseSystem9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化查詢優(yōu)化的必要性AnIntr829.2.1查詢優(yōu)化概述關(guān)系系統(tǒng)的查詢優(yōu)化既是RDBMS的關(guān)鍵技術(shù)又是關(guān)系系統(tǒng)的優(yōu)點(diǎn)所在;大大減輕了用戶的負(fù)擔(dān)。AnIntroductiontoDatabaseSystem9.2.1查詢優(yōu)化概述關(guān)系系統(tǒng)的查詢優(yōu)化既是RDBMS的關(guān)839.2.1查詢優(yōu)化概述由DBMS進(jìn)行查詢優(yōu)化的好處用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率系統(tǒng)可以比用戶程序的優(yōu)化做得更好 (1)優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以獲得這些信息

AnIntroductiontoDatabaseSystem9.2.1查詢優(yōu)化概述由DBMS進(jìn)行查詢優(yōu)化的好處AnI84由DBMS進(jìn)行查詢優(yōu)化的好處(2)如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。 在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的。(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)AnIntroductiontoDatabaseSystem由DBMS進(jìn)行查詢優(yōu)化的好處(2)如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改859.2.1查詢優(yōu)化概述集中式數(shù)據(jù)庫(kù)查詢開銷：I/O+CPU+內(nèi)存分布式數(shù)據(jù)庫(kù)查詢開銷：I/O+CPU+內(nèi)存+通信代價(jià)查詢優(yōu)化的總目標(biāo)選擇有效策略，求得給定關(guān)系表達(dá)式的值，使得查詢代價(jià)較小AnIntroductiontoDatabaseSystem9.2.1查詢優(yōu)化概述集中式數(shù)據(jù)庫(kù)查詢開銷：AnIntr869.2.2一個(gè)實(shí)例例3：求選修了課程Ｃ2的學(xué)生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';AnIntroductiontoDatabaseSystem9.2.2一個(gè)實(shí)例例3：求選修了課程Ｃ2的學(xué)生姓名AnI879.2.2一個(gè)實(shí)例（續(xù)）假設(shè)1：外存： Student:1000條,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)法

AnIntroductiontoDatabaseSystem9.2.2一個(gè)實(shí)例（續(xù)）假設(shè)1：外存：AnIntrod889.2.2一個(gè)實(shí)例（續(xù)）三種策略：Ｑ1＝ПＳname(бStudent.Sno=SC.Sno∧SC.Cno='2'(Student×SC))

Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))Ｑ2＝ПSname(StudentбSC.Cno='2'(SC))

AnIntroductiontoDatabaseSystem9.2.2一個(gè)實(shí)例（續(xù)）三種策略：AnIntroduc89執(zhí)行策略1Ｑ1＝ПＳname(бStudent.Sno=SC.Sno

∧SC.Cno='2'

(Student×SC))

①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秒AnIntroductiontoDatabaseSystem執(zhí)行策略1Ｑ1＝ПＳname(бStudent.Sno=S90不同的執(zhí)行策略,考慮I/O時(shí)間

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

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

②б

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

③П總時(shí)間=105＋50000＋50000秒=100105秒=27.8小時(shí)AnIntroductiontoDatabaseSystem不同的執(zhí)行策略,考慮I/O時(shí)間

中間結(jié)果大小=1000919.2.2一個(gè)實(shí)例（續(xù)）策略2.Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))

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

②б

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

③П

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

AnIntroductiontoDatabaseSystem9.2.2一個(gè)實(shí)例（續(xù)）策略2.Ｑ2＝ПＳname(929.2.2一個(gè)實(shí)例（續(xù)）策略3.Ｑ3＝ПSname(StudentбSC.Cno='2'(SC))

①б 讀SC表總塊數(shù)=10000/100=100塊

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

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

② 讀Student表總塊數(shù)=1000/10=100塊

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

③П

總時(shí)間＝5＋5秒＝10秒AnIntroductiontoDatabaseSystem9.2.2一個(gè)實(shí)例（續(xù)）策略3.Ｑ3＝ПSname(S939.2.2一個(gè)實(shí)例（續(xù)）策略4.Ｑ2＝ПＳname(StudentбSC.Cno='2'(SC))假設(shè)SC表在Cno上有索引，Student表在Sno上有索引

①б 讀SC表索引= 讀SC表總塊數(shù)=50/100<1塊 讀數(shù)據(jù)時(shí)間

中間結(jié)果大小=50條不必寫入外存AnIntroductiontoDatabaseSystem9.2.2一個(gè)實(shí)例（續(xù)）策略4.Ｑ2＝ПＳname(S949.2.2一個(gè)實(shí)例（續(xù)）② 讀Student表索引= 讀Student表總塊數(shù)=50/10=5塊 讀數(shù)據(jù)時(shí)間③П總時(shí)間<10秒AnIntroductiontoDatabaseSystem9.2.2一個(gè)實(shí)例（續(xù)）②AnIntroduction95第九章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化9.3小結(jié)AnIntroductiontoDatabaseSystem第九章關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處969.3代數(shù)優(yōu)化9.3.1關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則9.3.2查詢樹的啟發(fā)式優(yōu)化AnIntroductiontoDatabaseSystem9.3代數(shù)優(yōu)化9.3.1關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則An979.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則關(guān)系代數(shù)表達(dá)式等價(jià)指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的上面的優(yōu)化策略大部分都涉及到代數(shù)表達(dá)式的變換AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則關(guān)系代數(shù)表達(dá)式等價(jià)AnI98

9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則設(shè)E1、E2等是關(guān)系代數(shù)表達(dá)式，F(xiàn)是條件表達(dá)式

l.連接、笛卡爾積交換律 E1×E2≡E2×E1 E1E2≡E2E1 E1FE2≡E2FE1

AnIntroductiontoDatabaseSystem

9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則AnIntroduct999.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則

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

F

F

F

FAnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則

AnIntroducti1009.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則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}的子集AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則3.投影的串接定律AnI1019.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則4.選擇的串接定律

бF1（б

F2（E））≡бF1∧F2(E)選擇的串接律說明選擇條件可以合并這樣一次就可檢查全部條件。AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則4.選擇的串接定律AnI1029.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則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)))AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則5.選擇與投影的交換律An1039.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則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可推出： бF(E1×E2)≡бF1(E1)×бF2(E2)

AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則6.選擇與笛卡爾積的交換律1049.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則(3)假設(shè)：F=F1∧F2，

F1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性 бF(E1×E2)≡бF2(бF1(E1)×E2)

它使部分選擇在笛卡爾積前先做

AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則(3)假設(shè)：F=F1∧F1059.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則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)AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則7.選擇與并的交換AnI1069.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則9.選擇對(duì)自然連接的分配律 бF(E1E2)≡бF(E1)бF(E2)AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則9.選擇對(duì)自然連接的分配律1079.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則10.投影與笛卡爾積的交換

假設(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)AnIntroductiontoDatabaseSystem9.3.1關(guān)系代數(shù)等價(jià)變換規(guī)則10.投影與笛卡爾積的交換108關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）11.投影與并的交換

假設(shè)：E1和E2有相同的屬性名 πA1,A2,…,An(E1∪E2)≡ πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)AnIntroductiontoDatabaseSystem關(guān)系代數(shù)等價(jià)變換規(guī)則（續(xù)）11.投影與并的交換AnIn109小結(jié)1-2:連接、笛卡爾積的交換律、結(jié)合律3：合并或分解投影運(yùn)算4：合并或分解選擇運(yùn)算5-9：選擇運(yùn)算與其他運(yùn)算交換5，10，11：投影運(yùn)算與其他運(yùn)算交換AnIntroductiontoDatabaseSystem小結(jié)1-2:連接、笛卡爾積的交換律、結(jié)合律AnInt1109.3代數(shù)優(yōu)化9.3.1關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則9.3.2查詢樹的啟發(fā)式優(yōu)化AnIntroductiontoDatabaseSystem9.3代數(shù)優(yōu)化9.3.1關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則An1119.3.2查詢樹的啟發(fā)式優(yōu)化—典型啟發(fā)式規(guī)則：選擇運(yùn)算應(yīng)盡可能先做

目的：減小中間關(guān)系在執(zhí)行連接操作前對(duì)關(guān)系適當(dāng)進(jìn)行預(yù)處理按連接屬性排序在連接屬性上建立索引

投影運(yùn)算和選擇運(yùn)算同時(shí)做目的：避免重復(fù)掃描關(guān)系將投影運(yùn)算與其前面或后面的雙目運(yùn)算結(jié)合目的：減少掃描關(guān)系的遍數(shù)AnIntroductiontoDatabaseSystem9.3.2查詢樹的啟發(fā)式優(yōu)化—典型啟發(fā)式規(guī)則：選擇運(yùn)算應(yīng)盡1129.3.2查詢樹的啟發(fā)式優(yōu)化—典型啟發(fā)式規(guī)則：某些選擇運(yùn)算＋在其前面執(zhí)行的笛卡爾積===>連接運(yùn)算例：бStudent.Sno=SC.Sno(Student×SC)

StudentSC提取公共子表達(dá)式AnIntroductiontoDatabaseSystem9.3.2查詢樹的啟發(fā)式優(yōu)化—典型啟發(fā)式規(guī)則：某些選擇運(yùn)算1139.3.2查詢樹的啟發(fā)式優(yōu)化—算法算法：關(guān)系表達(dá)式的優(yōu)化輸入：一個(gè)關(guān)系表達(dá)式的語(yǔ)法樹。輸出：計(jì)算該表達(dá)式的程序。方法：（1）分解選擇運(yùn)算利用規(guī)則4把形如бF1∧F2∧…∧Fn(E)變換為бF1(бF2(…(бFn(E))…))AnIntroductiontoDatabaseSystem9.3.2查詢樹的啟發(fā)式優(yōu)化—算法算法：關(guān)系表達(dá)式的優(yōu)化A114關(guān)系代數(shù)表達(dá)式的優(yōu)化算法(續(xù))（2）通過交換選擇運(yùn)算，將其盡可能移到葉端對(duì)每一個(gè)選擇，利用規(guī)則4～9盡可能把它移到樹的葉端。

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

對(duì)每一個(gè)投影利用規(guī)則3，10，11，5中的一般形式盡可能把它移向樹的葉端。

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