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

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

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

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

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

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

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

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

8、先用員工E工作的部門(mén)劃分，再用管轄項(xiàng)目P的部門(mén)來(lái)劃分,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站點(diǎn)上的副本傳至

9、Toronto站點(diǎn)；2）在New York站點(diǎn)上求平均工資，傳至Toronto站點(diǎn)；3）Toronto, Edmonton, Vancouver, Montreal求最高工資，傳至Toronto匯總；,11,第三次作業(yè),習(xí)題: 假定全局關(guān)系和分段模式如下：全局關(guān)系 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使用變換準(zhǔn)則，將下面的全局查詢變化為分段查詢，并對(duì)它們加以簡(jiǎn)化。當(dāng)需要時(shí)用限定關(guān)系代數(shù)消除查詢中不用的段。 (a) 列出在Care中使用‘Aspirin’的Patient 名字； (b) 列出給病人開(kāi)出接受精細(xì)護(hù)理的醫(yī)生名字。,12,第三次作業(yè),(a) 全局關(guān)系上的查詢表達(dá)式(列出在Care中使用‘Aspirin’的Patie

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

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

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

16、代價(jià)為： X站點(diǎn)代價(jià)=2*3+2*3=12 Y站點(diǎn)代價(jià)=3*4+2*3=18 Z站點(diǎn)代價(jià)=3*4+2*3=18故選擇X站點(diǎn)作為收集站點(diǎn)代價(jià)最低,23,由簡(jiǎn)化過(guò)程得知半連接過(guò)程為：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’,做連接∞得到結(jié)果即:(R∝(S∝R)) ∞ ((S∝R)∝(T∝(S∝R)) ∞ (T∝(S∝R)),24,S’,T’,T’,R’,S’’,第五次作業(yè),1.假設(shè)兩個(gè)事務(wù)T 和 U 的 log 記錄如下所示: ,,,,,,,, 如果系統(tǒng)故障時(shí), 磁盤(pán)上記錄的Log記錄如下, 請(qǐng)描述數(shù)據(jù)庫(kù)恢復(fù)管理器的動(dòng)

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 (見(jiàn)課本),26,1. Undo是逆向完成2. Redo是順序完成3. 必須先Undo 后Redo,1.假設(shè)兩個(gè)事務(wù)T 和

19、 U 的 log 記錄如下所示: ,,,,,,,, 如果系統(tǒng)故障時(shí), 磁盤(pán)上記錄的Log記錄下, 請(qǐng)描述數(shù)據(jù)庫(kù)恢復(fù)管理器的動(dòng)作. a) b) c) d) ,第六次作業(yè),27,第六次作業(yè),一個(gè)沖突等價(jià)調(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,非沖突動(dòng)作的交換可得到一個(gè)等價(jià)調(diào)度,28,第六次作業(yè),2. 上題S1-----S4中, 哪個(gè)是可串調(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. 有如下的等待圖, 用分布式檢測(cè)算法檢測(cè)其是否有死鎖(給出檢測(cè)過(guò)程),T2T1,,Site1,,T1 T3,,,,Site2,Site3,30,第七次作業(yè),3. LWFG,31,第七次作業(yè),1） 將site3的LWFG傳給site1

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

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

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

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