數(shù)據(jù)庫原理與技術(shù)

第六章查詢處理6.1查詢處理概述

6.2代價(jià)估算

6.3基本運(yùn)算的實(shí)現(xiàn)

6.4表達(dá)式計(jì)算

6.5關(guān)系表達(dá)式轉(zhuǎn)換

6.6選擇執(zhí)行計(jì)劃

6.1查詢處理概述查詢處理是指從數(shù)據(jù)庫中提取數(shù)據(jù)的一系列活動(dòng)。主要包括：

將用高層數(shù)據(jù)庫語言表示的查詢語句翻譯為能在文件系統(tǒng)這一物理層次上實(shí)現(xiàn)的表達(dá)式

為優(yōu)化查詢而進(jìn)行各種轉(zhuǎn)換

查詢的實(shí)際執(zhí)行

輸入：SQL語句輸出：滿足查詢條件的數(shù)據(jù)

6.1查詢處理概述（2）查詢處理的基本步驟：

1語法分析與翻譯

2優(yōu)化

3執(zhí)行語法分析與翻譯關(guān)系代數(shù)表達(dá)式執(zhí)行計(jì)劃優(yōu)化器查詢語句執(zhí)行引擎查詢結(jié)果有關(guān)數(shù)據(jù)的統(tǒng)計(jì)值數(shù)據(jù)6.1查詢處理概述（3）查詢優(yōu)化是為關(guān)系代數(shù)表達(dá)式的計(jì)算選擇最有效的查詢計(jì)劃的過程。查詢執(zhí)行計(jì)劃：用于計(jì)算一個(gè)查詢的原語序列。執(zhí)行原語：加了“如何執(zhí)行”注釋的關(guān)系代數(shù)運(yùn)算。6.1查詢處理概述（4）查詢優(yōu)化的過程：代數(shù)優(yōu)化：力圖找出與給定關(guān)系代數(shù)表達(dá)式等價(jià)的但執(zhí)行效率更高的一個(gè)表達(dá)式。

查詢語句處理的詳細(xì)策略的選擇，例如選擇執(zhí)行運(yùn)算所采用的具體算法，選擇將使用的特定索引等等。

6.1查詢處理概述（5）對(duì)于關(guān)系數(shù)據(jù)庫系統(tǒng)，查詢優(yōu)化是：挑戰(zhàn)：必須進(jìn)行好的優(yōu)化，才有可接受的性能機(jī)會(huì)：關(guān)系表達(dá)式的語義層次高，提供了優(yōu)化的可能性。優(yōu)化器有理由比程序員做得更好：＊優(yōu)化器具有豐富的可使用的信息＊當(dāng)數(shù)據(jù)庫發(fā)生變化時(shí)優(yōu)化器容易再次進(jìn)行優(yōu)化＊優(yōu)化器能夠?qū)Χ喾N實(shí)現(xiàn)策略逐一進(jìn)行考慮＊優(yōu)化器集中了最優(yōu)秀的程序員的智慧和經(jīng)驗(yàn)

6.2代價(jià)估算

6.2.1用于估計(jì)代價(jià)的目錄信息

6.2.2查詢代價(jià)的度量

6.2.1用于估計(jì)代價(jià)的目錄信息

有關(guān)關(guān)系的統(tǒng)計(jì)信息nr：關(guān)系r中的元組數(shù)目br：含有關(guān)系r的元組的塊數(shù)目sr：關(guān)系r中一個(gè)元組的大小fr：關(guān)系r的塊因子，即一個(gè)塊中能存放的關(guān)系r的元組數(shù)若假定關(guān)系r的元組物理上存于同一文件中，則：br=

nr/fr

6.2.1用于估計(jì)代價(jià)的目錄信息（2）有關(guān)關(guān)系的統(tǒng)計(jì)信息（續(xù)）V(A,r)：關(guān)系r中屬性A所具有的不同值的數(shù)目。

V(A,r)等于ПA（r）的大小若A為關(guān)系r的碼，則V(A,r)=nrSC(A,r)：關(guān)系r的屬性A的選擇基數(shù)。表示關(guān)系r中滿足屬性A上的一個(gè)等值條件的平均元組數(shù)。若A為r的碼屬性，則SC(A,r)＝1

若A為非碼屬性，并假定V(A,r)個(gè)不同的值在元組上均勻分布，則SC(A,r)＝(nr/V(A,r))。說明：V(A,r)與SC(A,r)中的A可以是屬性組。

6.2.1用于估計(jì)代價(jià)的目錄信息（3）

有關(guān)索引的統(tǒng)計(jì)信息：

fi

