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

WORD格式--可編輯--專業(yè)資料完整版學(xué)習(xí)資料分享《數(shù)據(jù)庫系統(tǒng)實(shí)現(xiàn)》復(fù)習(xí)資料2.2.2 22.7.3 23.1.7 33.2.6 53.3.5 53.3.7 73.5.2 83.6.2 96.1.2 106.2.3 116.2.4 136.3.2 146.4.2 157.2.5 167.4.2 187.7.1 182.2.2習(xí)題2.2.2假設(shè)Megatron747磁道的磁頭位于磁道4096，即跨越磁道的1/16距離處。假設(shè)下一個請求是對一隨機(jī)磁道上一個塊。計(jì)算讀這個塊的平均時間。答案2平均移動的磁道：（1+2+…+4096）+（1+2+…+(65536-4096)）/65536=28928;存道時間：1+28928/4000=8.232ms;傳輸時間=0.13ms；旋轉(zhuǎn)等待時間=4.17ms；所以總的平均時間為8.232+0.13+4.17=12.532ms；2.7.3假設(shè)在習(xí)題2.7.1的病人記錄上添加另外的可重復(fù)字段，表示膽固醇化驗(yàn)，每一次膽固醇化驗(yàn)需要一個24字節(jié)的日期和化驗(yàn)的整數(shù)結(jié)果。如果a）重復(fù)化驗(yàn)保存在記錄中。b）化驗(yàn)存儲在另外一個塊中，記錄中存儲指向化驗(yàn)的指針。分別給出病人記錄的格式。1其他首部信息指向住址指向病史記錄長度指向化驗(yàn)（化驗(yàn)記錄）出生日期社會保險號碼病人ID姓名住址病史2記錄首部信息姓名的長度住址的長度病史的長度指向姓名指向住址指向病史指向化驗(yàn)出生日期社會保險號碼病人ID（化驗(yàn)記錄）姓名住址病史3.1.7如果我們使用一個擴(kuò)充的倒排索引，如圖3-10所示，那我們就能執(zhí)行許多其他類型的查詢。說明如何使用這種索引去找到：a)“cat”和“dog”彼此相距不超過5個位置并且出現(xiàn)在同一類元素（如標(biāo)題、正文或錨）中的文檔。b)“cat”后剛好隔一個位置就跟有“dog”的文檔。c)題目中同時出現(xiàn)“dog”和“cat”的文檔。A.獲得所有的桶條目“貓”和“狗”。通過類型分類這些條目,在類型中通過位置進(jìn)行分類。掃描記錄,保持一個“窗口”,記錄當(dāng)前的類型。在當(dāng)前類型上延長到五個位置之前。拿所有的新記錄和當(dāng)前窗口中的記錄作比較。如果我們找到一個條目:(1)有相反的詞,比如“狗”，如果當(dāng)前記錄為“貓”,和(2)有相同的文檔條目。那么這個文檔就是我們想要檢索的。B.獲得所有的桶條目“狗”。通過位置分類這些條目。掃描記錄,保持一個“窗口”,記錄一個位置之前的當(dāng)前位置。拿新記錄和當(dāng)前窗口中的記錄作比較。如果我們找到一個:記錄(1)有相反的詞“貓”,和(2)有相同的文檔條目。那么這個文檔是我們想要檢索的。C.我們沿著指針與“貓”來找到這個詞的出現(xiàn)。選擇從與貓有關(guān)的桶文件指針開始找，“貓”的類型是“標(biāo)題”。然后同樣我們找出桶條目“狗”的指針。如果這兩套指針相交,這個文檔就是滿足我們條件的。答案23.1.7A>找到所有包含“cat”和“dog”的文檔的指針集，然后按類型分類，然后按位置分類。選擇其中相距不超過5個位置且鍵值相反的記錄，即滿足條件。B>找到所有包含“dog”的文檔指針列表，然后再按位置分類，找出所有指示位置信息的指針列表，記錄所有指針往前移動兩個位置的位置信息。然后求得所有包含“cat”的文檔的位置指針列表，與剛才的位置信息的交集即滿足條件。C>從桶文件中選擇有“cat”出現(xiàn)且類型為“標(biāo)題”的文檔指針。接著，找到“dog”的桶中項(xiàng)目，并從中選擇類型為“標(biāo)題”的文檔指針。求兩個指針集相交，就得到滿足條件的文檔。3.2.6在例3.17中我們提出，如果我們使用更復(fù)雜的維護(hù)內(nèi)部結(jié)點(diǎn)鍵的算法，那么可以從右（或左）邊的非兄弟結(jié)點(diǎn)中借鍵。描述一個合適的算法，它可以通過從同層相鄰結(jié)點(diǎn)中借鍵來重新達(dá)到平衡，而不管這些相鄰結(jié)點(diǎn)是否是鍵-指針對太多或太少的結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。1、如果node的節(jié)點(diǎn)數(shù)大于等于min+1，刪除key,到52、如果node相鄰左節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)大于等于min+1，從node左節(jié)點(diǎn)借值key，將node的root值改為key，到53、如果node相鄰右節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)大于等于min+1，從node右節(jié)點(diǎn)借值key，將node的root值改為key，到54、刪除key，與其左節(jié)點(diǎn)合并，node=root到15、結(jié)束3.3.5假定鍵散列為4位序列，就像這一部分中可擴(kuò)展散列表和線性散列表的例子一樣。但是，假定塊中可存放三個記錄而非兩個記錄。如果開始時散列表中有兩個空存儲塊（對應(yīng)于0和1），請給出插入鍵值如下的記錄后的結(jié)構(gòu)：a)1111，1110，……0000，且散列方法是可擴(kuò)展散列b）1111，1110，……0000，且散列方法是線性散列，其充滿度閾值為75%。c)0000，0001，……1111，且散列方法是可擴(kuò)展散列。d)0000，0001，……1111，且散列方法是線性散列，其充滿度閾值為100%。(a)i=3(c)、與(a)的結(jié)構(gòu)相同，當(dāng)然順序可以升序也可以降序(d)、與(b)的相同，順序也可以反過來。3.3.7實(shí)際中有些散列函數(shù)并不像理論上那樣好。假定我們在整數(shù)鍵值i上定義一個散列函數(shù)h(i)=i2modB，其中B表示桶數(shù)。a)如果B=10，該散列函數(shù)會出現(xiàn)什么問題？b)如果B=16，該散列函數(shù)又有什么好處？c)該散列函數(shù)對哪些B值有用？答案1B=10時散列函數(shù)值=0,1,4,5,6,9，其中桶2,3,7,8的空間就被浪費(fèi)掉了，沒有鍵值存進(jìn)去，然后桶1,4,6,9這四個桶要記錄雙倍的鍵值（2）B=16時散列函數(shù)值=0,1,4,9所有的鍵值均勻分布在這四個桶中，方便集中管理（3）B=2冪或其開方仍為整數(shù)3.5.2選擇一個分段散列函數(shù)，且速度、內(nèi)存和硬盤大小三屬性各為一位二進(jìn)制數(shù)，使它能很好地劃分圖3-36中的數(shù)據(jù)。3.6.2把圖3-36的數(shù)據(jù)放到一棵kd-樹中。假定每塊能存放兩個記錄，給每一層挑選一個使數(shù)據(jù)劃分盡可能均勻的劃分值。分裂屬性的順序選擇：a)速度，然后內(nèi)存，再交替;b)速度，然后內(nèi)存，最后硬盤，再交替;c)不論什么屬性，只要它在每個結(jié)點(diǎn)產(chǎn)生最均勻的分裂。第三問不會，需要討論6.1.2對習(xí)題6.1.1中的每個事務(wù)，在計(jì)算中加入讀寫動作，并給出各步驟對主存和磁盤產(chǎn)生的影響。假設(shè)最初A=50且B=25.此外，請說明當(dāng)OUTPUT動作順序恰當(dāng)時，是否可能即使在事務(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)動作t內(nèi)存中的A內(nèi)存中的B磁盤中的A磁盤中的BREAD(B,t1)25255025READ(A,t2)5050255025t1:=t2+RITE(B,t1)7550755025t2:=t2+t112550755025WRITE(A,t2)125125755025Output（B,t1)75125755075Output(A,t2)1251257512575b)動作t內(nèi)存中的A內(nèi)存中的B磁盤中的A磁盤中的BREAD(A,t1)50505025READ(B,t2)2550255025t1:=t2+12650255025WRITE(A,t1)2626255025t2:=t1+12726255025WRITE(B,t2)2726275025Output（A,t1)2626272625Output(B,t2)2726272627c)動作t內(nèi)存中的A內(nèi)存中的B磁盤中的A磁盤中的BREAD(A,t1)50505025READ(B,t2)2550255025t1:=t1+t27550255025WRITE(A,t1)7575255025t2:=t1+t210075255025WRITE(B,t2)100751005025Output（A,t1)75751007525Output(B,t2)1007510075100如果OUTPUT動作順序恰當(dāng)，即使在事務(wù)執(zhí)行過程中發(fā)生故障，一致性仍能得到保持。6.2.3下面是兩個事務(wù)T和U的一系列日志記錄：<STARTU>;<U,A,10>;<STARTT>;<T,B,20>;<U,C,30>;<T,D,40>;<COMMITT>;<U,E,50>;<COMMITU>。請描述恢復(fù)管理器的行為，包括對磁盤和日志所作的改變，假設(shè)故障發(fā)生且出現(xiàn)在磁盤上的最后一條日志記錄為：a)<STARTT>b)<COMMITT>c)<U,E,50>d)<COMMITU>答案1若題目是:<STARTU>;<U,A,10>;<STARTT>….則答案是首先掃描日志,發(fā)現(xiàn)事務(wù)T和U都未commit,將其連接到未完成事務(wù)列.按照未完成事務(wù)列,從后往前逐步掃描日志并執(zhí)行undo操作，按照<U,A,10>將磁盤中A值寫為10,將<ABORTT>和<ABORTU>寫入日志中并刷新日志。首先掃描日志,發(fā)現(xiàn)事務(wù)T已經(jīng)commit，將其連接到已完成事務(wù)列,事務(wù)U未完成，將其連接到未完成事務(wù)列。按照未完成事務(wù)列，從后往前掃描日志執(zhí)行undo操作，按照<U,C,30>將磁盤中C值寫為30，<U,A,10>將磁盤A值寫為10。將<ABORTU>寫入日志中并刷新日志。首先掃描日志,發(fā)現(xiàn)事務(wù)T已經(jīng)commit，將其連接到已完成事務(wù)列,事務(wù)U未完成，將其連接到未完成事務(wù)列。按照未完成事務(wù)列從后往前掃描日志執(zhí)行undo操作，按照<U,E,50>將磁盤中E值寫為50，<U,C,30>將磁盤中C值寫為30，<U,A,10>將磁盤A值寫為10。將<ABORTU>寫入日志中并刷新日志。d)首先掃描日志,發(fā)現(xiàn)事務(wù)T、U已經(jīng)commit，將其連接到已完成列，未完成列為空，不做任何操作。6.2.4對于習(xí)題6.2.3描述的每種情況，T和U所寫的哪些值必然出現(xiàn)在磁盤上？哪些值可能出現(xiàn)在磁盤上？6.3.2使用習(xí)題6.2.7的數(shù)據(jù)，對該習(xí)題中（a）到（e）的各個位置回答：I：何時能寫入<CKPT>記錄Ii：對每一個可能發(fā)生的故障的時刻，為了找到所有可能未完成的事務(wù)，我們需要在日志中向后看多遠(yuǎn)。請考慮<ENDCKPT>記錄在崩潰發(fā)生以前寫入和未寫入的兩種情況。習(xí)題6.2.7數(shù)據(jù)：日志記錄序列：<STARTS>;<<S,A,60>;<COMMITS>;<STARTT>;<T,A,10>;<STARTU>;<U,B,20>;<T,C,30>;<STARTV>;<U,D,40>;<V,F,70>;<COMMITU>;<T,E,50>;<COMMITT>;<V,B,80>;<COMMITV>;假設(shè)在如下日志中的某一條寫入后立即開始一個非靜止檢查點(diǎn)：A)<S,A,60>B)<T,A,10>C)<U,B,20>D)<U,D,40>E)<T,E,50>第一問1在a）<S,A,60>后寫入STARTCKPT時，此時，只有s是活躍的，在<COMMITS>后寫入<ENDCKPT>記錄；2.在b）后寫入STARTCKPT時，此時，只有T是活躍的，在<COMMITT>后寫入<ENDCKPT>記錄；3.在C）后寫入STARTCKPT時，此時，只有U、T都是活躍的，在<COMMITT>后寫入<ENDCKPT>錄；4.在d）后寫入STARTCKPT時，此時，只有U、T、V都是活躍的，在<COMMITV>后寫入<ENDCKPT>記錄；5.在e）后寫入STARTCKPT時，此時，只有T、V都是活躍的，在<COMMITV>后寫入<ENDCKPT>錄；第二問在a）處，如果<ENDCKPT>記錄在崩潰前寫入的話，此時需要在日志中向后看到記錄<STARTCKPT(S)>；如果<ENDCKPT>記錄在崩潰后寫入的話，此時需要在日志中向后看到記錄<STARTS>;2.在b）處，如果<ENDCKPT>記錄在崩潰前寫入的話，此時需要在日志中向后看到記錄<STARTCKPT(T)>；如果<ENDCKPT>記錄在崩潰后寫入的話，此時需要在日志中向后看到記錄<STARTT>;3.在C）處，如果<ENDCKPT>記錄在崩潰前寫入的話，此時需要在日志中向后看到記錄<STARTCKPT(T，U)>；如果<ENDCKPT>記錄在崩潰后寫入的話，此時需要在日志中向后看到記錄<STARTT>;4、在d）處，如果<ENDCKPT>記錄在崩潰前寫入的話，此時需要在日志中向后看到記錄<STARTCKPT(T,U,V)>；如果<ENDCKPT>記錄在崩潰后寫入的話，此時需要在日志中向后看到記錄<STARTT>;5、在e）處，如果<ENDCKPT>記錄在崩潰前寫入的話，此時需要在日志中向后看到記錄<STARTCKPT(T，V)>；如果<ENDCKPT>記錄在崩潰后寫入的話，此時需要在日志中向后看到記錄<STARTT>;6.4.2下面是兩個事務(wù)T和U的一系列日志記錄：<STARTU>;<U,A,10,11>;<STARTT>;<T,B,20,21>;<U,C,30,31>;<T,D,40,41>;<COMMITT>;<U,E,50,51>;<COMMITU>。描述恢復(fù)管理器的行為，包括對磁盤和日志所作的改變，假設(shè)故障發(fā)生且出現(xiàn)在磁盤上的最后一條日志記錄如下：a）<STARTT>b)<COMMITT>c）<U,E,50,51>d）<COMMITU>答案1：a）首先掃描日志，發(fā)現(xiàn)事務(wù)U、T均未commit，將其連接到未完成列。按照未完成列，從后往前逐步掃描日志并執(zhí)行undo操作，按照<U,A,10,11>將磁盤中A值寫為10.b）首先掃描日志，發(fā)現(xiàn)事務(wù)T已為commit而U未commit，故將T連接到已完成列而U連接到未完成列。按照未完成列，從后往前掃描日志，按照<U,C,30,31>將磁盤中C寫為30，<U,A,10,11>將磁盤中A值寫為10。按照已完成列，從前往后掃描日志，按照<T,B,20,21>將磁盤中B寫為21，<T,D,40,41>將磁盤中D寫為41.c)最后一條記錄為<U,E,50，51>這時我們?yōu)镋往磁盤上寫入值51，但是崩潰在<COMMITU>記錄到達(dá)前發(fā)生，則E在磁盤上的值為50。d)最后一條記錄為<COMMITU>，這時U被認(rèn)為是已提交的事務(wù)。我們?yōu)镋往磁盤上寫入值51，E已經(jīng)具有值51。7.2.5對一下的每個調(diào)度：w3(A);r1(A);w1(B);r2(B);w2(C);r3(C);r1(A);r2(A);w1(B);w2(B);r1(B);r2(B);w2(C);w1(D);r1(A);r2(A);r1(B);r2(B);r3(A);r4(B);w1(A);w2(B);r1(A);r2(A);r3(B);w1(A);r3(C);r2(B);w2(B);w1(C);r1(A);w1(B);r2(B);w2(C);r3(C);w3(A);回答如下問題：I：調(diào)度的優(yōu)先圖是什么；Ii：調(diào)度是沖突可串行化的嗎？如果是，等價的串行調(diào)度有哪些；Iii：是否有等價的調(diào)度（不管事務(wù)對數(shù)據(jù)做什么），但又不是沖突等價的？7.2.5(i)每一個調(diào)度的優(yōu)先圖如下所示：a)b)112c)d)3——》2——》1e)(ii)由優(yōu)先圖的定義知，存在環(huán)路的優(yōu)先圖是不能串行化的。從(i)調(diào)度知a)，b)，c)均不是沖突可串行化的，而調(diào)度d)、e)是沖突可串行化的并且與其等價的串行調(diào)度有：（T3，T2，T1）、（T1，T2，T3）。（iii）在上述調(diào)度中沒有等價的調(diào)度同時又不是沖突等價的。7.4.2對下面的每個調(diào)度，在每個動作前插入適當(dāng)?shù)逆i（讀，寫或增量），并在事務(wù)末尾插入解鎖動作。然后說明該調(diào)度在一個支持這三類鎖的調(diào)度器上運(yùn)行時會發(fā)生什么。r1(A);r2(B);inc1(B);inc2(A);w1(C);w2(D);inc1(A);inc2(B);inc1(B);inc2(C);w1(C);w2(D);r1(A);r2(B);inc1(B);inc2(C);w1(C);w2(D)答案暫定為此，有待修改，詳見明日終稿a)sl1(A);r1(A);sl2(B);r2(B);il1(B);inc1(B);u1(B);u1(A);il2(A);inc2(A);u2(A);xl1(C);r1(C);w1(C);u1(C);xl2(D);r2(D);w2(D);u2(D);T1:讀A，增加B；寫CT2:讀B，增加A；寫Db)Il1(A);inc1(A);;u1(A);il2(B);inc2(B);u2(B);il2(C);inc2(C);u2(C);xl1(C);r1(C);w1(C);u1(C);xl2(D);r2(D);w2(D);u2(D);T1:增加A，寫CT2增加B，增加C；寫Dc)sl1(A);r1(A);sl2(B);r2(B);il1(B);inc1(B);u1(B);il2(C);inc2(C);u2(C);xl1(C);r1(C);w1(C);u1(C);xl2(D);r2(D);w2(D);u2(D);T1:讀A，增加B；寫CT2:讀B，增加C；寫D7.7.1假設(shè)我們在圖3-13中的B-樹上執(zhí)行下列動作。如果我們使用樹協(xié)議，什么時候我們可以釋放各個被搜索節(jié)點(diǎn)上的寫鎖：插入4b）插入30c）刪除37d）刪除7a)l(A),l(B),u(A),l(D),調(diào)整D，將其分裂為（2、3、）和（4、5、），將B調(diào)整為（4、7、），u(B),u(D)b)l(A),l(C),u(A),l(G