數(shù)據(jù)庫系統(tǒng)實(shí)現(xiàn)部分習(xí)題參考題答案

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

2、量=盤面數(shù)*磁道數(shù)*扇區(qū)數(shù)*扇區(qū)容量=10*100000*1000*1024字節(jié)=210*109字節(jié)注釋：1有10個(gè)盤面，每個(gè)盤面有100000個(gè)磁道。2磁道平均有1000個(gè)扇區(qū)，每個(gè)扇區(qū)為1024字節(jié).一個(gè)磁道存放存放1000*1024*8=8192000bits.直徑為3.5英尺那么中間磁道直徑為3.5/2英寸中間扇區(qū)所占的周長是80*3.5/2英寸所以，每個(gè)磁道的扇區(qū)中的平均密度是 注釋： 2磁道平均有1000個(gè)扇區(qū)，每個(gè)扇區(qū)為1024字節(jié). 3每個(gè)磁道的20%被用于間隙. 最大尋道時(shí)間是磁頭跨越全部柱面所花費(fèi)的時(shí)間。即1+0.0002*99999=20.9998ms： 1有10個(gè)盤面，

3、每個(gè)盤面有100000個(gè)磁道。 5磁頭移動(dòng)n個(gè)磁道所需要的時(shí)間是1+0.0002n ms。最大旋轉(zhuǎn)等待時(shí)間是磁頭旋轉(zhuǎn)一圈的時(shí)間。即1/(10000/60)= 6ms： 4磁盤旋轉(zhuǎn)為10000轉(zhuǎn)/min。該塊占用64個(gè)扇區(qū)，為此，磁頭必須越過64個(gè)扇區(qū)和扇區(qū)之間的63個(gè)間隙。由于間隙合在一起占72度圓弧，而扇區(qū)覆蓋剩余288度圓弧，那么被它們覆蓋的圓弧的總度數(shù)為： 72*(63/1000)+288*(64/1000)=22.968那么傳輸時(shí)間是22.968/360*0.6ms=0.03828ms：3每個(gè)磁道的20%被用于間隙。2磁道平均有1000個(gè)扇區(qū) 。d中最大旋轉(zhuǎn)等待時(shí)間為6ms。磁頭行進(jìn)的

4、平均距離是跨越柱面的1/3，那么平均尋道時(shí)間是：1+0.001*100000/3=34.33ms平均旋轉(zhuǎn)等待時(shí)間為磁盤旋轉(zhuǎn)半周所需時(shí)間: (1/2)*6ms=3msExercise 2.2.1(a)The disk has 10 * 10,000 = 100,000 tracks. The average track has 1000 * 512 = 512,000 bytes. Thus,the capacity is 51.2 gigabytes.Exercise 2.2.1(c)The maximum seek time occurs when the heads have to mov

5、e across all the tracks. Thus, substitute10,000 (really 9999) for n in the formula 1+.001n to get 11 milliseconds.Exercise 2.2.1(d)The maximum rotational latency is one full revolution. Since the disk rotates at 10,000 rpm, it takes1/10000 of a minute, or 1/167 of a second to rotate, or about 6 mill

6、iseconds.2.4.1計(jì)算以下位序列的奇偶校驗(yàn)位：a00111011。b00000000。c10101101。解：定義：如果有奇數(shù)個(gè)數(shù)據(jù)盤的第j位為1，在冗余盤中，我們選取位j為1,；如果在數(shù)據(jù)盤中的第j位有偶數(shù)個(gè)1，我們選取冗余盤的位j為0。即：有奇數(shù)個(gè)1，為1；有偶數(shù)個(gè)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習(xí)題2.4.9如果我們有例2.13的RAID6級(jí)方案，4個(gè)數(shù)據(jù)盤的塊分別為00110100、11100111、01010101和10000100。冗余盤的相應(yīng)塊是什么如果第3個(gè)盤的塊被重寫成011111

7、11，必須采取哪些步驟以改變其他盤注例2.13內(nèi)容：假設(shè)塊只有8位長，并且關(guān)注在我們的RAID6級(jí)例如中用到的7個(gè)磁盤的第一塊。首先，假設(shè)數(shù)據(jù)盤和冗余盤的第一塊的內(nèi)容如圖2-11所示。請(qǐng)注意，盤5的塊是前3個(gè)盤的塊模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個(gè)盤是數(shù)據(jù)盤,盤57是冗余盤.盤5的塊是前3個(gè)盤的塊的模2和, 盤5塊是10000110；盤6是盤1,2和4

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