：樹形結(jié)構(gòu)(如B＋樹)索引i的內(nèi)部結(jié)點(diǎn)的平均扇出。

HTi

：索引i的層數(shù)。對(duì)于關(guān)系r的屬性A上所建的平衡樹索引（如B＋樹），HTi＝

logfi(V(A,r))

對(duì)于散列索引，HTi＝1

LBi

：索引i中最低層索引塊數(shù)目，即索引葉層的塊數(shù)。對(duì)于散列索引，Lbi就是索引中的塊數(shù)。

算法A的代價(jià)估計(jì)記為EA。

6.2.2查詢代價(jià)的度量查詢代價(jià)：查詢處理對(duì)各種資源的使用情況

磁盤存取（簡(jiǎn)化為磁盤塊傳送數(shù)）

CPU時(shí)間

通信開銷

一個(gè)重要的影響因素：主存中緩沖區(qū)的大小M＊最好的情形，所有的數(shù)據(jù)可以讀入到緩沖區(qū)中＊最壞的情形，緩沖區(qū)只能容納數(shù)目不多的數(shù)據(jù)塊——大約每個(gè)關(guān)系一塊。

6.3基本運(yùn)算的實(shí)現(xiàn)

每一個(gè)基本的代數(shù)運(yùn)算都有多種不同的實(shí)現(xiàn)算法。

?適用于不同的情況

等值條件，范圍條件數(shù)據(jù)是聚集的，數(shù)據(jù)是非聚集的相關(guān)屬性上有索引，相關(guān)屬性上沒有索引

?執(zhí)行代價(jià)不同

6.3基本運(yùn)算的實(shí)現(xiàn)（2）6.3.1選擇運(yùn)算

6.3.2排序運(yùn)算

6.3.3連接運(yùn)算

6.3.4其他運(yùn)算

6.3.1選擇運(yùn)算全表掃描

方法：依次訪問表的每一個(gè)塊，對(duì)于每一個(gè)元組，測(cè)試它是否滿足選擇條件。代價(jià)：E=br

缺點(diǎn)：效率低

優(yōu)點(diǎn)：

對(duì)關(guān)系的存儲(chǔ)方式?jīng)]有要求，不需要索引。適用于任何選擇條件。

6.3.1選擇運(yùn)算（2）索引掃描

條件：表在選擇條件的屬性上建有索引。方法：訪問索引，根據(jù)索引項(xiàng)的指示去訪問數(shù)據(jù)元組。無序索引：訪問滿足等值條件的元組有序索引：訪問滿足范圍查找條件的一系列元組。

6.3.1選擇運(yùn)算.（3）代價(jià)：利用主索引，等值比較：

E=HTi+

SC(A，r)/fr

利用輔助索引，等值比較：

E=HTi+SC（A，r）利用主索引，非等值比較：

E=HTi+br/2

（假設(shè)大約一半的元組滿足比較條件）利用輔助索引，非等值比較：

E=HTi+LBi/2+nr/2

6.3.1選擇運(yùn)算（4）復(fù)雜條件的選擇合?。害姚?∧θ2∧…∧θn（r）析?。害姚?∨θ2∨…∨θn（r）

方法：利用一個(gè)索引進(jìn)行合取選擇。利用組合索引進(jìn)行合取選擇。利用多維索引進(jìn)行合取選擇。通過標(biāo)識(shí)符的交集進(jìn)行合取選擇。通過標(biāo)識(shí)符的并集進(jìn)行析取選擇。

6.3.2排序運(yùn)算排序運(yùn)算在數(shù)據(jù)庫中的重要意義：SQL查詢可能要求有序的查詢結(jié)果。

事先對(duì)于作為運(yùn)算對(duì)象的關(guān)系進(jìn)行排序，可以提高某些關(guān)系運(yùn)算（例如連接）的執(zhí)行效率。

內(nèi)排序：文件較小，整個(gè)排序過程都能在內(nèi)存中進(jìn)行。

外排序：文件較大，排序過程需要使用外存。

6.3.2排序運(yùn)算（2）外部排序-歸并算法：（設(shè)內(nèi)存中用于排序的緩沖區(qū)頁面數(shù)為M）第一階段，建立多個(gè)已排序的子表。

每次讀入M塊，進(jìn)行內(nèi)排序，將長(zhǎng)度為M塊的已排序子表（共

br/M

個(gè)）寫到外存中。

第二階段，對(duì)已排序子表進(jìn)行歸并（可能需進(jìn)行若干趟）。6.3.2排序運(yùn)算（3）第二階段，對(duì)已排序子表進(jìn)行歸并。

