數(shù)據(jù)庫系統(tǒng)實現(xiàn)習(xí)題全

1、（達建松 2141280）習(xí)題2.2.1 M egatron 777磁盤具有以下特性：1）有10個盤面，每個盤面有100000個磁道。2）磁道平均有1000個扇區(qū)，每個扇區(qū)為1024字節(jié)3）每個磁道的20%被用于間隙。4）磁盤旋轉(zhuǎn)為10000轉(zhuǎn)/min。5）磁頭移動n個磁道所需要的時間是1+0.0002n ms。回答下列有關(guān)Megatron777的問題。a）磁盤的容量是多少？b）如果磁道是在直徑3.5英寸的圓面上，那么一個磁道的扇區(qū)中的平均位密度是多少？c）最大尋道時間是多少？d）最大旋轉(zhuǎn)等待時間是多少？e）如果一個塊是65536字節(jié)（即64扇區(qū)），一個塊得傳輸時間是多少？f）平均尋道時間是多

2、少？g）平均旋轉(zhuǎn)等待時間是多少？答案：a) 磁盤容量=盤面數(shù)*磁道數(shù)*扇區(qū)數(shù)*扇區(qū)容量=10*100000*1000*1024字節(jié)=210*109字節(jié)注釋：已知1）有10個盤面，每個盤面有100000個磁道。2）磁道平均有1000個扇區(qū)，每個扇區(qū)為1024字節(jié).b) 一個磁道存放存放1000*1024*8=8192000bits.直徑為3.5英尺那么中間磁道直徑為3.5/2（英寸） 中間扇區(qū)所占的周長是80*3.5/2（英寸）所以，每個磁道的扇區(qū)中的平均密度是 注釋：已知： 2）磁道平均有1000個扇區(qū)，每個扇區(qū)為1024字節(jié). 3）每個磁道的20%被用于間隙. c) 最大尋道時間是磁頭跨越全

3、部柱面所花費的時間。即1+0.0002*99999=20.9998ms已知： 1）有10個盤面，每個盤面有100000個磁道。 5）磁頭移動n個磁道所需要的時間是1+0.0002n ms。 d) 最大旋轉(zhuǎn)等待時間是磁頭旋轉(zhuǎn)一圈的時間。即1/(10000/60)= 6ms已知： 4）磁盤旋轉(zhuǎn)為10000轉(zhuǎn)/min。e) 該塊占用64個扇區(qū)，為此，磁頭必須越過64個扇區(qū)和扇區(qū)之間的63個間隙。由于間隙合在一起占72度圓弧，而扇區(qū)覆蓋剩余288度圓弧，則被它們覆蓋的圓弧的總度數(shù)為： 72*(63/1000)+288*(64/1000)=22.968則傳輸時間是（22.968/360）*0.6ms=0

4、.03828ms已知：3）每個磁道的20%被用于間隙。2）磁道平均有1000個扇區(qū) 。d）中最大旋轉(zhuǎn)等待時間為6ms。f) 磁頭行進的平均距離是跨越柱面的1/3，則平均尋道時間是：1+0.001*（100000/3）=34.33msg) 平均旋轉(zhuǎn)等待時間為磁盤旋轉(zhuǎn)半周所需時間: (1/2)*6ms=3ms（潘達）習(xí)題2.3.1假設(shè)我們正在為Megatron747磁盤調(diào)度I/O請求，磁頭的初始位置在磁道32000，圖2-9的請求已經(jīng)產(chǎn)生。在下列兩種情況下，每一種請求在何時可以完全得到服務(wù)？a) 我們采用電梯調(diào)度算法（起初朝任何一個方向開始移動都是允許的）。b) 我們采用先到達先服務(wù)調(diào)度。請求的柱

5、面到達時間800004800014000104000020圖2-9 4個塊訪問請求的到達時間Megatron747磁盤的平均尋道時間、旋轉(zhuǎn)等待時間和傳輸時間分別為6.46、4.17和0.13（所有時間均以ms計算）。因為每個塊訪問導(dǎo)致0.13ms傳輸時間和4.17ms平均旋轉(zhuǎn)等待時間，即無論尋道時間是多少，都需為每一次塊訪問加上4.3ms。尋道時間可通過Megatron747的規(guī)則計算：1+磁道數(shù)/4000（1+磁道數(shù)/500）。對于電梯調(diào)度算法，計算方式及結(jié)果如下。對柱面8000的第一個請求需要進行尋道，因為磁頭初始位置不是8000。這樣訪問8000完成的尋道時間為1+(32000-8000

6、)/4000ms，即在時間1+(32000-8000)/4000+4.3=11.3ms處第一次訪問將完成。在此之前，對柱面48000和4000訪問的請求分別于第1和第10時間到達，由于沿著柱面從高到低(32000->8000)方向還有請求4000，則先處理4000的請求。即在第11.3ms后，磁頭由柱面8000向柱面4000移動，此段尋道時間為1+(8000-4000)/4000=2ms，則4000訪問完成時間為11.3+2+4.3=16.8ms。當(dāng)訪問4000柱面完成時，僅有訪問48000柱面的請求未完成，因此磁頭將沿著從低到高移動，移動到48000需要1+(48000-4000)/4

7、000=12ms，即在12+16.8=28.8ms才可到達48000柱面。在向48000移動過程中，移動到40000柱面的尋道時間為1+(40000-4000)/4000=10ms，即在16.8+10=26.8ms訪問到40000，在此之前訪問40000的請求已經(jīng)到達(在第20ms到達的)，故而，在訪問48000之前，先處理訪問40000的請求，即對40000柱面的請求在16.8+10+4.3=31.3ms處理完成。從柱面40000到48000的尋道時間為1+(48000-40000)/4000=3ms，則48000的請求處理完成時間為31.1+3+4.3=38.4ms。綜上所述，對于電梯調(diào)度