9、000100冗余塊 5)101011006)010101117)110011112.4.10RAID 6 方案 從磁盤崩潰中恢復(fù)使用足夠多的冗余盤處理多個(gè)磁盤的崩潰，例如，基于海明碼的糾錯(cuò)技術(shù)7個(gè)盤，其中14為數(shù)據(jù)盤，57為冗余盤。數(shù)據(jù)盤與冗余盤之間的關(guān)系由一個(gè)37矩陣描述如下：盤5的位是盤1,2,3相應(yīng)位的模2和。盤6的位是盤1,2,4相應(yīng)位的模2和。盤7的位是盤1,3,4相應(yīng)位的模2和。習(xí)題2.4.10 假設(shè)塊只有8位長，采用帶有7個(gè)磁盤的RAID 6級(jí)方案，描述從以下故障中恢復(fù)所要采取的步驟： a)盤1和盤4； b)盤1和盤7； c)盤2和盤5。2.5.1假設(shè)一條記錄有如下所示順序的字段

10、:一個(gè)長度為15的字符串，一個(gè)2字節(jié)整數(shù)，一個(gè)SQL2日期，一個(gè)SQL2時(shí)間無小數(shù)點(diǎn)。如果a)字段可在任何字節(jié)處開場(chǎng)；b)字段必須在4的倍數(shù)的字節(jié)處開場(chǎng)；c)字段必須在8的倍數(shù)的字節(jié)處開場(chǎng)；這條記錄占用多少個(gè)字節(jié)First, note that SQL2 dates require 10 bytes, and SQL2 times require 8 bytes if there is no decimal point; this material is in Section 3.1.3.a) The bytes requirsed by each of the fields is 15 +

11、2 + 10 + 8 = 35.b) Round each of the four field lengths up to a multiple of 4, to get 16 + 4 + 12 + 8 = 40.c) Round up again, to a multiple of 8, to get 16 + 8 + 16 + 8 = 48.首先，請(qǐng)注意SQL2日期需要10個(gè)字節(jié)，SQL2次需要8個(gè)字節(jié)沒有小數(shù)點(diǎn)，點(diǎn)，這種材料是在3.1.3節(jié)。A由每個(gè)字段需要的字節(jié)是15+2+10+8=35。B每此循環(huán)的四個(gè)字段長度為4的倍數(shù),即所有字段長度為4的倍數(shù)，得到16+ 4 +12+8=40。C

12、再次循環(huán)，到8的倍數(shù),即所有字段長度為8的倍數(shù)，得到16+8+16+8= 48。2.6.5采用如習(xí)題2.6.4一樣的RAID4級(jí)方案，假設(shè)數(shù)據(jù)盤1有故障。在以下情況下恢復(fù)該磁盤的塊：a)盤2盤4的內(nèi)容為01010110、11000000和00111011，同時(shí)冗余盤保存著11111011。b)盤2盤4的內(nèi)容為11110000、11111000和00111111，同時(shí)冗余盤保存著00000001。答案:a、磁盤1的內(nèi)容：0 1 0 1 0 1 1 0b、磁盤1的內(nèi)容：0 0 1 1 0 1 1 02.6.7如果我們有例2.22的RAID6級(jí)方案，4個(gè)數(shù)據(jù)盤的塊分別為00111100、110001

13、11、01010101和10000100。a)冗余盤的相應(yīng)塊是什么b)如果第三個(gè)盤的塊被重寫成10000000，必須采取哪些步驟以改變其他盤答案：RAID6級(jí)方案，4個(gè)數(shù)據(jù)塊，3個(gè)冗余塊第1對(duì)應(yīng)數(shù)據(jù)塊123的模2和，第2對(duì)應(yīng)124的模2和，第3對(duì)應(yīng)134的模2和a數(shù)據(jù)塊 100111100211000111301010101410000100冗余塊 110101110201111111311101101b 原第三塊01010101與重寫塊10000000模2和為11010101，其中為1的位為1、2、4、6、8所以只要對(duì)冗余塊1、2塊的1、2、4、6、8位求反得01111011，1010101

14、0習(xí)題3.1.1假定一個(gè)存儲(chǔ)塊可存放5個(gè)記錄，或20個(gè)鍵-指針對(duì)。有n個(gè)記錄，如果表示成n的函數(shù)，創(chuàng)立以下兩種數(shù)據(jù)文件各需要多少個(gè)數(shù)據(jù)塊：a稠密索引；b稀疏索引答案：解:a.稠密索引因?yàn)橐粋€(gè)存儲(chǔ)塊存儲(chǔ)5個(gè)記錄，n個(gè)存儲(chǔ)記錄需要n/5個(gè)數(shù)據(jù)塊，稠密索引需要為每個(gè)記錄建設(shè)鍵-指針對(duì)，所以鍵-指針需要n/20個(gè)數(shù)據(jù)庫，所以表示成n的函數(shù)是n/5+n/20=n/4b.稀疏索引因?yàn)橐粋€(gè)存儲(chǔ)塊存儲(chǔ)5個(gè)記錄，n個(gè)存儲(chǔ)記錄需要n/5個(gè)數(shù)據(jù)塊，但是稀疏索引需要為每個(gè)數(shù)據(jù)塊建設(shè)鍵-指針對(duì)，所以鍵-指針對(duì)需要(n/5)/20個(gè)數(shù)據(jù)塊，所以表示成n的函數(shù)是n/5+(n/5)/20=21n/100習(xí)題3.1.2如果數(shù)據(jù)

