分布式數(shù)據(jù)庫系統(tǒng)復(fù)習(xí)題

1、一、 何為分布式數(shù)據(jù)庫系統(tǒng)？一個分布式數(shù)據(jù)庫系統(tǒng)有哪些特點？答案：分布式數(shù)據(jù)庫系統(tǒng)通俗地說，是物理上分散而邏輯上集中的數(shù)據(jù)庫系統(tǒng)。分布式數(shù)據(jù)庫系統(tǒng)使用計算機(jī)網(wǎng)絡(luò)將地理位置分散而管理和控制又需要不同程度集中的多個邏輯單位連接起來，共同組成一個統(tǒng)一的數(shù)據(jù)庫系統(tǒng)。因此，分布式數(shù)據(jù)庫系統(tǒng)可以看成是計算機(jī)網(wǎng)絡(luò)與數(shù)據(jù)庫系統(tǒng)的有機(jī)結(jié)合。一個分布式數(shù)據(jù)庫系統(tǒng)具有如下特點：物理分布性，即分布式數(shù)據(jù)庫系統(tǒng)中的數(shù)據(jù)不是存儲在一個站點上，而是分散存儲在由計算機(jī)網(wǎng)絡(luò)連接起來的多個站點上，而且這種分散存儲對用戶來說是感覺不到的。邏輯整體性，分布式數(shù)據(jù)庫系統(tǒng)中的數(shù)據(jù)物理上是分散在各個站點中，但這些分散的數(shù)據(jù)邏輯上卻構(gòu)成一個

2、整體，它們被分布式數(shù)據(jù)庫系統(tǒng)的所有用戶共享，并由一個分布式數(shù)據(jù)庫管理系統(tǒng)統(tǒng)一管理，它使得“分布”對用戶來說是透明的。站點自治性，也稱為場地自治性，各站點上的數(shù)據(jù)由本地的DBMS管理，具有自治處理能力，完成本站點的應(yīng)用，這是分布式數(shù)據(jù)庫系統(tǒng)與多處理機(jī)系統(tǒng)的區(qū)別。另外，由以上三個分布式數(shù)據(jù)庫系統(tǒng)的基本特點還可以導(dǎo)出它的其它特點，即：數(shù)據(jù)分布透明性、集中與自治相結(jié)合的控制機(jī)制、存在適當(dāng)?shù)臄?shù)據(jù)冗余度、事務(wù)管理的分布性。二、 簡述分布式數(shù)據(jù)庫的模式結(jié)構(gòu)和各層模式的概念。分布式數(shù)據(jù)庫是多層的，國內(nèi)分為四層：全局外層：全局外模式，是全局應(yīng)用的用戶視圖，所以也稱全局試圖。它為全局概念模式的子集，表示全局應(yīng)用所

3、涉及的數(shù)據(jù)庫部分。全局概念層：全局概念模式、分片模式和分配模式全局概念模式描述分布式數(shù)據(jù)庫中全局?jǐn)?shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)特性，與集中式數(shù)據(jù)庫中的概念模式是集中式數(shù)據(jù)庫的概念視圖一樣，全局概念模式是分布式數(shù)據(jù)庫的全局概念視圖。分片模式用于說明如何放置數(shù)據(jù)庫的分片部分。分布式數(shù)據(jù)庫可劃分為許多邏輯片，定義片段、片段與概念模式之間的映射關(guān)系。分配模式是根據(jù)選定的數(shù)據(jù)分布策略，定義各片段的物理存放站點。局部概念層：局部概念模式是全局概念模式的子集。局部內(nèi)層：局部內(nèi)模式局部內(nèi)模式是分布式數(shù)據(jù)庫中關(guān)于物理數(shù)據(jù)庫的描述，類同集中式數(shù)據(jù)庫中的內(nèi)模式，但其描述的內(nèi)容不僅包含只局部于本站點的數(shù)據(jù)的存儲描述，還包括全局

4、數(shù)據(jù)在本站點的存儲描述。三、 簡述分布式數(shù)據(jù)庫系統(tǒng)中的分布透明性，舉例說明分布式數(shù)據(jù)庫簡單查詢的各級分布透明性問題。分布式數(shù)據(jù)庫中的分布透明性即分布獨立性，指用戶或用戶程序使用分布式數(shù)據(jù)庫如同使用集中式數(shù)據(jù)庫那樣，不必關(guān)心全局?jǐn)?shù)據(jù)的分布情況，包括全局?jǐn)?shù)據(jù)的邏輯分片情況、邏輯片段的站點位置分配情況，以及各站點上數(shù)據(jù)庫的數(shù)據(jù)模型等。即全局?jǐn)?shù)據(jù)的邏輯分片、片段的物理位置分配，各站點數(shù)據(jù)庫的數(shù)據(jù)模型等情況對用戶和用戶程序透明。分布透明性包括三個層次：分片透明性，是分布透明性中的最高層；位置透明性，也稱分配透明性，是分布透明性的中間層；局部數(shù)據(jù)模型透明性，也稱局部映像透明性，即與各站點上數(shù)據(jù)庫的數(shù)據(jù)模型

