【文章內(nèi)容簡介】 個頁都可容納4個記錄。在這種情況下，可擴(kuò)展散列需要4個數(shù)據(jù)頁和1個目錄頁，而線性散列只需要正好4個頁。 考慮一個包含有1,000,000個元組的關(guān)系R(a, b, c, d)。已知：每頁可容納10個元組；R按堆文件組織、記錄無序。假設(shè)屬性a是R的一個候選鍵，取值范圍0～999,999。若有三種可能的存取路徑：1）掃描堆文件R；2) +樹索引；3）。那么，對以下給定的每個查詢，指明具有最小查詢處理代價應(yīng)選用的存取方法。（1） 檢索R的所有元組；（2） 檢索滿足a50的所有元組；（3） 找a＝50的所有元組?！窘獯稹浚?）如果是檢索R所有的元組，采用直接掃描堆文件即可。利用索引反而是浪費(fèi)存取索引項(xiàng)的代價。（2）如果檢索a50的所有元組，由于a是利用B+樹索引只需要查詢一次索引文件的代價與讀取最多50次I/O的數(shù)據(jù)文件的代價，利用散列索引要查詢50次索引文件的代價與最多50次I/O的數(shù)據(jù)文件的代價，而掃描堆文件需要掃描完整一個文件的代價。因此，選用B+樹索引是最理想的。（3）如果檢索a=50的記錄，由于a 是候選鍵，滿足條件的記錄只能有一條，所以利用散列索引只需1~2次I/O，而利用B+樹索引也只要2~3次，但掃描堆文件則是一個不確定的代價，最壞可能要掃描完整個文件。所以選用散列索引最合適。 （1）針對屬性a不是R候選鍵情況；（2）如果R是基于a的排序文件?！窘獯稹浚?）針對屬性a不是候選鍵的情況，檢索R所有元組是一樣的，掃描堆文件是最好的方式。檢索a50的所有元組，由于a不是候選鍵，不能確定滿足條件的記錄數(shù)目，而且由于B+樹/散列索引一定不是聚集索引，所以有可能最壞的代價比掃描整個文件還要差。檢索a=50的元組也一樣，即使有散列索引，但由于非聚集，讀取數(shù)據(jù)文件所用的I/O數(shù)可能與滿足條件的記錄數(shù)一樣多。所以在這兩種情況下采用堆文件的方式也許最好。（2）針對R是基于排序文件的的情況，由于索引是聚集的，檢索所有元組采用掃描堆文件最合理。對a50的范圍檢索，采用B+樹索引合理。對于a=50的檢索采用散列索引最合理。（1） 假設(shè)有最理想的散列鍵值均勻分布，那么，在引起第一次桶分裂前，可被插入的最大數(shù)據(jù)項(xiàng)數(shù)和Next值分別是多少？請給出簡要解釋。（2） 畫出或標(biāo)示在只插入一個記錄就引發(fā)桶分裂后的索引文件結(jié)構(gòu)示圖。（3） 假設(shè)有最理想的散列鍵均勻分布，那么，會導(dǎo)致四個桶都發(fā)生分裂的最少需要插入數(shù)據(jù)項(xiàng)數(shù)及Next值分別是多少？請給出簡要解釋?！咀ⅲ}目有誤】【解答】（1）6項(xiàng)，Next=0。只要有溢出項(xiàng)發(fā)生，Next值就會變化，就會有分裂發(fā)生。而從圖中看到: 這時所有桶空閑項(xiàng)總和正好為6個，故在不發(fā)生分裂的情況下可插入的最大記錄數(shù)為6。（2）由于最后一個數(shù)據(jù)頁是滿的，只要插入一個屬于該桶的記錄項(xiàng)，就會發(fā)生溢出，引發(fā)桶分裂。分裂后，Next = 1。（3）8項(xiàng)．首先，插入63引起第一次（也正好是第一個桶）分裂；插入41,73引起第二個桶分裂，因只有5被分到新分裂桶中，分裂后第二個桶仍是滿的。插入137引起第三個桶分裂。最后，要導(dǎo)致第四次分裂――讓第三個個桶溢出，至少還需插入4個都進(jìn)入第三個桶的記錄項(xiàng)（如18, 34, 66, 130）。綜合以上分析，可得出：為導(dǎo)致四個桶都分裂一次的最少插入記錄項(xiàng)數(shù)是8。 ，給出基于可擴(kuò)展散列索引的存貯組織結(jié)構(gòu)圖?！窘獯稹?，(a)所示。（1）6項(xiàng)。（1）相同。 （2）(b)所示。（3）10項(xiàng)?？蓴U(kuò)展散列情況比較簡單，讓每個溢出就可導(dǎo)致該桶分裂。 關(guān)于位圖編碼和壓縮位圖的解碼，回答以下問題。 （1）已知位圖編碼011000,000,01000,00100； 給出對應(yīng)的壓縮位圖編碼。 （2）已知位圖編碼000,1000,000,000,01000,001000,0； 給出對應(yīng)的壓縮位圖編碼。 （3）已知壓縮編碼 1110100100110110011011； 給出對應(yīng)的位圖編碼。【解答】（1）011000,000,01000,00100對應(yīng)的壓縮位圖編碼0100110111110101（2）000,1000,000,000,01000,001000,0對應(yīng)的壓縮位圖編碼1011，11101010，110101（3）1110100100110110011011對應(yīng)的位圖編碼000,000,000,110,000,001,010,001 考慮一個有1,000,000個記錄的文件，且字段F有m個不同值。作為m的函數(shù)，F(xiàn)的位圖索引有多少個字節(jié)？【解答】F的位圖索引有的字節(jié)數(shù)：1000000*m / 8 關(guān)于空間索引，簡要回答以下問題。（1） 描述空間數(shù)據(jù)的兩種主要類型。（2） 描述空間查詢的三種主要類型。（3） 為什么在多媒體應(yīng)用中最鄰近查詢非常重要？（4） 為什么B+樹索引不同于一個空間索引？對于點(diǎn)數(shù)據(jù)，何時你使用一個B+樹索引效果優(yōu)于空間索引？對于點(diǎn)數(shù)據(jù)，何時你使用空間索引優(yōu)于B+樹索引？【解答】 （1）空間數(shù)據(jù)的兩種主要類型：n 點(diǎn)數(shù)據(jù)（point data）：空間點(diǎn)數(shù)據(jù)的基本特點(diǎn)是只有位置，沒有大小、邊界，不占據(jù)空間。n 區(qū)域數(shù)據(jù)（region data）：區(qū)域數(shù)據(jù)是同時具有位置和邊界的空間延展?？蓪^(qū)域位置視為區(qū)域的固定‘錨點(diǎn)’，比如重心點(diǎn)。（2）空間查詢的三種主要類型：n 范圍查詢(range queries)：?？臻g范圍查詢通常關(guān)聯(lián)著一個區(qū)域，并要求返回與目標(biāo)區(qū)域范圍重疊(overlap)或位于目標(biāo)區(qū)域內(nèi)的、指定類型的所有區(qū)域?qū)ο?。n 最鄰近點(diǎn)查詢(nearestneighbor query)：要求找出離指定點(diǎn)最近的對象。n 空間連接查詢(spatial join queries)：關(guān)聯(lián)連接兩個或兩類空間區(qū)域的查詢。這類查詢的典型例子包括“找相互間距離不超過200公里的城市組對”，“找靠近某區(qū)域（如一個湖泊）的所有城市”。(3) 因?yàn)橥ㄟ^映射/變換多媒體對象到特征向量點(diǎn)，可將查找相似對象問題轉(zhuǎn)換為關(guān)于特征向量點(diǎn)集的最小鄰近點(diǎn)查詢問題來處理；而通過最臨近查詢，可以高效解決多媒體應(yīng)用中碰到的很多相似對象匹配或搜索問題。(4) B+樹索引只是一維索引，對二維或更高維空間點(diǎn)數(shù)據(jù)或區(qū)域數(shù)據(jù)查詢基本沒有作用。對于點(diǎn)數(shù)據(jù)，僅當(dāng)進(jìn)行單個維檢索，且按B+樹搜索鍵的前綴檢索按該鍵排序的數(shù)據(jù)文件時，B+樹索引效果才會優(yōu)于空間索引。其它情況，空間索引對于點(diǎn)數(shù)據(jù)的檢索都要好于B+樹索引。 考慮含100萬個記錄點(diǎn)的關(guān)系R(x,y)，這些記錄點(diǎn)隨機(jī)分布在矩形區(qū)域(0,0)－(1000, 1000)內(nèi)。假設(shè)：① 每個頁可存放100個記錄點(diǎn)的數(shù)據(jù)，B樹的每個葉結(jié)點(diǎn)可容納200個鍵值－指針對；② x值落在[450,550]范圍內(nèi)的記錄點(diǎn)數(shù)約有10萬個， y也是如此；而x和y同時落在[450,550]范圍內(nèi)的記錄點(diǎn)數(shù)約有1萬個。試估算執(zhí)行范圍450 ≤ x, y ≤ 550內(nèi)的記錄點(diǎn)查詢時，所需的I/O次數(shù)?！窘獯稹堪袯＋樹的根保存在主存，且葉結(jié)點(diǎn)的指針已按照查找鍵排序；訪問每一維的10萬個指針，需要檢查一個B樹中間層結(jié)點(diǎn)和所有包含所需指針的葉結(jié)點(diǎn)。對每個B樹，我們需要查看約500個葉結(jié)點(diǎn)X: B樹要查找100,000/200＝500個葉節(jié)點(diǎn)Y: B樹要查找100,000/200＝500個葉節(jié)點(diǎn)訪問B樹的中間節(jié)點(diǎn)：X,Y的B＋樹中間節(jié)點(diǎn)各1次。 因此，檢索B+樹，獲得1萬個記錄指針，大約需要進(jìn)行1002次的I/O操作。而檢索這1萬個目標(biāo)記錄指針對應(yīng)的數(shù)據(jù)記錄，最壞情況下，可能還需要進(jìn)行1萬次的I/O操作。這通常已超過數(shù)據(jù)文件本身的所有頁。 ①（左上角）中所標(biāo)示的、含有三個數(shù)據(jù)點(diǎn)網(wǎng)格文件。（1）給出在按列表順序分別插入第4和5這些數(shù)據(jù)點(diǎn)后的網(wǎng)格文件。（2）討論如何使用網(wǎng)格文件處理區(qū)域數(shù)據(jù)?！窘獯稹浚?）。（2）基于網(wǎng)格文件頁很容易回答范圍查詢和最鄰近查詢。 對于范圍查詢，我們使用線性標(biāo)度識別要存取的網(wǎng)格目錄項(xiàng)組，然后分別檢查這組目錄項(xiàng)對應(yīng)的數(shù)據(jù)桶，來計算回答范圍查詢的結(jié)果。 對于鄰近查詢，我們首先檢索給定點(diǎn)所屬的網(wǎng)格目錄項(xiàng)，并搜索它所指向的數(shù)據(jù)頁。如果該頁是空的，我們就使用線性標(biāo)度計算包含給定點(diǎn)分區(qū)之所有鄰近分區(qū)，檢查這些鄰近分區(qū)數(shù)據(jù)桶中的數(shù)據(jù)點(diǎn)，來確定最鄰近點(diǎn)。. ，獨(dú)立回答以下問題。（1）標(biāo)示一個能插入R4，但不能插入R3的新對象邊界。（2）標(biāo)示一個能同時包含在R1和R6，但被插入R6的新對象邊界。（3）標(biāo)示一個能同時包含在R1和R6，但被插入R1的新對象邊界；該對象將被存放在哪個葉節(jié)點(diǎn)？（4）若搜索某對象時需要同時檢索R1和R2子樹，試給出該對象的一個例子。（5）給出一個示例查詢，需要檢查R3和R4，但不要檢查R5（如果沒有這樣的查詢，則給出解釋說明）。（6）給出一個示例查詢，需要檢查R3和R5，但不要檢查R4（如果沒有這樣的查詢，則給出解釋說明）?！窘獯稹浚?）一個能插入R4，但不能插入R3的新對象邊界。NEW包含在R4中，但不包含在R3中，所以能插入R4，但不能插入R3。（2）一個能同時包含在R1和R6，但被插入R6的新對象邊界。NEW同時包含在R1與R6中，但是對于R6能完全覆蓋NEW，所以被插入到R6中。（3）一個能同時包含在R1和R6，但被插入R1的新對象邊界。NEW同時包含在R1與R6中，但是對于R1能完全覆蓋NEW，所以被插入到R1中。對比題中的圖可知道，NEW靠R4最近，所需的擴(kuò)展也最小，所以應(yīng)該被插入到R4中。（4）由于R12與R16同時包含在R1與R2中，所以要檢索他們兩個數(shù)據(jù)項(xiàng)時，需要同時檢索R1和 R2子樹。（5）例如，要檢索R9和R10時，由于它們同時包含在R3與R4中，但與R5沒有關(guān)系，所以需要檢查R3和 R4，但不要檢查R5。第六章 關(guān)系操作符賦值。（1） 說明最有選擇性存儲路徑的概念。（2） 什么情況下可認(rèn)為一個選擇條件能匹配選擇索引？對一個給定的索引，如何來區(qū)分選擇條件中的主項(xiàng)和非主項(xiàng)？ （3） “塊嵌入連接”算法是否肯定優(yōu)于“頁嵌入連接”算法？為什么？（4） 如何理解基于索引的嵌套循環(huán)連接可避免枚舉叉積結(jié)果？塊嵌入連接和排序歸并連接能避免枚舉叉積結(jié)果嗎？（5） 從代價、主存要求等方面，比較基于排序和基于散列的消除重復(fù)算法，說明它們的優(yōu)缺點(diǎn)。（6） 從代價、主存要求等方面，比較兩趟算法的排序歸并連接和散列連接，說明它們的優(yōu)缺點(diǎn)。（7） 混合散列索引連接是如何改進(jìn)基本散列連接算法的？（8） 說明可用全關(guān)系一趟算法實(shí)現(xiàn)的一元操作符、可用全關(guān)系一趟算法實(shí)現(xiàn)的二元操作符。（9） 若S是較小關(guān)系，分別給出RS和S R的一趟算法描述。（10） 通過一具體例子，說明緩沖區(qū)置換策略會影響連接算法的性能。【解答】（1） 當(dāng)同時存在多種存取路徑時，稱具有最小存取代價的存取路徑為最具選擇性存取路徑。本質(zhì)上，它指在執(zhí)行查詢賦值期間需要存取的頁數(shù)最少的那個查詢存取路徑。（2） 稱一個索引能匹配選擇條件，如果索引可被用來檢索滿足條件的元組。一個主項(xiàng)是指能匹配索引的那個合取子項(xiàng)。（3） 肯定。對兩個大小分別為M和N個頁的關(guān)系連接，頁嵌入連接算法的代價為M+ M*N，而塊嵌入連接算法的代價為N+ M*N/(B2)，其中，B為可用的主存緩存塊數(shù)。（4） 在基于索引的嵌套循環(huán)連接算法中，對外層關(guān)系的每個元組，只需要以當(dāng)前外層元組的連接屬性值作為搜索鍵值，從索引檢索匹配元組，并不需要掃描整個內(nèi)存關(guān)系去檢查與每個內(nèi)層關(guān)系元組是否匹配。因此，可避免枚舉叉積結(jié)果。排序歸并連接只需要比較兩個排序關(guān)系的對應(yīng)等值分區(qū)元組，因此，也可避免枚舉叉積結(jié)果。但嵌套循環(huán)連接算法不能避免枚舉叉積結(jié)果，它只是比簡單嵌套循環(huán)連接算法更快（因?yàn)榭蓽p少掃描內(nèi)層關(guān)系的次數(shù)）。（5） 假設(shè)待排序關(guān)系的大小為T個頁?；谂判蛩惴ㄒ罂捎镁彺骓摂?shù)B (T)1/2以保證可按兩階段完成排序，相應(yīng)算法代價都為M+2T次I/Os。而基于散列算法要求可用緩存頁數(shù)B足夠容納最大的劃分(子桶)，在劃分均勻情況下，也是要求B (T)1/2。但若散列劃分不均勻，則可能需要比(T)1/2更大一些的B值。散列算法代價也是M+2T次I/Os?？紤]到DB系統(tǒng)有優(yōu)化得很好的排序工具(函數(shù))、排序方法的投影結(jié)果集是排序的、散列可能存在偏斜和CPU的代價等因素，選用排序方法似乎更好些。（6） 對等值連接，散列索引通常能提供很好的性能。假設(shè)兩個待連接關(guān)系的大小分別為M、N個頁。當(dāng)緩存較大B (f*max(M,N))1/2（這里，f為主存散列因子）時，散列連接代價只有（M+N）*3次I/Os。如果還有更大的緩存可能，除了實(shí)現(xiàn)正常散列算法需要的主存頁數(shù)外，還有額外緩存能駐留存儲1個甚至更多個桶，那么，采用混合散列連接還可以大幅度地改善性能。B (max(M,N))1/2時，改進(jìn)的排序歸并算法代價也只有（M+N）*3次I/Os，排序歸并連接還有一個額外的優(yōu)勢――可產(chǎn)生按連接鍵排序的輸出結(jié)果。當(dāng)主存很大時，用散列連接效果通常會更好，但當(dāng)需要基于連接屬性的排序輸出，也可能選擇排序歸并算法。當(dāng)可用主存很少，排序需要多個階段，散列需要遞歸進(jìn)行多次子桶劃分時，排序歸并和散列連接算法的性能都會顯著下降。另外，對非等值連接，不能用散列連接算法，我們只能選用排序歸并，或索引嵌入循環(huán)等連接實(shí)現(xiàn)方法。（7） 混合索引連接能顯著改善性能。例如，通過在劃分階段（而不是將它留到探測階段）就完成首個桶的元組匹配比較， 這能節(jié)省掉第一個分區(qū)的讀/寫代價。（8） 全關(guān)系算法指操作施加于整個關(guān)系上而非施加于單個元組上，關(guān)系中的多個不同元組可能會共同影響一個結(jié)果元組，或已處理過的元組對隨后的元組處理有影響。如果希望一趟完成全關(guān)系算法，那么要求主存比較大。對于消除重復(fù)或分組聚合等一元操作，要求能容納得下整個運(yùn)算結(jié)果。