15、塊中可以存放50個(gè)記錄，或500個(gè)鍵-指針對(duì)，但是存放數(shù)據(jù)和索引的數(shù)據(jù)塊都要求最多只能填滿80%，重做習(xí)題3.1.1.答案:答：我們知道一個(gè)記錄在存放時(shí)有數(shù)據(jù)文件和索引文件，它們分別占用存儲(chǔ)塊，由題中所述可知在索引塊中我們采用了稠密索引和稀疏索引，這樣兩種形式。只要分別計(jì)算出這兩個(gè)局部的存儲(chǔ)塊的大小，再求和就能求出需要的存儲(chǔ)塊。下面分別來求： a)一個(gè)數(shù)據(jù)文件和一個(gè)稠密索引數(shù)據(jù)文件的大小容易知道，由給定的記錄數(shù)為n，且每個(gè)存儲(chǔ)塊可存放50個(gè)記錄, 數(shù)據(jù)塊充滿度不許超過80%。我們得到數(shù)據(jù)文件所占用的存儲(chǔ)塊大小為：n/(50*0.8); 稠密索引是指塊中只存放記錄的鍵以及指向記錄本身的指針，數(shù)據(jù)

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

17、索引在索引中只為每個(gè)數(shù)據(jù)塊存放一個(gè)鍵。但要注意如果此題按照書中所給出的稀疏索引的比例存放記錄的話，參見P92.那么又由每個(gè)存儲(chǔ)塊可存放500個(gè)鍵-指針對(duì)，索引塊充滿度不許超過80%。這樣我們就能得到索引文件所占用的存儲(chǔ)塊大小為：n/(50*500*0.8)。這樣才能保證結(jié)果的正確性。 所以總的結(jié)果=數(shù)據(jù)文件所占用的存儲(chǔ)塊+索引文件所占用的存儲(chǔ)塊= n/(50*0.8)+ (n/50*0.8)/500*0.8=401n/160003.2.1 假定存儲(chǔ)塊能放10個(gè)記錄或者99個(gè)鍵和100個(gè)指針，再假定B樹結(jié)點(diǎn)的平均充滿程度為70%；即有69個(gè)鍵和70個(gè)指針。我們可以用B樹作為幾種不同構(gòu)造的一局部。

18、對(duì)下面描述的每種構(gòu)造，確定：11000000個(gè)記錄的文件所需的總塊數(shù)；2檢索一個(gè)給定鍵值的記錄所需的平均磁盤I/O數(shù)?？梢约俣ㄗ畛踉谥鞔嬷胁淮嬖谌魏螙|西，并且查找鍵是記錄的主鍵。*a)數(shù)據(jù)文件是按查找鍵排序的順序文件，每塊存放10個(gè)記錄。B樹為稠密索引。b)同a一樣，但組成數(shù)據(jù)文件的記錄沒有特定順序；每塊存放10個(gè)記錄。c)同a一樣，但B樹為稀疏索引。!d)B樹的葉結(jié)點(diǎn)中不放指向數(shù)據(jù)記錄的指針，而是保存記錄本身。每塊可存放10個(gè)記錄，但平均每個(gè)葉結(jié)點(diǎn)的充滿度為70%，即每個(gè)葉結(jié)點(diǎn)存入7個(gè)記錄。*e)數(shù)據(jù)文件是順序文件，且B樹是稀疏索引，但數(shù)據(jù)文件的每個(gè) 基本塊有一個(gè)溢出塊。平均來講， 基本塊是

19、滿的，而溢出塊只半滿。不過，記錄在 基本塊和溢出塊中沒有特定的順序。張恩斌 2141287習(xí)題3.2.1假定存儲(chǔ)塊能放10個(gè)記錄或者99個(gè)鍵和100個(gè)指針，再假定B樹結(jié)點(diǎn)的平均充滿程度為70%；即有69個(gè)鍵和70個(gè)指針。我們可以用B樹作為幾種不同構(gòu)造的一局部。對(duì)下面描述的每種構(gòu)造，確定：11000000個(gè)記錄的文件所需的總塊數(shù)；2檢索一個(gè)給定鍵值的記錄所需的平均磁盤I/O數(shù)?？梢约俣ㄗ畛踉谥鞔嬷胁淮嬖谌魏螙|西，并且查找鍵是記錄的主鍵。數(shù)據(jù)文件是按查找鍵排序的順序文件，每塊存放20個(gè)記錄。B-樹為稠密索引a(1)1000000/10=100000塊。B樹為稠密索引，葉結(jié)點(diǎn)中為數(shù)據(jù)文件的每一個(gè)記錄

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

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

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

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