8、算法而言每個請求的完成時間如下表：請求的柱面到達時間完全得到服務(wù)時間8000011.348000138.440001016.8400002031.1對于FCFS算法而言每個請求的完成時間如下表：請求的柱面到達時間完全得到服務(wù)時間800000+7+4.3=11.348000111.3+11+4.3=26.640001026.6+12+4.3=42.9400002042.9+10+4.3=57.2（周紅磊 2141284）習(xí)題 2.3.2 假設(shè)我們使用兩臺Megatron 747 磁盤 互相作為鏡像。然而，我們使第一個磁盤的磁頭保持在柱面的靠內(nèi)一半，第二個磁盤的磁頭保持在柱面靠外的一半，而不是允許

9、從兩個磁盤都能讀任何的塊。假設(shè)讀請求是對隨機的磁道，我們始終不必去寫：a) 系統(tǒng)的能夠讀塊的平均速率是多少？ 讀塊的平均速率為之前單個磁頭的兩倍。b) 這個速率與無任何約束的鏡像Megatron 747 磁盤的平均速率相比如何？ 平均速率一樣。c）你預(yù)計該系統(tǒng)的缺點是什么？ 1. 缺點是以空間為代價換取時間。 2. 如果其中的一個磁頭壞了，則讀取操作就出問題了，每次只能讀取一半的數(shù)據(jù)。2.4.1計算下列位序列的奇偶校驗位：a）00111011。b）00000000。c）10101101。解：定義：如果有奇數(shù)個數(shù)據(jù)盤的第j位為1，在冗余盤中，我們選取位j為1,；如果在數(shù)據(jù)盤中的第j位有偶數(shù)個1，

10、我們選取冗余盤的位j為0。即：有奇數(shù)個1，為1；有偶數(shù)個1，為0。0 0 1 1 1 0 1 10 0 0 0 0 0 0 01 0 1 0 1 1 0 1-10010110（薛鑫）2.4.2如果我們在一個串末附加一個位作為該串奇數(shù)位置的奇偶校驗位，另一個位作為該串各偶數(shù)位置的奇偶位，我們就有了與一個串關(guān)聯(lián)的兩個奇偶位。對于習(xí)題2.4.1的每一個串，找出按這種方法計算的兩個位。a）00111011。b）00000000。c）10101101。解：RAID5級，不必將一個盤作為冗余盤，而把其他盤作為數(shù)據(jù)盤；相反我們可以把每個磁盤作為某些塊的冗余盤來處理。12345678-0 0 1 1 1 0

11、1 1 100 0 0 0 0 0 0 0 001 0 1 0 1 1 0 1 10（韓月 2141276）2.4.7采用如習(xí)題2.4.5一樣的RAID4級方案，假設(shè)數(shù)據(jù)盤1有故障。在下列情況下恢復(fù)該磁盤的塊：a） 盤2至盤4的內(nèi)容為01110110、11000000和00101011，同時冗余盤保存著11110011。b） 盤2至盤4的內(nèi)容為11110000、11111000、00110011，同時冗余盤保存著10000001。解:a. 1->0 1 1 0 1 1 1 0 2->0 1 1 1 0 1 1 0 3->1 1 0 0 0 0 0 0 4->0 0 1

12、0 1 0 1 1冗->1 1 1 1 0 0 1 1b. 1->1 0 1 1 1 0 1 0 2->1 1 1 1 0 0 0 0 3->1 1 1 1 1 0 0 0 4->0 0 1 1 0 0 1 1冗->1 0 0 0 0 0 0 12.4.8假設(shè)習(xí)題2.4.5第1個盤得塊被改變?yōu)?1010101。其他盤上相應(yīng)的塊必須做什么樣的改變？解：a) 由數(shù)據(jù)盤各位的模2和可求得冗余盤的各位，即00000110。當(dāng)盤1由01010110改為01010101時，求盤1舊值與新值的模2和，得到00000011。將冗余塊自身和00000011求模2和，得到新的冗

13、余塊，即00000101。所以盤1變?yōu)?1010101，冗余盤變?yōu)?0000101，盤2、3、4沒變化。b) 由數(shù)據(jù)盤各位的模2和可求得冗余盤的各位，即01110101。當(dāng)盤1由11110000改為01010101時，求盤1舊值與新值的模2和，得到10100101。將冗余塊自身和10100101求模2和，得到新的冗余塊，即11010000。所以盤1變?yōu)?1010101，冗余盤變?yōu)?1010000，盤2、3、4沒變化。（張柳影 2141286）習(xí)題2.4.9如果我們有例2.13的RAID6級方案，4個數(shù)據(jù)盤的塊分別為00110100、11100111、01010101和10000100。a） 冗

14、余盤的相應(yīng)塊是什么？b） 如果第3個盤的塊被重寫成01111111，必須采取哪些步驟以改變其他盤？注例2.13內(nèi)容：假設(shè)塊只有8位長，并且關(guān)注在我們的RAID6級示例中用到的7個磁盤的第一塊。首先，假設(shè)數(shù)據(jù)盤和冗余盤的第一塊的內(nèi)容如圖2-11所示。請注意，盤5的塊是前3個盤的塊模2和，第6行是行1、2、4的模2和，而最后一行是行1、3、4的模2和。磁盤內(nèi)容數(shù)據(jù)塊 1)111100002)101010103)010101014)10000100冗余塊 5)011000106)000110117)10001001圖2-11 所有磁盤的第一塊答案：a)前4個盤是數(shù)據(jù)盤,盤57是冗余盤.盤5的塊是前3

