1、軟件學院高級數(shù)據(jù)庫考試攻略金培權(quán)數(shù)據(jù)庫系統(tǒng)實現(xiàn)Homework 1使用關系代數(shù)表達式實現(xiàn)下列13小題：給定下面的關系：圖書（圖書號，書名，作者，單價，庫存量），讀者（讀者號，姓名，工作單位，地址），借閱（圖書號，讀者號，借期，還期，備注）注：還期為NULL表示該書未還。檢索讀者Rose的工作單位和地址檢索讀者Rose所借閱讀書（包括已還和未還圖書）的圖書名和借期Homework 1檢索未借閱圖書的讀者姓名用SQL語言完成48小題：查詢語句結(jié)果可以計算如下：1. 取FROM子句中列出的各個關系的元組的所有可能的組合2. 將不符合WHERE子句中給出的條件的元組去掉3. 如果有GROUP BY子句

2、，則將剩下的元組按GROUP BY子句中給出的屬性值分組4. 如果有HAVING子句，則按照HAVING子句中給出的條件檢查每一組，去掉不符合條件的組5. 按照SELECT子句的說明，對于指定的屬性和屬性上的聚集（例如一組中的和）計算出結(jié)果元組6. 按照ORDER BY子句中的屬性列的值對結(jié)果元組進行排序Homework 1檢索Ullman所寫的書的書名和單價SELECT 書名，單價FROM 圖書WHERE 作者=Ullman檢索讀者“李林”借閱未還的圖書的圖書號和書名SELECT 圖書號，書名FROM圖書，讀者，借閱WHERE 圖書.圖書號 = 借閱.圖書號 AND 讀者.讀者號 = 借閱.

3、讀者號AND 讀者.姓名 = “李林” AND 借閱.還期 = NULL；Homework 1檢索借閱圖書數(shù)目超過3本的讀者姓名SELECT 姓名FROM 讀者，借閱WHERE 借閱.讀者號 = 讀者.讀者號GROUP BY 讀者號HAVING COUNT(*) 3;Homework 1檢索沒有借閱讀者“李林”所借的任何一本書的讀者姓名和讀者號SELECT 姓名，讀者號FROM 讀者，借閱WHERE 借閱.讀者號 = 讀者.讀者號AND借閱.圖書號NOT IN (SELECT 圖書號FROM 借閱，讀者WHERE 借閱.讀者號 = 讀者.讀者號AND 讀者.姓名 = 李林);Homework

4、1檢索書名中包含“Oracle”的圖書書名及圖書號。SELECT 圖書號，書名FROM 圖書WHERE 書名LIKE %Oracle%;Homework 1現(xiàn)有如下關系模式：R(A，B，C，D，E，F(xiàn)，G)，R上存在的函數(shù)依賴有：ABE，AB，BC，CD該關系模式滿足第幾范式嗎?為什么?滿足1NF范式。因為每一個屬性值都只含有一個值，所以滿足1NF。由于R的候選碼為（A,F,G），而B、C、D局部依賴于A，所以不滿足2NF。如果將關系模式R分解為：R1(A，B，E)，R2(B，C，D)，R3(A，F(xiàn)，G)，該數(shù)據(jù)庫模式最高滿足第幾范式?最高滿足2NF范式。因為對于模式R2， BC，CD，存在傳

5、遞依賴，所以不滿足3NF。Homework 1請將關系模式R無損連接并且保持函數(shù)依賴地分解到3NF，要求給出具體步驟。1.求R上函數(shù)依賴集F的最小FD集合： F = ABE,AB,BC,CD；U = A,B,C,D,E先將R保持函數(shù)依賴地分解到3NF。2.所有不在F中出現(xiàn)的屬性組成R(F,G)Homework 13.對F按相同的左部分組，并去除子集，得到：p = R1（A,B,E）；R2（B,C）；R3(C,D)；R(F,G)Homework 1無損連接且保持函數(shù)依賴地分解到3NFHomework 15.而R是R4的子集，所以從p中去掉R（F,G）6. p=R1（A,B,E）,R2（B,C），

6、R3（C,D），R4（A,F,G）為最終結(jié)果Homework 1Megatron 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回答下列有關Megatron 777的問題：磁盤的容量是多少？Homework 1如果磁道是在直徑3.5英寸的圓面上，那么一個磁道的扇區(qū)中的平均位密度是多少？我們選取中間磁道來計算平均位密度，中間磁道的直徑為 3.5inch/2 ，該磁道的周長為(3.5/2

7、)inch，扇區(qū)所占的周長是80%(3.5/2)inch。同時，每個磁道的容量是100010248 bits所以一個磁道的扇區(qū)中的平均位密度是（100010248）bits/(80%3.5/2)inch = 1861733.6 bpi最大尋道時間是多少？最大尋道時間 1 + 0.0002* 99 999 = 21msHomework 1最大旋轉(zhuǎn)等待時間是多少？最大旋轉(zhuǎn)等待時間：60 x 1000ms /10 000 = 6ms如果一個塊是65536字節(jié)（即64扇區(qū)），一個塊的傳輸時間是多少？如果一個塊是65536字節(jié)（即64扇區(qū)）,則磁頭必須越過64個扇區(qū)以及扇區(qū)之間的63個間隙。需要的時間為