第一趟：將頭M-1個(gè)已排序子表的各塊逐步讀入內(nèi)存，歸并并輸出。將下M-1個(gè)已排序子表的各塊逐步讀入內(nèi)存，歸并并輸出。

……

已排序子表數(shù)目減少到原來的1/（M-1）

第二趟：以第一趟的輸出作為輸入，重復(fù)過程。第三趟：以第二趟的輸出作為輸入，重復(fù)歸并過程

……

直至歸并為一個(gè)已排序文件。6.3.2排序運(yùn)算（4）

第二階段第一趟：

將頭M-1個(gè)已排序子表的每一個(gè)的第一塊讀入內(nèi)存的一個(gè)緩沖頁

repeat

在所有緩沖頁中的第一個(gè)元組中挑選排序碼值最小的元組； 把該元組寫到第M個(gè)緩沖頁，并將其從原緩沖頁中刪除；

if任何一個(gè)歸并段文件Ri的緩沖頁為空并且沒有到達(dá)Ri末尾

then讀入Ri的下一塊到相應(yīng)的緩沖頁；

if第M個(gè)緩沖頁滿

then將第M個(gè)緩沖頁寫到磁盤，并清空該緩沖頁；

until 所有的緩沖頁均空將下M-1個(gè)已排序子表的每一個(gè)的第一塊讀入內(nèi)存，歸并。

…….6.3.2排序運(yùn)算（5）

初始關(guān)系

歸并段文件歸并段文件

排序結(jié)果第一階段第二階段第二階段創(chuàng)建歸并段文件第一趟歸并第二趟歸并6.3.2排序運(yùn)算（6）代價(jià)估算：趟數(shù)=

logM-1(br/M)

E=br(2

logM-1(br/M)

+1)

6.3.3連接運(yùn)算二元運(yùn)算，涉及兩個(gè)關(guān)系。

r|><|

s,r|><|s

重要的運(yùn)算，多種不同的實(shí)現(xiàn)算法。

6.3.3連接運(yùn)算（2）

自然連接結(jié)果集大小的估計(jì)：

基于主碼、外碼連接的情況：結(jié)果集的元組數(shù)等于外碼所在關(guān)系的元組數(shù)。

一般情況：（假設(shè)連接屬性A的每個(gè)值在關(guān)系的元組中等概率出現(xiàn)），結(jié)果集的元組數(shù)為：

nr*(ns/V(A,s))或ns*(

nr/V(A,r))說明：

當(dāng)V(A,s)與V(A,r)不同時(shí)，取兩個(gè)估計(jì)值中較小者。若兩個(gè)關(guān)系中的元組在連接屬性上的取值能匹配上的很少時(shí)，上述估計(jì)值太高。但實(shí)際上這種情況很少發(fā)生。6.3.3連接運(yùn)算（3）嵌套循環(huán)連接塊嵌套循環(huán)連接索引嵌套循環(huán)連接排序-歸并連接散列連接復(fù)雜連接的實(shí)現(xiàn)

6.3.3連接運(yùn)算（4）嵌套循環(huán)連接

foreach元組trinrdobeginforeach元組tsinsdobegin

測(cè)試元組對(duì)(tr,ts)是否滿足連接條件θ

如果滿足，把tr

ts加到結(jié)果中

endend6.3.3連接運(yùn)算（5）嵌套循環(huán)連接（續(xù)）優(yōu)點(diǎn)：對(duì)參加運(yùn)算的關(guān)系沒有要求，適合于任何連接條件。代價(jià)：最壞情況（緩沖區(qū)只能夠容納每個(gè)關(guān)系的一個(gè)塊）：

nr

bs+br或ns

br+bs

最好情況（內(nèi)層關(guān)系s能完全放在內(nèi)存中）：

bs+br

6.3.3連接運(yùn)算（6）塊嵌套循環(huán)連接：以塊的方式循環(huán)，以減少塊讀寫次數(shù)。

foreach塊Brofrdobeginforeach塊Bsofsdobeginforeach元組trinBrdobeginforeach元組tsinBsdo

begin

測(cè)試元組對(duì)(tr,ts)是否滿足連接條件θ

如果滿足，把tr

ts加到結(jié)果中

endendendend6.3.3連接運(yùn)算（7）

塊嵌套循環(huán)連接（續(xù)）優(yōu)點(diǎn)：對(duì)參加運(yùn)算的關(guān)系沒有要求，適合于任何連接條件。代價(jià)：最壞情況（緩沖區(qū)只能夠容納每個(gè)關(guān)系的一個(gè)塊）：

br*bs+br或bs*br+bs

最好情況（內(nèi)層關(guān)系s能完全放在內(nèi)存中）：

