數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)習(xí)題答案市公開課金獎(jiǎng)市賽課一等獎(jiǎng)?wù)n件

Chapter15第1頁(yè)Exercise15.2.1.aOpen(){R.open();將R在分組屬性上排序，得到S[];len=size(S);s:=S[0];R.Close();cursor=0;

}GetNext(){sum:=0;grplen=0;if(cursor>len)returnnotfound;j:=cursor;while(S[cursor][a]=S[j][a]){grplen++;sum+=s[j][b];j++;}.cursor:=j;returnS[cursor][a]sum/grplen;}Close(){.}第2頁(yè)Exercise15.2.3.a假設(shè)R（X,Y）與S（Y,Z）連接1.讀取R全部元組，并用它們結(jié)構(gòu)一個(gè)以Y為查找關(guān)鍵字內(nèi)存查找結(jié)構(gòu)，并設(shè)置一個(gè)是否已連接字段，將內(nèi)存M-1塊用于這一目標(biāo)2.將S中每一塊讀到內(nèi)存中緩沖區(qū)，對(duì)S每個(gè)元組t，找到R中與t在Y全部屬性上都符合元組，將這些元組標(biāo)識(shí)為joined，然后連接并輸出。3.S掃描完成后，將R中全部未標(biāo)識(shí)為joined元組和空元組連接并輸出Exercise15.3.2.aB(S)+(B(S)×B(R))/(M-1)<=00M>=528第3頁(yè)Exercise15.3.4Open(){R.Open();S.Open();s:=S.getNext();r:=R.getNext();R.Close();if(rorsisnotfound)empty:=1}GetNext(){if(empty=1)returnnotfound;REPEAT{

與書上相同}UNTIL(r與s能連接);RETURNr和s連接Close(){R.Close();S.Close();}第4頁(yè)Exercise15.4.2.asqrt(0)=142Exercise15.4.5當(dāng)子表數(shù)小于M時(shí)，有額外緩沖區(qū)。在每次讀子表時(shí)，能夠?qū)⒆颖砥渌鼔K同時(shí)讀入緩沖區(qū)，在進(jìn)行歸并時(shí)，假如某個(gè)子表S所在一個(gè)緩沖區(qū)塊讀完之后，直接使用該子表S保留于額外緩沖區(qū)下一塊進(jìn)行歸并，而不用再?gòu)腟所在磁盤中讀取到內(nèi)存。第5頁(yè)Exercise15.5.1(3-2M/B(S))(B(R)+B(S))=(3-2×500/10000)(10000+10000)=58000.B(S)/M=10000/500=20。但假如取20個(gè)桶，每個(gè)桶500個(gè)塊，那么混合散列連接沒(méi)有多出緩沖區(qū)用于存放一個(gè)完整桶和其余19個(gè)桶一個(gè)塊，所以我們?nèi)?1個(gè)桶，S和R每個(gè)桶塊數(shù)都是10000/21=477。對(duì)S和R，21個(gè)桶中都有20個(gè)桶寫到磁盤中。所以S和R寫回時(shí)磁盤I/O均為10000*20/21，而第二趟讀S和R磁盤I/O也均是10000*20/21，另外條一趟讀S和R代價(jià)均為10000，故總代價(jià)為：2*10000+2*(10000*20/21+10000*20/21)=58096第6頁(yè)Exercise15.5.5.a考慮最基本情況：因?yàn)樯⒘袝r(shí)每次讀和寫操作都是1個(gè)塊為單位，而一個(gè)塊磁盤I/O時(shí)間為100.5ms，所以一塊一塊地處理磁盤總I/O時(shí)間為3(B(R)+B(S))*100.5=452250ms一次讀或?qū)戇B續(xù)塊則能夠降低I/O時(shí)間。那么設(shè)桶數(shù)為k，能夠在緩沖區(qū)中每個(gè)桶設(shè)置為t個(gè)塊，并另外增加一個(gè)大小為t塊作為輸入緩沖區(qū)，讀取S和R時(shí)均讀取連續(xù)t塊。則(k+1)t<=101。進(jìn)行散列時(shí)，桶中t個(gè)塊滿時(shí)就一次寫回磁盤。因?yàn)樽x寫都是以連續(xù)t個(gè)塊為單位，一次讀/寫連續(xù)t塊代價(jià)為(100+t/2)，完成整個(gè)表讀寫次數(shù)為B/t。所以有：散列時(shí)讀操作S：B(S)/t*(100+t/2),R:B(R)/t*(100+t/2)寫回磁盤時(shí)，每次寫回t個(gè)塊，則寫S：B(S)/t*(100+t/2)，同理R:B(R)/t*(100+t/2)再次讀R和S時(shí)，一次讀t塊，則讀S：B(S)/t*(100+t/2)，讀R：B(R)/t*(100+t/2)總I/O時(shí)間3(100(B(S)+B(R))/t+(B(S)+B(R))/2)S每個(gè)桶塊數(shù)加上作為R輸入緩沖區(qū)t個(gè)塊必須小于或等于M，即B(S)/k+t<=101；而且

(k+1)t<=101，題目要求用盡可能小桶，讀寫盡可能多連續(xù)塊，則取t=101/(k+1)，得到min(k)=6,t=14。

總I/O時(shí)間最小:300*1500/14+3*1500/2=34393ms第7頁(yè)Exercise15.6.4.a表掃描I/O為：10000 索引掃描I/O為：T(R)/k=500000/k500000/K<=10000時(shí)，即k>=50，用索引掃描;不然用表掃描Exercise15.6.5對(duì)三種連接都會(huì)首先進(jìn)行選擇操作，得到R中滿足條件元組，共3個(gè)。即做選擇操作代價(jià)都一樣?，F(xiàn)在將R看成僅有3條元組關(guān)系，對(duì)比3三種連接方法。認(rèn)為B(R)=0基于排序：兩趟排序代價(jià):3(B(R)+B(S))=3B(S)基于HASH：因?yàn)閷?duì)3個(gè)元組進(jìn)行Hash代價(jià)為0，故對(duì)S中每個(gè)元組一旦Hash到對(duì)應(yīng)桶中即可進(jìn)行連接輸出，并不用寫回磁盤，故代價(jià)為B(S)基于索引：假如索引聚簇則代價(jià)為T(R)B(S)/V(S,name)，假如索引是非聚簇則代價(jià)為T(R)T(S)/V(S,name)。因?yàn)橥娪懊餍菢O少，所以T(S)/V(S,name)比1略大，所以基于索引代價(jià)約為3綜上可知，基于索引代價(jià)最小，其次為Hash，最終是排序第8頁(yè)

第9頁(yè)Exercise1