15、個盤的塊的模2和, 盤5塊是10000110；盤6是盤1,2和4的模2和, 盤6塊是01010111；盤7是盤1,3,4的模2和, 盤7塊是11100101。磁盤內(nèi)容數(shù)據(jù)塊 1)001101002)111001113)010101014)10000100冗余塊 5)100001106)010101117)11100101b)如果第3個盤的塊被重寫成01111111，求這個序列和序列01010101(該塊的舊值)的模2和，則得到00101010；其中為1的位為3、5、7，所以只要對冗余塊5和7的3、5、7位取反，故盤5和盤7的重寫值分別為10101100、11001111。磁盤內(nèi)容數(shù)據(jù)塊 1)0

16、01101002)111001113)011111114)10000100冗余塊 5)101011006)010101117)11001111（樊星宇 2141312）2.4.10RAID 6 方案 從磁盤崩潰中恢復(fù)使用足夠多的冗余盤處理多個磁盤的崩潰，例如，基于海明碼的糾錯技術(shù)7個盤，其中14為數(shù)據(jù)盤，57為冗余盤。數(shù)據(jù)盤與冗余盤之間的關(guān)系由一個3´7矩陣描述如下：1. 盤5的位是盤1,2,3相應(yīng)位的模2和。 2. 盤6的位是盤1,2,4相應(yīng)位的模2和。 3. 盤7的位是盤1,3,4相應(yīng)位的模2和。 習(xí)題2.4.10 假設(shè)塊只有8位長，采用帶有7個磁盤的RAID 6級方案，描述從下

17、列故障中恢復(fù)所要采取的步驟： a)盤1和盤4； b)盤1和盤7； c)盤2和盤5。 （蔣娜 2141288）習(xí)題3.1.1假定一個存儲塊可存放5個記錄，或20個鍵-指針對。已知有n個記錄，如果表示成n的函數(shù)，創(chuàng)建以下兩種數(shù)據(jù)文件各需要多少個數(shù)據(jù)塊：a）稠密索引；b）稀疏索引答案：解:a.稠密索引因為一個存儲塊存儲5個記錄，n個存儲記錄需要n/5個數(shù)據(jù)塊，稠密索引需要為每個記錄建立鍵-指針對，所以鍵-指針需要n/20個數(shù)據(jù)庫，所以表示成n的函數(shù)是n/5+n/20=n/4b.稀疏索引因為一個存儲塊存儲5個記錄，n個存儲記錄需要n/5個數(shù)據(jù)塊，但是稀疏索引需要為每個數(shù)據(jù)塊建立鍵-指針對，所以鍵-指針

18、對需要(n/5)/20個數(shù)據(jù)塊，所以表示成n的函數(shù)是n/5+(n/5)/20=21n/100習(xí)題3.1.2如果數(shù)據(jù)塊中可以存放50個記錄，或500個鍵-指針對，但是存放數(shù)據(jù)和索引的數(shù)據(jù)塊都要求最多只能填滿80%，重做習(xí)題3.1.1.答案:答：我們知道一個記錄在存放時有數(shù)據(jù)文件和索引文件，它們分別占用存儲塊，由題中所述可知在索引塊中我們采用了稠密索引和稀疏索引，這樣兩種形式。只要分別計算出這兩個部分的存儲塊的大小，再求和就能求出需要的存儲塊。下面分別來求： a)一個數(shù)據(jù)文件和一個稠密索引數(shù)據(jù)文件的大小容易知道，由已知給定的記錄數(shù)為n，且每個存儲塊可存放50個記錄, 數(shù)據(jù)塊充滿度不許超過80%。我

19、們得到數(shù)據(jù)文件所占用的存儲塊大小為：n/(50*0.8); 稠密索引是指塊中只存放記錄的鍵以及指向記錄本身的指針，數(shù)據(jù)文件中每個鍵在索引中都被表示出來，且稠密索引文件中的索引塊保持鍵的順序和文件中的排序順序一致，又由已知每個存儲塊可存放500個鍵-指針對，索引塊充滿度不許超過80%。這樣我們就能得到索引文件所占用的存儲塊大小為：n/(500*0.8)。 所以總的結(jié)果=數(shù)據(jù)文件所占用的存儲塊+索引文件所占用的存儲塊= n/(50*0.8)+ n/(500*0.8)=（11/400）*n b)一個數(shù)據(jù)文件和一個稀疏索引同上，數(shù)據(jù)文件的大小容易知道，由已知給定的記錄數(shù)為n，且每個存儲塊可存放50個記

20、錄, 數(shù)據(jù)塊充滿度不許超過80%。我們得到數(shù)據(jù)文件所占用的存儲塊大小為：n/(50*0.8); 稀疏索引與稠密索引不同點在于，稀疏索引在索引中只為每個數(shù)據(jù)塊存放一個鍵。但要注意如果本題按照書中所給出的稀疏索引的比例存放記錄的話，參見P92.則又由已知每個存儲塊可存放500個鍵-指針對，索引塊充滿度不許超過80%。這樣我們就能得到索引文件所占用的存儲塊大小為：n/(50*500*0.8)。這樣才能保證結(jié)果的正確性。 所以總的結(jié)果=數(shù)據(jù)文件所占用的存儲塊+索引文件所占用的存儲塊= n/(50*0.8)+ (n/50*0.8)/500*0.8=401n/16000（萬康 2141289）習(xí)題3.1.

