第一節(jié)中介紹了通過關系代數(shù)表達式變換對查詢優(yōu)化的方法。但是我們并不知道每一步變換是否真會得到好處，也就是不知道是否真會使執(zhí)行查詢的代價降低。這一節(jié)中我們介紹另一種優(yōu)化方法。這種方法是把查詢分解執(zhí)行，根據對所付出代價的多少來決定如何分解，如何執(zhí)行。 這套方法是E，Wong等人提出的，他們在實現(xiàn)INGRES中采用了這種方法。
為介紹方便，先給出一個例子，我們在整節(jié)中都要用到它。
* 例12.3
關系：供給商 SUPPLIER(S#,SNAME,CITY)
零件 PARTS(P#,PNAME,SIZE)
項目 PROJECT(J#,JNAME,CITY)
庫存 INVENTORY(S#,P#,QOH)
供貨情況 SUPPLY(S#,J#,P#,QU)
其中QOH：現(xiàn)有數(shù)量 QU：要用的數(shù)量
查詢：
RANGE OF (S,P,J,V,Y) IS (SUPPLIER, PARTS, PROJECT, INVENTORY, SUPPLY)
RETRIEVE (S.SNAME)
WHERE (S.S#=V.S#) AND (S.S#=Y.S#) AND (S.CITY=J.CITY)
AND (P.P#=V.P#) AND (V.P#=Y.P#) AND (J.J#=Y.J#)
AND (V.QOH>Y.QU) AND (P.PNAME='BOLTS')
AND (P.SIZE='#6') AND (Y.QO>100)
這個查詢是找出：所有為同城市中某些項目提供#6螺絲，提供量大于100并且現(xiàn)有量比提供量多的供給者名字。
此查詢可用圖12-4表示。
SNAME ┌─┐ CITY ┌─┐
←─┤S ├────────┤J │
└┬┘ └┬┘
│S# S# │J#
│ │
┌┴┐ QOH>QU ┌┴┐ QU>100
│V ├────────┤Y │←──
└─┘ P# └─┘
P#
┌─┐
│P │←── PNAME='BOLTS'
└─┘ PSIZE=’#6’
圖12-4 例12.3的查詢示意圖
執(zhí)行此查詢的最笨的方法：
(1)形式卡氏積S×P×J×V×Y
(2)從卡氏積中限制篩選出滿足限定條件的元組
(3)在S.SNAME上投影
若假定各關系的元組數(shù)如下：
┏━━━━━━━━━┯━━━━━━━━━━┓
┃ 關系 │ 元組數(shù) ┃
┠─────────┼──────────┨
┃ SUPPLIER │ 10 ┃
┃ PARTS │ 100 ┃
┃ PROJECT │ 10 ┃
┃ INVENTORY │ 100 ┃
┃ SUPPLY │ 400 ┃
┗━━━━━━━━━┷━━━━━━━━━━┛
那么，卡氏積的元組總數(shù)為4×108 。這個算法顯然是太壞了。
另外，我們會注重到此查詢涉及到5個變元S,P,J,V,Y,我們把它稱為5元查詢，涉及一個變元的查詢我們稱為一元查詢。
2.1分解
前面的例子中所指出的主要問題是當查詢涉及到卡氏積時，卡氏積的元組數(shù)會組合性地增長。這樣不僅需要大量的存貯空間，而且執(zhí)行查詢的時間很長。因此優(yōu)化應把主要注重力放在，第一，減小組合復雜性上；第二，把一個關系上的一元運算（一元查詢）映象為一個存取調用的序列時，應找出存取次數(shù)最少的方法。下面討論這兩點，以第一點為主。
查詢的處理過程分為兩步：分解和一元查詢處理。分解是動態(tài)的，如何分解受到一元查詢處理結果的影響。處理的過程如圖12-5所示。其中DECOMP負責把查詢分解為一些一元查詢。此部分的性能可通過它所產生出一元查詢的數(shù)目多少來大體估計。此部分的第一個目標是要減少產生出一元查詢的數(shù)目。
查詢 ┌──── ┐ ┌───────── ┐ ┌───────┐
──→│DECOMP ├──→│OVQP(一元查詢處理)├─→│AMI(存取接口) │
└──── ┘ └───────── ┘ └─┬─┬───┘
↑ │ │↑
└──────────────────── ┘ ↓│
│ │
│存貯的│
│ 數(shù)據 │
圖12-5 查詢處理過程示意圖
是否每個查詢都可分解呢？回答是肯定的。任一n元查詢Q(X1 ，X2 ，...,Xn ），其中Xi 的范圍是關系Ri 。假如我們從Rn 中取出一元組α代入Xn ，那么得到一個n-1元查詢Q(X1 ，X2 ,...，Xn-1 ,α）。假如Rn 有K個元組，則元組代入使Q變?yōu)镵個n-1元查詢。由此可見，無論付出代價如何，通過元組代入總可以把任何查詢分解成一些一元查詢。
另外一個問題是：除了元組代入以外是否還有其它分解方法呢？這里介紹兩種：
(1)一元子查詢提取：Q被替換為一個一元查詢Q'和一個在其后執(zhí)行的查詢Q"。
Q ──→(Q',Q")
(2)化簡：Q被替換為兩個查詢Q'和Q"，Q"在Q'執(zhí)行后執(zhí)行，它們只有一個公共變元。
X1 ,X2 ,...,Xm , Xm ,...,Xn
Q' Q"
Q'(X1 ,X2 ,...,Xm ),Q"(Xm ,...,Xn )
*例12.4 考慮對例12.3的查詢分解。
例12.3中的查詢可以分出兩個一元查詢：
RETRIEVE PARTS1(P.P#)
WHERE (P.PNAME='BOLTS') AND (P.SIZE='#6')
和
RETRIEVE SUPPLE1(Y.S#,Y.J#,Y.P#,Y.QU)
WHERE(Y.QU>100)
于是，查詢變成：
RANGE OF (S,P,J,V,Y) IS (SUPPLIER,PARTS1, PROJECT,
INVENTORY,SUPPLY1)
RETRIEVE(S.SNAME)
WHERE(S.S#=V.S#)AND (S.S#=Y.S#)
AND (S.CITY=J.CITY)AND (P.P#=V.P#)
AND (V.P#=Y.P#)AND (J.J#=Y.J#)AND (V.QOH>Y.QU)
圖12-6給出了這個查詢的示意圖。從圖中可以看出，這個查詢可以很輕易地化簡一個涉及（P,V）的查詢和在其后執(zhí)行的、涉及（S,J,Y,V）的查詢。
SNAME ┌─┐ CITY ┌─┐
←─┤S ├────────┤J │
└┬┘ └┬┘
│S# S# │J#
│ │
┌┴┐ QOH>QU ┌┴┐
│V ├────────┤Y1│
└─┘ P# └─┘
P#
┌─┐
│P1│
└─┘
圖12-6 提取一元子查詢后的示意圖
綜上所述，在分解中可以采用3種方法：
(1)一元子查詢提取
(2)化簡
(3)元組代入
(1)幾乎總會得到好處，因為在關系之間的運算之前盡可能減少關系的體積對減少付出的代價起很大作用。這一點我們在第一節(jié)中已經介紹過了。(2)經常會得到好處（但并不是總會得到好處）。(3)則是必須的，但又是我們最不希望采用的方法。當別無其它方法時必須用這種方法來分解。我們在后面要給出綜合使用這三種方法分解查詢的算法。
2.2 一元子查詢的提取
考慮n元的情況，假定x1 ,x2 ,...,xn 是查詢Q的變元，xi 的變換范圍是Ri 。一般地說來，Q有兩部分，即結果屬性表T1 和限定條件C。假定C是合取范式形式的，即
C=C1 ∧C2 ∧...∧Ck
其中Ci 是析取式，我們稱Ci 為限定條件的子句。假定有一些子句Cm+1 ,Cm+2 ,...Ck ，其中每個都只涉及一個變元，那么對應這些變元的那些關系就可以分別被對應的限定條件縮小它們的體積。換句話說，假如限定條件C是合取式，那么就可以用只涉及一個變元的布爾因子作為限定條件來縮減對應的關系。假如只需要關系的某些屬性，則在需要的屬性上投影也可能會減少關系的元組數(shù)（因為去掉了冗余）。對于每個變元，第一個問題是要確定可以做哪些限制篩選、可以做哪些投影。
對關系Ri 的限定條件越多，Ri 就會被限制得越少。所以我們應盡可能加上一些限制條件。有時通過傳遞性可以推導出一些新的限定條件，如：
(a=b) AND (b=c) => (a=c)
(a>b) AND (b>c) => (a>c)
*例12.5 考慮從例12.3的查詢推導出新的一元子句。
例12.3中的查詢的條件子句(V.QOH>Y.QU)和(Y.QU>100)可以推出(V.QOH>100)。推出的子句可以作為一元子句來限制V所對應的關系INVENTORY。
一元子查詢提取算法：
(1)把限定條件變成合取范式。
(2)加入所有由傳遞性推導出的一元子句。
(3)對于每個變元Xi ，確定：
1)涉及到Xi 的一元子句，
2)Ri在結果屬性表中涉及到的屬性和查詢Q中多元子句中所涉及的屬性。
(4)為每個Xi 形成一個一元查詢Qi ，此查詢相當于對(3) 2)所確定的那些屬性投影用(3) 1)中確定的子句作為限定條件進行限制篩選。假如(3) 1)中沒有一元子句并且(3) 2)中確定的屬性是Ri 的所有屬性，那么就去掉這個Qi 。因為這種情況下的結果就是Ri 。
*例12.6 把一元子查詢提取算法用于例12.3的查詢。
對例12.3的查詢用此算法的第(3)步結果如下：
┏━━━━━━┯━━━┯━━━━━━━━┯━━━━━━━━━━━━┓
┃ 關系 │ 變元 │ 一元子句 │ 需要的屬性 ┃
┠──────┼───┼────────┼────────────┨
┃SUPPLIER