24、中不放指向數(shù)據(jù)記錄的指針，而是保存記錄本身。每塊可存放10個(gè)記錄，但平均每個(gè)葉結(jié)點(diǎn)的充滿度為70%，即每個(gè)葉結(jié)點(diǎn)存放7個(gè)記錄。e(1) 1000000/7=142858塊如果在B樹底層結(jié)點(diǎn)平均每塊有70個(gè)指針，然后有142858/70=2041個(gè)B樹塊在最底層，下一層的B樹需要2041/70=30個(gè)B樹塊，第三層需要30/70=1塊，所以需要142858+2041+30+1=144930塊。 (2)查詢匹配的記錄有1000個(gè)，就需要1000/7=143塊，143/70=3塊，3/70=1塊，第三層需要1塊。所以總共需要143+3+1+1=148塊。3.2.5假設(shè)字段如3.2.1，記錄有個(gè)首部，

25、它由兩個(gè)四字節(jié)的指針和一個(gè)字符組成，且我們希望在一個(gè)4096個(gè)字節(jié)的塊中裝入盡可能多的記錄，使用的塊首部由10個(gè)4字節(jié)的整數(shù)組成，對(duì)習(xí)題3.2.1中的三個(gè)情況，我們各能將多少記錄裝入塊中參考3.2.1題答案( 4096 40 ) / 35( 4096 40 ) / 40( 4096 80 ) / 483.3.3 假假設(shè)在圖散列表中發(fā)生以下插入和刪除，請(qǐng)說明將產(chǎn)生什么情況：1)記錄g到記錄j分別插入桶0到桶3。2)記錄a和b記錄被刪除。3)記錄k到n分別插入桶0到桶3。4)記錄c和d被刪除。答案：(題目沒給出是否順序產(chǎn)生這4種情況還是各自獨(dú)立發(fā)生)設(shè)4種情況獨(dú)立發(fā)生g直接插入到桶0中的第二個(gè)存儲(chǔ)

26、塊；增加一個(gè)新存儲(chǔ)塊在該存儲(chǔ)塊的第一塊上存儲(chǔ)h，并鏈接到桶1的第一塊上；i直接插入到桶2中的第二個(gè)存儲(chǔ)塊；增加一個(gè)新存儲(chǔ)塊在該存儲(chǔ)塊的第一塊上存儲(chǔ)j，并鏈接到桶1的第一塊上；2、在桶3上刪除該a記錄并將剩下的記錄移動(dòng)到塊前部以使其緊湊；在桶2上直接刪除該b記錄習(xí)題3.7.4利用3.7.2節(jié)的方法，編碼以下位圖011000000100000001001000000010000010010100010001000000000001000010000答案：位向量有4個(gè)段(1,0,6,7)，1的編碼是01；0的編碼是00；6的編碼110110；7的編碼110111。它的編碼是0100110110110

27、111位向量有6個(gè)段(0,7,5,2,1,3)，0的編碼是00； 7的編碼110111；5的編碼110101；2的編碼是1010；1的編碼是01；3的編碼是1011。它的編碼是001101111101011010011011位向量有3個(gè)段(3,11,4)，3的編碼是1011；11的編碼是11101011；4的編碼是110100。它的編碼是101111101011110100Exercise 4.2.1(a)The iterator for pi_L(R) can be described informally as follows:Open():R.Open()GetNext():Let t

28、= R.GetNext(). If Found = False, return. Else, construct and return the tuple consistingof the elements of list L evaluated for tuple t.Close():R.Close()Exercise 4.2.1 (b)Here is the iterator for delta(R):Open():First perform R.Open(). Then, initialize a main-memory structure S that will represent a

29、 set oftuples of R seen so far. For example, a hash table could be used. Initially, set S is empty.GetNext():Repeat R.GetNext() until either Found = False or a tuple t that is not in set S is returned. Inthe later case, insert t into S and return that tuple.Close():R.Close()Exercise 4.2.1 (d)For the

30、 set union R1 union R2 we need both a set S that will store the tuples of R1 and a flag CurRelas in Example 6.13. Here is a summary of the iterator:Open()Perform R1.Open() and initialize to empty the set S.GetNext()If CurRel = R1 then perform t = R1.GetNext(). If Found = True, then insert t into S a

31、ndreturn t. If Found = False, then R1 is exhausted. Perform R1.Close(), R2.Open(), setCurRel = R2, and repeatedly perform t = R2.GetNext() until either Found = False (inwhich case, just return), or t is not in S. In the latter case, return t.Close():Perform R2.Close()題4.3.1假設(shè)B(R)=B(S)=10000,并且M=1000