21、5 假定一個存儲塊可以存放5個記錄，或20個鍵-指針對，或100個指針。如果我們使用圖3-7的間接桶模式： a)如果平均每個查找鍵值出現(xiàn)在10個記錄中，存放在5000個記錄和它的輔助索引共需要多少塊？如果不使用桶又需要多少塊？ b)如果給定鍵值的記錄數(shù)沒有限制，所需的最大和最小存儲塊數(shù)各為多少？ 圖3-7 通過在輔助索引中使用間接層以節(jié)省空間解:a)使用桶時 每個數(shù)據(jù)存儲塊可以存儲5個記錄，所以5000個記錄需要的數(shù)據(jù)存儲塊個數(shù)為5000/5=1000 每個桶存儲塊可以存放100個指針，所以存放這5000個記錄輔助索引需要的桶 存儲塊個數(shù)為5000/100=50 每個索引塊設(shè)有20個鍵-指針對

22、，平均每個鍵值出現(xiàn)在10個記錄中，所以存放這5000個記錄的輔助索引需要的索引塊數(shù)為 5000/(20*10)=25 總塊數(shù)=5000/5+5000/100+5000/(20*10) =1000+50+25=1075不使用桶時 索引指針直接對應(yīng)到相應(yīng)的數(shù)據(jù)存儲塊的記錄上塊總數(shù)為5000/5+5000/20=1250圖3-5 輔助索引b)給定鍵值的記錄數(shù)沒有限制 假設(shè)給定鍵值的記錄數(shù)為1，就可以得到最多的存儲塊數(shù)為 5000/5+5000/100+5000/(20*1)=1000+50+250=1300 假設(shè)給定鍵值的記錄數(shù)為5000，就可以得到最少的存儲塊數(shù)為 5000/5+5000/100+

23、1=1051（張恩斌 2141287）習(xí)題3.2.1假定存儲塊能放10個記錄或者99個鍵和100個指針，再假定B樹結(jié)點的平均充滿程度為70%；即有69個鍵和70個指針。我們可以用B樹作為幾種不同結(jié)構(gòu)的一部分。對下面描述的每種結(jié)構(gòu)，確定：（1）1000000個記錄的文件所需的總塊數(shù)；（2）檢索一個給定鍵值的記錄所需的平均磁盤I/O數(shù)。可以假定最初在主存中不存在任何東西，并且查找鍵是記錄的主鍵。a） 數(shù)據(jù)文件是按查找鍵排序的順序文件，每塊存放20個記錄。B-樹為稠密索引a(1)1000000/10=100000塊。B樹為稠密索引，葉結(jié)點中為數(shù)據(jù)文件的每一個記錄設(shè)有一個鍵指針對。首先有100000數(shù)

24、據(jù)塊，如果在B樹底層結(jié)點平均每塊有70個指針，然后有1000000/70=14286個B樹塊在最底層，下一層的B樹需要14286/70=205個B樹塊，第三層需要205/70=3塊，第四層需要1個根塊，所以需要100000+14286+205+3+1=114495塊。 (2)匹配記錄有1000個，首先1000/10=100數(shù)據(jù)塊，1000/70=15塊，15/70=1塊，第三層需要1塊，第四層需要1塊。所以需要100+15+1+1+1=118塊。b）同a）一樣，但組成數(shù)據(jù)文件的記錄沒有特定順序；每塊存放20個記錄。b(1) 1000000/10=100000塊。首先有100000數(shù)據(jù)塊，如果在

25、B樹底層結(jié)點平均每塊有70個指針，然后有1000000/70=14286個B樹塊在最底層，下一層的B樹需要14286/70=205個B樹塊，第三層需要205/70=3塊，第四層需要1個根塊，所以需要100000+14286+205+3+1=114495塊。 (2) 匹配記錄有1000個，首先1000/10=100數(shù)據(jù)塊，1000/70=15塊，15/70=1塊，第三層需要1塊，第四層需要1塊。1000個記錄可能分布在1000個塊中，所以需要1000+15+1+1+1=1018塊。c）同a）一樣，但B樹為稀疏索引。c(1) 1000000/10=100000塊。若B樹為稀疏索引，在葉結(jié)點中為數(shù)據(jù)

26、文件的每個塊設(shè)有一個鍵指針對。首先有100000數(shù)據(jù)塊，如果在B樹底層結(jié)點平均每塊有70個指針，然后有100000/70=1429個B樹塊在最底層，下一層的B樹需要1429/70=21個B樹塊，第三層需要21/70=1塊，第四層需要1個根塊。所以需要100000+1429+21+1+1=101452 (2)匹配記錄有1000個，1000/10=100，首先100/70=2塊，2/70=1塊，第三層需要1塊，第四層需要1塊。所以需要100+2+1+1+1=105塊。d）數(shù)據(jù)文件是順序文件，且B-樹是稀疏索引，但數(shù)據(jù)文件的每個基本塊有一個溢出塊。平均來講，基本塊是滿的，而溢出塊只半滿。不過，記錄在