bs+br

6.3.3連接運(yùn)算（8）塊嵌套循環(huán)連接（續(xù)）一些改進(jìn)：

連接屬性是內(nèi)層關(guān)系的碼時(shí)，內(nèi)層循環(huán)可中途跳出。內(nèi)層循環(huán)輪流做正、反向掃描，重用緩沖區(qū)中的數(shù)據(jù)，以減少磁盤讀取。內(nèi)層循環(huán)利用索引。

6.3.3連接運(yùn)算（9）索引嵌套循環(huán)連接：在內(nèi)層循環(huán)中利用連接屬性上的索引。

foreach元組trinrdobeginforeach與元組tr滿足連接條件的索引項(xiàng)

ins關(guān)系在連接屬性上的索引dobegin利用索引取到相應(yīng)的ts

把tr

ts加到結(jié)果中

endend

6.3.3連接運(yùn)算（10）索引嵌套循環(huán)連接（續(xù)）代價(jià)：最壞情況（緩沖區(qū)只能夠容納關(guān)系r的一個(gè)塊和索引的一個(gè)塊）：

br+nr*c

或bs+ns*c

最好情況不必考慮，因?yàn)椴槐夭捎盟饕短籽h(huán)連接方法。對(duì)關(guān)系S使用連接條件利用索引進(jìn)行選擇操作的代價(jià)6.3.3連接運(yùn)算（11）排序-歸并連接類似于外排序的歸并算法的思路，進(jìn)行連接運(yùn)算。前提：兩個(gè)關(guān)系的元組都已按連接屬性排好序。適用于自然連接和等值連接。a3b1d8d13f7m5q6aAaGcLdNmB

rsa1a2a1a3在歸并連接中使用的已排序關(guān)系rs6.3.3連接運(yùn)算（12）pr:=r的第一個(gè)元組的地址ps:=s的第一個(gè)元組的地址；while(ps≠nullandpr≠null)dobegints:=ps所指向的元組；Ss:={ts}； 讓ps指向關(guān)系s的下一個(gè)元組；done:=false; while(notdoneandps≠null)dobegints’:=ps所指向的元組；

if(ts’[JoinAttrs]=ts[JoinAttrs])thenbeginSs:=Ss∪{ts’}； 讓ps指向關(guān)系s的下一個(gè)元組；

endelsedone:=true；

end在連接屬性上具有相同值的S元組被加入到了Ss中。Ps指向在連接屬性上具有另一個(gè)值的S元組。6.3.3連接運(yùn)算（13）tr:=pr所指向的元組；

while(pr≠nullandtr[JoinAttrs]<ts[JoinAttrs])do begin

讓pr指向關(guān)系r的下一個(gè)元組；

tr:=pr所指向的元組；

end while(pr≠nullandtr[JoinAttrs]=ts[JoinAttrs])do beginforeachtsinSsdo begin將tstr加入結(jié)果中；end

讓pr指向關(guān)系r的下一個(gè)元組；

tr:=pr所指向的元組；

endend在r中跳過中不能與Ss中的s元組匹配的r元組。在r中前進(jìn)，將r元組與Ss中的每個(gè)s元組連接，直至r元組中的連接屬性值大于s元組的連接屬性值。

6.3.3連接運(yùn)算（14）

在歸并連接中使用的已排序關(guān)系

a3b1d8d13f7m5q6aAaGcLdNmBprpsa1a2a1a3在歸并連接中使用的已排序關(guān)系rs6.3.3連接運(yùn)算（15）排序-歸并連接（續(xù)）代價(jià)：br+bs6.3.3連接運(yùn)算（16）排序-歸并連接（續(xù)）---混合歸并連接思想：利用有序索引，對(duì)未排序的關(guān)系采用排序-歸并連接。前提：一個(gè)關(guān)系（r）按連接屬性排好序，另一個(gè)關(guān)系（S）未排序，但在連接屬性上有B+樹索引。方法：r的元組與s的B+樹葉結(jié)點(diǎn)進(jìn)行“連接”，（結(jié)果的“元組”為r元組與s元組地址）按s元組地址排序，

訪問s的塊，完成連接。

6.3.3連接運(yùn)算（17）散列連接適用于自然連接和等值連接。