32、.計(jì)算嵌套連接的磁盤I/O代價(jià)。因?yàn)镸=1000，我們將用999個(gè)內(nèi)存塊來按照大小為999塊的chunk對(duì)S進(jìn)展緩沖，我們需要10000/999=10.01次迭代。每一次迭代中，我們用999個(gè)磁盤I/O讀取S的chunk，并且在外層循環(huán)中我們必須用10000個(gè)磁盤I/O來完整地讀取R，總共需要用10.01*10000=100100個(gè)，加上S的10000個(gè)，總共需要磁盤I/O代價(jià)為10000+100100=110100.假設(shè)B(R)= B(S)=10000 ,并且M=1000,計(jì)算嵌套循環(huán)連接的磁盤I/O代價(jià)The formula in Section 6.4.4 gives 10000 + 1

33、0000*10000/999 or 110,101.這個(gè)公式在6.4.4 章節(jié)所給的結(jié)果是10000+10000*10000/999或者110,101編者注: 6.4.4章節(jié)公式:B(S)+Exercise 4.3.1The formula in Section 6.4.4 gives 10000 + 10000*10000/999 or 110,101.題4.3.2 對(duì)于習(xí)題4.3.1中的關(guān)系，使用嵌套循環(huán)連接算法計(jì)算RS時(shí)我們需要什么樣的M值，磁盤I/O才不超過：a200000；！b25000；！c15000.a)B(S)+(B(S)*B(R)/(M-1)=528b) B(S)+(B(S)

34、*B(R)/(M-1)=6668cB(S)+(B(S)*B(R)/(M-1)=20001.Exercise 4.4.1 (a)An iterator for delta(R) must do the first sorting pass in its Open() function. Here is a sketch:Open():Perform R.Open() and repeatedly use R.GetNext() to read memory-sized chunks of R. Sorteach into a sorted sublist and write out the li

35、st. Each of these lists may be thought of as havingits own iterator. Open each list and initialize a data structure into which the current elementof each list may be read into main memory. Use GetNext() for each list to initialize the mainmemory structure with the first element of each list. Finally

36、, execute R.Close().GetNext():Find the least tuple t in the main-memory structure, and output one copy of it. Delete all copiesof t in main memory, using GetNext() for the appropriate sublist, until all copies of t havedisappeared, then return. If there was no such tuple t, because all the sublists

37、were exhausted,set Found = False and return.Close():Close all the sorted sublists.Exercise 4.4.2 (c)For R1 intersect R2 do the following:Open():Open R1 and R2, use their GetNext() functions to read all their tuples in main-memory-sizedchunks, and create sorted sublists, which are stored on disk. Ini

38、tialize a main-memory datastructure that will hold the current tuple of each sorted sublist, and use the Open() andGetNext() functions of an iterator from each sublist to initialize the structure to have the firsttuple from each sublist. Finally, close R1 and R2.GetNext():Find the least tuple t amon

39、g all the first elements of the sorted sublists. If t occurs on a list fromR1 and a list from R2, then output t, remove the copies of t, use GetNext from the two sublistsinvolved to replentish the main-memory structure, and return. If t appears on only one of thesublists, do not output t. Ratherm re

40、move it from its list, replentish that list, and repeat thesesteps with the new least t. If no t exists, because all the lists are exhausted, set Found = Falseand return.Close():Close all the sorted sublists.Exercise 6.5.3(b)The formula of Fig. 6.16 gives 5*(10000+10000) = 100,000. Note that the mem

41、ory available, whichis 1000 blocks, is larger than the minimum required, which is sqrt(10000), or 100 blocks. Thus, themethod is feasible代價(jià)代價(jià)是aaaaassasdhh解：消除重復(fù)需要內(nèi)存大小為，所以所需的內(nèi)存大小為20000=1002個(gè)塊大小分組需要內(nèi)存大小為，所以所需的內(nèi)存大小為20000=1002個(gè)塊大小并需要內(nèi)存大小為，所以所需的內(nèi)存大小為20000+20000=200個(gè)塊大小連接需要內(nèi)存大小為，因?yàn)槊總€(gè)關(guān)系都是20000個(gè)塊，所以所需內(nèi)存大小為2

42、0000=1002個(gè)塊大小5.2.5針對(duì)表達(dá)式L(R(a,b,c) S(b,c,d,e) ,盡可能下推投影，其中L是: a)b+cx c+dy 。b)a,b,a+dz。We cannot push down b+c -& x, because both b and c are used in the join. Notice that if wereplaced b+c by their sum before joining, we would join tuples whose sum b+c agreed, but that had different values of b and c.

43、 What we can push down is:1. The elimination of a from R.2. The elimination of e from S.3. The replacement of c+d by y in S. Thus, the answer is:pi_b+c-x, y(pi_b,c(R) JOIN pi_b, c, c+d-y(S)因?yàn)樵诼?lián)接中b和c都被用到，所以我們不能推出b+c-x。注意：如果我們?cè)谶B接之前用b+c的和來替換b+c，我們可以連接b和c相加所允許的元祖，但是b和c的值是不同的。我們可以推出的是：從R中消去a從S中消去e在S中y替換c