27、基本塊和溢出塊中沒有特定的順序。d(1) 但數(shù)據(jù)文件的每個基本塊有一個溢出塊。平均來講基本塊是滿的，而溢出塊只是半滿。所以基本快的記錄為10個，溢出塊記錄為5個。所以有1000000/15=66667個數(shù)據(jù)塊。然后有66667/70=953個B樹塊在最低層，下一層的B樹需要953/70=14個B樹塊，第三層需要14/70=1。因此有66667的數(shù)據(jù)塊和953+14+1=968塊個索引塊。一共67635塊。 (2)1000/15=67塊，67/70=1塊，第二層需要1塊，第三層需要1塊。因此有67個數(shù)據(jù)塊和3個索引塊?？偣?0塊磁盤I/O。e）B樹的葉結(jié)點中不放指向數(shù)據(jù)記錄的指針，而是保存記錄本

28、身。每塊可存放10個記錄，但平均每個葉結(jié)點的充滿度為70%，即每個葉結(jié)點存放7個記錄。e(1) 1000000/7=142858塊如果在B樹底層結(jié)點平均每塊有70個指針，然后有142858/70=2041個B樹塊在最底層，下一層的B樹需要2041/70=30個B樹塊，第三層需要30/70=1塊，所以需要142858+2041+30+1=144930塊。 (2)查詢匹配的記錄有1000個，就需要1000/7=143塊，143/70=3塊，3/70=1塊，第三層需要1塊。所以總共需要143+3+1+1=148塊。（謝勝男 2141283）習(xí)題3.2.2假設(shè)查詢是范圍查詢且匹配的記錄有200個，在這

29、種情況下，重做習(xí)題3.2.1。假定存儲塊能放10個記錄或者99個鍵和100個指針，再假定B樹結(jié)點的平均充滿程度為70%；即有69個鍵和70個指針。我們可以用B樹作為幾種不同結(jié)構(gòu)的一部分。對下面描述的每種結(jié)構(gòu)，確定：（1）1000000個記錄的文件所需的總塊數(shù)；（2）假設(shè)查詢是范圍查詢且匹配的記錄有200個，檢索一個給定鍵值的記錄所需的平均磁盤I/O數(shù)。可以假定最初在主存中不存在任何東西，并且查找鍵是記錄的主鍵。a）數(shù)據(jù)文件是按查找鍵排序的順序文件，每塊存放20個記錄。B-樹為稠密索引。b）同a）一樣，但組成數(shù)據(jù)文件的記錄沒有特定順序；每塊存放20個記錄。c）同a）一樣，但B樹為稀疏索引。d）數(shù)

30、據(jù)文件是順序文件，且B-樹是稀疏索引，但數(shù)據(jù)文件的每個基本塊有一個溢出塊。平均來講，基本塊是滿的，而溢出塊只半滿。不過，記錄在基本塊和溢出塊中沒有特定的順序。!e）B樹的葉結(jié)點中不放指向數(shù)據(jù)記錄的指針，而是保存記錄本身。每塊可存放10個記錄，但平均每個葉結(jié)點的充滿度為70%，即每個葉結(jié)點存放7個記錄。解：a)（1）1000000/20=50000塊B樹為稠密索引，葉結(jié)點中為數(shù)據(jù)文件的每一個記錄設(shè)有一個鍵指針對。首先有50000數(shù)據(jù)塊，如果在B樹底層結(jié)點平均每塊有70個指針，然后有1000000/70=14286個B樹塊在最底層，下一層的B樹需要14286/70=205個B樹塊，第三層需要205

31、/70=3塊，第四層需要1個根塊，所以需要50000+14286+205+3+1=64495塊。（2）匹配記錄有200個，首先200/20=10數(shù)據(jù)塊，200/70=3塊，3/70=1塊，第三層需要1塊，第四層需要1塊。所以需要10+3+1+1+1=16塊。b)(1)1000000/20=50000塊B樹為稠密索引，葉結(jié)點中為數(shù)據(jù)文件的每一個記錄設(shè)有一個鍵指針對。首先有50000數(shù)據(jù)塊，如果在B樹底層結(jié)點平均每塊有70個指針，然后有1000000/70=14286個B樹塊在最底層，下一層的B樹需要14286/70=205個B樹塊，第三層需要205/70=3塊，第四層需要1個根塊，所以需要500

32、00+14286+205+3+1=64495塊。(2)匹配記錄有200個， 200/70=3塊，3/70=1塊，第三層需要1塊，第四層需要1塊。200個記錄可能分布在200個塊中，所以需要200+3+1+1+1=206塊。c)(1) 1000000/20=50000塊若B樹為稀疏索引，在葉結(jié)點中為數(shù)據(jù)文件的每個塊設(shè)有一個鍵指針對。首先有50000數(shù)據(jù)塊，如果在B樹底層結(jié)點平均每塊有70個指針，然后有50000/70=715個B樹塊在最底層，下一層的B樹需要715/70=11個B樹塊，第三層需要11/70=1塊。所以需要50000+715+11+1=50727。(2)匹配記錄有200個，200/

33、20=10，首先10/70=1塊，第二層1塊，第三層需要1塊。所以需要10+1+1+1=13塊d)（1）但數(shù)據(jù)文件的每個基本塊有一個溢出塊。平均來講基本塊是滿的，而溢出塊只是半滿。所以基本塊的記錄為20個，溢出塊記錄為10個。所以有1000000/30=33334個數(shù)據(jù)塊。然后有33334/70=477個B樹塊在最低層，下一層的B樹需要477/70=7個B樹塊，第三層需要7/70=1。因此有33334的數(shù)據(jù)塊和477+7+1=485塊個索引塊。一共33819塊。（2）200/30=7塊，7/70=1塊，第二層需要1塊，第三層需要1塊。因此有7個數(shù)據(jù)塊和3個索引塊?？偣?0塊磁盤I/O。e)(1

34、) 1000000/7=142858塊如果在B樹底層結(jié)點平均每塊有70個指針，然后有142858/70=2041個B樹塊在最底層，下一層的B樹需要2041/70=30個B樹塊，第三層需要30/70=1塊，所以需要142858+2041+30+1=144930塊。(2)查詢匹配的記錄有200個，就需要200/7=15塊，15/70=1塊，第二層需要1塊，第三層需要1塊。所以總共需要15+1+1+1=18塊。（岳鑫 2151382）習(xí)題3.7.3考慮一個有1 00 000個記錄的文件，且字段F有m個不同值：a)作為m的一個函數(shù)，F(xiàn)的位圖索引有多少個字節(jié)？b)假定編號從1到1 00 000的記錄的字