基本思想:將兩個(gè)關(guān)系按連接屬性值劃分成有相同散列函數(shù)值的元組集合。關(guān)系r在一個(gè)散列劃分中的元組只需要與關(guān)系s在對(duì)應(yīng)的劃分中的元組相比較。在r和s的每一對(duì)劃分中進(jìn)行索引嵌套循環(huán)連接（散列索引）。6.3.3連接運(yùn)算（18）散列連接方法：確定連接屬性上的散列函數(shù)h，用于對(duì)s元組和r元組進(jìn)行劃分。確定連接屬性上的散列函數(shù)h’，用于逐個(gè)對(duì)每一劃分中的s元組構(gòu)造散列索引，再對(duì)同一劃分中的r元組查找散列索引，同時(shí)進(jìn)行連接。

6.3.3連接運(yùn)算（19）關(guān)系的散列劃分rs關(guān)系r的劃分關(guān)系s的劃分01234012346.3.3連接運(yùn)算（20）

/*對(duì)關(guān)系s進(jìn)行劃分*/

置Hs0,

Hs1…,Hsmax為空

foreach元組tsinsdobegini:=h(ts[JoinAttrs])；

Hsi

:=Hsi

∪{ts}；

end/*對(duì)關(guān)系r進(jìn)行劃分*/置Hr0,

Hr1…,Hrmax為空

foreach元組trinrdobegini:=h(tr[JoinAttrs])；

Hri

:=Hri

∪{tr}；

end6.3.3連接運(yùn)算（21）/*對(duì)每一分劃進(jìn)行索引嵌套循環(huán)連接*/ fori:=0tomaxdobegin讀Hsi

，在內(nèi)存中建立其散列索引；

foreach元組trinHri

dobegin檢索Hsi的散列索引，定位所有滿足

ts[JoinAttrs]=tr[JoinAttrs]的元組ts foreach匹配的元組tsinHsi

dobegintr

ts加入結(jié)果中；end end end構(gòu)造用輸入關(guān)系查找用輸入關(guān)系6.3.3連接運(yùn)算（22）散列連接（續(xù)）

代價(jià)：最基本的情況為3（br+bs）+2*max

討論：

max的值應(yīng)選得足夠大，使內(nèi)存中能容納構(gòu)造用輸入關(guān)系的任一分劃以及其上的散列索引，max至少應(yīng)為

bs/M

。顯然最好用較小的關(guān)系作為構(gòu)造用輸入關(guān)系。當(dāng)bs>M2時(shí)，關(guān)系的劃分不可能一趟完成，需要遞歸劃分。當(dāng)對(duì)于某個(gè)i，Hsi中的元組數(shù)大于內(nèi)存容量時(shí)，需要進(jìn)行溢出處理，想辦法使Hsi變小。改進(jìn)：混合散列連接當(dāng)M

2>

>bs時(shí)，充分利用內(nèi)存空間，減少磁盤I/O的方法。前提：讀每個(gè)關(guān)系一遍就能完成散列劃分，構(gòu)造用輸入關(guān)系的每一個(gè)分劃都能完全放入內(nèi)存。6.3.3連接運(yùn)算（23）復(fù)雜連接的實(shí)現(xiàn)合取式：r|><|

1∧

2∧…∧

ns

用一種高效技術(shù)計(jì)算某一條件下的連接r|><|

1s，在生成結(jié)果元組時(shí)測(cè)試其他條件。析取式：r|><|

1∨

2∨…∨

ns==>r|><|

1s

r|><|

2s…

r|><|

ns

6.3.4其他運(yùn)算

消除重復(fù)

投影

并、交、差

外連接

聚集

6.3.4其他運(yùn)算（2）消除重復(fù)用排序的方法用散列的方法投影投影，消除重復(fù)并、交、差排序的方法

散列的方法6.3.4其他運(yùn)算（3）外連接計(jì)算連接，然后將適當(dāng)?shù)脑M加到結(jié)果中。例r]><|θs

計(jì)算r|><|θS==>q1

計(jì)算r-∏R(q1)，在s對(duì)應(yīng)的分量填上空值，加到q1中。

6.3.4其他運(yùn)算（4）外連接（續(xù)）修改連接算法修改嵌套循環(huán)連接算法進(jìn)行左外連接、右外連接。修改排序-歸并連接算法進(jìn)行全外連接、左外連接、右外連接。修改散列連接算法進(jìn)行全外連接、左外連接、右外連接。6.3.4其他運(yùn)算（5）聚集排序的方法散列的方法6.4表達(dá)式計(jì)算

例Пcustomer_name（σbalance<2500(account)|><|customer）

Пcustomer_nameσbalance<2500customeraccount|><|6.4表達(dá)式計(jì)算（2）

實(shí)體化的方法—建立臨時(shí)關(guān)系代價(jià)：各個(gè)運(yùn)算的代價(jià)加上中間結(jié)果寫到磁盤的代價(jià)。(nr/fr)

