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

考量下列和電影資料庫相關的資料庫綱目（Schema）： 表1: 電影列表MovieList(title:string, year:int) 表2: 男演員Actor(actorName:string, actedIn:string), actedIn 外鍵（foreign key）到 MovieList 表3: 女演員Actress(actressName:string, actedIn:string), actedIn 外鍵（foreign key） 到MovieList 表4: 類型Genres(title:string, genre:string), title 外鍵（foreign key）到MovieList 表5: 關鍵字Keywords(keyword:string, movieTitle:string), movieTitle 外鍵（foreign key）到MovieList 表6: 最佳電影TopMovies(distribution:char(10), votes: int, rank: float, title: string), title 外鍵（foreign key）到MovieList 表7: 最爛電影WorstMovies(distribution:char(10), votes: int, rank: float, title: string), title 外鍵（foreign key）到MovieList 將下列要求轉換成SQL 語句：（每小題4 分，共20 分） 列出每個類型的電影數量。 找出所有“哈利波特”系列電影有在2001 年演出，但是沒有在2010 年演出的男女 演員。 找出所有演過超過10 種類型電影的男演員。 找出同時屬於動作與恐怖類，但是沒有戰爭這個關鍵字的電影名稱。 找出有演出過被評為最爛電影，但是沒有演出過被評為最佳電影的男女演員。

考量一個關聯綱目（Relation Schema）R=(A,B,C,D,E,F,G)，並有下列的函數相依關係 A Î B , BC Î DE , AEF Î C , AC Î DE 回答下列問題：（每小題5 分，共20 分） 請計算並說明{A,B}的泛封閉集合（Closure）。 請問R 的候選關聯鍵為何？並說明。 R 是否為BCNF？請說明。 將R 分解為滿足第三正規化（3NF）的關聯綱目。 102年公務人員高等考試一級暨二級考試試題 類 科： 資訊處理 全一張 （背面） 10 20 30 40

5 7 8 14 16 22 24 26 30 32 36 42 44 46 三、B+-tree 是常用的資料庫索引（Index）結構，請回答下列問題： 簡述B+-tree 的結構特性及優點。（6 分） 下列B+-tree 的各中間節點最大連結索引數（Fanout）為5，請加入（Insert）索引值 為9 的資料檔至下列B+-tree 中，並說明其執行節點分割（Split）的方法。（6 分） 請將下列三個索引值24、26、30 從上列結果Insert 9 之後的B+樹狀圖中，依序刪 除，並優先採用和兄弟節點（Sibling）重分配的方式滿足B+-tree 的特性。（8 分）

考量兩個關連R(x,y)與S(y,z)，我們要從這兩個關連的y 屬性去做連接（Join），關 連R 占150 個記憶體區塊，關連S 則占100 個記憶體區塊，RS 這兩個關連的屬性 均未做過任何排序，回答下列問題： 假設記憶體緩衝區剩下26 個記憶體區塊（M=26），以Block-nested Loop Join 計 算在y 屬性上來連接（Join）關連R 與S 的花費（Cost），並說明之。（6 分） 同上，但是以Hash-based Join 來計算花費，並說明之。（8 分） 假設關連R 與S 的y 屬性上有排序過的叢集索引（Clustered Index），試以Merge Join 的方式計算在y 屬性上來連接（Join）關連R 與S 的花費，並說明之。（6 分）

若Wi(M)表示一個交易Ti 將名為M 的資料寫入（Write）資料庫中，Ri(M)表示一個 交易Ti 將名為M 的資料讀入（Read）程式變數中，若一個資料交易包括有三筆資 料變數X、Y、Z 和三個交易T1、T2、T3，每個交易在執行完最後一個動作就會立 刻提交（Commit），交易T1、T2、T3 如下： T1：R1(X),W1(X),R1(Y),W1(Y) T2：R2(Z),R2(X),W2(X),R2(Y),W2(Y) T3：R3(Y),R3(Z),W3(Y),W3(Z) 下列有三個和交易T1、T2、T3 的排程分別為S1、S2、S3，其執行情形如下： S1：R3(Y),R3(Z),R1(X),W3(Y),W1(X),R2(Z),W3(Z),R2(X),W2(X),R1(Y),R2(Y), W1(Y),W2(Y) S2：R1(X),W1(X),R1(Y),W1(Y),R3(Y),R3(Z), W3(Y),W3(Z),R2(Z),R2(X),W2(X), R2(Y),W2(Y) S3：R3(Y),R3(Z),R1(X),W1(X),W3(Y),W3(Z), R2(Z),R2(X),W2(X),R1(Y),W1(Y), R2(Y),W2(Y) 請分別畫出S1、S2、S3 的可順序圖（Precedence Graph）。（9 分） 請分別說明S1、S2 和S3 是否為衝突可序性（Conflict-Serializable）？若是的話， 請給一個等價可序性執行順序。（6 分） 請利用嚴格二階段鎖定法（Strict Two-Phase Locking）加入一些鎖定（Locking） 和解除鎖定（Unlocking）到交易T3，使T3 成為嚴格及可順序的交易。（5 分）