5、無關(guān)，是分布透明性的最底層。四、 討論分布式數(shù)據(jù)庫更新應(yīng)用中的各級分布透明性問題。分片透明性：應(yīng)用程序如同數(shù)據(jù)庫不是分布的那樣來執(zhí)行更新操作，編程人員不必知道被更新的屬性是否是分片模式的定義中使用的屬性。位置透明性：應(yīng)用程序員必須要知道分片情形，并將給出明確的處理。這是一種非常簡單的更新應(yīng)用，最后四個語句可以任何次序或并行執(zhí)行。本地映像透明性：應(yīng)用程序員必須明確地處理片段的位置。若為更新應(yīng)用，還必須考慮片段的復(fù)制問題五、 數(shù)據(jù)庫設(shè)計中分片設(shè)計的基本目的是什么？何為水平分片？舉例說明初級分片和導(dǎo)出分片的方法。分片設(shè)計的基本目的是產(chǎn)生一個對全局?jǐn)?shù)據(jù)合適的劃分方案。使用這種方案得到的片段作為分布式數(shù)

6、據(jù)庫中數(shù)據(jù)的分配和存儲單位時，不但能夠減少應(yīng)用中的操作量，而且能夠?qū)τ趹?yīng)用具有最大可能的本地性，即使得各片段位于其使用最多的站點，或者說，使絕大多數(shù)應(yīng)用所使用的數(shù)據(jù)位于該應(yīng)用的原發(fā)站點。但是，不是所有的全局?jǐn)?shù)據(jù)都必須進(jìn)行分片，應(yīng)考慮到有可能一個全局關(guān)系根本不需要分片。特別是，如果分片一個全局關(guān)系所能夠獲得的好處太小，不足以補(bǔ)償因分片造成的開銷，就不必須對該全局關(guān)系進(jìn)行分片。水平分片是對全局關(guān)系執(zhí)行“選擇”操作，把具有相同性質(zhì)的元組進(jìn)行分組，構(gòu)成若干個不相交的子集。水平分片的方法可歸為初級分片和導(dǎo)出分片兩類。初級分片：以關(guān)系自身的屬性性質(zhì)為基礎(chǔ)，執(zhí)行“選擇”操作，將該關(guān)系分片成若干個不相交的片段

7、。例如：S(S#,SNAME,AGE,SEX) DefinefragmentS1asselect*fromswheresex=MDefinefragmentS2asselect*fromswheresex=F導(dǎo)出分片：全局關(guān)系的導(dǎo)出式水平分片不是以其自身的屬性性質(zhì)為基礎(chǔ)，而是從另一個關(guān)系的屬性性質(zhì)或水平片段推導(dǎo)出來的。采用導(dǎo)出分片可使片段與片段之間的“連接”變得更容易。例如：設(shè)全局關(guān)系SC(S#,C#,GRADE)S(S#,SNAME,AGE,SEX)若要將SC劃分為男生的各門課成績和女生的各門課成績。這就不可能從SC本身的屬性性質(zhì)來執(zhí)行選擇，必須從關(guān)系S的屬性性質(zhì)或水平片段來導(dǎo)出。defin

8、efragmentSC1asselectSCS#，C#，GRADEfromSC，SwhereSCS#=S.S#andSEX=MdefinefragmentSC2asselectSC.S#，C#，GRADEfromSC，SwhereSC.S#=S.S#andSEX=F如果S已經(jīng)進(jìn)行水平分片，分為SF、和SM，分別為男生全體和女生全體，則上述的片段定義可以基于片段SF和SM導(dǎo)出：definefragmentSC1asselect*fromSCwhereS#in(selectSF.S#fromSF) definefragmentSC2asSelect*fromSCwhereS#in(selectSM

9、.S#fromSM)六、 水平分片正確性原則的三個條件是什么？請說明它們的意義。1)完整性條件。各片段定義中的限定語集合必須是完整的，即至少是它們允許值的集合。例如：SEX=M,F季節(jié)=春，夏，秋，冬2)可重構(gòu)條件。如果限定語集合是完整的，則通過并操作總能重構(gòu)全局關(guān)系。3)不相交條件。如果限定語之間是互斥的，它們的片段必不相交。其意義是確定一組合適的不相交的，完整的限定語。七、 數(shù)據(jù)庫的片段位置分配設(shè)計中，何為冗余分配？請簡述其兩種設(shè)計方法。在確定數(shù)據(jù)片段的位置分配時，冗余分配即要每個片段映射到一個或多個站點上。冗余分配的設(shè)計較為復(fù)雜，使用冗余分配，設(shè)計者必須決定每一片段復(fù)制的程度。復(fù)制的利益

10、隨著檢索與更新間的比值而增加，因為數(shù)據(jù)維護(hù)的一致性需要將更新傳播到所有副本。然而，系統(tǒng)可以允許臨時不一致性，在這種情況下，復(fù)制變得更加有用。此外，復(fù)制增加了從故障中恢復(fù)的能力，這是因為同一數(shù)據(jù)的幾個副本不大可能同時全部丟失或破壞，而且當(dāng)某一故障損壞被經(jīng)常訪問的一些副本時，應(yīng)用可以訪問其他的副本。冗余分配的兩種設(shè)計方法：1)“所有得益站點”法：首先確定非復(fù)制問題的解，然后在全部站點中確定一組站點，給這組中的每一站點分配片段的一個副本，這樣做所得到的好處要比為此而付出的費用合算。2)“附加復(fù)制”法：首先確定非復(fù)制的問題的解，然后從最有益處起逐步附加復(fù)制的副本，此過程直到“附加復(fù)制”已無明顯好處時結(jié)