35、段F的值按循環(huán)方式給出。因此 ，每個值每隔m個記錄出現(xiàn)一次。使用壓縮索引需要多少個字節(jié)？答：a）100 000*m/81 00 000 * m是總共位圖索引的位數(shù)，用總共的位數(shù)除以8得到所需的字節(jié)數(shù)。 b)j=log2m 共需要100 000/ m*2j）* m/8.解釋：對于每個未壓縮的位圖向量來說，共有1 00 000位二進制來表示，且其中每m個0后有一個1，因為對于m個0后有一個1進行壓縮索引需要2j（其中j=log2m）位二進制，而對于1 00 000位二進制可以出現(xiàn)1 00 000/ m個1，所以，對于一個壓縮的位圖向量需要1 00 000/ m*2j位二進制位來表示，而總共有m個位

36、圖向量，所以一個需要（1 00 000/ m*2j）* m個二進制位來表示，轉(zhuǎn)換成字節(jié)為（1 00 000/ m*2j）* m/8.習(xí)題3.7.4 利用3.7.2節(jié)的方法，編碼下列位圖a) 01100000010000000100b) 100000001000001001010001c) 0001000000000001000010000答案：a) 位向量有4個段(1,0,6,7)，1的編碼是01；0的編碼是00；6的編碼110110；7的編碼110111。它的編碼是0100110110110111b) 位向量有6個段(0,7,5,2,1,3)，0的編碼是00； 7的編碼110111；5的編碼

37、110101；2的編碼是1010；1的編碼是01；3的編碼是1011。它的編碼是001101111101011010011011c) 位向量有3個段(3,11,4)，3的編碼是1011；11的編碼是11101011；4的編碼是110100。它的編碼是101111101011110100（李翰博 2151388）題4.3.1假設(shè)B(R)=B(S)=10000,并且M=1000.計算嵌套連接的磁盤I/O代價。因為M=1000，我們將用999個內(nèi)存塊來按照大小為999塊的chunk對S進行緩沖，我們需要10000/999=10.01次迭代。每一次迭代中，我們用999個磁盤I/O讀取S的chunk，并

38、且在外層循環(huán)中我們必須用10000個磁盤I/O來完整地讀取R，總共需要用10.01*10000=100100個，加上S的10000個，總共需要磁盤I/O代價為10000+100100=110100.題4.3.2 對于習(xí)題4.3.1中的關(guān)系，使用嵌套循環(huán)連接算法計算RS時我們需要什么樣的M值，磁盤I/O才不超過：a）200000；！b）25000；！c）15000.a)B(S)+(B(S)*B(R)/(M-1)<=200000得M>=528b) B(S)+(B(S)*B(R)/(M-1)<=25000得M>=6668c）B(S)+(B(S)*B(R)/(M-1)<=

39、15000得M>=20001.代價代價是aaaaassasdhh（陳思思 2151387）解：a) 消除重復(fù)需要內(nèi)存大小為，所以所需的內(nèi)存大小為20000=1002個塊大小b) 分組需要內(nèi)存大小為，所以所需的內(nèi)存大小為20000=1002個塊大小c) 并需要內(nèi)存大小為，所以所需的內(nèi)存大小為20000+20000=200個塊大小連接需要內(nèi)存大小為，因為每個關(guān)系都是20000個塊，所以所需內(nèi)存大小為20000=1002個塊大小解：a) 簡單的排序-連接需要內(nèi)存大小為，因為B(R)=B(S)=10000,M=500,滿足這一條件磁盤I/O的需求為：5(B(R)+B(S)=5*(10000+10

40、000)=50000b)4.4.8節(jié)更有效排序-連接，磁盤I/O的需求為：3(B(R)+B(S)=3*(10000+10000)=30000c)集合并,磁盤I/O的需求為：3(B(R)+B(S)=3*(10000+10000)=30000（郭曉丹 2151384）習(xí)題4.5.1 如果B(S)=B(R)=10000，M=500，對于一個混合散列連接需要多少磁盤I/O？答：若選擇桶數(shù)k=B(S)/M=20,那么平均每個桶將有S的元組的500個塊，我們在內(nèi)存中容納這些桶中的一個以及其它19個桶中的19個塊，那么就需要519個塊，大于內(nèi)存塊數(shù)，我們選擇k=21.當(dāng)在第一趟中散列S時，我們有對應(yīng)20個桶

41、的20個緩沖區(qū)，桶大小的預(yù)期是B(S)/k=476,對于S，在第一趟中我們用來讀取S的所有內(nèi)容所使用的磁盤I/O的數(shù)目是B(S)=10000，并且B(S)-B(S)/k=10000-476=9524個I/O用來將20個桶寫到磁盤。當(dāng)我們在第一趟中處理R時，需要讀取R的所有內(nèi)容(1000次磁盤I/O)，并將它的21個桶中的20個寫到磁盤上（B(R)(k+1)/k=9523.8個磁盤I/O）。在第二趟中，我們讀取寫到磁盤上的所有桶9524+9523.8=19047.8個磁盤I/O。總的磁盤I/O的數(shù)量就是20000個用于讀取R和S，19047.8個用于將這些關(guān)系中的20/21寫出，再有19047.

42、8個用于再次讀取那些元組，總數(shù)就是58095個磁盤I/O。習(xí)題4.6.1 假設(shè)B(R)=10000，T(R)=500000。R.a上有一個索引，令V(R.a)=k，k是某個常數(shù)，在下面情況下給出a=0(R)的代價作為k的一個函數(shù)。你可以忽略訪問索引自身所需的磁盤I/O。a) 索引是非聚簇的b) 索引是聚簇的c) R是聚簇的，并且不使用索引答：a) T(R)/V(R,a) = 500 000/kb) B(R)/V(R,a) = 10 000/kc) B(R) = 10 000（秦琦冰 2141290）習(xí)題5.2.1給出例子證明：a 重復(fù)消除()不能下推到投影之下b重復(fù)消除不能下推到包并或包差之下

