本章講解查詢編譯器及其優(yōu)化器的體系結(jié)構(gòu)绍弟。查詢處理器有三大步驟：
- 語法分析杏死，將SQL轉(zhuǎn)換成語法分析樹
- 生成邏輯執(zhí)行計劃厢岂，將語法分析樹轉(zhuǎn)換成關(guān)系代數(shù)表達(dá)式
- 生成物理執(zhí)行計劃轧苫，物理查詢計劃楚堤，指明了要執(zhí)行的操作，而且找出了這些操作執(zhí)行的順序含懊，執(zhí)行每步所用的算法身冬，獲得所存儲數(shù)據(jù)的方式，以及數(shù)據(jù)從一個操作傳遞到另一個操作的方式岔乔。
5.1 語法分析和預(yù)處理
5.1.1 語法分析與語法分析樹
語法分析樹的節(jié)點有兩種：
- 原子酥筝。如關(guān)鍵字，關(guān)系或?qū)傩缘拿Q雏门，常數(shù)嘿歌，括號，運算符茁影，以及其他模式成分宙帝。
- 語法類。在一個查詢中起相似作用的查詢子成分所形成族的名稱募闲。如<Query>表示 select-from-where 形式的查詢步脓，<Condition>表示屬于條件的任何表達(dá)式。
一般蝇更，原子是葉子節(jié)點沪编；語法類，其子節(jié)點通過該語言的語法規(guī)則之一進(jìn)行描述年扩。
如何設(shè)計一個語言的語法以及如何進(jìn)行語法分析蚁廓，即將一個程序或查詢語言轉(zhuǎn)換成語法分析樹，這些屬于編譯領(lǐng)域厨幻。
5.1.2 SQL一個簡單子集的語法
數(shù)據(jù)表模式如下
StarsIn(movieTitle, movieYear, starName)
MovieStar(name, address, gender, birthdate)
SELECT movieTitle
FROM StarsIn
WHERE starName IN (
SELECT name
FROM MovieStart
WHERE birthdate LIKE '%1960'
SELECT movieTitle
FROM StarsIn, MovieStar
WHERE starName = name AND birthdate LIKE '%1960'
5.1.3 預(yù)處理器
預(yù)處理器有多個重要的功能相嵌。
- 視圖查詢替換
- 語義檢查腿时。如檢查表是否存在；檢查字段是否在表中饭宾；也會檢查字段是否有二義性等
- 檢查類型批糟。如屬性的類型必須與其使用相適應(yīng)。
5.1.4 預(yù)處理涉及視圖的查詢
視圖實際上就是一個查詢語句看铆。如果一條SQL查詢中用到了一個視圖徽鼎，則在from列表中用到該視圖的地方，必須用模式該視圖的語法樹來替換弹惦。
下面舉一個例子否淤，創(chuàng)建視圖
CREATE VIEW ParamountMovies AS
SELECT title, year
FROM Movies
WHERE studioName='Paramount'
SELECT title
FROM ParamountMovies
WHERE year=1979
其關(guān)系代數(shù)表達(dá)式樹如下
下面左圖就是視圖預(yù)處理的正式結(jié)果，對視圖進(jìn)行了替換棠隐。但是石抡，還可以使用查詢處理技術(shù)對左圖所示的樹進(jìn)行改進(jìn)，如將選擇和投影操作向樹的底層移動和合并助泽。
5.2 用于改進(jìn)查詢計劃的代數(shù)定律
本節(jié)列出一些代數(shù)定律啰扛，用于將一個表達(dá)式樹轉(zhuǎn)換成一個等價的表達(dá)式樹，后者可能有更有效的物理查詢計劃嗡贺。
5.2.1 交換律與結(jié)合律
與數(shù)學(xué)定義保持一致隐解。
交換律：該運算符的參數(shù)的順序無關(guān)緊要，可以交換暑刃。
結(jié)合律：該運算符出現(xiàn)的兩個地方厢漩，既可以從左邊進(jìn)行組合，也可以從右邊進(jìn)行組合岩臣。
當(dāng)一個運算符既滿足結(jié)合律溜嗜，又滿足交換律，則可以對用這個運算符連接起來的任意多個操作數(shù)進(jìn)行隨意組合與排列架谎，而不會改變結(jié)果炸宵。例如，((w+x)+y)+z=(y+x)+(w+z)谷扣。
5.2.2 涉及選擇的定律
由于選擇可以明顯地減少關(guān)系的大小土全，因此，進(jìn)行有序查詢處理最重要的規(guī)則之一就是只要不改變表達(dá)式的結(jié)果会涎，就把選擇在語法樹上盡可能地下移裹匙。
當(dāng)選擇條件比較復(fù)雜時，將條件分解末秃，這樣好處是概页，部分條件涉及的屬性較少，可移到某個方便的地方练慕，而整體條件不一定能夠移入惰匙。這就是分解定律技掏。我們也可以任意交換選擇運算符的順序。
對于二元運算符進(jìn)行下推選擇项鬼，如積哑梳，并，交绘盟，差鸠真，連接。取決于下推選擇到每個參數(shù)是可選還是必須的奥此。
- 對于并弧哎，選擇必須下推到兩個參數(shù)中
- 對于差雁比，選擇必須下推到第一個參數(shù)中稚虎，第二個參數(shù)可選
- 對于其他運算符，只要求選擇下推到其中一個參數(shù)偎捎。對于連接和積蠢终，將選擇下推到兩個參數(shù)是沒有意義的，因為參數(shù)可能沒有選擇所要求的屬性茴她。另外寻拂，即使可以同時下推到兩者，該做法也不一定能改進(jìn)計劃丈牢。
5.2.3 下推選擇
不一定非要進(jìn)行下推操作祭钉，有時候也要上移。例如當(dāng)查詢包含視圖時己沛，有時首先將選擇盡可能的往樹的上部移動慌核，然后再把選擇下推到所有可能的分支。
5.2.4 涉及投影的定律
下推投影時申尼，投影一般留在原處垮卓，即下推投影確實涉及在一個已存在的投影之下的某個地方引入一個新的投影。
下推投影是有用的师幕，但不如下推選擇那么有用粟按。原因是，選擇通常以較大的因子減少關(guān)系的大小霹粥，而投影不改變元組灭将，只減少元組的長度。
5.2.6 有關(guān)去重的定律
一般而言后控，將去重操作移到樹的下邊庙曙，減少了中間關(guān)系的大小，從而可能是有用的忆蚀。