流水線的方法—不建臨時(shí)關(guān)系，一個(gè)操作的結(jié)果傳給下一個(gè)操作作為輸入。6.4表達(dá)式計(jì)算（3）流水線的實(shí)現(xiàn)：需求驅(qū)動(dòng)—在操作樹的頂端將數(shù)據(jù)往上拉。生產(chǎn)者驅(qū)動(dòng)—將數(shù)據(jù)從操作樹的底層往上推需求驅(qū)動(dòng)的流水線方法比生產(chǎn)者驅(qū)動(dòng)的流水線方法使用更廣泛，因?yàn)樗菀讓?shí)現(xiàn)。6.4表達(dá)式計(jì)算（4）說明：流水線技術(shù)限制了實(shí)現(xiàn)操作的可用算法。

例若連接運(yùn)算的左端輸入來自流水線，則不可用排序-歸并連接算法，

可用索引嵌套循環(huán)連接算法。若連接運(yùn)算的兩端輸入均來自流水線，則限制更大。并非所有情況下都是流水線方法的代價(jià)小于實(shí)體化方法的代價(jià)，因?yàn)榱魉€方法對(duì)于運(yùn)算的實(shí)現(xiàn)算法有限制。

6.5關(guān)系表達(dá)式轉(zhuǎn)換

查詢優(yōu)化是為關(guān)系代數(shù)表達(dá)式的計(jì)算選擇最有效的查詢計(jì)劃的過程。

查詢優(yōu)化的過程：代數(shù)優(yōu)化：力圖找出與給定關(guān)系代數(shù)表達(dá)式等價(jià)的但執(zhí)行效率更高的一個(gè)表達(dá)式。

查詢語句處理的詳細(xì)策略的選擇，例如選擇執(zhí)行運(yùn)算所采用的具體算法，選擇將使用的特定索引等等。6.5.1表達(dá)式的等價(jià)性

兩個(gè)表達(dá)式等價(jià)：產(chǎn)生的結(jié)果關(guān)系具有相同的屬性集和相同的元組集。

例

Пcustomer_name

(σbranch-city=”Brooklyn”

(branch|><|(account|><|depositor)))

等價(jià)于

Пcustomer_name

((σbranch-city=”Brooklyn”

(branch))|><|(account|><|depositor))

6.5.1表達(dá)式的等價(jià)性（2）

Пcustomer_nameσbranch_city=”Brooklyn”branchaccountdepositorПcustomer_nameσbranch_city=”Brooklyn”branchaccountdepositor6.5.2等價(jià)規(guī)則等價(jià)規(guī)則

將一個(gè)表達(dá)式轉(zhuǎn)換為與之等價(jià)的另一個(gè)表達(dá)式的規(guī)則。符號(hào)：θ、θ1、θ2等表示謂詞，

L1、L2、L3等表示屬性列表，

E、E1、E2等表示關(guān)系代數(shù)表達(dá)式。關(guān)系名r是關(guān)系代數(shù)表達(dá)式的特例，在E可以出現(xiàn)的地方它就可以出現(xiàn)。

6.5.2等價(jià)規(guī)則（2）1.選擇運(yùn)算的級(jí)聯(lián)：合取選擇運(yùn)算可分解為單個(gè)選擇運(yùn)算的序列。

σθ1∧θ2(E)=σθ1(σθ2(E))2.選擇運(yùn)算滿足交換律

σθ1(σθ2(E))=σθ2(σθ1(E))3.投影運(yùn)算的級(jí)聯(lián)：投影運(yùn)算序列中只有最后一個(gè)運(yùn)算是需要的，其余的可省略?！荓1(∏L2(…(∏Ln(E))…))=∏L1(E)

6.5.2等價(jià)規(guī)則（3）

4.選擇與笛卡爾積以及theta連接相結(jié)合

a.σθ(E1×E2)=E1|><|θE2

b.σθ1(E1|><|θ2

E2)=E1|><|θ1∧θ2

E25.theta連接運(yùn)算滿足交換律：

E1|><|θE2=E2|><|θE1

自然連接也滿足交換律

E1|><|

E2=E2|><|

E16.5.2等價(jià)規(guī)則（4）6.連接運(yùn)算的結(jié)合律

a.自然連接運(yùn)算滿足結(jié)合律：

(E1|><|

E2)

|><|

E3=E1

|><|

(E2|><|

E3)

b.theta連接具有以下方式的結(jié)合律：

(E1|><|θ1

E2)|><|θ2∧θ3E3

=E1|><|θ1∧θ3(E2|><|θ2E3)