8、：64（扇區(qū)+間隙）-1（間隙）=64*（6/1000）-(6/1000)*0.2=0.3828msHomework 1平均尋道時間是多少？平均旋轉(zhuǎn)等待時間為：6ms/2=3ms平均旋轉(zhuǎn)等待時間是多少？1+0.0002*99999/3=7.67msHomework2假設一條記錄有如下順序的字段：一個長度為23的字符串，一個2字節(jié)整數(shù)，一個SQL日期，一個SQL時間（無小數(shù)點）。字段可在任何字節(jié)處開始？一個SQL日期是10個字節(jié)的字符串，一個SQL時間是8個字節(jié)的字符串。因為是任何字節(jié)處開始的，所以記錄長度需要23+2+10+8=43字節(jié)。Homework2字段必須在8的倍數(shù)的字節(jié)處開始？Hom

9、ework2字段必須在4的倍數(shù)的字節(jié)處開始？因為必須是4的倍數(shù)，而長度為23的字符串需要分配24個字節(jié)，2字節(jié)的整數(shù)需要分配4個字節(jié)，SQL日期需要分配12個字節(jié)，SQL時間需要分配8個字節(jié)。所以：24+4+12+8=48字節(jié)。Homework2假設我們有4096字節(jié)塊，塊中存儲200字節(jié)長的記錄。塊首部由一個偏移量表組成，它使用2字節(jié)長指針指向塊內(nèi)記錄。通常，每天向每塊插入兩條記錄，刪除一條記錄。刪除記錄必須使用一個“刪除標記”代替它的指針，因為可能會有懸掛指針指向它。更明確地說，假設任何一天刪除記錄總發(fā)生在插入之前。如果剛開始時塊是空的，多少天之后，不再有插入記錄的空間？第一天，只做插入操

10、作，插入兩條記錄，同時使用2個指針指向記錄，總計增加了2（2+200） = 404字節(jié)。Homework2之后的每一天都先刪除一條記錄再增加兩條記錄，凈增404-200 = 204字節(jié)。由于（4096-404）/204 = 1820，即在1+18 = 19天之后，塊中剩余空間為20字節(jié)。在第20天，先刪除一條記錄，余下200+20=220字節(jié)空間，這時候只能夠再插入一條記錄（202字節(jié)）。Homework2 一個病人記錄包含以下定長字段：病人的出生日期，社會保險號碼，病人ID，每一個字段都是9字節(jié)長。它還有下列變長字段：姓名，住址和病史。如果記錄內(nèi)一個指針需要8字節(jié)，記錄長度是一個2字節(jié)整數(shù)，

11、不包含變長字段空間，這條記錄需要多少字節(jié)？你可以假設不需要對字節(jié)進行對齊。記錄長度出生日期住址指針病史指針保險號碼病人ID姓名住址病史Homework2定長字段有3個，每個有9個字節(jié)長，所以需要39=27字節(jié)。而記錄的首部需要寫入記錄的長度和指向所有除第一個以外的變長字段起始處的指針。而記錄長度2字節(jié)，指向“住址”的指針8字節(jié)，指向“病史”的指針8字節(jié)。所以一共需要27+2+8+8=45字節(jié)。Homework3 Homework3 T(W)/V(W,a) = 400/50 = 8T(Y)/V(Y,c) = 200/50 = 4Homework3 T(W)*T(Y)=400*200=80000T

12、(Z)/3=100/3=33.3T(W)/V(W,a)*V(W,b)=400/(50*40)=0.2Homework3 T(W)/3*V(W,a)=400/（3*50）=2.67T(X)*T(Y)/3=300*200/3=20000Homework4如果R和S都是非聚集的，似乎嵌套循環(huán)連將需要大約T(R)T(S)/M次磁盤I/O時間。你怎樣做才能明顯好于這個代價？假設 S(R)=S(S),每次迭代時讀取R的元組塞滿 M-1塊的chunk,此時迭代次數(shù)為T(R)*S(R)/(M-1)，那么總的磁盤I/O時間為T(R)+T(R)*T(S)*S(R)/(M-1)。近似為： T(R)*T(S)*S(R

13、)/M.例如：1個block中能存放10個元組,即S(R)=1/10*block，那么效率提高10倍。Homework4如果R和S中只有一個是非聚集的，你應該怎樣執(zhí)行嵌套循環(huán)連接？考慮兩種情況：較大的關系是非聚集的和較小的事非聚集的假定 R為較小關系，S為較大關系（1）S是非聚集的：方案1：For each loop:Read M -1 blocks of RRead all of S (using 1 block) + join代價為：B(R)+B(R)*T(S)/(M-1)Homework4方案2：Read M-1 blocks (M-1)1/S(S) tuples) of SRead a