44、+d因此，答案是：a)b+c-x,y(b,c(R) JOIN b,c,c+d-y(S)b)a,b,a+d-z(a,b,c(R) JOIN b,c,d(S)林楊 21513775.7.1考慮一個(gè)關(guān)系R(a,b,c,d),該關(guān)系有一個(gè)a上的劇簇索引以及每一個(gè)其他屬性上的非聚簇索引。相關(guān)參數(shù)為：B(R)=500,T(R)=5000,V(R,a)=50,V(R,b)=1000,V(R,c)=5000,V(R,d)=500。給出最正確查詢方案索引掃描或者表掃描然后進(jìn)展一個(gè)過濾器操作步驟以及以下選擇運(yùn)算的每一個(gè)的磁盤I/O開銷：(A)a=1ANDb=2ANDc=3(R)(B)a=1ANDb=3(R)(C)

45、a=1ANDb=2ANDd=3(R)以第一道題為例,有以下幾種方式：1表掃描后進(jìn)展過濾，其代價(jià)是B(R)，即500次的磁盤I/O，因?yàn)镽是聚集的。2使用a的索引以及索引掃描來找出a=1的元組，然后利用過濾操作來檢測(cè)b=2以及c=3，由于有B(R)/V(R,a)=10個(gè)元組的a=1，并且索引是聚集的，我們大約需要10次I/O。3使用b的索引以及索引掃描來找出b=2的元組，然后利用過濾操作來檢測(cè)a=1以及c=3，由于有T(R)/V(R,b)=5個(gè)元組的b=2，并且索引是非聚集的，我們大約需要5次I/O。4使用c的索引以及索引掃描來找出c=3的元組，然后利用過濾操作來檢測(cè)a=1以及b=2，由于有T(

46、R)/3=167個(gè)元組的c=3，并且索引是非聚集的，我們大約需要167次I/O。我們可以看到代價(jià)最小的方案是第三種，估計(jì)代價(jià)為5次磁盤I/O。因此，這個(gè)選擇的最正確物理方案搜索b=2的元組，然后為另外兩個(gè)條件進(jìn)展過濾。5.7.1考慮一個(gè)關(guān)系R(a,b,c,d),該關(guān)系有一個(gè)a的聚簇索引以及對(duì)每一個(gè)其他屬性的非聚簇索引。相關(guān)變?cè)獮?B(R)=1000,T(R)=5000,V(R,a)=20,V(R,b)=1000,V(R,c)=5000,V(R,d)=500.對(duì)于以下各項(xiàng)選擇，給出最正確查詢方案(索引掃描或者表掃描，然后進(jìn)展一個(gè)過濾步驟)以及磁盤I/O開銷a)a=1 and b=2 and d=

47、3(R) b)a=1 and b=2 and c=3(R) c)a=1 and b=3(R)Use an index-scan using the nonclustering index on c. Since V(R,c) = 5000, only one block should be retrieved. Filter the retrieved tuples for a=1 and d=3. The expected disk I/O cost is 1.使用索引掃描，使用非聚簇索引掃描c，當(dāng)V(R,c)=5000，只有一塊被檢索到。用a=1 and b=2 and d=3過濾檢索元組

48、。預(yù)期的磁盤I/O的成本是1。編者注： R被聚簇那么為B(R) ,R沒有被聚簇那么為B(R)，以a=常數(shù)來掃描的算法代價(jià)是：如果索引是聚簇索引那么為B(R)/V(R,a)；如果索引是非聚簇索引那么為T(R)/V(R,a)以不等項(xiàng)，形如a常數(shù)來掃描的算法代價(jià)是：如果索引是聚簇索引那么為B(R)/3；如果索引是非聚簇索引那么為T(R)/3編者注：1) 表-掃描后進(jìn)展過濾。因?yàn)镽為聚簇，其代價(jià)為B(R)=1000,即1000次磁盤I/O2) 使用a的索引以及索引掃描找出a=1的元祖，然后利用過濾操作符來檢查b=2 and d=3,因?yàn)閍聚簇索引，為會(huì)有B(R)/V(R,a)=50個(gè)元祖，需要50次I

49、/O3) 使用b的索引以及索引掃描找出b=2的元祖，然后利用過濾操作符來檢查a=1 and d=3,因?yàn)閎非聚簇索引，為會(huì)有T(R)/V(R,b)=5個(gè)元祖，需要5次I/O4) 使用d的索引以及索引掃描找出d=3的元祖，然后利用過濾操作符來檢查b=2 and a=1,因?yàn)閐非聚簇索引，為會(huì)有T(R)/V(R,d)=10個(gè)元祖，需要10次I/O5) 使用c的索引以及索引掃描找出所有元祖，然后利用過濾操作符來檢查a=1 and b=2 and d=3,因?yàn)閏非聚簇索引，為會(huì)有T(R)/V(R,c)=1個(gè)元祖，需要1次I/O6.1.2對(duì)習(xí)題6.1.1中的每個(gè)事務(wù)，在計(jì)算中參加讀寫動(dòng)作，并給出各步驟對(duì)