43、。c投影不能下推到集合并之下。d投影不能下推到集合差或包差之下。例子證明如下：(a) 重復(fù)消除不能下推到投影之下:R(a,b) = (1,2),(1,3)R = R, a(R) = (1),(1)a R = (1),(1),(aR) = (1),not equal;(b) 重復(fù)消除不能下推到包差之下：R(a,b) = (1,2),(1,2), S(a,b) = (1,2)R BS = (1,2), (R BS) = (1,2)(R ) B(S) = (1,2) B(1,2) = , not equal;重復(fù)消除不能下推到包并之下：R(a,b) = (1,2),(1,2), S(a,b) = (

44、1,2)RBS = (1,2),(1,2),(1,2),(RBS) = (1,2)(R)B(S) = (1,2)B(1,2) = (1,2),(1,2),not equal;(c) 投影不能下推到集合并之下：R(a,b) = (1,2) , S(a,b) = (1,3)a(RS) =a(1,2),(1,3) = (1,1)(a R)(aS) = (1)(1) = (1)，not equal；(d) 投影不能下推到集合差之下：R(a,b) = (1,2) , S(a,b) = (1,3)a(R-S) = (1)(a R)-(aS) = (1)-(1) = ， not equal；投影不能下推到包

45、差之下：R(a,b) = (1,2),(1,2), S(a,b) = (1,3)R BS = (1,2)，（1,2）, a(R BS) = (1)，（1）(a R ) B(aS) = (1)，（1) B(1) = （1） , not equal;（尹旭明 2151381）習(xí)題5.2.3 某些集合的定律也適用于包；某些則不然。下面每一條定律對于集合都是成立的。判定對包是否也正。對包不正確的給出反例，對包正確的加以證明。a)R-R= b)RR=Rc)RR=Rd)R(ST)=(RS) (RT)解答：a):對于任何包與自身做差運算都為空集。故此定律對包正確。b):包與其本身做交運算其結(jié)果仍是該包本身。

46、故此定律對包正確。c):不正確：反例：假設(shè)R=1,1,2,2 RR=1,1,1,1,2,2,2,2Rd):左邊R(ST) 假設(shè)元組m在R(ST)的結(jié)果當(dāng)中，對于R的元組r，S的元組s，T的元組t對于ST有必存在一個相同的s和t。對于R(ST)則m包含了每一個r和s（或者t）那么對于右邊(RS) (RT)必然存在一個元組包含了每一個r和s，以及另一個元組包含了每一個r和t。則最終的右邊的結(jié)果元組m包含了這兩個元組的至少一個相同元組。即m包含了每一個r和s(或者t).（龐國彬 2151378）習(xí)題5.4.1下面是4個關(guān)系 W、X、Y和Z的關(guān)鍵統(tǒng)計值：W(a,b)X(b,c)Y(c,d)Z(d,e)

47、T(W)=400T(X)=300T(Y)=200T(Z)=100V(W,a)=50V(X,b)=60V(Y,c)=50V(Z,d)=10V(W,b)=40V(X,c)=100V(Y,d)=20V(Z,e)=50估計下列表達式結(jié)果關(guān)系的大?。?a) W X Y Zb) 𝛔a=10(W)c) 𝛔c=20(Y)d) 𝛔c=20(Y) Ze) W × Yf) 𝛔d>10(Z)g) 𝛔a=1 AND b=2(W)h) 𝛔a=1 AND b>2(W)i)答：(a) 各關(guān)系做連接操作結(jié)果為：

