高級數(shù)據(jù)庫系統(tǒng)作業(yè)答疑

1、高級數(shù)據(jù)庫系統(tǒng)作業(yè)答疑,2016.1,1,第一次作業(yè),1. 用自己語言定義下列分布式數(shù)據(jù)庫系統(tǒng)中的術語。 全局/局部數(shù)據(jù)、全局/局部DBMS、 全局外/概念模式等（第一章）2. 分布式數(shù)據(jù)庫系統(tǒng)分類？P6-83.分布式DBMS具有哪些集中式DBMS不具備的功能？（P15，34） (見課本),2,第二次作業(yè),已知有如下兩種段分配: A> R1在Site1, R2在Site2, R3在Site3.

2、 B> R1和R2在Site1, R2和R3在Site3.另已知有如下應用(所有應用的頻率相同) A1: 在Site1上發(fā)出, 讀5個 R1記錄, 5個 R2記錄 A2: 在Site3上發(fā)出, 讀5個R3記錄 , 5個R2記錄 A3: 在Site2上發(fā)出, 讀10個R2記錄.問: 1. 如果以本地應用為主要設計目標, 那個分配較優(yōu)?2. 假定A3改為要修改10個R2記

3、錄, 并仍以本地應用為其設計目標, 則那個分配方案較優(yōu)?,3,第二次作業(yè),解：首先完善模型如下：假定：本地讀寫的代價可忽略不計； 異地讀寫操作的代價均相等，記為1故可知，第1個問題，A、B兩種分配方案代價相等。 第2個問題，A分配方案較優(yōu)。,4,分別寫回site1和site3(保持數(shù)據(jù)一致性),從site1或者site3讀取,A> R1在Site1, R2在Site2, R3在Si

4、te3.B> R1和R2在Site1, R2和R3在Site3. A1: 在Site1上發(fā)出, 讀5個 R1記錄, 5個 R2記錄 A2: 在Site3上發(fā)出, 讀5個R3記錄 , 5個R2記錄 A3: 在Site2上發(fā)出, 讀10個R2記錄.,第二次作業(yè),2.2 分布式數(shù)據(jù)庫設計的主要目標？ P412.6 數(shù)據(jù)分片基本原則？數(shù)據(jù)分片基本類型和方法？P44 （見課本）2.9 COMPANY

5、關系數(shù)據(jù)庫：表EMPLOYEE 、DEPARTMENT 、P67DEPT-LOCATION 、PROJECT、WORKS-ON 、DEPENDENT ; 站點B(部門2)、C(部門3)：頻繁訪問EMPLOYEE表的NAME,ESSN,SALARY和SUPERSSN屬性和PROJECT表 站點A(總部門1)：經(jīng)常存取DEPENDENT、定期訪問所有雇員和項目信息 考慮分片和分布。解： (1) 所有表存放

6、于站點A： 部門1要經(jīng)常訪問所有雇員和項目信息 (2) 因為站點B和C分別屬于部門2和3，所以先對DEPARTMENT按DNO水平分片， 取DNO=2、3 分別得到部門2和3的數(shù)據(jù)存放于站點B和C (3)將EMPLOYEE、PROJECT以及DEPT_LOCATION分別和部門2和3的DEPARTMENT 數(shù)據(jù)在DNO屬性上半連接，得到部門2和3上的EMPLOYEE

7、、PROJECT以及 DEPT_LOCATION數(shù)據(jù),5,第二次作業(yè),(4) 對水平分片后的EMPLOYEE進行垂直分片，得到只含有 {NAME,ESSN,SALARY,SUPERSSN,DNO}的片段 (5) WORKS-ON 與 EMPLOYEE和PROJECT都相關，既可以用員工E工作的部門也 可以用管轄項目P的部門來對WORKS-ON水平分片，或者分片更細一些，

8、先用員工E工作的部門劃分，再用管轄項目P的部門來劃分,6,第三次作業(yè),7,第三次作業(yè),3.6解：R JN S = R JN S JN T =,8,第三次作業(yè),3.6(續(xù))R∝S S∝R S∝T T∝ SR∝ T 、T∝R 為空,9,第三次作業(yè),10,第三次作業(yè),3.8解：1）將Boce站點上的副本傳至

