資訊處理 103 年高等資料庫設計考古題

假設我們要對一個檔案採用可擴充式雜湊（extendible hashing）方法建立索引，而 該檔案所包含的資料紀錄之搜尋鍵值如下： 2, 3, 5, 7, 11, 17, 19, 23, 29, 31 如果雜湊函數為h(x) = x mod 8，且每個bucket 可以儲存三筆紀錄，請畫出該檔案 之可擴充式雜湊結構。（25 分）

在資料庫的回復系統裡，有關檢查點技術（checkpointing）： 請解釋其作用。（10 分） 執行檢查點的頻率應該根據那些因素調整？如何調整？（15 分）

考慮關聯表r1(A,B,C)、r2(C,D,E)及r3(E,F)，其主鍵（primary key）分別是A、C 及E。 假設r1 有1000 筆資料，r2 有500 筆資料，而r3 有2000 筆資料，請估算r1⋈r2⋈r3 運算結果的大小。（15 分） 又假設你可以在這些關聯表裡建立索引以加速這個合併運算的計算，你會如何進 行？為什麼？（10 分）

考慮以下兩筆交易，其中A 與B 之初始值皆為0： T1: read(A); read(B); if A=0 then B:=B+1; write(B). T2: read(B); read(A); if B=0 then A:=A+1; write(A). 當此兩交易T1與T2同時執行時，請說明是否有可能產生一個序列化排程（serializable schedule）。（10 分） 請加入鎖定（lock）與解鎖（unlock）指令到交易T1 與T2 中，使其遵守兩階段鎖 定協定（two-phase locking protocol），並說明在執行上述交易時，是否會導致死 結（deadlock）發生？（15 分）