11、束。這種方法是典型的啟迪式方法。采用這種方法考慮到隨著冗余度的增加得益逐漸減少。一般，當(dāng)一個片段只有兩三個副本時，系統(tǒng)的得益在增加；但當(dāng)副本數(shù)再增加時，系統(tǒng)的得益就不再明顯增加。八、 舉例說明數(shù)據(jù)片段分配的費用和得益估算方法。 九、 請分析分布式查詢策略優(yōu)化的重要性（參照例3.1舉例說明）。為了實現(xiàn)這一查詢，可以有六種可能的查詢策略，如下所示： 估算結(jié)果列如下表所示十、考慮教學(xué)數(shù)據(jù)庫中的全局關(guān)系S（s#，sname，age，sex）和SC（s#，c#，grade）被水平分片。S的分片限定語為：sex=“M”和sex=“F”，SC的分片限定語為：c#20。若有查詢問題：“查找至少有一門課程的成績

12、在90分以上的男學(xué)生姓名”，它的關(guān)系代數(shù)表達(dá)式為：sname（sex=”M”grade90（S.s#=SC.s#（SSC）請給出它的查詢樹。按等價變換準(zhǔn)則進(jìn)行變換，并給出變換的查詢樹。它的查詢樹如下圖a，按等價變換準(zhǔn)則進(jìn)行變換后，得出b,c,d圖。 十一、簡述基于半連接算法的查詢優(yōu)化原理，舉例討論。 答案二：基本原理1.通常有兩次傳輸2.但是傳輸?shù)臄?shù)據(jù)量和傳輸整個關(guān)系相比，要遠(yuǎn)遠(yuǎn)少3.一般有：T半card（R），可減少站點間的數(shù)據(jù)傳輸量5.半連接的損失：傳輸pB(S)=C0+C1*size(B)*val(BS)6.基本原理是在傳到另一個站點做連接前，消除與連接無關(guān)的數(shù)據(jù)，減少做連接操作的數(shù)據(jù)量

13、，從而減小傳輸代價十二、假定站點1上的關(guān)系R和站點2上的關(guān)系S在屬性R.A和S.B上做關(guān)于R.A=S.B的連接操作。請用半連接方法表示該連接操作，畫出相應(yīng)的示意圖，給出代價估算分析。答案：當(dāng)連接操作采用半連接方法表示時，有采用半連接方法表示連接操作示意圖如下圖所示：因傳輸代價可用下式估算：T=C0+C1*X則：十三、假定一個查詢要進(jìn)行關(guān)系R1和R2的連接，R1和R2的數(shù)據(jù)分布如圖所示。設(shè)片段大小為F11=50，F(xiàn)12=50，F(xiàn)21=100，F(xiàn)22=200；數(shù)據(jù)通信代價由C（x）=x給出（即C0=0，C1=1）；每個站點上的本地連接代價由J（x1，x2）=5*（x1+ x2）給出，且每個站點上的

14、并操作代價（x1，x2）=2*（x1+ x2）。請分別計算FT（Q，S1，R1）、FT（Q，S2，R1）、FT（Q，S1，R2）、FT（Q，S2，R2），并據(jù)此，選擇在基于直接連接算法的查詢優(yōu)化中哪一個關(guān)系保持分片狀態(tài)。 站 點S1S2關(guān)系R1F11F12R2F21F22答案：當(dāng)關(guān)系R1保持分片狀態(tài)時，站點S1的完成時間FR(Q,S1,R1)為：FT（Q,S1,R1）=200+2*（100+200）+5*（50+300）=2550，其中200是傳送F22的通信代價，2*（100+200）是F21和F22的并操作代價，5*（50+300）是R2和F11的連接操作代價。同樣地，F(xiàn)T（Q,S2,R1）=100+2*（100+200）+5*（50+300）=2450.因此，查詢的響應(yīng)時間在R1保持分片狀態(tài)時為2550。同樣計算R2保持分片狀態(tài)時得到FT（Q,S1,R2）=50+2*（50+50）+5*（100+100）=1250FT（Q,S1,R2）=50+2*（50+50）+5*（100+200）=1750因此，在R2保持分片狀態(tài)時，查詢的響應(yīng)時間1750。由于R1保持分片狀態(tài)時