其中θ2只涉及E2與E3的屬性。由于任意一個(gè)條件都可為空，因此笛卡爾積運(yùn)算也具有結(jié)合律。6.5.2等價(jià)規(guī)則（5）

7.選擇運(yùn)算在下面兩個(gè)條件下對(duì)theta連接運(yùn)算具有分配律：a.當(dāng)選擇條件θ0的所有屬性只涉及參與連接運(yùn)算的表達(dá)式之一(E1)時(shí)：

σθ0(E1|><|θE2)=(σθ0(E1))|><|θE2b.當(dāng)選擇條件θ1只涉及E1的屬性，選擇條件θ2只涉及E2的屬性時(shí)：

σθ1∧θ2(E1|><|θE2)=(σθ1(E1))|><|θ(σθ2(E2))6.5.2等價(jià)規(guī)則（6）8.投影運(yùn)算對(duì)theta連接運(yùn)算具有分配律：a.令L1、L2分別是E1、E2的屬性。假設(shè)連接條件θ只涉及L1∪L2中的屬性，則：∏L1∪L2

(E1|><|θE2)=(∏L1(E1))

|><|θ(∏L2(E2))b.考慮連接E1|><|θE2。令L1、L2分別是E1、E2的屬性；令L3是E1中出現(xiàn)在連接條件θ中但不在L1∪L2中的屬性；令L4是E2中出現(xiàn)在連接條件θ中但不在L1∪L2中的屬性。那么：∏L1∪L2

(E1|><|θE2)=∏L1∪L2

((∏L1∪L3(E1))

|><|θ(∏L2∪L4(E2)))

6.5.2等價(jià)規(guī)則（7）

9.集合運(yùn)算并與交滿足交換律

E1∪E2=E2∪E1E1∩E2=E2∩E1

集合差運(yùn)算不滿足交換律10.集合運(yùn)算并與交滿足結(jié)合律

(E1∪E2)∪E3=E1∪(E2∪E3)(E1∩E2)∩E3=E1∩(E2∩E3)

集合差運(yùn)算不滿足結(jié)合律6.5.2等價(jià)規(guī)則（8）

11.選擇運(yùn)算對(duì)并、交、差運(yùn)算具有分配律：

σp（E1-E2）=σp（E1）-σp（E2）

σp（E1∪E2）=σp（E1）∪σp（E2）

σp（E1∩E2）=σp（E1）∩σp（E2）

進(jìn)一步有：

σp（E1-E2）=σp（E1）-E2σp（E1∩E2）=σp（E1）∩E2

但對(duì)于∪不成立。

6.5.2等價(jià)規(guī)則（9）

12.投影運(yùn)算對(duì)并運(yùn)算具有分配律∏L(E1∪E2)=(∏L(E1))∪(∏L(E2))

最小的等價(jià)規(guī)則集：若一個(gè)等價(jià)規(guī)則集中的任何一條規(guī)則都不能由其它規(guī)則結(jié)合起來導(dǎo)出，則稱該等價(jià)規(guī)則集為最小的等價(jià)規(guī)則集。

6.5.2等價(jià)規(guī)則（10）

例Пcustomer-name(σbranch-city=”Brooklyn”∧balance>1000

(branch|><|(account|><|depositor)))

規(guī)則6a==>Пcustomer-name(σbranch-city=”Brooklyn”∧balance>1000

((branch|><|account)|><|depositor))規(guī)則7a==>Пcustomer-name((σbranch_city=”Brooklyn”∧balance>1000

(branch|><|account))|><|depositor)6.5.2等價(jià)規(guī)則（11）Пcustomer-name((σbranch-city=”Brooklyn”∧balance>1000(branch|><|account))|><|depositor)規(guī)則7b==>Пcustomer-name((σbranch-city=”Brooklyn”(branch)|><|σbalance>1000(account))|><|depositor)規(guī)則8b==>Пcustomer-name(Пaccount-number(σbranch-city=”Brooklyn”(branch)|><|σbalance>1000(account))|><|depositor)

6.5.2等價(jià)規(guī)則（12）說明：

規(guī)則只說明兩個(gè)表達(dá)式等價(jià)，并不說明哪一個(gè)更好。

連接的次序很重要，好的連接次序序列產(chǎn)生小的中間結(jié)果。

規(guī)則的使用會(huì)產(chǎn)生大量的等價(jià)表達(dá)式，優(yōu)化器要采用適當(dāng)?shù)募夹g(shù)來減少所產(chǎn)生的表達(dá)式的數(shù)量。

6.6選擇執(zhí)行計(jì)劃關(guān)系代數(shù)表達(dá)式的基礎(chǔ)上，執(zhí)行計(jì)劃進(jìn)一步說明：