50、主存和磁盤產(chǎn)生的影響。假設(shè)最初A=50且B=25.此外，請(qǐng)說明當(dāng)OUTPUT動(dòng)作順序恰當(dāng)時(shí)，是否可能即使在事務(wù)的執(zhí)行過程中發(fā)生了故障，一致性仍能得到保持。6.1.1事務(wù)：a) B:=A+B;A:=A+B;b)A:=B+1;B:=A+1;c)A:=A+B;B:=A+B; a)動(dòng)作t內(nèi)存中的A內(nèi)存中的B磁盤中的A磁盤中的BREAD(B,t1)25255025READ(A,t2)5050255025t1:=t2+RITE(B,t1)7550755025t2:=t2+t112550755025WRITE(A,t2)125125755025OutputB,t1)75125755

51、075Output(A,t2)1251257512575b)動(dòng)作t內(nèi)存中的A內(nèi)存中的B磁盤中的A磁盤中的BREAD(A,t1)50505025READ(B,t2)2550255025t1:=t2+12650255025WRITE(A,t1)2626255025t2:=t1+12726255025WRITE(B,t2)2726275025OutputA,t1)2626272625Output(B,t2)2726272627c)動(dòng)作t內(nèi)存中的A內(nèi)存中的B磁盤中的A磁盤中的BREAD(A,t1)50505025READ(B,t2)2550255025t1:=t1+t27550255025WRITE(

52、A,t1)7575255025t2:=t1+t210075255025WRITE(B,t2)100751005025OutputA,t1)75751007525Output(B,t2)1007510075100如果OUTPUT動(dòng)作順序恰當(dāng)，即使在事務(wù)執(zhí)行過程中發(fā)生故障，一致性仍能得到保持。6.2.3下面是兩個(gè)事務(wù)T和U的一系列日志記錄：; ; ; ; ; ; ; ; ; 。請(qǐng)描述恢復(fù)管理器的行為，包括對(duì)磁盤和日志所做的改變，假設(shè)故障發(fā)生且出現(xiàn)在磁盤上的最后一條日志記錄為：a) b) c) d)a事務(wù)T、U未提交，要被撤銷。向后掃描日志，遇到記錄，于是將A在磁盤上的值存為10。最后，記錄和被寫到

53、日志中且日志被刷新。b事務(wù)T已提交，U未提交，要被撤銷。向后掃描日志，遇到記錄，于是將C在磁盤上的值存為30。最后，記錄被寫到日志中且日志被刷新。c事務(wù)T已提交，U未提交，要被撤銷。向后掃描日志，首先遇到記錄，將E在磁盤上的值存為50。接著遇到記錄，于是將C在磁盤上的值存為30。最后，記錄被寫到日志中且日志被刷新。d) 事務(wù)T、U均被提交。什么都不做。6.2.3 下面是兩個(gè)事務(wù)T和U的一系列日志記錄：;.描述恢復(fù)管理器的行為，包括對(duì)磁盤盒日志所做的改變，假設(shè)發(fā)生故障且出現(xiàn)在磁盤上的最后一條日志記錄為(編者注：故障發(fā)生在以下語句的后一句，試描述如何恢復(fù))：a) b) c) d)U is iden

54、tified as committed, while T is not. Thus, T must be undone. Scanning the log backwards,we set C to 30 and A to 10. Then, we write an T record on the log.a.不需要undob.C=30,A=10 事務(wù)U狀態(tài)是提交，而T不是。因此，T必須undone。掃描日志，我們?cè)O(shè)置C=30和A=10。然后，我們?cè)谌罩緦懸粋€(gè)記錄。c.E=50,C=30,A=10編者注：undo還沒有提交的數(shù)據(jù)要恢復(fù),數(shù)據(jù)時(shí)老數(shù)據(jù)使用redo日志重做上題Since T is

55、not complete, we can be sure that none of its changes reached disk, and we can ignore log records about T. On the other hand, U was committed, and its log record reached disk, so some of its changes may have reached disk. To be sure, we must redo all of the actions of U. Thus, we first set B to 20 a

