【正文】 理的基本過程。（2） 什么是查詢語法樹？試給出一個具體查詢的語法樹表示示例。（3） 說明查詢賦值邏輯計劃與物理計劃的區(qū)別。試給出：（a）基礎(chǔ)上，附加標注每個節(jié)點賦值方法、主存需求以及節(jié)點之間數(shù)據(jù)傳遞方法的更詳細計劃。（4） 描述SQL查詢基本塊的概念，并說明將查詢塊轉(zhuǎn)換為代數(shù)表達式樹的基本過程。（5） 請舉一個反例，說明流水線方式未必總是最有效方法。（6） 分別給出“下推選擇有很好效果，及下推選擇效果反而不好”的兩個查詢賦值例子。（7） 解釋說明許多典型優(yōu)化器只選擇左深樹的原因。（8） +樹索引。（a）若R、S數(shù)據(jù)文件的每個頁恰好為1個元組，那么，利用這兩索引執(zhí)行R?=？（b）若R、S數(shù)據(jù)文件的每個頁有多個元組，情況又當如何？【解答】（1） 查詢首先被解析(預編譯)，如果能通過，將產(chǎn)生合法的語法分析樹。通過初步查詢計劃生成器，可將語法分析樹轉(zhuǎn)換為初步的邏輯查詢計劃樹（即關(guān)系代數(shù)表達式樹）。初步邏輯查詢計劃通過查詢優(yōu)化處理，產(chǎn)生一個有效的、并添加了有關(guān)操作實現(xiàn)細節(jié)說明的‘最優(yōu)’查詢計劃――查詢賦值計劃樹。（2） 查詢語法樹，指的是SQL查詢表達經(jīng)過查詢預編譯處理后產(chǎn)生的、類似編譯語言語法樹的樹形表達形式。這種樹形表達有助于我們更準確地觀察查詢語句的語法結(jié)構(gòu)，也更適合機器自動分析處理。查詢語法樹的節(jié)點可以是以下兩者之一：l 原子類：屬詞法成份，相當于程序語言編譯器的token，如關(guān)鍵字(SELECT / FROM / WHERE…)、關(guān)系或?qū)傩缘拿?、常?shù)、括號、運算符等。原子節(jié)點沒有子節(jié)點。l 語法類：在查詢表達中起相似作用的查詢子成份族名稱。通常用角括號將描述名括起來表示。語法類子節(jié)點通常有子節(jié)點，并通過語法規(guī)則(產(chǎn)生式)進行描述。關(guān)于語法樹表示示例，可參見書本p225 。（3） 邏輯查詢計劃：指由查詢處理器通過將查詢語法樹中的節(jié)點和結(jié)構(gòu)，按一定的替換規(guī)則分別替換為關(guān)系代數(shù)操作符后，所生成的代數(shù)表達式樹。通常依據(jù)一定規(guī)則直接替換生成的代數(shù)表達式樹，只是一種初步的邏輯查詢計劃，還需經(jīng)過進一步的優(yōu)化重寫，才能得到比較合理的邏輯查詢計劃。物理查詢計劃：通常指由最終版本邏輯查詢的計劃，通過附加補充具體實現(xiàn)和執(zhí)行細節(jié)說明，而得到的實際查詢賦值執(zhí)行計劃。（4） 基本塊是一個簡單的SFW成份：有且只有1個SELECT和FROM關(guān)鍵字、最多一個WHERE子句、最多一個GROUP BY/HAVING 子句；且WHERE子句的條件表達式具有合取規(guī)范形式。將查詢塊轉(zhuǎn)換為代數(shù)表達式樹的基本過程為：用一個關(guān)系代數(shù)表達式來替換一個查詢塊，其中，關(guān)系代數(shù)表達式自下而上由以下內(nèi)容組成：u FromList中提到的全部關(guān)系叉積，作為下級選擇操作符選擇sc的參數(shù)；u 選擇sc，其中，C是SFWC結(jié)構(gòu)成份中的條件表達式（整個選擇作為下級投影操作符的參數(shù)）；u 投影pL，其中，L是SelList中的屬性。附加處理其它擴展查詢代數(shù)操作符（GROUP BY、HAVING）等，如有的話。（5） 流水線方式允許我們避免創(chuàng)建和讀取臨時關(guān)系文件，能節(jié)省大量的磁盤I/O操作。從而有益于減少查詢賦值代價。但這只是一個啟發(fā)式定律。有時當物化代價不大且物化方式有助于利用某些其它特性――如索引聚集特性――時，或當主存嚴重不足而勉強使用流水線方式時，采用流水化方式代價可能反而會更大。舉例：，若將連接左節(jié)點的輸入數(shù)據(jù)：先物化并按sid字段排序，則計劃賦值執(zhí)行的總代價將會更低。（6） 賦值查詢時，連接是一個相對昂貴的操作。通過下推選擇到連接之前，往往可以減小參與連接的關(guān)系大小，從而提高整個查詢賦值的性能。但這僅是一個啟發(fā)式定律，也存在一些情況，比如，選擇沒有索引可用，或先做選擇可能導致原關(guān)系索引不可用等情況，下推選擇策略也有可能反而會影響賦值效果。l “下推選擇有很好效果”的例子，可參見書本P231231。l “下推選擇反而影響效果”的例子，可參見書本P233234。（7） 許多典型優(yōu)化器只選擇左深樹的原因：l 隨著連接數(shù)目的增加，可選的計劃數(shù)目急劇增加，從候選計劃空間中剪枝變?yōu)榉浅ｊP(guān)鍵和重要。l 左深樹內(nèi)層節(jié)點總是基關(guān)系，允許我們產(chǎn)生所有完全流水化方式的計劃，即所有連接都允許利用流水線方式賦值，在開始連接之前，不需要等待第二關(guān)系。（8） （a） 當R和S的每個頁都是只含1個元組時，利用索引是一個很好的賦值方案。 因為每個數(shù)據(jù)頁最多被讀1次，掃描B+樹檢索數(shù)據(jù)的代價可能很小。（b）當R和S的每個頁都有很多元組時，如果索引是非聚集的（沒有排序數(shù)據(jù)文件可用），則單個數(shù)據(jù)頁可能會被多次讀取。而若將數(shù)據(jù)文件按索引鍵排序后（即索引為聚集索引），則每個匹配的數(shù)據(jù)頁通常只需被讀1次。 考慮關(guān)系模式：Employee(eid: integer, ename: string, sal: integer, title: string, age: integer)。假設(shè)有如下的索引（索引項均為鍵/指針對）：eid上的散列索引 / age上的散列索引/sal上的B+樹索引 / age,sal上的聚集B+樹索引。已知：關(guān)系總頁數(shù)10,000，每個元組100字節(jié)；每個索引項20字節(jié)。（1） 對如下的每個選擇條件，計算檢索滿足條件元組的最有選擇性存取路徑代價。 (a) sal 100；(b) age=25； (c) age=20； (d) eid=1,000；(e) sal200 ∧ age30； (f) sal200 ∧ age=20； (g) sal200 ∧ title=’CFO’；(h) sal200 ∧ age30∧ title=’CFO’（2） 試針對上述各條件，描述計算“將滿足條件元組按年齡分組的平均工資”的最便宜賦值方法，并估算總代價。（3） 對如下兩個選擇條件：（i）sal200 ∨ age=20。 （j）sal200 ∨ title=’CFO’ ，描述其最便宜賦值方法。【解答】（1） 若假設(shè)每個數(shù)據(jù)頁包含20個元組，則關(guān)系元組總數(shù)＝10000頁(20元組/頁)＝200,000；因索引項為20字節(jié)，元組大小為100字節(jié)，故B+樹的葉節(jié)點總數(shù)=10,00020/100＝2,000。對于非聚集索引，根據(jù)每個滿足條件指針檢索對應元組，可能都要讀取一個頁。注意，對組合鍵age,sal索引項大小取40字節(jié)，葉節(jié)點總數(shù)=4000.（a） 對于sal100，這時，利用非聚集索掃描的代價:= (B+樹索引掃描代價) + (按指針檢索滿足條件的元組代價)= 2+ 2,000 + 200,000*= 20202，這比文件掃描的10000代價大得多。對于選擇sal100，因為sal上不存在聚集索引，文件掃描或許是最好的。（b） 對age=25，聚集B+樹索引應是最好的選項，其代價：＝B+樹搜索的2次＋B+樹葉節(jié)點數(shù)*＋10000頁*（選擇性）＝2 ＋ 4000* + 10,000* = 1402利用（非聚集）散列索引是次好的選項，其代價： ＝元組總數(shù)* //每個元組讀1個頁＝200,000*=20,000 //若索引是聚集的，則代價可大幅降低（c） 對age20，聚集B+樹索引應是最好的選項，其代價為1402：（d） 對eid=1000，因為eid是候選鍵，可以假設(shè)每個桶中只有1個元組。這樣，總的代價≈ （2或3）。（e） 對sal200 ∧ age30，利用age,sal上的聚集B+樹索引檢索代價最小，代價大小:1402。（f） 對sal200 ∧ age=20，利用age,sal上的聚集B+樹索引檢索代價最小，*，則代價只有：＝B+樹搜索的2次＋B+樹葉節(jié)總數(shù)**＋10000頁**＝2 ＋ 4000* *+ 10,000** = 142（g） 對sal 200 ∧ title = ”CFO”，文件掃描代價最?。?0000。（h） 對sal 200 ∧ age 30 ∧ title = ”CFO” 先利用age,sal上的聚集B+樹索引檢索滿足sal 200 ∧ age 30的元組，再對檢索到元組檢查title = ”CFO”條件，進行過濾。代價：1402次I/Os。（2）（a） 對于sal100，因為結(jié)果只需要平均工資，利用sal上的B+樹只索引掃描（indexonly scan）就可實現(xiàn)賦值。，這時，利用非聚集索掃描的代價:=（定位起始葉節(jié)點的2次I/O）+ (掃描滿足條件的B+樹索引葉節(jié)點) = 2＋ 2,000 ＝ 202（b） 對age=25，聚集B+樹索引應是最好的選項，其代價：=（定位起始葉節(jié)點的2次I/O）+ (掃描滿足條件的B+樹索引葉節(jié)點) = 2＋ 4,000 ＝ 402次I/Os（c） 對age20，同（b），代價也是402次I/Os（d） 對eid=1000，同（1）（d），總的代價≈ （2或3）。（e） 對sal200 ∧ age30，利用age,sal上的聚集B+樹索引檢索代價最小，代價大小:402。（f） 對sal200 ∧ age=20，利用age,sal上的聚集B+樹索引檢索代價最小，*，則代價只有：＝B+樹搜索的2次＋B+樹葉節(jié)總數(shù)** ＝2 ＋ 4000* *= 42（g） 對sal 200 ∧ title = ”CFO”，文件掃描代價最小：10000。（h） 對sal 200 ∧ age 30 ∧ title = ”CFO” 先利用age,sal上的聚集B+樹索引檢索滿足sal 200 ∧ age 30的元組，再對檢索到元組檢查title = ”CFO”條件，進行過濾。代價：1402次I/Os。（3）（i） 對于sal 200∨age = 20，該情況（即使是對單個條件sal200）下，文件掃描應是最便宜的賦值方法。（j） 對sal 200 ∨ title = ”CFO”，同樣，文件掃描也是最好的賦值方法。 考慮關(guān)系模式Executives(ename, title, dname, address{假定這些屬性均為字串且等長})，關(guān)系實例包含10,000個頁，可用緩存頁數(shù)為10。 （1） 對于查詢SELECT , FROM Executives E WHERE =’EFO’，假設(shè)有10%的元組滿足選擇條件。（a） 假定title上有B+樹索引，試針對索引是聚集/非聚集兩種情況，說明最好計劃的代價；（b） 假定ename上有聚集B+樹索引，試說明最好計劃的代價；（c） 假定ename,title上有聚集B+樹索引，試說明最好計劃的代價。（2） 對于查詢SELECT FROM Executives E WHERE =’EFO’ and =’Toy’， 假設(shè)有10%=’EFO’、有5%=’Toy’。（a） 假定只有title上的聚集B+樹索引可用，試說明最好計劃的代價；（b） 假定只有dname上的聚集B+樹索引可用，試說明最好計劃的代價；（c） 假定同時有title、dname上的聚集B+樹索引可用，試說明最好計劃的代價；（d） 假定只有title,dname上的聚集B+樹索引可用，試說明最好計劃的代價；（e） 假定只有title,ename上的聚集B+樹索引可用，試說明最好計劃的代價；（f） 假定只有dname,title,ename上的聚集B+樹索引可用,試說明最好計劃代價。（g） 假定只有ename,title,dname上的聚集B+樹索引可用,試說明最好計劃代價.（3） 對于查詢SELECT FROM Executives E WHERE ’W%’ GROUP BY ， 假設(shè)有10%的元組滿足選擇條件。（a） 假定只有title上的聚集B+樹索引可用，試說明最好計劃的代價；（b） 假定只有dname上的聚集B+樹索引可用，試說明最好計劃的代價；（c） 假定只有title,dname上的聚集B+樹索引可用，試說明最好計劃的代價；（d） 假定只有dname,title上的聚集B+樹索引可用，試說明最好計劃的代價?！窘獯稹考僭O(shè)單字段搜索鍵的索引項大小＝元組大小*，B+樹索引葉節(jié)點總數(shù)＝10000/4 =2500；雙字段組合鍵索引項大小=元組大小*，B+樹索引葉節(jié)點總數(shù)＝5000。（1）① 利用title上的非聚集B+樹索引，代價:= 2 + 2500*+ （元組總數(shù)）* 最好計劃是文件掃描，代價：10,000次I/Os若有title上的聚集B+樹索引可用，使用它應是最好計劃，代價=2 + 2500*+ （數(shù)據(jù)文件總頁數(shù)）* ＝2+250+1000=1252② 這時索引不匹配選擇條件，基本沒有什么作用，最好計劃是文件掃描，代價＝10,000I/Os③ 雖然索引不匹配選擇條件，但仍可用只掃描索引來實現(xiàn)賦值，這時需要掃描所有的頁節(jié)點。代價＝組合鍵B+樹索引葉節(jié)點總數(shù)＝5000.（2）① 若使用title上的聚集B+樹索引，代價:= 2 + 頁節(jié)點數(shù)*+ （數(shù)據(jù)頁數(shù)）** ＝2＋2500*+10,000*=1252 次I/Os 這個代價比文件掃描低，是最好計劃。② 情況類似①③ 題目有錯（不可能同時有兩個聚集索引）。④ 若title,dname上的聚集B+樹索引可用，這時，由于有較大的選擇性，使用該索引應是最好的計劃，代價＝2＋5000*+10,000*=752 次I/Os。⑤ 若title,ename上的聚集B+樹索引可用，這時，雖然索引包含了輸出字段，但仍需要檢索實際元組以檢查關(guān)于dname條件。故代價＝2＋5000*+10,000*=1502 次I/Os。⑥ 若dname,title,ename上的聚集B+樹索引可用，這時，基于該索引的只索引掃描應是最好計劃，代價＝2＋7500*（可能更?。?402 次I/Os。⑦ 若dname,title,ename上的聚集B+樹索引可用，雖然索引不匹配選擇條件，但可用只索引掃描，基于該索引的只索引掃描