每個(gè)運(yùn)算的實(shí)現(xiàn)算法各運(yùn)算的執(zhí)行順序是否采用流水線技術(shù)注意：每個(gè)運(yùn)算的最小代價(jià)算法組合起來不一定是整個(gè)表達(dá)式的最佳算法，必須考慮各個(gè)運(yùn)算之間的相互作用。6.6選擇執(zhí)行計(jì)劃（2）兩類主要的優(yōu)化算法：

基于代價(jià)的方法

啟發(fā)式方法6.6.1基于代價(jià)的優(yōu)化

通過使用等價(jià)規(guī)則為給定的查詢語句產(chǎn)生一系列查詢執(zhí)行計(jì)劃，并選擇其中代價(jià)最小或接近最小的。

等價(jià)于給定查詢的不同查詢計(jì)劃可能很多，因此優(yōu)化的代價(jià)太大，所以：

采用一些巧妙的技術(shù)來減少需要考慮的表達(dá)式的數(shù)目。

采用啟發(fā)式方法來減少需考慮的表達(dá)式的數(shù)目。

6.6.1基于代價(jià)的優(yōu)化（2）減少需要考慮的表達(dá)式數(shù)目的技術(shù)只考慮左深連接次序

r1r2r3r4r5左深連接樹r1r2r3r4r5非左深連接樹6.6.1基于代價(jià)的優(yōu)化（3）找多個(gè)關(guān)系的最佳連接順序時(shí)，不是簡(jiǎn)單地考慮所有的可能順序，而是為每個(gè)子集找出最佳連接順序，這樣能大大減少需要檢查的連接順序的總數(shù)。如果檢查一個(gè)表達(dá)式的某部分后發(fā)現(xiàn)這一部分的最小代價(jià)已經(jīng)比先前已檢查過的整個(gè)表達(dá)式的執(zhí)行計(jì)劃的最小代價(jià)要大，則可以終止對(duì)這個(gè)表達(dá)式的檢查。如果發(fā)現(xiàn)計(jì)算一個(gè)子表達(dá)式的代價(jià)最小的方法所用的代價(jià)比先前已檢查過的整個(gè)表達(dá)式的最小代價(jià)執(zhí)行計(jì)劃所需代價(jià)還大，則沒有必要對(duì)包含該子表達(dá)式的任何完整表達(dá)式進(jìn)行檢查。6.6.2啟發(fā)式優(yōu)化運(yùn)用啟發(fā)式規(guī)則，對(duì)關(guān)系代數(shù)表達(dá)式進(jìn)行等價(jià)變換。常用的規(guī)則：

盡早進(jìn)行選擇運(yùn)算

盡早進(jìn)行投影運(yùn)算

避免進(jìn)行笛卡爾積運(yùn)算

………..

6.6.2啟發(fā)式優(yōu)化（2）

啟發(fā)式優(yōu)化的步驟:

1.將合取選擇分解為單個(gè)選擇運(yùn)算的序列。這有助于將選擇運(yùn)算往查詢樹下層移。

2.把選擇運(yùn)算在查詢樹上下推到最早可能執(zhí)行的地方。

例如，盡可能將σθ(r|><|s)轉(zhuǎn)換成σθ(

r)|><|s或r|><|σθ(s)

3.

通過使用|><|的結(jié)合律，重新組織查詢樹，使得具有限制比較嚴(yán)格的選擇運(yùn)算的葉結(jié)點(diǎn)關(guān)系首先執(zhí)行。

4.將跟有選擇條件的笛卡爾積運(yùn)算替換成連接運(yùn)算。

5.將投影屬性加以分解并在查詢樹上盡可能往下推。必要時(shí)可以引入新的投影運(yùn)算。

6.識(shí)別那些可用流水方式執(zhí)行其運(yùn)算的子樹，并采用流水線方法執(zhí)行之。

6.6.3嵌套子查詢的優(yōu)化

復(fù)雜嵌套子查詢的優(yōu)化相當(dāng)困難，許多優(yōu)化器對(duì)于嵌套子查詢的優(yōu)化僅做了少量的工作。

例selectcustomer-name from

borrower whereexists(select*

from

depositor

where

depositor.customer-name =borrower.customer-name)SQL概念上按以下方式執(zhí)行查詢：計(jì)算外層查詢的from子句中的關(guān)系的笛卡爾積，然后對(duì)該笛卡爾積的每個(gè)元組用位于where子句中的謂詞進(jìn)行測(cè)試。本例中，即測(cè)試子查詢運(yùn)算結(jié)果是否為空。6.6.3嵌套子查詢的優(yōu)化（2）