14、ll of R(using 1 block) + join代價為：T(S)+B(R)*T(S)*S(S)/(M-1)選擇代價最小的方案（2）R是非聚集的：方案1：For each loop:Read M-1 blocks (M-1)1/S（R）tuples) of RRead all of S (using 1 block)+ join代價為：T(R)+T(R)*B(S)*S(R)/(M-1)Homework4方案2：For each loop:Read M-1 blocks of SRead all of R(using 1 block)+ join代價為：B(S)+T(R)*B(S)/(M

15、-1)選擇代價最小的方案比較2種情況下的最優(yōu)代價Homework4假設這節(jié)中所描述算法的第二趟不需要所有的M個緩沖區(qū)，因為子表數(shù)小于M。我們怎樣通過使用額外的緩沖區(qū)來節(jié)省磁盤I/O？原本我們需要將第一趟中得到的有序子表都寫回磁盤，現(xiàn)在由于子表數(shù)小于M，可以將部分子表不寫回，直接存儲在內(nèi)存緩沖區(qū)中，從而減少第二趟中的讀子表操作，對于這樣每塊我們節(jié)省了 2 次IO.Test 1假設某磁盤塊參數(shù)如下：容量36.7GB,傳輸速率45MB/S，旋轉(zhuǎn)一圈時間4ms，平均尋道時間5ms，最小尋道時間0.65ms，一個磁道大小180KB。如果磁盤塊大小4KB,請回答下面問題：（1）隨機讀取1000個磁盤塊需要

16、多少時間（ms）？（2）假定（1）中的1000個磁盤塊在單個磁道上連續(xù)存儲，并且所有磁盤塊存儲在相鄰的磁道上，此時讀取這1000個磁盤塊需要多少時間？Test 1Test 1順序讀取1000個塊TestB+-Tree設定如下：N: 記錄數(shù) n: B+-Tree的階，即節(jié)點所能容納的鍵數(shù)R: 讀取一個磁盤塊的旋轉(zhuǎn)延遲S: 讀取一個磁盤塊的尋道時間T: 讀取一個磁盤塊的傳輸時間m: 在內(nèi)存的m條記錄查找一條記錄的時間假設所有磁盤塊都不在內(nèi)存中現(xiàn)在考慮壓縮B+-Tree，假設每個節(jié)點的鍵值壓縮1倍，即同樣空間可壓縮存儲2n個鍵值和2n+1個指針。額外代價是解壓縮，設每個壓縮鍵值的內(nèi)存解壓時間為c，請

17、問在一棵滿的n階壓縮B+-Tree中查找給定記錄地址的時間多少？（n+1可近似表示為n）Test2. 讀塊的時間 = R + S + T3. 每塊有n條記錄，內(nèi)存查找時間為 n6. 增加了解壓時間2cn，內(nèi)存查找時間變?yōu)?nFinal Exam 考試形式不同于往年，往年為開卷考試，今年為閉卷考試，總共10個判斷題，及4個大題。10個判斷，30分，個人感覺不容易，考點比較細，都是一些概念的判斷，考的基本都是前三章的內(nèi)容，請大家仔細復習。（eg:ER圖是自下向頂設計的；關系模型中候選碼一定要存在；一個只有2個屬性的關系模式一定滿足第三范式嗎）第一個大題考的是PPT第七章的內(nèi)容，查詢優(yōu)化，老師上課講

18、的PPT上不全，只要把書上P153頁內(nèi)容掌握即可完美答題。題目難度：一顆星Final Exam第二個大題考的是PPT第十章的內(nèi)容，并發(fā)調(diào)度，考察沖突可串性及優(yōu)先圖的畫法，掌握PPT即可。題目難度：一顆星第三個大題考的是模糊查詢結(jié)合B+樹索引查詢（問題是否能用B+樹索引查詢應用于模糊查詢能否提高查詢效率），金老師上課基本沒提到模糊查詢，因此需要自己結(jié)合SQL中模糊查詢的原理和B+樹索引查詢原理解答。題目難度：四顆星第四個大題考的是PPT第八章的內(nèi)容，查詢執(zhí)行，主要考察優(yōu)化的歸并排序算法。題目難度：五顆星（題目見附錄）附第五題 我們想將關系R按某個字段排序。已知R的下列信息：R包含 100000 個元組，即 T(R) = 100000. 一個磁盤塊大小為 4000 bytes.R的元組大小為 400 bytes，即S(R) 400. 關系R在磁盤上是非連續(xù)（contiguous）存放的 排序字段的大小為 32 bytes.記錄指針的大小為 8 bytes.（普通硬盤讀寫一個塊的時間都是30t，固態(tài)硬盤讀取一個塊的時間是t，寫出一個塊的時間為50t。) 考慮下面改進的歸并排序算法。原來的兩階段歸并排序的第一階段是將排序后的整個元組寫到chunk中，現(xiàn)在我們僅將排序后的 寫出。第一階段，我