9、Toronto站點；2）在New York站點上求平均工資，傳至Toronto站點；3）Toronto, Edmonton, Vancouver, Montreal求最高工資，傳至Toronto匯總；,11,第三次作業(yè),習題: 假定全局關系和分段模式如下：全局關系 Doctor (D#, Name, Dept) Patient (P#, Name, Dept, Treat, D#) Care (P#, Drug

10、, QTY)分段模式 Doctor1 = SLDEPT=‘Surgery’(Doctor) Doctor2 = SLDEPT=‘Pediatrics’(Doctor) Doctor3 = SLDEPT ?‘Surgery’ and DEPT ?‘Pediatrics’(Doctor) Patient1 = SLDEPT=‘Surgery’ and treat=‘inte

11、nsing’(Patient) Patient2 = SLDEPT=‘Surgery’ and treat ?‘intensing’(Patient) Patient3 = SLDEPT ?‘Surgery’ (Patient) Care1 = Care SJ p#=p# Patient1 Care2 = Care SJ p#=p# Patient2

12、 Care3 = Care SJ p#=p# Patient3使用變換準則，將下面的全局查詢變化為分段查詢，并對它們加以簡化。當需要時用限定關系代數(shù)消除查詢中不用的段。 (a) 列出在Care中使用‘Aspirin’的Patient 名字； (b) 列出給病人開出接受精細護理的醫(yī)生名字。,12,第三次作業(yè),(a) 全局關系上的查詢表達式(列出在Care中使用‘Aspirin’的Patie

13、nt 名字),13,全局關系轉化為分段關系,第三次作業(yè),(a),14,上推UN下推PJ 和 SL,第三次作業(yè),(a),15,第三次作業(yè),(b)全局關系上的查詢表達式,D1 與P3 JN為空,P2 無符合條件的元組,D2 與P1 JN為空,D3 與P1 JN為空,16,第四次作業(yè),17,第四次作業(yè),18,第四次作業(yè),3.7如果習題中的三個關系R,S,T分別位于三個不同的站點X,Y,Z。若采用基于半連接的算法計算R∞S∞T,請選擇使得傳輸

14、代價最小的連接執(zhí)行站點和確定半連接序列,19,X,Y,Z,第四次作業(yè),假設每個屬性域長度均為1B，考慮所有的半連接a),選擇得益最高的P2進行優(yōu)化，并對受到影響的的方案重新計算得益和費用,20,在有益方案中選擇得益最高的或者費用最少的方案進行優(yōu)化,b),選擇收益更高的P4進行優(yōu)化，對受影響的半連接重新計算費用和得益c),選擇P1進行優(yōu)化,S’ = S∝R,T’ = T∝S’,2*2,2*2,21,d) 選

15、擇p3繼續(xù)進行優(yōu)化 最終得到的關系如下： R(站點X) S(站點Y) T(站點Z),R’ = R∝S’,22,S’’ = S’ ∝ T’,所以選擇各站點做連接的

16、代價為： X站點代價=2*3+2*3=12 Y站點代價=3*4+2*3=18 Z站點代價=3*4+2*3=18故選擇X站點作為收集站點代價最低,23,由簡化過程得知半連接過程為：S’ = S∝R (R.B 和R.C從X->Y) 將S’傳送給T,做半連接T∝S’得到T’ (S’.D從Y->Z ) 將S’傳送給R,做半連接R∝S’得到R’ (S’.D從Y

17、->X ) 將T’ 傳送給S’，做半連接S’ ∝ T’ (T’.D從Z->Y ) 最終將S’’和T’傳到R’,做連接∞得到結果即:(R∝(S∝R)) ∞ ((S∝R)∝(T∝(S∝R)) ∞ (T∝(S∝R)),24,S’,T’,T’,R’,S’’,第五次作業(yè),1.假設兩個事務T 和 U 的 log 記錄如下所示: ,,,,,,,, 如果系統(tǒng)故障時, 磁盤上記錄的Log記錄如下, 請描述數(shù)據(jù)庫恢復管理器的動

18、作. a) b) c) d) ,25,第五次作業(yè),1．(a)undo U, undo T （不能是undo T，undo U ） (b)undo T, redo U (c)undo T, redo U (d)redo T, redo U (見課本),26,1. Undo是逆向完成2. Redo是順序完成3. 必須先Undo 后Redo,1.假設兩個事務T 和

