復習題(一)1、設R是二元關系，請分別說明下列關系表達式的結果是什么?并將E1和E2轉換為等價的關系代數(shù)表達式E1=E2=參考答案：如果R只有1行，則結果為空；否則，結果為R本身。參考答案：結果為R中第1分量和第2分量交換位置后仍然屬于R的數(shù)據(jù)行。2、設有下列關系:R(A,B,C,D)S(C,D,E)T(F,C,D)bbcdcdmecdfaefcdncefbbefefnfadedgefdgcd(1)試計算下列關系表達式的值：E1={t|(u)(v)(w)(R(u)∧S(v)∧T(w)∧u[3]>’c’∧v[2]≠’d’∧w[3]≠’f’∧u[4]=v[2]∧v[1]>w[2]∧t[1]=u[2]∧t[2]=u[3]∧t[3]=v[1]∧t[4]=w[3]∧t[5]=w[2])}E2=A,B,R.C,R.D,E,F(A<‘f’∧E<'n'∧F≠'c'(R?S?T))E3=R÷C,D(S)(2)試將E1轉換為等價的關系代數(shù)表達式(3)試將E2轉換為等價的關系元組演算表達式(4)對E2進行代數(shù)優(yōu)化(1)試計算下列關系表達式的值：E1={t|(u)(v)(w)(R(u)∧S(v)∧T(w)∧u[3]>’c’∧v[2]≠’d’∧w[3]≠’f’∧u[4]=v[2]∧v[1]>w[2]∧t[1]=u[2]∧t[2]=u[3]∧t[3]=v[1]∧t[4]=w[3]∧t[5]=w[2])}參考答案：E1(B,R.C,S.C,T.D,T.C)aeedcbeedcgeedcE2=A,B,R.C,R.D,E,F(A<'f'∧E<'n'∧F≠'c'(R?S?T))參考答案：E2(A,B,R.C,R.D,E,F)bbcdmedgcdmeE3=R÷C,D（S）參考答案：E3(AB)bbdg(2)試將E1轉換為等價的關系代數(shù)表達式參考答案：E1=B,R.C,S.C,T.D,T.C(C<’c'∧R.D≠'d'∧T.D≠'f'∧R.D=S.D∧S.C>T.C(RⅹSⅹT))(3)試將E2轉換為等價的關系元組演算表達式參考答案：E2={t|u)(v)(w)(R(u)∧S(v)∧T(w)∧u[1]<'f'∧v[3]<'n'∧w[1]≠'c'∧u[3]=v[1]∧u[4]=v[2]∧v[1]=w[2]∧v[2]=w[3]∧t[1]=u[1]∧t[2]=u[2]∧t[3]=u[3]∧t[4]=v[2]∧t[5]=v[3]∧t[6]=w[1])}(4)對E2進行代數(shù)優(yōu)化參考答案：3、設有下列關系:R(A,B,C,D)S(A,B,E)T(C,F,G)a2b2c2d1a1b1e2ca3b1c2d2a1b1a3b1c3d3a1b4e2ca3b3c1d1a3b4c2d2a3b4e3試計算下列關系表達式的值：E1={t|(u)(v)(w)(R(u)∧S(v)∧T(w)∧u[2]=’b1’∧v[1]>’a1’∧w[1]>’c1’∧u[1]>v[1]∧u[2]=v[2]∧u[3]=w[1]∧t[1]=u[4]∧t[2]=v[3]∧t[3]=w[2])}E2=R.B,R.C,S.A,F(D>’d1’∧E=’e3’∧F>’f2’∧R.A=S.A∧R.B=S.B∧R.C=T.C(R×S×E3=R÷S(2)試將E1轉換為等價的關系代數(shù)表達式(3)試將E2轉換為等價的關系元組演算表達式(4)對E2進行代數(shù)優(yōu)化（1）試計算下列關系表達式的值：E1={t|(u)(v)(w)(R(u)∧S(v)∧T(w)∧u[2]=’b1’∧v[1]>’a1’∧w[1]>’c1’∧u[2]=v[2]∧u[3]=w[1]∧t[1]=u[4]∧t[2]=v[3]∧t[3]=w[2])}參考答案：E1(DEF)d2e2d2e2fE2=R.B,R.C,S.A,F(D>’d1’∧E=’e3’∧F>’f2’∧R.A=S.A∧R.B=S.B∧R.C=T.C(R×參考答案：E2(R.BR.CS.AF)b4cE3=R÷S參考答案：E3(A，B)(2)試將E1轉換為等價的關系代數(shù)表達式參考答案：E1=R.D,R.E,T.F(B>’b1’∧S.A>’a1’∧T.C>’c1’∧R.A>S.A∧R.B=S.B(R×試將E2轉換為等價的關系元組演算表達式參考答案：E2={t|(u)(v)(w)(R(u)∧S(v)∧T(w)∧u[4]>’d1’∧v[3]=’e3’∧w[2]>’f2’∧R.A=S.A∧R.B=S.B∧R.C=T.C∧t[1]=u[2]∧t[2]=u[3]∧t[3]=v[1]∧t[4]=w[(4)對E2進行代數(shù)優(yōu)化4、設有下列關系:R(A,B,C)S(B,C,D,E)T(D,F,G)a1b2c1b2c2d1e1d1f1g1a1b2c2b2c2d2e1d1f2g2a2b2c1b2c1d2e2d2f1g3a2b2c2b2c1d3e3d2f3g4a2b3c1b3c4d1e1d3f1g5a3b1c2d3f2g6a3b2c4a3b3c4試計算下列關系表達式的值：E1=A,S.B,E,F(A=’a2’∧E=’e1’∧G<’g4’(R?S?E2={xyz|(quvw)∧(R(wqx)∧S(qxyu)∧T(yvz)∧w>’a2’∧u<’e2’∧v=’f1’)}試將E1轉換為等價的關系元組演算表達式試將E2轉換為等價的關系代數(shù)表達式對E1進行代數(shù)優(yōu)化試計算下列關系表達式的值：E1=A,S.B,E,F(A=’a2’∧E=’e1’∧G<’g4’(R?S?參考答案：E1(A,S.C,E,F)a2c2ea2c2e1E2={xyz|(quvw)∧(R(wqx)∧S(qxyu)∧T(yvz)∧w>’a2’∧u<’e2’∧v=’f1’)}參考答案：E2(C,D,G)c4d1g試將E1轉換為等價的關系元組演算表達式參考答案：E1={t|(u)(v)(w)(R(u)∧S(v)∧T(w)∧u[2]=v[1]∧u[3]=v[2]∧v[3]=w[1]∧u[1]=’a2’∧v[4]=’e1’∧w[3]<’g4∧t[2]=v[2]∧t[3]=v[3]∧t[4]=w[2]}試將E2轉換為等價的關系代數(shù)表達式參考答案：E2=C,D,G(A>’a2’∧E<’e1’∧G=’f1’∧R.B=S.B∧R.C=S.C∧S.D=T.D(R×E2=C,D,G(A>’a2’∧E<’e2’∧F=’f1’(R?對E1進行代數(shù)優(yōu)化5、以下定義的是某汽車修理廠管理系統(tǒng)數(shù)據(jù)庫，其中加下劃線的為關系模式主鍵，斜體字為外鍵。該修理廠雇用若干名修理工并劃分為不同的班組，汽車維修以班組為單位進行，每個班組安排一名修理工作為組長負責分配給該組的汽車維修事宜。修理工(工號，姓名，年齡，參加工作時間，班組號)班組(班組號，人數(shù)，組長工號)汽車(車牌號，車主姓名，車型，聯(lián)系電話)維修(維修記錄編號，車牌號，班組號，維修時間，收費)試針對上述關系數(shù)據(jù)庫寫出如下SQL查詢：(1)查詢該修理廠劃分的維修班組總數(shù)。(2)查詢各維修班組的班組號及其組長姓名。(3)查詢車牌號為“V0075”的汽車在“2011-01-01”至“2011-12-31”期間由修理工“E029”所在班組進行維修的費用總額。(4)將修理工“E010”所在分組編號調(diào)整為“T03”。參考答案：（1）SELECTCOUNT(班組號)FROM班組（2）SELECT班組號，姓名組長姓名FROM班組，修理工WHERE組長工號=工號（3）SELECTSUM(收費)FROM維修，班組，修理工WHERE車牌號＝’V0075’AND維修時間>=’2011-01-01維修時間<=’2011-12-31’AND工號＝’E029維修.班組號=班組.班組號AND班組.班組號=修理工.班組號（4）UPDATE修理工SET班組號=’T03WHERE工號=’E0106、以下定義的是某手機話費充值卡管理系統(tǒng)數(shù)據(jù)庫，其中加下劃線的為關系模式主鍵，斜體字為外鍵。每張充值卡通過卡號及密碼為手機號碼充值，一張充值卡只能為一個手機號碼充值且一次充值過程必須消費完卡上的所有金額。每個手機號碼只屬于一個機主，而每位機主可以擁有多個手機號碼。充值卡(卡號，密碼，面額，是否已售出)手機(手機號碼，開戶時間，開戶地點，機主編號)充值(卡號，手機號碼，充值時間)機主(機主編號，姓名，身份證號碼，聯(lián)系地址，聯(lián)系方式)針對上述關系數(shù)據(jù)庫寫出如下SQL查詢：(1)查詢尚未售出(是否已售出屬性取值為“否”)的充值卡張數(shù)。(2)查詢“劉”姓手機機主的姓名及持有的手機號碼。(3)查詢開戶地點為“西安交通大學”的所有手機號碼在“2010-11-01”至“2010-11-30”期間的充值總額。(4)將卡號為“SX010323”的充值卡面額增加一百元。（1）SELECTcount(*)FROM充值卡WHERE是否已售出＝’否’（2）SELECT姓名，手機號碼FROM手機，機主WHERE姓名like‘劉%’and手機.機主編號＝機主.機主編號（3）SELECTsum(面額)FROM充值卡，充值，手機WHERE開戶地點＝’西安交通大學’and充值時間>’2010-11-01’and充值時間<’2010-11-30’and充值卡.卡號＝充值.卡號and手機.手記號碼＝充值（4）UPDATE充值卡SET面額＝面額＋100WHERE卡號＝’SX010323’7、以下是某學生食堂就餐卡管理系統(tǒng)中的部分表，其中加下劃線的屬性為主鍵，斜體字屬性為外鍵，每個學生只可辦理一張就餐卡。學生(學號，姓名，性別，班級，出生年月，卡號)就餐卡(卡號，開戶日期，失效日期，密碼，余額，每日消費限額)POS終端(POS編號，地理位置)消費(卡號，POS編號，消費日期，消費金額)充值(卡號，充值時間，金額)針對上述關系數(shù)據(jù)庫寫出如下SQL查詢：(1)查詢卡號為“053021”的就餐卡余額及每日消費限額。(2)查詢編號為“018”的POS終端2010年12月的總收入。(3)查詢“張蓓”同學2010年10月1日(4)查詢曾經(jīng)在“西八食堂”(地理位置)就餐過的學生學號及姓名。(5)請為一名新入校同學增加其相關信息，學號：10054001，姓名：白楊，性別：女，班級：計算機01，出生日期：1992-11-08，該同學于2010-09-01辦理的新就餐卡卡號為060567，失效日期：2014-08-31，默認密碼：123456，每日消費限額：50元。參考答案：（1）SELECT余額,每日消費限額FROM就餐卡WHERE就餐卡.卡號＝’053021’（2）SELECTSUM(消費金額)FROM消費WHEREPOS編號=’018’AND消費日期>=’2010-12-01’AND消費日期<=’2010-12-30’（3）SELECTCOUNT(消費)FROM消費，學生WHERE學生.姓名=‘張培’AND消費日期=’2010-10-01’AND消費.POS編號=’029’（5）INSERTINTO學生VALUES(‘10054001’,‘白楊’,‘女’,‘計算機01’,‘1992-11-08’,‘060567’INSERTINTO就餐卡VALUES(‘020567’,’2008-09-01’,‘2012-08-31’,8、下面定義的是某網(wǎng)上書店的數(shù)據(jù)庫，其中加下劃線的是主鍵，斜體字的是外鍵圖書(圖書編號，書名，定價，庫存冊數(shù)，出版社)客戶(客戶編號，賬號，口令，賬戶余額，客戶類別，電話，送貨地址)訂單(訂單編號，客戶編號，下單時間，支付金額)訂單明細(訂單編號，圖書編號，單價，定購冊數(shù))針對上述關系數(shù)據(jù)庫寫出如下SQL查詢：(1)查詢書名以“數(shù)據(jù)庫系統(tǒng)”開頭的所有圖書編號及庫存冊數(shù)。(2)查詢2010年01(3)查詢編號為“0323”的客戶購買過的所有圖書名稱及各種圖書的定購冊數(shù)。(4)將科學出版社出版的《數(shù)據(jù)庫系統(tǒng)教程》庫存冊數(shù)增加100冊。參考答案：（1）SELECT圖書編號，庫存冊數(shù)FROM圖書WHERE書名LIKE‘數(shù)據(jù)庫系統(tǒng)%’（2）SELECTSUM(支付金額)FROM訂單WHERE下單時間＝’2010-01-22（3）SELECT書名，定購冊數(shù)FROM圖書，訂單，訂單明細WHERE圖書.圖書編號＝訂單明細.圖書編號AND訂單.訂單編號＝訂單明細.訂單編號AND客戶編號＝’0323（4）UPDATE圖書SET庫存冊數(shù)＝庫存冊數(shù)＋100WHERE書名＝’數(shù)據(jù)庫系統(tǒng)教程’AND出版社=’科學出版社’9、設有關系模式R（A,B,C,D,E,G）函數(shù)依賴集F={BE,DG,AB,EA,DEC}及R的一個分解р={R1(D,G),R2(B,E),R3(C,D,E),R4(A,B)}(1)試判斷р是否無損聯(lián)結？（構造M矩陣判斷）(2)試判斷р是否保持函數(shù)依賴集F？并說明為什么？參考答案：（1）р的初始符號表：（A,B,C,D,E,G）R1b11b12b13a4b15a6R2b21a2b23b24a5b26R3b31b32a3a4aR4a1a2b43b44р經(jīng)過F變換后的終止符號表：（A,B,C,D,E,G）R1b11b12b13a4b15a6R2a1a2b23bR3a1a2a3aR4a1a2b43b（2）р是無損聯(lián)結分解，因為р經(jīng)過F變換后的終止符號表中出現(xiàn)了全’a’行10、設有關系模式R（A,B,C,D,E,G,H），F(xiàn)={CDB，CDEA，AB，BE，GAEH，HEG}（1）試求F的最小函數(shù)依賴集FMIN；（2）試求R的所有候選鍵；（3）試將R分解成3NF模式集，要求分解無損連接且保持函數(shù)依賴;參考答案：（1）Fmin={CDA,AB,BE,GA,GH,HG}或{CDA,AB,BE,HA,GH,HG}（2）KEY1=CDGKEY2=CDH（3）R可分解為：{R1(C,D,A),R2(A,B),R3(B,E),R4(H,A),R5(G,H),R6(C,D,G)}或{R1(C,D,A),R2(A,B),R3(B,E),R4(H,A),R5(G,H),R6(C,D,H)}或{R1(C,D,A),R2(A,B),R3(B,E),R4(G,A),R5(G,H),R6(C,D,H)}或{R1(C,D,A),R2(A,B),R3(B,E),R4(G,A),R5(G,H),R6(C,D,G)}11、判斷下列關系模式最高屬于第幾范式，并解釋原因R1(ABCDE)，F(xiàn)=F={ED,DA,AE,BA}R2(EXGH)，F(xiàn)={E→H,E→G,GHX→E}R3(XYZ)，F(xiàn)={X→Y,Y→Z,Z→X}R4(ABCD)，F(xiàn)={A→B,CD→A}R5(XYZ),F={X→→Y|Z}參考答案：R1的候選鍵是{BC}，最高屬于1NF。R2的候選鍵是{GHX,EX}，最高屬于3NFR3的候選鍵是{X,Y,Z}，最高屬于BCNFR4的候選鍵是{CD}，最高屬于2NFR5的候選鍵是{XYZ}，最高屬于BCNF12、下面是用ORDB的定義語言定義的數(shù)據(jù)庫：CREATETYPEMyStringcharvarying；CREATETABLEuniversity(unameMyString, cityMyString, presidentref(faculty), staffsetof(ref(faculty)), editsetof(ref(coursetext)));CREATETABLEfaculty(fnointeger, fnameMyString, ageinteger, salaryinteger, works_forref(university), teachsetof(ref(coursetext)));CREATETABLEcoursetext(cnameMyString, textnameMyString, teacherref(faculty), editorref(university));（1）試畫出上述數(shù)據(jù)庫的對象聯(lián)系圖參考答案：（2）試用ORDB的查詢語言寫出下列查詢：檢索采用“MathematicalAnalysis"教材講授”MATHS”課的教師工號和姓名。參考答案：SELECTF.fno，F(xiàn).fnameFROMfacultyasFWHEREF.teachIN(‘MATHS’，’MathematicalAnalysis’)；檢索西安地區(qū)各大學超過年齡50歲的教師姓名參考答案：SelectB.fnameFromuniversityasA,A.staffasBWhereA.city=‘xian’AndB.age>50檢索西安交大每位老師上課所用教材及其編寫學校參考答案：SelectB.fname,C.textname,C.editor.unameFromuniversityasA,A.staffasB,B.teachasCWhereA.uname=‘西安交大’13、考慮用二元聯(lián)系（圖1）對三元聯(lián)系（圖2）的表示：分別給出圖1中E，A，B，C，RA，RB和RC的一個實例，這些實例不對應圖2中A，B，C和R的任何實例；更改圖1中的ER圖，引入適當?shù)募s束以確保滿足約束的E，A，B，C，RA，RB和RC的任何實例都對應于A，B，C和R的一個實例；更改以上的轉化以表示在三元聯(lián)系上的全參與約束；ABABECRARCRBBARC圖1圖1圖2解：令E={e1,e2},A={a1,a2},B={b1},C={c1},RA={(e1,a1),(e2,a2)},Rb={(e1,b1)},Rc={(e1,c1)}；可以看出，由于元組（e2,a2）的原因，不存在任何實例對應于E,Ra,Rb,Rc如下圖所示：通過引入E和關系Ra，Rb，Rc之間的全部參與的約束條件，以便在E中的每個元組都和A，B，C有關系。假設A全部參與關系R，則在A和Ra之間引入全部參與約束。4）將E看作弱實體集，而將Ra,Rb,Rc看作標志聯(lián)系集。如下圖14、分別判斷下列圖中G1和G2是否互模擬(bisimulation)，并說明理由aaaabccbG1=G2=ababcabccG1G2ddd解:（１）在圖中標出各點的狀態(tài),我們構造關系S={(P0,Q0),(P1,Q1),(P2,Q1),(P3,Q2),(P4,Q3)}可知G2可以模擬G1,下面我們討論S+1={(Q0,P0),(Q1,P1),(Q1,P2),(Q2,P3),(Q3,P4)}是否可模擬,在G2中Q0有一個a變換可對應到G1中2個變換,即(Q1,P1)∈S-1,(Q1,P2)∈S-1。但Q1有兩個變換b,c，而在Ｇ１中公存在只有b或只有c的狀態(tài)點，可知Ｇ１和Ｇ２不能互模擬。（２）如圖，標出各狀態(tài)點，構造有關系S={(P0,Q0),(P1,Q1),(P1,Q2),(P2,Q3),(P2,Q4),(P3,Q5)},可知其中Ｇ１中的點均可由G2中的點模擬，下面我們考慮S+1={(Q0,P0),(Q1,P1),(Q2,P1),(Q3,P2),(Q4,P2),(Q5,P3)}，可知同樣其中Ｇ２中的點均可由Ｇ１中的點模擬，所以Ｇ１和Ｇ２互模擬。復習題2設關系r1(A，B，C)，r2(C，D，E)有如下特性：r1有200000個元組，r2有45000個元組，一塊中可容納25個r1元組或30個r2元組。試估算以下每一種策略計算r1|><|r2所需存取的塊數(shù)：嵌套循環(huán)連接塊嵌套循環(huán)連接歸并連接散列連接解：r1需要8000個塊，r2需要1500個塊。假設有一個存儲器有M頁。如果M>8000，那么使用平坦嵌套循環(huán)，通過1500＋8000次磁盤存取就可以很容易的完成連接操作。因此我們只考慮M<=8000的情況。1）嵌套循環(huán)連接：使用r1作為外關系，我們需要進行200000×1500＋8000＝300，008，000次磁盤存取。如果r2是外關系，那么我們需要45000×8000＋1500＝360001500次磁盤存取。2）塊嵌套循環(huán)連接：如果r1是外關系，我們需要×1500＋8000次磁盤存取，如果r2是外關系，我們需要×8000＋1500次磁盤存取。3）歸并連接假設r1和r2最初沒有按連接關鍵字進行排序，那么總的排序加上輸出的耗費為Bs＝1500（2＋1）＋8000（2＋1）次磁盤存取。假設具有相同連接屬性值的所有員組裝入內(nèi)存中，那么總的耗費是Bs＋1500＋8000次磁盤存取。4）散列連接我們假設不發(fā)生溢出。因為r2比較小，所以我們用r2作為創(chuàng)建關系，用r1作為探針關系。如果M>1500，那么就不需要進行遞歸分割，于是耗費為3（1500＋8000）＝28500次磁盤存取，否則耗費為2（1500＋8000）＋1500＋8000次磁盤存取。設關系r1(A，B，C)，r2(C，D，E)和r3(E，F(xiàn))，其主碼分別為A，C，E。假設r1有1500個元組，r2有2500個元組，r3有1000個元組。試估計r1|><|r2|><|r3的大小；給出一個有效計算r1|><|r2|><|r3的策略；答：1）因為連接具有結合律和交換性，所以不管我們怎樣連接r1,r2和r3，最終連接r1，r2和r3得到的結果都是一樣的。因此，我們只考慮基于（（r1r2）r3）連接策略下的大小。因為C為r2的關鍵字，所以連接r1和r2產(chǎn)生至多包含1500個元組的關系。同樣，把前面得到的結果和r3進行連接，將產(chǎn)生至多包含1500個元組的關系，因為E為r3的關鍵字。因此，最終關系最多包含有1500個元組。2）計算這個連接的一個有效的策略是為關系r2上的屬性C和關系r3上的屬性E創(chuàng)建索引。然后對于r1中的每個元組，我們按照下面锝方法作：A．使用在C上創(chuàng)建的索引，在r2中查找最多一個元組，這個元組與r1中的C匹配。B．使用在E上創(chuàng)建的索引，在r3中查找最多一個元組，這個元組與r2中的E值匹配。Considerahash-joinoftworelationsRandShavingB(R)=1000andB(S)=500.ThevaluesinRandSareskewedsuchthatthehashfunctionassignsthreetimesasmanytuplestoeven-numberedhashbucketsastoodd-numberedbuckets.Howmuchmemorywouldberequiredtoperformthejoinintwopasses?Whatistheperformanceofthehash-joingiventheskewedhashing?Howwouldtheperformanceofusingthehash-joincomparetousingasorted-mergealgorithm?1。散列連接要用兩趟完成，則需要遞歸劃分，對關系s的劃分所需趟數(shù)估計為，所以有，M=8.9。對關系r進行劃分所需趟數(shù)估計為，且，M=11。因為散列算法要求內(nèi)存滿足小的操作對象，所以需要8.9*4KB=35.6KB的內(nèi)存。2.增加分區(qū)的個數(shù)，使得每個分區(qū)的大小（包括該分區(qū)上的散列索引在內(nèi)）小于內(nèi)存容量。3.基于散列的算法使用一個散列函數(shù)將操作對象分割到桶中，然后操作被分別應用到桶和桶對上能被內(nèi)存所容納。基于排序歸并連接的算法可對大于內(nèi)存的關系進行排序，可知在關系以排序的情況下，歸并連接是比較可取的。散列和排序在某種意義下是對偶的，因為能用散列實現(xiàn)的連接也可用排序來實現(xiàn)，反之亦然。基于散列的算法常常優(yōu)于基于排序的算法，我們假設內(nèi)存能容納100個塊，則用散列連接對S劃分為5個劃分，則代價為3（1000+500）=4500次塊傳輸，用排序歸并對R的排序需次快傳輸，對S的排序需次塊傳輸，把排序寫回磁盤需要1500次塊傳輸，歸并步驟還需1500次塊傳輸以讀回數(shù)據(jù)，因此歸并排序總代價為5850次塊傳輸。什么是可恢復調(diào)度？舉例說明。答：假設在一個調(diào)度中，Tj讀取了Ti寫入的數(shù)據(jù)，Ti在提交前發(fā)生故障，我們必須中止Tj以保證事務地原子性。若Tj在Ti出現(xiàn)故障后是可中止的，那么我們就稱該調(diào)度是可恢復調(diào)度。可恢復調(diào)度應滿足：對于每個事務Ti和Tj，如果Tj讀取了由Ti所寫的數(shù)據(jù)項，則Ti先于Tj提交。Stateifthefollowingstatementsaretrueorfalse.ForanyscheduleS1andanyserialscheduleS2,ifS1isconflictequivalenttoS2,thenS1isconflictserializable.ForanyschedulesS1andS2,ifS1andS2areconflictserializable,thenS1andS2areconflictequivalent.Allserializableschedulesarerecoverable.Allrecoverableschedulesareserializable.AllserialschedulesareACR(avoidcascadingrollback).Anyschedulethatcanbeproducedbyatwo-phaselockingmechanismcanalsobeproducedbyavalidationmechanism.Anyschedulethatcanbeproducedbyavalidationmechanismcanalsobeproducedbyatwo-phaselockingmechanism.Anyschedulethatcanbeproducedbyatwo-phaselockingmechanismwithshared(read)andexclusive(write)locks,canalsobeproducedbyatwo-phaselockingmechanismwithexclusivelocksonly.1）ANSWER:true2）ANSWER:false3）ANSWER:false4）ANSWER:false5）ANSWER:true6）ANSWER:false7）ANSWER:true8）ANSWER:true設一個嵌入式SQL應用程序中80%的時間花在運行SQL代碼上，20%的時間花在運行主語言代碼上。如果只對SQL代碼實施了并行，那么可以期望得到多大的加速比？說明理由。答：由于不能被并行話的部分占總運行時間的20%，所以可獲得的加速比最多不會超過5。給定如下數(shù)據(jù)圖(DataGraph)：11paper4section5title6algorithm7proof8section9title1011proof12usesalgorithm13section1415161718aboutabouttitle2section3titleexpexpdatagraph試分別給出其DataGuide圖和1-Iindex索引圖如圖：11paper2,4,8,13section3,5,9,14title6,10algorithmproof12uses15,1617,18aboutexp6,107,11algorithmDataGuide圖PS：此圖為我自己畫的，不知道是否正確，有懂行的麻煩看看！11paper2,4,8,13section3,5,9,14title6,10algorithm7proof11proof12uses15,1617,18aboutexp1-index復習題3假如存在永遠不會發(fā)生軟硬件故障的數(shù)據(jù)庫系統(tǒng)，對于這樣的系統(tǒng)，還需要故障恢復管理器嗎？解釋你的回答。Considerthefollowinglogrecordsinasystemthatincurredacrash.<T1,start><T2,start><T1,x,1,2><T1,commit><T2,y,1,3><T3,start><T3,x,2,3><checkpoint{T2,T3}><T3,z,1,2><T3,commit>failureWhichtransactionsshouldberedone,andwhichshouldbeundonewhenthesystemrecovers?ConsiderthefollowinglogwheretheDPTrepresentstheDirtyPageTableandTTrepresentstheTransactionTableAnswerthefollowingquestions(usingtheARIES-likealgorithmwestudiedinclass):WhatisthesmallestLSNaccessedduringtheAnalysisphase.FillinthecontentsoftheDirtyPageTableandtheTransactionTableattheendoftheAnalysisphase.(youmaynotneedallthespacewegiveyou)AtwhichLSNdoestheRedophasebegin?Whatentries(specifyonlyLSNs)dogetundoneaspartoftheUndophase?解:1)thesmallestLSNaccessedduringtheAnaylsisphaseis102)seethisPageIDRecLSN110340550870XIDStatusLastLSNT1abort903)104)40,10假設一個系統(tǒng)運行三種類型的事務：A類事務以50/s的速度運行，B類事務以100/s的速度運行，C類事務以200/s的速度運行。假設系統(tǒng)所處理的事務中A、B、C三類事務所占比例分別為30%，30%，40%。如果A、B、C三類事務之間互不干擾，系統(tǒng)的平均事務吞吐量是多少？什么因素會使不同類型事務之間產(chǎn)生相互干擾，導致計算出的平均事務吞吐量不準確？如果不同類型事務之間相互干擾的因素非常復雜，那么用什么方法可以得到比較準確的平均事務吞吐量？答：1）2）引起事務之間干擾的最重要的原因之一是封鎖競爭。在前面的例子中，假設事務A和事務B都是更新事務，而事務C是查詢事務。由于處理器和磁盤之間的速度不匹配，很可能會出現(xiàn)下面的情況：A類型的一個事務持有一個“熱”數(shù)據(jù)項的鎖，并且在等待將其寫道磁盤中來完成操作，在在這個時候B類或C類一個事務正在等待事務A持有的封鎖。在這種情況下，一些CPU循環(huán)就被浪費了。因此，觀察到的事物吞吐量會比計算出來的吞吐量要小。相反，如果A類型的事務和B類型的事務是大量消耗磁盤資源的事務，而C類型事務時大量消耗CPU資源的事務，那么觀察到的事物吞吐量將會比計算到吞吐量大。封鎖競爭也會導致死鎖，這種情況下一些事務將不得不被終止。事務的終止和重啟將會導致觀察到的吞吐量比計算出來的吞吐量要小。數(shù)據(jù)結構大小的限制，事務管理器事務記錄函數(shù)花費時間的變化情況等因素會導致觀察到的吞吐量和計算出來的吞吐量之間的不同。3）如果不同類型事務之間的相互干擾因素非常復雜，那么我們可以采用性能模擬的辦法對系統(tǒng)得吞吐量進行測試。首先需要建立模型，然后再模型上進行各種實驗，可以通過改變不同的實驗環(huán)境來估算出系統(tǒng)得平均吞吐量。對于下列每一種任務，哪一種并行形式(查詢間并行、操作間并行、操作內(nèi)并行)可能是最關鍵的？說明理由。提高一個執(zhí)行許多小的查詢的系統(tǒng)吞吐量；在磁盤和處理器數(shù)目都很大的情況下，提高一個執(zhí)行少量大的查詢的系統(tǒng)吞吐量；答：查詢間并行指的是：不同的查詢或不同的事務彼此并行地執(zhí)行。操作內(nèi)并行指的是：我們可以通過并行的執(zhí)行每一個運算，如排序，選擇，投影，連接等，來加速一個查詢速度。操作間并行指的是：我們可以通過并行地執(zhí)行每一個查詢表達式中地多個不同的運算，來加快一個查詢的處理速度。通過上面的介紹，我們可以知道，對于a查詢間并行；對于b，操作內(nèi)并行。ConsiderarelationT(A,B)thatcontains10000recordspartitionedonto5disksaccordingtothefollowingstrategies:Roundrobin.Hash-partitionbasedonhashfunction(Amod5)Assumethe5diskscorrespondingtohasvalues0,1,…,4contain3000,1500,1500,2000,2000tuplesrespectively.Range-partitionbasedonvectoronB[20,40,60,80]Assumethediskresponsiblefor<20has1000records,theonefor[20,40)has2000records,andtheotherdisksinthisorderhave2000,2000,3000records,respectively.Noindexiscreated.Assumeprocessingonetupletakes1msforanyquery.Whatarethecostsofprocessingthefollowingqueriesusingeachoftheabovestrategies?select*fromTselect*fromTwhereA=20select*fromTwhere20<A<30select*fromTwhere70<B<851234Roundrobin2222Hash-partiton3333Range-partition3333ConsiderarelationT(A,B)thatcontains10000recordspartitionedonto5disksaccordingtorange-partitionbasedonvectoronA[20,40,60,80].The5disks(intheorderoftheirresponsiblerangescontain1000,2000,2000,2000,3000records,respectively.Describeanefficientalgorithmforansweringthefollowingquery:selectA,sum(B)fromTgroupbyAYourstrategyshouldminimizethenumberoftuplestransmittedfromonedisktoanother.FortheDTD,XML,andXQUERYgivenbelow,answerthequestionslistednext.TheDocumentTypeDefinitionmyfriend.dtd:<!ELEMENTmyfriends(person*)><!ELEMENTperson(id,name?,cell-phone*,children?)><!ELEMENTchildren(child*)><!ELEMENTchild(name,toys*)><!ELEMENTname(#PCDATA)><!ELEMENTtoys(#PCDATA)><!ELEMENTid(#PCDATA)>...]<!ELEMENTemployees(emp*)><!ELEMENTemp(id,work-phone,(contact|address)><!ELEMENTaddress(city,zip,street)><!ELEMENTid(#PCDATA)>]<!ELEMENTcontact(#PCDATA)>...]TheXMLDocumentfriends.xml:<myfriends><person><id>1</id><name>``jack''</name><cellphone>2222</cellphone></person><person><id>2</id><cellphone>3333</cellphone><children><child><name>c1</name></child><children><child><name>c2</name><toys>t1</toys></child><child><name>c2</name></child>...</children></person></myfriends>TheXMLDocumentemployees.xml:<employees><emp><id>1</id><workphone>9999</workphone><contact>``me''</contact></emp><emp><id>2</id><workphone>8888</workphone><address><city>c</city><zip>z</zip><street>s</street></address></emp></employees>TheXQUERYexpression:<contact-info>FOR$outerin(friends.xml)//person,LET$child:=$outer/childrenWHERE($outer/cellphone>2000)RETURN$outer/idFOR$innerIN(employees.xml)/employees/emp[id=$outer/id]RETURN{<contact>$outer/cellphone$child/child$inner/workphone$inner/address/city</contact>}</contact-info>1)ListtheXMLoutputthattheXQUERYexpressionwouldgeneratewhenappliedtothegivenXMLinputdocuments.2)DesignarelationalschematostorethetwogivenXMLdatafiles.3)ListtheSQLquerythatyouwouldgeneratetoexecutethegivenXQUERYexpressiononyourrelationaldatabase.StatewhatfinalcomputationswouldremaintobedonebytheXQUERYprocessorbeyondexecutingyourSQLstatement,ifany.解:1)<contact-info><id>1</id><contact><cellphone>2222</cellphone><workphone>9999</workphone></contact><id>2</id><contact><cellphone>3333</cellphone><child><name>c1</name></child><child><name>c2</name><toys>t1</toys></child><child><name>c2</name></child><workphone>8888</workphone><city>c</city></contact></contact-info>2)person(pid,cellphone,name)child(cid,parentid,name)toy(tid,cid,toy_name)emp(pid,workphone,contact,city,zip,street)person(pid,name,cellphoneSetMultiSet(cellphones),ChildSetMultiSet(children))cellphones(cellphone)children(name,toySetMultiSet(toys))toys(toyname)emp(pid,workphone,contact,city,zip,street)selectperson.cellphone,array(selectchild.toyformchildwherechild.parentid=person.pid)aschild_array,emp.workphone,emp.cityfromperson,child,empwhereperson.pid=emp.pidANDperson.cellphone>2000Supposeyouhavetorepresenttheinformationaboutparts.Eachparthasaname(unique),andatextualdescription.Partsmaybesimpleorcomplex.Asimpleparthasacolorbutnochildrensubparts.Acomplexparthasanumberofchildrensubparts(whichcanbesimpleorcomplex),eachofwhichmayberepeated.(E.g.,acarhas4wheels.)Youcanassumethateachpartcanbeachildsubpartofatmostoneotherpart(soeachpart,togetherwithitssubparts,canbeviewedasatree).Donotassumeanyfixednumberoflevelsofpartcomposition.DefinetheschemaofXMLdocumentscontainingpartinformationusingDTDs.GiveanexampleofadocumentinstancewhichisvalidundertheDTDs.WritethefollowingqueriesinXQuery:findthenamesofalltheyellowparts.findallthepartsthathaveatleast5distinctchildrensubparts.findallthepartscontainingadescendantsubpartnamed“spoke"andnotcontainingadescendantsubpartnamed“tire".ANSWER:<!DOCTYPEParts[<!ELEMENTParts(part)+><!ELEMENTPart(description,subpartinfo*|color))><!ATTLISTPartnameID#REQUIRED><!ELEMENTsubpartinfo(part)><!ATTLISTsubpartinfonameID#REQUIRED><!ELEMENTqty(#PCDATA)><!ELEMENTname(#PCDATA)>]>2)<parts><partname=”bicycle”><subpartinfo><partname=”wheel”><subpartinfo><partname=”rim”><color>silver</color></part><qty>1</qty></subpartinfo><subpartinfo><partname=”spokes”><color>silver</color></part><qty>40</qty></subpartinfo><subpartinfo><partname=”tire”><color>black</color></part><qty>1</qty></subpartinfo></part><qty>2</qty></subpartinfo><subpartinfo><partname=”brake”><color>black</color></part><qty>2</qty></subpartinfo><subpartinfo><partname=”gear”><color>black</color></part><qty>3</qty></subpartinfo><subpartinfo><partname=”frame”><color>yellow</color></part><qty>1</qty></subpartinfo></part></parts>3)(a)for$pin//partwhere$p[color=”yellow”]return$p/@name(b)for$pin//partwherecount($p/subpartinfo)>=5return$p(c)for$pin//partWhere($p//name=”sopke”)and(not($p//name=”tire”))Return$pConsidertherelationPARTS,whichhasPart#ashashkeyandwhichincludesrecordswiththefollowingPart#values:2369,3760,5046,4871,5659,2222,1821,1074,7115,1620,2428,3943,4750,3157,6975,4981,9208.Thehashfunctionuses8buckets,numbered0to7.Eachbucketisonediskblockandholdstworecords.Loadtheserecordsintothefileinthegivenorderusingthehashfunctionh1(K)=Kmod8.CalculatetheaveragenumberofblockaccessesforarandomretrievalonPart#.Nowloadtherecordsintoexpandablehashfilesbasedonlinearhashing.Startwithasinglediskblock,usingthehashfunctionh2(K)=Kmod2,andshowhowthefilegrowsandhowthehashfunctionschangeastherecordsareinserted.Assumethatblocksaresplitwheneveranoverflowoccurs,andshowthevalueofnateachstage.解:1)平均查找代價：(8＋6＊2＋3＋3＋3）/17＝1.712)Considerahash-joinoftworelationsRandShavingB(R)=1000andB(S)=500.ThevaluesinRandSareskewedsuchthatthehashfunctionassignsthreetimesasmanytuplestoeven-numberedhashbucketsastoodd-numberedbuckets.Howmuchmemorywouldberequiredtoperformthejoinintwopasses?Whatistheperformanceofthehash-joingiventheskewedhashing?Howwouldtheperformanceofusingthehash-joincomparetousingasorted-mergealgorithm?解：1）散列連接要用兩趟完成，則需要遞歸劃分，對關系s的劃分所需趟數(shù)估計為，所以有，M=8.9。對關系r進行劃分所需趟數(shù)估計為，且，M=11。因為散列算法要求內(nèi)存滿足小的操作對象，所以需要8.9*4KB=35.6KB的內(nèi)存。2）.增加分區(qū)的個數(shù)，使得每個分區(qū)的大小（包括該分區(qū)上的散列索引在內(nèi)）小于內(nèi)存容量。3）.基于散列的算法使用一個散列函數(shù)將操作對象分割到桶中，然后操作被分別應用到桶和桶對上能被內(nèi)存所容納。基于排序歸并連接的算法可對大于內(nèi)存的關系進行排序，可知在關系以排序的情況下，歸并連接是比較可取的。散列和排序在某種意義下是對偶的，因為能用散列實現(xiàn)的連接也可用排序來實現(xiàn)，反之亦然。基于散列的算法常常優(yōu)于基于排序的算法，我們假設內(nèi)存能容納100個塊，則用散列連接對S劃分為5個劃分，則代價為3（1000+500）=4500次塊傳輸，用排序歸并對R的排序需次快傳輸，對S的排序需次塊傳輸，把排序寫回磁盤需要1500次塊傳輸，歸并步驟還需1500次塊傳輸以讀回數(shù)據(jù)，因此歸并排序總代價為5850次塊傳輸。Assumethatthefollowingrelationisfragmentedhorizontallybyplant-number:employee(name,address,salary,plant-number)Assumethateachfragmentisstoredatthecorrespondingplantsite.DescribeagoodprocessingstrategyforthefollowingqueriesissuedattheSanJosesite.FindallemployeesattheNewYorkplant.Findthehighest-paidemployeeatNewYork,Boston,Toronto,respectively.Findtheaveragesalaryofallemployees.答：1）a.紐約節(jié)點發(fā)送查詢;b.讓紐約節(jié)點返回查詢結果。2）a.分別向NewYorl,Boston,Toronto發(fā)送查詢最高工資員工的請求；b.在所有的節(jié)點上計算查詢；c.向SanJose返回結果。3）a.向所有的節(jié)點發(fā)送查詢員工平均工資和人數(shù)的請求；b.各個節(jié)點將計算結果返回到SanJose；c.在SanJose對各個節(jié)點返回的結果進一步求所有員工工資的平均值；d.返回計算出的結果。Considerthefollowingnaturallanguagedescription:JohnSmithistheauthorof"MyLifeasaBug".JohnSmith'sagentisMaryJones.JohnSmithis35yearsold.ThesonofBobSmithisJohnSmith.RepresenttheinformationinthisdescriptionasRDFtriples.UsetheRDFgraphformattorepresentthetriples,withlabeledovalsandlabeleddirectedarcs.Thatis,youdonotneedtouseXMLsyntaxtodescribetheRDFstatements.Usesensiblelabelnames,butyourlabelsdonotneedtobeinURIsyntax.解：<author,“MyLifeasaBug”,JohnSmith><agent,MaryJones,JohnSmith><age,JohnSmith,35yearsold><son,BobSmith,JohnSmith>ConsiderthefollowingRDFdocumentusingtheXMLsyntax.Drawtheequivalentgraph.Forconvenience,youmayuseQNamesforyournodeandedgelabels.<rdf:RDFxmlns:rdf="/1999/02/22-rdf-syntax-ns#"xmlns:rdfs=”/2000/01/rdf-schema#”xmlns:u="/uni#"xml:base=”/uni”><rdfs:Classrdf:ID=”Person”/><rdfs:Classrdf:ID=”Student”/><rdfs:subClassOf=”#Person”/></rdfs:Class><rdfs:Classrdf:ID=”Professor”><rdfs:subClassOf=”#Person”/></rdfs:Class><rdfs:Classrdf:ID=”Course”/><rdf:Propertyrdf:ID=”advises”><rdfs:domainrdf:resource=”#Professor”/><rdfs:rangerdf:resource=”#Student”/><rdfs:subPropertyOf=”#knows”></rdf:Property><rdf:Propertyrdf:ID=”takes”><rdfs:domainrdf:resource=”#Student”/><rdfs:rangerdf:resource=”#Course”/></rdf:Property><rdf:Propertyrdf:ID=”teaches”><rdfs:domainrdf:resource=”#Professor”/><rdfs:rangerdf:resource=”#Course”/></rdf:Property><rdf:Propertyrdf:ID=”knows”/><u:Professorrdf:ID=”alan”><u:teachesrdf:resource=”#cs100”/><u:advisesrdf:resource=”#rob”/><u:advisesrdf:resource=”#sarah”/></u:Professor><u:Studentrdf:ID=”rob”><u:takesrdf:resource=”#cs100”/><u:takesrdf:resource=”#cs200”/></u:Student></rdf:RDF>解：TranslatethefollowingRDFGraphintotheRDF/XMLsyntax.FornodeandsarcslabeledwithQNames,assumethestandardprefixesapply.Forothernames,assumetheyarealllocaltothedocumentyouarewriting.Answer:<?xmlversion="1.0"?><rdf:RDFxmlns:rdf="/1999/02/22-rdf-syntax-ns#"xmlns:rdfs="/2000/01/rdf-schema#"><rdfs:Classrdf:ID="Person"/><rdfs:Classrdf:ID="Director"><rdfs:subClassOfrdfs:Resource="#Person"/></rdfs:Class><rdfs:Classrdf:ID="Actor"><rdfs:subClassOfrdfs:Resource="#Person"/></rdfs:Class><rdfs:Classrdf:ID="Movie"></rdfs:Class><rdf:Descriptionrdf:about="jackson"> <rdf:typerdfs:Resource="#Director"/> <name>PeterJackson</name> <directsrdfs:Resource="#fellowship"/></rdf:Description><rdf:Descriptionrdf:about="wood"> <rdf:typerdfs:Resource="#Actor"/> <name>ElijahWood</name></rdf:Description><rdf:Descriptionrdf:about="fellowship"> <rdf:typerdfs:Resource="#Movie"/> <stars> <rdf:bag> <rdf:liResource="#wood"/> <rdf:liResource="#mckellan"/> </rdf:bag></stars><title>TheFellowshipoftheRing</title></rdf:Description><rdf:Descriptionrdf:about="mckellan"> <rdf:typerdfs:Resource="#Actor"/> <name>IanMckellan</name></rdf:Description></rdf:RDFGiventhefollowingDescriptionLogicknowledgebase答案：acPS：此題答案未經(jīng)證實，如有錯誤，恕不負責！答案：RDF(S)Entailment:GiventheRDFgraphS:答案：ynnyPS：此題答案未經(jīng)證實，如有錯誤，恕不負責！答案：(a)YES(b)SolutionNo.Thesecondtripleisnotentailed(c)SolutionNo.Bothtriplesarenotentailed