加載中. ..
PDF
103年公務人員高等考試一級暨二級考試試題
代號：22740
等 別： 高考二級
類 科： 資訊處理
科 目： 高等資料庫設計
考試時間： 2小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
全一頁
一、假設我們要對一個檔案採用可擴充式雜湊（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：
T
1: read(A);
read(B);
if A=0 then B:=B+1;
write(B).
T
2: 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 分）