56、nd then set D to 40.因?yàn)門沒有完成，我們可以肯定他的任何變化都沒有到達(dá)磁盤，我們可以忽略關(guān)于T的日志記錄，另一方面，U提交了，他的日志寫道了磁盤上。它的一些變化也到達(dá)磁盤的?？梢钥隙ǖ氖?，我們必須重做U的所有行動(dòng)，因此，我們首先B=20，然后到D=40編者注：redo已經(jīng)提交的數(shù)據(jù)要重新做，數(shù)據(jù)時(shí)新數(shù)據(jù)6.2.3下面是兩個(gè)事務(wù)T和U的一系列日志記錄：;。請(qǐng)描述恢復(fù)管理器的行為，包括對(duì)磁盤和日志所作的改變，假設(shè)故障發(fā)生且出現(xiàn)在磁盤上的最后一條日志記錄為：a) b) c) d)答案1假設(shè)題目是:; ; .那么答案是首先掃描日志,發(fā)現(xiàn)事務(wù)T和U都未commit,將其連接到未完成事

57、務(wù)列.按照未完成事務(wù)列,從后往前逐步掃描日志并執(zhí)行undo操作，按照將磁盤中A值寫為10,將和寫入日志中并刷新日志。首先掃描日志,發(fā)現(xiàn)事務(wù)T已經(jīng)commit，將其連接到已完成事務(wù)列,事務(wù)U未完成，將其連接到未完成事務(wù)列。按照未完成事務(wù)列，從后往前掃描日志執(zhí)行undo操作，按照將磁盤中C值寫為30，將磁盤A值寫為10。將寫入日志中并刷新日志。首先掃描日志,發(fā)現(xiàn)事務(wù)T已經(jīng)commit，將其連接到已完成事務(wù)列,事務(wù)U未完成，將其連接到未完成事務(wù)列。按照未完成事務(wù)列從后往前掃描日志執(zhí)行undo操作，按照將磁盤中E值寫為50，將磁盤中C值寫為30，將磁盤A值寫為10。將寫入日志中并刷新日志。d)首先掃描

58、日志,發(fā)現(xiàn)事務(wù)T、U已經(jīng)commit，將其連接到已完成列，未完成列為空，不做任何操作。6.2.4對(duì)于習(xí)題6.2.3描述的每種情況，T和U所寫的哪些值必然出現(xiàn)在磁盤上哪些值可能出現(xiàn)在磁盤上6.3.2使用習(xí)題6.2.7的數(shù)據(jù)，對(duì)該習(xí)題中a到e的各個(gè)位置答復(fù)：I：何時(shí)能寫入記錄Ii：對(duì)每一個(gè)可能發(fā)生的故障的時(shí)刻，為了找到所有可能未完成的事務(wù)，我們需要在日志中向后看多遠(yuǎn)。請(qǐng)考慮記錄在崩潰發(fā)生以前寫入和未寫入的兩種情況。習(xí)題6.2.7數(shù)據(jù)：日志記錄序列：;假設(shè)在如下日志中的某一條寫入后立即開場(chǎng)一個(gè)非靜止檢查點(diǎn)：A)B)C)D)E)第一問1在a后寫入START CKPT時(shí)，此時(shí)，只有s是活潑的，在后寫入記

59、錄；2.在b后寫入START CKPT時(shí)，此時(shí)，只有T是活潑的，在后寫入記錄；3.在C后寫入START CKPT時(shí)，此時(shí)，只有U、T都是活潑的，在后寫入錄；4.在d后寫入START CKPT時(shí)，此時(shí)，只有U、T、V都是活潑的，在后寫入記錄；5.在e后寫入START CKPT時(shí)，此時(shí)，只有T、V都是活潑的，在后寫入錄；第二問在a處，如果記錄在崩潰前寫入的話，此時(shí)需要在日志中向后看到記錄；如果記錄在崩潰后寫入的話，此時(shí)需要在日志中向后看到記錄;2. 在b處，如果記錄在崩潰前寫入的話，此時(shí)需要在日志中向后看到記錄；如果記錄在崩潰后寫入的話，此時(shí)需要在日志中向后看到記錄;3. 在C處，如果記錄在崩潰前

60、寫入的話，此時(shí)需要在日志中向后看到記錄；如果記錄在崩潰后寫入的話，此時(shí)需要在日志中向后看到記錄;4、在d處，如果記錄在崩潰前寫入的話，此時(shí)需要在日志中向后看到記錄；如果記錄在崩潰后寫入的話，此時(shí)需要在日志中向后看到記錄;5、在e處，如果記錄在崩潰前寫入的話，此時(shí)需要在日志中向后看到記錄；如果記錄在崩潰后寫入的話，此時(shí)需要在日志中向后看到記錄;6.4.2下面是兩個(gè)事務(wù)T和U的一系列日志記錄：;。描述恢復(fù)管理器的行為，包括對(duì)磁盤和日志所作的改變，假設(shè)故障發(fā)生且出現(xiàn)在磁盤上的最后一條日志記錄如下：a b) c d答案1：a首先掃描日志，發(fā)現(xiàn)事務(wù)U、T均未commit，將其連接到未完成列。按照未完成列