48、100*200*300*400 = 2,400,000,000. 由于屬性 b 在兩個關(guān)系里面出現(xiàn)，由其中較大的決定，即V(W,b) 和 V(X,b), 取60. 類似地，對于 c 取 100,對于d 取20. 結(jié)果2,400,000,000/60/100/20=20000 (b) T(W)/V(W,a) = 400/50 = 8. (c) T(Y)/V(Y,c)= 200/50 = 4.(d) ( T(Y)/V(Y,c) )*Z(d,e)/Max(V(Y,d), V(Z,d)=(200/50)*100 / 20=20.(e) W × Y=400*200=80000(f) T(Z)/

49、3 = 100/3 = 33(g) T(W) / (V(W,a)*V(W,b) =400 / 40*50 = 1/5(h) T(W) / V(W,a) * 3 = 400/50*3 =2.67(i) T(X X.c < Y.c Y) = T(X)T(Y)/3*V(X,c) = 200（王亞珂 2151383）5.4.2下面是4個關(guān)系E,F,G,H的統(tǒng)計值：E(a ,b ,c)F(a ,b ,d)G(a ,c ,d)H(b ,c ,d)T(E)=1000T(F)=2000T(G)=3000T(H)=4000V(E ,a)=500V(F ,a)=50V(G ,a)=500V(H ,b)=40

50、0V(E ,b)=100V(F ,b)=200V(G ,c)=300V(H ,c)=200V(E ,c)=20V(F ,d)=100V(G ,d)=100V(H ,d)=800利用這一節(jié)中的估計技術(shù)，估計這些元組的連接會產(chǎn)生多少結(jié)果元組？答案：1000*2000*3000*4000/(500*500*200*400*300*200*100*800)=1/4000000（隨云仙 2151380）習(xí)題5.6.1 對習(xí)題5.4.1中的關(guān)系，給定評價以下所有可能的鏈接順序的動態(tài)規(guī)劃表項 a)只有左深樹。 b)所有樹。在每一種情況下什么是最佳選擇？表5-1 單集合的表WXYZ大小400300200100

51、代價0000最優(yōu)計劃WXYZ表5-2關(guān)系對的表W，XW，YW，ZX，YX，ZY，Z大小20008000040000600300001000代價000000最優(yōu)計劃WXWYWZXYXZYZTW，X=TW*TX/maxV W,b ,VX,b =400*300/60=2000依次類推可以計算出剩下的關(guān)系對的大小表5-3 三個關(guān)系為一組表W，X，YW，X，ZX，Y，ZW，Y，Z大小40002000003000400000代價60020006001000最優(yōu)計劃(XY)W(WX)Z(XY)Z(YZ)W三個關(guān)系為一組，這里我們以計算W，X，Y為例子，依次考慮三對中的每一個。如果我們以WX開始，則代價就是這

52、個關(guān)系的大小為2000（參見關(guān)系對的表格）。以WY開始的中間關(guān)系的代價為80000，以XY開始的中間關(guān)系的代價為600，由于后者是三個選擇中最小的，我們選擇了這個計劃（XY）W，該選擇不僅反映在W，X，Y的代價表項中，而且也反映在最優(yōu)計劃行。依次類推可以確定三個關(guān)系為一組表中剩下的項。只有左深樹時以可能的最佳方法選擇三個進行連接，然后與第四個連接，如下：表5-4 左深樹關(guān)系表分組代價(XY)W)Z4600(WX)Z) Y202000(XY)Z) W3600(YZ)W) X401000連接代價等于關(guān)系的大小加上代價。有兩種通用的方法可以計算全部四個關(guān)系的連接： 1.以可能的最佳方法選擇三個進行連

53、接，然后與第四個連接。 2.將四個關(guān)系劃分為兩對，將每一對進行連接，再將兩個結(jié)果進行連接。表5-5 所有樹分組連接及代價分組代價(XY)W)Z4600(WX)Z) Y202000(XY)Z) W3600(YZ)W) X401000(WX)(YZ)3000(WY)(X Z)110000(WZ)(XY)40600（王亞杰 2151386）習(xí)題5.6.2下面是4個關(guān)系W、X、Y和Z的關(guān)鍵統(tǒng)計值：W(a,b)X(b,c)Y(c,d)Z(d,a)T(W)=400T(X)=300T(Y)=200T(Z)=100V(W,a)=50V(X,b)=60V(Y,c)=50V(Z,d)=10V(W,b)=40V(X

54、,c)=100V(Y,d)=20V(Z,a)=50給定評價以下所有可能的鏈接順序的動態(tài)規(guī)劃表項 a)只有左深樹。 b)所有樹。在每一種情況下什么是最佳選擇？解：由題意得對于單個的集合，它們的大小、代價以及最佳計劃如下圖所示，即對每一個單獨的關(guān)系給定他們每一個的大小分別是400、300、200、100，代價為0，這是因為他們不需要中間關(guān)系，并且最佳的表達式就是關(guān)系本身對于關(guān)系對，由于兩個關(guān)系的鏈接中仍然沒有中間關(guān)系，所以每對關(guān)系的代價為0.兩個關(guān)系中任意一個可以作為左參數(shù)，因此有兩種可能的計劃。因此，對于每一個關(guān)系對，我們都按照字母的順序選擇在前面的作為左參數(shù)，結(jié)果由TW，X=TW*TX/max

55、V W,b ,VX,b算出，于是關(guān)系對的結(jié)果如下圖所示三個關(guān)系為一組，這里我們以計算W，X，Y為例子，依次考慮三對中的每一個。如果我們以WX開始，則代價就是這個關(guān)系的大小為2000（參見關(guān)系對的表格）。以WY開始的中間關(guān)系的代價為80000，以XY開始的中間關(guān)系的代價為600，由于后者是三個選擇中最小的，我們選擇了這個計劃（XY）W，該選擇不僅反映在W，X，Y的代價表項中，而且也反映在最優(yōu)計劃行。依次類推可以確定三個關(guān)系為一組表中剩下的項。只有左深樹時以可能的最佳方法選擇三個進行連接，然后與第四個連接，如下有兩種通用的方法可以計算全部四個關(guān)系的連接： 1.以可能的最佳方法選擇三個進行連接，然后與第四個連接。 2.將四個關(guān)系劃分為兩對，將每一對進行連接，再將兩個結(jié)果進行連接。（林楊 2151377）5.7.1考慮一個關(guān)系R(a,