19、 U 的 log 記錄如下所示: ,,,,,,,, 如果系統(tǒng)故障時, 磁盤上記錄的Log記錄下, 請描述數(shù)據(jù)庫恢復管理器的動作. a) b) c) d) ,第六次作業(yè),27,第六次作業(yè),一個沖突等價調(diào)度如下：S1’=W2(x),W1(x),R1(x),R3(x),C1,W2(y),R3(z),C3,R2(x),C2S2’=R3(z),R2(z),R3(y),W2(y),W1(x),R3(x)

20、,W1(x),R1(x),C1,C2,C3 S3’=W2(x),W2(y),R2(z),C2,R3(z),R3(x),R3(y),C3,R1(x),W1(x),C1S4’=W2(x),W2(y),C2,W1(x),R1(x),A1,R3(z),R3(x),R3(z),R3(y),C3,非沖突動作的交換可得到一個等價調(diào)度,28,第六次作業(yè),2. 上題S1-----S4中, 哪個是可串調(diào)度? 解：,P(S1),T1,T

21、2,T3,P(S2),T1,T2,T3,P(S3),T1,T2,T3,P(S4),T1,T2,T3,先序圖,29,S3和S4為可串調(diào)度,第七次作業(yè),3. 有如下的等待圖, 用分布式檢測算法檢測其是否有死鎖(給出檢測過程),T2T1,,Site1,,T1 T3,,,,Site2,Site3,30,第七次作業(yè),3. LWFG,31,第七次作業(yè),1） 將site3的LWFG傳給site1

22、 (EX E3 E1),32,檢測到包含有EX的LOOP,存在潛在的死鎖,第七次作業(yè),33,2） 將site1上修改過的LWFG傳給site2，得到GWFG,(EX T3 T1 T2）,檢測到不包含有EX的LOOP,存在全

23、局死鎖,第七次作業(yè),4.已知有事務如例5-1(p.111), 并且T1的TS是20, T2的TS是25重啟動間隔是5, 給出按基本T/O方式執(zhí)行的過程(調(diào)度).,34,第七次作業(yè),4.,20 < 25,35,對X的讀操作的時戳只需要與WTM(x) 比較，若小于WTM(x)則拒絕,對X的寫操作的時戳需要與WTM(x)和RTM(x) 比較，若小于WTM(x) 或 RTM(x)則拒絕,第八次作業(yè),6.10這里我們選擇最常用的三種方法

24、：ROWA方法，Gifford方法和集中式協(xié)議的主副本封鎖法來進行分析。（1）ROWA方法首先分析ROWA方法下系統(tǒng)對這12個事務的可用性。由于寫操作要求對所有副本加鎖，所以對于任何一種網(wǎng)絡分割情況，事務1~9都不可能申請全部的鎖，因此它們都不能執(zhí)行，而事務10~12是只讀事務，它們只要求鎖定一個副本，所以它們可以在出現(xiàn)網(wǎng)絡分割時，在各自所在的網(wǎng)絡組內(nèi)執(zhí)行（如果存在這樣的網(wǎng)絡組）。,36,下圖表示了對于每個事務和每種網(wǎng)絡分割情況來說

25、，某事務可在其內(nèi)執(zhí)行的網(wǎng)絡組。只讀事務10‘，11’和12‘與事務10，11和12相同，但是對他們不要求一致性。在ROWA方法中，讀副本不必考慮數(shù)據(jù)的一致性，只鎖定一個副本，并從中讀出數(shù)據(jù)。事實上，數(shù)據(jù)項多副本的一致性是由寫鎖全部副本來保證的，當無故障發(fā)生時，更新必然是對全部副本進行；當發(fā)生故障時使得有些副本無法加鎖，從而導致更新事務不能執(zhí)行更新操作，所以副本的一致性得以保證，故讀出數(shù)據(jù)是一致的。,,,,,,,,,,第九次作業(yè),具有許可