分布式數(shù)據(jù)庫習(xí)題

1、分布式數(shù)據(jù)庫習(xí)題 第一章 1.1請用自己的語言定義下列分布式數(shù)據(jù)庫系統(tǒng)中的術(shù)語： 全局/局部數(shù)據(jù) 全局?jǐn)?shù)據(jù)是指參與全局應(yīng)用，可被多個站點上的應(yīng)用訪問的數(shù)據(jù)； 局部數(shù)據(jù)是指只提供本站點的局部應(yīng)用所需要的數(shù)據(jù)。 全局/局部用戶（應(yīng)用） 在分布式數(shù)據(jù)庫系統(tǒng)中，一個用戶或一個應(yīng)用如果只訪問他注冊的那個站點上的數(shù)據(jù)稱為局 部用戶 （應(yīng)用）。 如果訪問涉及兩個或兩個以上站點中的數(shù)據(jù)，稱為全局用戶（應(yīng)用） 。 全局/局部DBMS 全局?jǐn)?shù)據(jù)庫系統(tǒng)是協(xié)調(diào)全局事務(wù)的，協(xié)調(diào)各局部 DBMSA完成全局應(yīng)用，保證數(shù)據(jù)庫的 全局一致性，執(zhí)行并發(fā)控制，實現(xiàn)更新同步，提供全局恢復(fù)功能的數(shù)據(jù)庫管理系統(tǒng)。 局部數(shù)據(jù)庫管理系統(tǒng)位于

2、局部場地上，是為建立和管理局部數(shù)據(jù)庫，提供場地自治能 力，執(zhí)行局部應(yīng)用及全局查詢的子查詢的數(shù)據(jù)庫管理系統(tǒng)。 全局/局部DB 全局?jǐn)?shù)據(jù)庫（GDB是指從整個系統(tǒng)角度出發(fā)，由全局?jǐn)?shù)據(jù)庫管理系統(tǒng)進(jìn)行管理的數(shù)據(jù)庫， 它由各個局部數(shù)據(jù)庫邏輯組合而成； 局部數(shù)據(jù)庫（LDB是指從各個站點的角度出發(fā)，由局部數(shù)據(jù)庫管理系統(tǒng)進(jìn)行管理的數(shù)據(jù)庫， 它由全局?jǐn)?shù)據(jù)庫的某種邏輯分割而成。 全局外模式 是全局應(yīng)用的用戶視圖，是全局概念模式的子集，也稱全局視圖。 全局概念模式 描述分布式數(shù)據(jù)庫中全局?jǐn)?shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)特性，是分布式數(shù)據(jù)庫的全局概念視圖。 分片模式 描述全局?jǐn)?shù)據(jù)的邏輯劃分。每一個全局關(guān)系可以分為若干不相交的部分，

3、 每一部分稱為一個 片段，分片模式定義片段以及全局關(guān)系到片段的映像。 分配模式 分配模式定義片段的存放結(jié)點。 根據(jù)選定的數(shù)據(jù)分布策略， 定義各片段的物理存放站點， 即 定義片段映像的類型，確定分布式數(shù)據(jù)庫是冗余的還是非冗余的，以及冗余的程度。 局部概念模式 是全局概念模式的子集，對每個站點來說，在該站點上全部物理映像的集合就稱為該站點上 的局部概念模式。 1.2采用分布式數(shù)據(jù)庫系統(tǒng)的主要原因是什么？ 分布式數(shù)據(jù)庫系統(tǒng)適合于單位分散的部門， 允許各個部門將其常用的數(shù)據(jù)存儲在本地， 實施 就地存放本地使用，從而提高響應(yīng)速度，降低通信費用。采用分布式數(shù)據(jù)庫的原因主要有兩 方面：(1)集中式數(shù)據(jù)庫系統(tǒng)

4、的不足：數(shù)據(jù)按實際需要已經(jīng)在網(wǎng)絡(luò)上分布存儲，如果再采用 集中式處理，勢必造成附加成本和通信開銷； 應(yīng)用程序集中在一臺計算機上運行， 一旦該計 算機發(fā)生故障，將會影響整個系統(tǒng)的運行，可靠性不高；集中式處理導(dǎo)致系統(tǒng)的規(guī)模和配置 都不夠靈活，系統(tǒng)的可擴展性較差。 (2)分布式數(shù)據(jù)庫系統(tǒng)的優(yōu)點：具有靈活的體系結(jié)構(gòu)； 適應(yīng)分布式的管理和控制機構(gòu)； 經(jīng)濟性能優(yōu)越；系統(tǒng)的可靠性高、 可用性好；局部應(yīng)用的響 應(yīng)速度快；可擴展性好，易于集成現(xiàn)有系統(tǒng)。 1.3分布式數(shù)據(jù)庫系統(tǒng)可分為那些類？ (1) 按局部數(shù)據(jù)庫數(shù)據(jù)管理系統(tǒng)的數(shù)據(jù)模型分類： 同構(gòu)型DDBS (包括兩種：同構(gòu)同質(zhì)型。同構(gòu)異質(zhì)型) ，異構(gòu)型DDBS (

5、2) 按分布式數(shù)據(jù)庫系統(tǒng)的全局控制系統(tǒng)類型分類： 全局控制集中型 DDBS全局控制分散型 DDBS全局控制可變型 DDBS 1.5分布式DBMS具有哪些集中式 DBMS不具備的功能？ (1) 物理分布性：分布式數(shù)據(jù)庫中的數(shù)據(jù)不是存儲在一個站點上，而是分散存儲在由計 算機網(wǎng)絡(luò)聯(lián)結(jié)起來的多個站點上。 (2) 邏輯整體性：分布式數(shù)據(jù)庫中的數(shù)據(jù)物理上是分散在各個站點中的，但這些分散的 數(shù)據(jù)邏輯上卻是一個整體。 (3) 站點自治性：站點自治性也稱場地自治性， 各站點上的數(shù)據(jù)由本地的 DBM翦理，具 有資質(zhì)處理能力，完成本站點的應(yīng)用(本地應(yīng)用) 。 (4) 集中與自治相結(jié)合的控制機制：同一站點上的用戶可共

6、享本站點上局部數(shù)據(jù)庫中的 數(shù)據(jù)，以完成局部應(yīng)用；分布式數(shù)據(jù)庫系統(tǒng)上的用戶都可共享在分布式數(shù)據(jù)庫系統(tǒng) 的各個站點上存儲的數(shù)據(jù)，以完成全局應(yīng)用。 (5) 適當(dāng)增加數(shù)據(jù)冗余度：在集中式數(shù)據(jù)庫中，盡量減少冗余度是系統(tǒng)目標(biāo)之一。而在 分布式系統(tǒng)中卻通過冗余數(shù)據(jù)提高系統(tǒng)的可靠性、可用性和改善系統(tǒng)性能。 (6) 事務(wù)管理的分布性：數(shù)據(jù)的分布性必然造成事務(wù)執(zhí)行和管理的分布性。即，一個全 局事務(wù)的執(zhí)行可分解為在若干個站點上子事務(wù)(局部事務(wù))的執(zhí)行。 1.6請用自己的語言解析“什么時候需要進(jìn)行數(shù)據(jù)分片和數(shù)據(jù)復(fù)制” 。 數(shù)據(jù)分片：全局?jǐn)?shù)據(jù)庫是由各個局部數(shù)據(jù)庫邏輯組合而成， 數(shù)據(jù)庫中的一個關(guān)系描述了某些 數(shù)據(jù)之間的邏

7、輯相關(guān)性， 但不同站點的用戶需要該關(guān)系中的元組可能不同。 這就需要對這個 關(guān)系進(jìn)行分割，并將分割后的片段存放在相應(yīng)的站點上。 數(shù)據(jù)復(fù)制：當(dāng)一個分布式數(shù)據(jù)庫中用戶數(shù)量較大， 地理分布較廣，而且需要實時地訪問相同 數(shù)據(jù)時可以采用數(shù)據(jù)復(fù)制技術(shù)，它通過將這些共享數(shù)據(jù)復(fù)制到位于不同地點的多個數(shù)據(jù)庫 中，從而實現(xiàn)數(shù)據(jù)的本地訪問， 減少了網(wǎng)絡(luò)符合，并提高了數(shù)據(jù)訪問的性能，而且通過對數(shù) 據(jù)庫中的數(shù)據(jù)定期同步的更新，從而確保了所有的用戶使用同樣的、最新的數(shù)據(jù)。 1.7在分布式數(shù)據(jù)庫系統(tǒng)中，為什么要對數(shù)據(jù)進(jìn)行分片？什么是關(guān)系的片段？關(guān)系的片段有 哪些主要類型？ 對數(shù)據(jù)分片的目的是產(chǎn)生一個對全局?jǐn)?shù)據(jù)合適的劃分方案，

8、 使用這種方案得到的片段作為分 布式數(shù)據(jù)庫中數(shù)據(jù)的分配和存儲單位時， 不但能夠減少應(yīng)用中的操作量，而且能夠?qū)τ趹?yīng)用 具有最大可能的本地性，即使得各片段位于其使用最多的站點。 關(guān)系的片段：對數(shù)據(jù)庫管理系統(tǒng)中的關(guān)系進(jìn)行分割， 將分割后得到的各部分元組， 就稱為該 關(guān)系的邏輯片段。 關(guān)系的片段主要類型有： (1)水平片段：按一定的條件把全局關(guān)系的所有元組劃分成若干不相交的子集，每個子集 為關(guān)系的一個片段。也是通過對一全局對象的實例(或元組)進(jìn)行選擇得到的子集構(gòu)。 (2) 垂直片段：把一個全局關(guān)系的屬性集分成若干子集，并在這些子集上做投影運算，每 個投影為垂直分片。也是通過將全局對象在其屬性子集上進(jìn)行

9、投影得到的。 (3) 混合分片：將水平分片與垂直分片方式綜合使用則為混合分片。第二章 2.1概述分布式數(shù)據(jù)庫系統(tǒng)的創(chuàng)建方法、方法特點和適用范圍。 分布式數(shù)據(jù)庫系統(tǒng)的創(chuàng)建方法即分布式數(shù)據(jù)庫系統(tǒng)的實現(xiàn)方法， 大致可分為兩種：組合 法和重構(gòu)法。 (1) 采用組合法創(chuàng)建分布式數(shù)據(jù)庫系統(tǒng) 組合法也稱集成法，這是一種自底向上(bottom up)的創(chuàng)建方法。它是利用現(xiàn)有的計算機網(wǎng) 絡(luò)和獨立存在于各個站點上的現(xiàn)存數(shù)據(jù)庫系統(tǒng)， 通過建立一個分布式協(xié)調(diào)管理系統(tǒng)， 將它們 集成為一個統(tǒng)一的分布式數(shù)據(jù)庫系統(tǒng)。 特點：這種方法由于是利用現(xiàn)存的網(wǎng)絡(luò)和現(xiàn)存的數(shù)據(jù)庫系統(tǒng)， 僅僅需要建立一個分布式協(xié)調(diào) 管理系統(tǒng)。因此，相對來

10、說，如果該系統(tǒng)不是很大的話，其工作量可能會比較小，實現(xiàn)的周 期會短些，花費的人力、物力會少些，用戶也比較容易接受，因為它有利于保護現(xiàn)有的投資。 適用范圍：采用組合法的分布式數(shù)據(jù)庫系統(tǒng)往往是異構(gòu)或同構(gòu)異質(zhì)的分布式數(shù)據(jù)庫系統(tǒng)。 (2) 采用重構(gòu)法創(chuàng)建分布式數(shù)據(jù)庫系統(tǒng) 重構(gòu)法是根據(jù)系統(tǒng)的實現(xiàn)環(huán)境和用戶需求， 按分布式數(shù)據(jù)庫系統(tǒng)的設(shè)計思想和方法， 采用統(tǒng) 一的觀點，從總體設(shè)計做起，包括各站點上的數(shù)據(jù)庫系統(tǒng)，重新建立一個分布式數(shù)據(jù)庫系統(tǒng)。 特點：這種方法的優(yōu)點在于，可以按照統(tǒng)一的思想來考慮分布式數(shù)據(jù)庫系統(tǒng)中的各種問題， 有效地解決分布式數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)一致性、 完整性和可靠性。但是花費的人力、物力會比

11、較多，研制周期也比較長，系統(tǒng)建設(shè)的代價會比較大。在實際應(yīng)用中， 究竟應(yīng)該采用哪種方 法，要根據(jù)具體情況做具體分析后決定。 適用范圍：采用重構(gòu)法創(chuàng)建的分布式數(shù)據(jù)庫系統(tǒng)， 通常是同構(gòu)異質(zhì)，甚至是同構(gòu)同質(zhì)的分布 式數(shù)據(jù)庫系統(tǒng)。 2.2分布式數(shù)據(jù)庫設(shè)計的主要目標(biāo)是什么？ 分布式數(shù)據(jù)庫設(shè)計的目標(biāo)除包括集中式數(shù)據(jù)庫設(shè)計中的目標(biāo)外，還要包括以下幾點： (1)分布式數(shù)據(jù)庫的本地性或近地性 分布式數(shù)據(jù)庫系統(tǒng)中最重要的目標(biāo) (至少在使用廣域網(wǎng)的情況下，以及某些使用局域網(wǎng) 的情況下)是盡量減少對網(wǎng)絡(luò)的利用，即盡可能減少站點之間的通信次數(shù)和通信量。所以, 分布式數(shù)據(jù)庫設(shè)計中的一個主要原則是使數(shù)據(jù)和應(yīng)用實現(xiàn)最大程度的本

12、地性。 本地性的優(yōu)點 不僅僅減少了遠(yuǎn)程訪問的次數(shù)，而且簡化了對該應(yīng)用執(zhí)行的控制。 (2) 控制數(shù)據(jù)的適當(dāng)冗余 控制數(shù)據(jù)的適當(dāng)冗余是分布式數(shù)據(jù)庫系統(tǒng)設(shè)計的又一個目標(biāo)。 分布式系統(tǒng)在可用性和可 靠性方面優(yōu)于非分布式系統(tǒng)，其原因之一是因為分布式數(shù)據(jù)庫系統(tǒng)中存在數(shù)據(jù)的適當(dāng)冗余。 (3) 工作負(fù)荷分布 分布式計算機系統(tǒng)的一個重要特征是把工作負(fù)荷分布在網(wǎng)絡(luò)中的各個站點上。 分布工作 負(fù)荷的目的是充分利用每個站點計算機的能力和資源， 以提高應(yīng)用執(zhí)行的平行程度， 從而提 高系統(tǒng)的性能。 (4) 存儲的能力和費用 數(shù)據(jù)庫的分布會受到各站點的存儲能力的影響。 在網(wǎng)絡(luò)中可以有專門用于存儲數(shù)據(jù)的站 點，也可以有完全不

13、支持大容量存儲的站點。 上述的設(shè)計目標(biāo)都要達(dá)到是非常困難的， 因為這會使優(yōu)化模型變得非常復(fù)雜。 因此，可 以將上面的某些特征考慮為約束條件而不是目標(biāo)。 2.3概述分布式數(shù)據(jù)庫設(shè)計的關(guān)鍵問題及其解決方法。 作為數(shù)據(jù)庫系統(tǒng)設(shè)計的核心部分是數(shù)據(jù)庫設(shè)計，數(shù)據(jù)庫設(shè)計的主要問題是模式 (也稱概 念模式，描述數(shù)據(jù)庫應(yīng)用所使用的全部數(shù)據(jù) )和內(nèi)模式(也稱物理模式，描述概念模式映射到 存儲區(qū)域，并確定合適的存取方法 )的設(shè)計。這兩個問題在分布式數(shù)據(jù)庫中變?yōu)槿帜Ｊ皆O(shè) 計和每個站點的局部數(shù)據(jù)庫設(shè)計的問題， 其中的關(guān)鍵是數(shù)據(jù)庫的全局模式應(yīng)如何劃分： 并映 射到合適站點上。這就產(chǎn)生了分布數(shù)據(jù)庫設(shè)計所特有的兩個新問題：

14、 數(shù)據(jù)的分片設(shè)計和片段 的位置分配設(shè)計。 分布式數(shù)據(jù)庫的分布設(shè)計要求確定數(shù)據(jù)的分片和片段的分配。分片是指把一全局對象 (實體或關(guān)系)細(xì)分成若干邏輯片段的過程；分配是指把各片段映射到一個或多個站點的過 程，片段是最合適的數(shù)據(jù)分配單位。 2.6數(shù)據(jù)分片應(yīng)遵守哪些基本原則？數(shù)據(jù)分片有哪些基本類型和方法？ 分片方法，必須遵守如下規(guī)則： 若 R=R1, R2, , , Rn滿足： 1) 完整性(completeness) 條件： 如果 a R,則必有 a Ri , i=l , 2, 2)可重構(gòu)(reconstructed)條件： R= U Ri ,(水平分片 )或R* Ri，(垂直分片) 3) 不相交(

15、disjoint) 條件： Ri n Rj= (j) , i 豐 j , i , j : =1, 2, , , n(水平分片) Ri n Rj=主鍵屬性， i , j=1 , 2, , , n(垂直分片) 有兩種基本的數(shù)據(jù)分片方法： (1) 使用水平分片方法得到水平片段，水平片段是通過對一全局對象的實例 (或元組) 進(jìn)行選擇得到的子集構(gòu)成。 水平分片是對全局關(guān)系執(zhí)行“選擇” 操作，把具有相同性質(zhì)的元組進(jìn)行分組， 構(gòu)成若干 個不相交的子集。水平分片的方法可歸為初級分片 (primary fragmentation) 和導(dǎo)出分片 (derivation fragmentation) 兩類。 (2)

16、 使用垂直分片方法得到垂直片段，垂直片段是通過將全局對象在其屬性子集上進(jìn) 行投影得到的。 一個全局關(guān)系的垂直分片是通過“投影”操作把它的屬性分成若干組。確定一全局關(guān)系 R的垂直分片需要根據(jù)應(yīng)用以“同樣方式” (例如具有相同的使用頻率)訪問的屬性來進(jìn)行分 組。這里把垂直分片問題和垂直群集 (vettical clustering) 問題區(qū)分開來，垂直分片的組 必須只焦基個鍵屬性上重疊，其他屬性不可重疊，而垂直群集的組在其他屬性上也可以重疊。 通過交替水平分片與垂直分片，可以產(chǎn)生混合分片。 2.7為什么說在關(guān)系型分布式數(shù)據(jù)庫中使用導(dǎo)出式水平分片，使關(guān)系之間的連接變得更加容 易？試舉一例。 全局關(guān)系

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

18、e fragment SC2 as select SC.S# , C#, SCORE from SC, S where SC.S#=S.S# and SEX= F 如果S已經(jīng)進(jìn)行水平分片，分為 SF、和SM分別為男生全體和女生全體，則上述的片 段定義可以基于片段 SF和SM導(dǎo)出： define fragment SC 1 as select*from SC where S# in(select SF.S# from SF) define fragment SC2 as Select * from SC where S# in(select SM.S# from SM) 由此可見，使用導(dǎo)出式水平

19、分片， 使關(guān)系之間的連接變得更加容易。 這是因為可將連接 條件代之以子查詢，從而使它變?yōu)橐话愕呐袆e條件。 2.8采用DATAID-D方法的分布式數(shù)據(jù)庫設(shè)計與傳統(tǒng)的集中式數(shù)據(jù)庫設(shè)計在步驟和內(nèi)容上有 什么不同？ DATAID D是作為集中式數(shù)據(jù)庫設(shè)計 DATAID 一 1方法論的擴充而構(gòu)造的， 后者分成 四個階段：需求分析、概念設(shè)計、邏輯設(shè)計和物理設(shè)計。 DATAID D要求對其增加兩個階 段：分布要求分析階段和分布設(shè)計階段 1) 分布要求分析階段：需要這一階段是為了收集關(guān)于分布的信息， 如水平分片的劃分謂 詞，每一應(yīng)用在各站點激活的頻率等。 為了收集關(guān)于數(shù)據(jù)和應(yīng)用分布的信息， 必須從概念設(shè) 計階

20、段的某些結(jié)果出發(fā)來收集關(guān)于分布要求。 因此，分布要求分析階段將位于概念設(shè)計階段 之后。 2) 分布設(shè)計階段：這一階段始于全局?jǐn)?shù)據(jù)庫模式的規(guī)格說明和所收集的分布要求， 然后 產(chǎn)生全局?jǐn)?shù)據(jù)的分片模式和片段的位置分配模式， 分配模式描述了分配在各站點上的數(shù)據(jù)情 況。 2.9考慮圖2.12所示的公司數(shù)據(jù)庫的分片和分布。 假設(shè)該公司有三個計算機站點， 站點B和 C分別屬于部門2和3.現(xiàn)在希望在站點 B和C上分別頻繁訪問 EMPLOYEE和PROJECT表 中有關(guān)工作在該部門的雇員和該部門管轄的項目信息。 雇員信息主要是指 EMPLOYEE表的 NAME , ESSN, SALARY和SUPERSSN屬性

21、。站點 A供公司總部（部門 1）使用，經(jīng)常存 取為保險目的而記錄的 DEPENDENT信息外，還定期地存取所有雇員和項目的信息。根據(jù) 這些給出的要求，對 COMPANY關(guān)系數(shù)據(jù)庫中關(guān)系進(jìn)行分片和分布。 EMPLOYEE FNAME MINIT LNAME ESSN BDATE ADDRESS SEX SALARY SUPERSSN DNO DEPARTMENT DNAME DNO MGRSSN MGRSTARTDATE DEPT_LOCATION DNO DLOCATION PROJECT PNAME PNUMER PLOCATION DNO WORKS_ON ESSN PNO HOURS D

22、EPENDENT ESSN DEPENDENT NAME _ SEX BDATE RELATIONSHIP 圖 2.12 COMPANY 關(guān)系數(shù)據(jù)庫模式的一個可能的關(guān)系數(shù)據(jù)庫狀態(tài)（主碼用下標(biāo)線標(biāo)出） 解：根據(jù)給出的要求，圖 2.12中的整個數(shù)據(jù)庫可以被存儲在站點 A。為了確定將要復(fù)制到 站點2和3上的片段，先根據(jù) DEPARTMENT的主碼DNO勺值進(jìn)行水平分片，然后基于外碼 部門號（DNON務(wù)導(dǎo)出的片段應(yīng)用到關(guān)系 EMPLOYEEPROJEC下日DEPT_LOCATIONS,再在剛才 得到的EMPLOYEE段上進(jìn)行垂直分片，得到只含屬性 NAME, ESSN, SALARY* SUPERSS

23、N DNO）勺片段。圖2. 13給出了 EMPD寒日EMPD3勺混合分片，它包括了分別滿足條件 DN0 = 2 和 DN0 = 3 的 EMPLOYEE組。類似地， PROJECT,DEPARTMENTDEPT- LOCATIONS按部門 編號進(jìn)行水平分片，這些片段根據(jù)其相應(yīng)的部門號分別存儲在站點 B和C上，如下圖所示。 EMPD5 FNAME MINIT LNAME ESSN SALARY SUPERSSN DNO John B Simth 123456789 20000 333445555 2 Franisa T Wong 333445555 10000 888665555 2 Remin

24、ia K Naraya 666884444 15000 333445555 2 Joyee A English 453453453 20000 333445555 2 DEP5 DName DNO MGRSSN MGRSTARTDATE Research 2 333445555 2003-05-22 DEP5_LOC5 DNO LOCATION 2 Bellaire 2 Sugarlnd 2 Housten PROJS55 PNAME PNUMBER PLOCAION DNO Product X 1 Bellaire 2 Product Y 2 Sugarlnd 2 Product Z 3 H

25、ousten 2 DEP5_LOCS ESSN PNO HOURS 123456789 1 32.5 123456789 2 7.5 666884444 3 40.0 453453453 1 20.0 453453453 2 20.0 333445555 2 10.0 333445555 3 10.0 333445555 10 10.0 333445555 20 10.0 a）站點B上的對應(yīng)部門2的關(guān)系片段 現(xiàn)在需要對WORKS_ON系進(jìn)行分片，并且確定哪些WORKS_ON段要存儲在站點 B和C 上口這時面臨這樣一個問題， WORKS_ON的屬性沒有一個可以直接指明每個元組所屬的部 門。實標(biāo)上

26、 WORKS_ON的每個元組與雇員 e和項日P相聯(lián)系。我們既可以以 e工作的部門 也可以以管轄P的部門d來分片WORKS_ON。如果對表 WORKS_ON所有元組增加一個 d_d 的限制，分片就會變得更加容易，即雇員只能為那些他所在部門管轄的項目工作。 然而，在 圖2. 12中的數(shù)據(jù)庫沒有給出這樣的限制。所以，對此可以先以雇員工作的部門 表述）來分片WORKS_ON后進(jìn)一步以管轄雇員工作項目的部門來分片，如下圖所示。 EMPD4 FNAME MINIT LNAME SSN SALARY SUPERSSN DNO Ahcia J Zelaya 999887777 25000 987654321

27、4 Jennifer S Wallace 987654321 43000 888665555 4 Ahmad V Jabbar 999887777 25000 987654321 4 EMPD4 FNAME MINIT LNAME ESSN SALARY SUPERSSN DNO John B Simth 123456789 20000 333445555 2 Franisa T Wong 333445555 10000 888665555 2 Reminia K Naraya 666884444 15000 333445555 2 Joyee A English 453453453 2000

28、0 333445555 2 DEP4 DName DNUMBER MGRSSN MGRSTARTDATE Administr 4 987654321 2003-01-01 DEP4_LOCS DNUMBER LOCATION 4 Statland DEP4_LOCS ESSN PNO HOURS 333445555 10 10.0 999887777 30 30.0 999887777 10 10.0 987987987 10 35.0 987987987 30 5.0 987654321 30 20.0 987654321 20 15.0 （用條件C PROJS55 PNAME PNUMBE

29、R PLOCAION DNO Computer 10 Statland 4 Newbener 30 Statland 4 b）站點B上的對應(yīng)部門4的關(guān)系片段 在上圖中，片段G1,G2和G3的并集給出了為部門 2工作的雇員的所有 WORKS_ONta。 同樣地，片段G4,G5和G6的并集給出了為部門 3的雇員的所有 WORKS_ON組。另一方面， 片段GI !LII和G7的并集給出了被部門 2管轄的項目的所有 WORKS_ON組。因此，可以 把片段G1,G2,G3,G4和G的并集放到站點 B上，把片段 G5,G5,G6,G2和G8的并集放在站點 C上，可以看到片段 G2和G4在兩個站點上均被復(fù)制

30、。 這就清楚地論證了對于大型數(shù)據(jù)庫而言，數(shù)據(jù)的分片和分配是一個多么復(fù)雜的問題。第三章 3.3概述基于關(guān)系代數(shù)等價變換的查詢優(yōu)化算法的基本原理和實現(xiàn)步驟。 基本原理：把查詢問題轉(zhuǎn)變?yōu)殛P(guān)系代數(shù)表達(dá)式 ，分析得到查詢樹（語法樹），進(jìn)行從全局到片段 的變換得到基于片段的查詢樹，然后利用關(guān)系代數(shù)變換規(guī)則的優(yōu)化算法，盡可能先執(zhí)行選擇和 投影操作.這樣，一方面可以減少其后操作的操作量，另一方面可以減少操作次數(shù) .對該查詢樹 進(jìn)行優(yōu)化，從而達(dá)到查詢優(yōu)化的目的. 實現(xiàn)步驟： 1、 將一個查詢問題轉(zhuǎn)換成關(guān)系代數(shù)表達(dá)式 2、 從關(guān)系代數(shù)表達(dá)式到查詢樹的變換：對一個關(guān)系代數(shù)表達(dá)式進(jìn)行語法分析，可以得 到一顆語法書，即

31、樹的葉子是已知的關(guān)系（或片段） 、樹的結(jié)點是關(guān)系操作符、節(jié) 點是按代數(shù)表達(dá)式中的操作順序組成的一組關(guān)系操作符。 3、 從全局查詢到片段查詢的變換：在具有分片透明性的系統(tǒng)中，這個變換的典型方法 是：把基于全局關(guān)系的查詢樹中的全局關(guān)系名用其重構(gòu)該全局關(guān)系的各片段名替 換，變換成相應(yīng)在片段上的查詢樹。 4、 利用關(guān)系代數(shù)等價變換規(guī)則的優(yōu)化算法，對片段上的查詢樹進(jìn)行優(yōu)化處理，最后達(dá) 到優(yōu)化查詢的目的。 3.4概述基于半連接算法查詢優(yōu)化的基本原理和使用情形。 原理：經(jīng)半連接操作，可減少操作關(guān)系的數(shù)據(jù)量，從而減少站點間數(shù)據(jù)的傳輸量。 適用情況：如果只需要一個關(guān)系中的一小部分元組參與和另一個關(guān)系連接的話，

32、這是一 個使數(shù)據(jù)傳輸量最小化的非常有效的方案。此時， T半T全，采用半連接方案是合適的。 3.5概述基于直接連接算法查詢優(yōu)化的基本原理和適用情形。 基本原理：基于直接連接算法的查詢優(yōu)化處理中的站點依賴算法、 分片和復(fù)制算法。站點依 賴和數(shù)據(jù)復(fù)制算法，以及 Hash劃分算法，主要是使得連接操作的數(shù)據(jù)傳送量?。ㄗ詈檬菬o 數(shù)據(jù)傳送）和負(fù)載均衡，從而達(dá)到優(yōu)化的目的。 使用情形：直接連接查詢優(yōu)化的算法有四種， 通過比較，站點依賴算法的數(shù)據(jù)傳送量最小 （實 際上沒有），連接數(shù)據(jù)量最小切利用索引，因而能獲得最佳性能。其次是 Hash劃分算法， 最后是片段和復(fù)制算法。盡管如此，站點依賴算法只有在給出適當(dāng)?shù)目捎?/p>

33、語義信息時才使用； Hash劃分算法要求相對均勻的數(shù)據(jù)分布來得到良好的性能，最壞的情況下，兩個關(guān)系可能 被映射到同一個站點， 而達(dá)不到負(fù)載均衡；在某個關(guān)系已經(jīng)復(fù)制在包含其他關(guān)系片段的站點 中，可在本地立即進(jìn)行無數(shù)據(jù)傳送處理，這種場合下使用分片和復(fù)制算法要好于 Hash劃分 算法。在高速的局域網(wǎng)中，本地處理的代價也必須考慮在內(nèi)， 那么使用全連接是比較合適的。 此時，查詢優(yōu)化策略就是去確定選擇執(zhí)行全連接的最佳方法。 3.6設(shè)有關(guān)系R, S, T如圖3.13所示。 (1) 計算連接R8S8To Rx S, S8 R, S8T, R, T工 S, R工T 圖 3-13 (1) R8 g T A B C

34、 D E I 2 3 5 6 6 9 1 6 8 3 8 9 5 3 5 6 6 9 2 6 8 3 8 9 (2) R S (2)計算半連接 A B C 2 3 5 5 3 6 1 6 8 3 4 6 5 3 5 2 6 8 B C D 3 5 6 3 5 9 6 8 3 5 9 6 4 1 6 5 8 4 D E I 6 6 9 8 7 8 8 5 6 3 8 9 A B C 2 3 5 1 6 8 5 3 5 2 6 8 S8 R B C D 3 5 6 3 5 9 6 8 3 S T B C D 3 5 6 6 8 3 5 9 6 4 1 6 T R為空 F T為空 Ts S D E

35、I 6 6 9 3 8 9 3.7如果習(xí)題3.6中的三個關(guān)系 R, S, T分別位于三個不同的站點 X, Y, Z。若采用基于半 連接算法計算連接 R8S8T,請選擇使得傳輸代價最少的連接執(zhí)行的站點和確定半連接序 列。 假設(shè)每個屬性域長度均為 1B,考慮所有的半連接 萬案 半連接 P 得益 費用 傳送屬性 P1 R 00 S 2/3 1/3*3*6 2*5 S.B S.C P2 S00 R 1/2 1/2*3*6 2*4 R.B R.C P3 Soo T 2/3 1/3*3*6 1*3 T.D P4 T 00 S 1/2 1/2*3*6 1*4 S.D 1、選擇得益高于P2進(jìn)行優(yōu)化，得到新的R

36、,S,T,并對受到影響的方案重新計算得意和費用。 新的R,S,T如下： P S TP 對受到影響的方案重新計算得益和費用 萬案 半連接 P 得益 費用 傳送屬性 P1 R 8 S 2/3 1/3*3*6 2*5 S.B S.C P2 SR - 1/2 1/2*3*6 2*4 -R7BR.C P3 S00 T 2/3 1/3*3*6 1*3 T.D P4 T 00 S 1/2 1/2*3*6 1*4 S .D 2、選擇得益最高的 P4進(jìn)行優(yōu)化，得到新的 R,S,T,并對受到影響的方案重新計算得益和 費用。 新的R,S,T如下: O 3 5e 5P 3P 6矽 IP 6 口 87 4P 6 丁 5

37、Q 3r S 以 5- 6w 8/ 3中 對受到影響的方案重新計算得益和費用 萬案 半連接 P 得益 費用 傳送屬性 P1 R 8 S 2/3 1/3*3*6 2*5 S.B S.C P2 S R H72 - 1/2*3*6 2*4 - R.B R.C P3 S8 T 2/3 1/3*3*6 1*3 T.D P4 T 3 S 1/2 1/236 1 4 S .D 3、依照1或者2的方法得到新的 R,S,T如下： R= S= T 對受到影響的方案進(jìn)行重新計算得益和費用得到: 萬案 半連接 P 得益 費用 傳送屬性 P1 R 8 S 2/3 1/3*3*6 2*5 S.B S .C P2 Soo

38、R 1/2 1/2*3*6 2*4 -R?BRC- P3 S8 T 2/3 1/3*3*6 1*3 T.D P4 1 8 S 1/2 1/2*3*6 T4- S .D 4、選擇得益最高的 P3進(jìn)行優(yōu)化，得到 X , Y , Z站點上最終的R,S,T.X,Y,Z站點上最終 的R,S ,T如下: R=Au O 3 5/ 如 6盧 8P A 4審 3砂 A & 6 8 B- o 8 3# 5肝 6/ * 3- B* C 3P 5口 卻 6P 阱 5P 3/ 5 2 6# 6 D* 6 5# 9 6a 8， 3# T= X站點代價=2*3+2*3=12 Y站點代價=4*3+2*3=18 Z站點

39、代價=4*3+2*3=18 故選X站點作為收集站點代價最低。 由簡化過程得知半連接過程為： 1. S=S R 2. 將S傳送給T,做半連接TS得到T。 3. 將S傳送給R,做半連接FU S得到R. 4. 將T傳送給S,做半連接S - T得到S， 即：(R(SR) 8(S R) (T(SR) 8(T(SR) (1) 在站點Y上作關(guān)系S在R和S公共屬性集B, C上的投影兀B,C(S);把該結(jié)果 送到站點X ; (2) 在站點X上計算半連接，設(shè)其結(jié)果為 R，則R = RS; (3) 在站點Z上作關(guān)系T在S和T公共屬性D上的投影兀D(T);把結(jié)果送到站點 X ; (4) 在站點Y上計算半連接，設(shè)其結(jié)果

40、為 S,則S = S T;結(jié)果送到站點 X; (5)在站點X上計算半連接，得到最后結(jié)果所以選擇各站點做連接的代價: 3.8 設(shè)某公司的雇員關(guān)系為 employee(name, address, salary, plant-number),按 plant-number 水平分片這個關(guān)系，每個片段都有兩個副本：一個副本存放在 New York站點，另一個副本 存放在工廠的站點。請為在 Toronto站點提出的下列查詢設(shè)計一個好的處理策略。 (1) 找出Boce廠的所有雇員。 (2) 找出所有雇員的平均工資。 (3) 找出在如下每個站點工資最高的雇員姓名： Toronto, Edmonton , V

41、ancouver, Montreal o (4) 找出該公司中工資最低的雇員姓名。 答：(1)找出Boce廠的所有雇員。 直接從 Boce的employee分段中投影出 employee的name屬性，再將其發(fā)送到 Toronto 站點，呈現(xiàn)給所需用戶。 (2) 找出所有雇員的平均工資。 在New York站點將所有分段數(shù)據(jù)中的 employee的salary相加，取平均值，計算完畢 之后再將該值發(fā)送到 Toronto站點。 (3) 找出在如下每個站點工資最高的雇員姓名： Toronto, Edmonton , Vancouver, Montreal o 對各個站點的各自的工資進(jìn)行降序排列(以

42、 salary的值為標(biāo)準(zhǔn))，選出salary的max 值，對其name屬性做投影，將數(shù)據(jù)發(fā)送到 Toronto站點。 (4) 找出該公司中工資最低的雇員姓名。 各站點中降序排列(salary)，選出各站點的 min (salary)發(fā)送到Toronto站點，再將 各自的salary作比較，對最小值的 employee的name屬性做投影。 (1)找出Boce廠的所有雇員。 答：將New York站點上的副本傳至 Toronto站點 (2) 找出所有雇員的平均工資。 答：在New York站點上球平均工資，傳至 Toronto站點 (3) 找出在如下每個站點工資最高的雇員姓名： Toronto,

43、 Edmonton , Vancouver, Montreal o 答：Toronto, Edmonton, Vancouver, Montreal 求最高工資，傳至 Toronto 匯總。 (4)找出該公司中工資最低的雇員姓名。 答：各站點中降序排列(salary)，選出各站點的 min (salary)發(fā)送到Toronto站點，再 將各自的salary作比較，對最小值的 employee的name屬性做投影。 第四章 4.7請用自己的語言描述兩階段提交的過程。 第一階段：表決階段，目的是形成一個共同的決定。協(xié)調(diào)者向所有參與者發(fā)出“準(zhǔn)備提 交”信息。如果某個參與者準(zhǔn)備提交，就回答“就緒” 信

44、息，否則回答撤銷信息。參與者 在回答之前應(yīng)把有關(guān)信息寫入子自己的日志中。 協(xié)調(diào)者在發(fā)出準(zhǔn)備提交信息前也要把有關(guān)信 息寫入自己的日志中。如果在規(guī)定時間內(nèi)協(xié)調(diào)者收到了所有參與者 “就緒”的信息，則將做 出提交的決定，否則撤銷。 第二階段：執(zhí)行階段，目的是實現(xiàn)這個決定， 協(xié)調(diào)者將有關(guān)決定的信息先寫入日志，然 后把這個決定發(fā)送給所有參與者。 參與者收到命令之后首先往日志中寫入 “收到提交或撤銷” 決定的信息，并向協(xié)調(diào)者發(fā)送“應(yīng)答”消息，最后執(zhí)行有關(guān)決定。協(xié)調(diào)者收到所有參與者的 應(yīng)答消息后，一個事務(wù)的執(zhí)行到此結(jié)束，有關(guān)日志信息可以脫機保存。 4.8為什么說兩階段提交協(xié)議在不丟失運行日志信息的情況下，可從

45、任何故障恢復(fù)？ 因為在執(zhí)行過程中維護了事務(wù)日志，記錄了執(zhí)行恢復(fù)所需要的信息。 4.9在分布式數(shù)據(jù)庫系統(tǒng)中對多副本數(shù)據(jù)的更新通常采用什么方法？快照方法的優(yōu)點和缺點 是什么？ 答：對多副本數(shù)據(jù)更新通常有主文本更新法、移動主文本法和快照方法。 快照方法的優(yōu)點是：可完成復(fù)雜的查詢，而又不阻止更新；不必考慮數(shù)據(jù)的輔文本，只 關(guān)心每一數(shù)據(jù)的主文本和在這些主文本上定義的任意多個快照；避免了某些并發(fā)控制的開 銷，又便于復(fù)雜查詢完成，可提高系統(tǒng)可用性。 快照方法的缺點是：快照為了與主文本保持同步， 不許定時刷新，快照是一個制度關(guān)系, 其中數(shù)據(jù)只能讀而不能寫，對更新操作無效。 第五章 5.2描述分布式事務(wù)的可串行

46、化理論的一些定義：事務(wù)、沖突操作、并發(fā)調(diào)度、串行調(diào)度、 一致性調(diào)度、兩個調(diào)度等價、可串行化調(diào)度。 事務(wù)：在分布式系統(tǒng)中，事務(wù)是一個分布式操作的序列， 被操作的數(shù)據(jù)分布在不同的站點上。 沖突操作：如果兩個操作 P和Q,對同一個數(shù)據(jù) X操作，其中至少有一個是寫操作 W（X） 則P和Q稱為沖突操作。 并發(fā)調(diào)度：并發(fā)事務(wù)的一個調(diào)度簡稱并發(fā)事務(wù)。 串行調(diào)度：若一個調(diào)度 S,其每個事務(wù)的執(zhí)行均有 TiTj，即事務(wù)Ti所有操作都先于事務(wù) Tj操作，每個事務(wù)相繼執(zhí)行，這樣的調(diào)度 S成為串行調(diào)度。 一致性調(diào)度：執(zhí)行一個調(diào)度可以使得數(shù)據(jù)庫從一個一致性狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€一致性狀態(tài)， 則 稱調(diào)度為一致性調(diào)度。 可串行化

47、調(diào)度：如果一個調(diào)度等價于某個串行調(diào)度，則該調(diào)度稱為可串行調(diào)度。 兩個調(diào)度等價：沖突等價以及視圖等價。 5.5什么是兩階段封鎖協(xié)議？它如何保證可串行性？為什么人們經(jīng)常更愿意采用嚴(yán)格兩階段 封鎖和嚴(yán)酷兩階段封鎖？ 兩階段封鎖協(xié)議：一個事務(wù)所有的封鎖操作（讀寫）都在第一個解鎖操作之前，則該 事務(wù)遵守兩階段封鎖協(xié)議。這樣一個事務(wù)被分成兩個階段： 上升階段（成長階段）：只能獲取新鎖，而不能釋放已有的鎖 收縮階段（衰退階段）：只能釋放已有的鎖，而不能獲得新鎖 保守2PL:要求事務(wù)在開始執(zhí)行前就持有所有它要訪問的數(shù)據(jù)項上的鎖。 嚴(yán)格2PL:事務(wù)提交或撤銷之前，絕對不釋放任何一個寫鎖；在事務(wù)結(jié)束時，同時釋放

48、所有的鎖。 嚴(yán)酷2PL:事務(wù)在提交或撤銷之前，不能釋放任何一個鎖。 如何保證可串行性：如果事務(wù)T稍后必須封鎖數(shù)據(jù)項 Y,哪么在它使用完數(shù)據(jù)項 X之后， 獲得數(shù)據(jù)項Y之前，不可以釋放數(shù)據(jù)項 X上的鎖。因此T必須一直持續(xù)有 X的鎖，直到該事 務(wù)需要讀或?qū)懙乃袛?shù)據(jù)項都被他自己封鎖，然后， T才可以釋放X上的鎖。透明合適，即 時T已經(jīng)完成X,另一個要訪問 X的事務(wù)也可能會被強制等待。同樣對于數(shù)據(jù)項 Y,如果T 封鎖了 Y則其他事務(wù)也要等待。因此就保證了可串行性。 為什么人們經(jīng)常更愿意采用嚴(yán)格兩階段封鎖和嚴(yán)酷兩階段鎖 ，因為在嚴(yán)格兩階段封鎖 中事務(wù)T在提交或撤銷之前，絕對的不釋放任何一個排他鎖 ；在事

49、務(wù)結(jié)束時，同時釋放所有 鎖。因此，除非事務(wù)T已經(jīng)提交，否則，任何其他的事務(wù)都不可以讀或?qū)懹墒聞?wù) T所寫的數(shù) 據(jù)項，從而產(chǎn)生了一個對可恢復(fù)性而言的調(diào)度。改變有數(shù)據(jù)處理器所發(fā)出的操作命令不分， 這對于僅當(dāng)操作被提交或撤銷時保證鎖的什加市很必要的。 而在嚴(yán)酷2PL中，事務(wù)T在提交 或撤銷之前，不鞘釋放任何一個鎖，因此比嚴(yán)格兩階段鎖更容易實現(xiàn)。 第六章 6.3概述分布式可靠性協(xié)議的組成以及它們各自的使用范圍。 答：分布式數(shù)據(jù)庫系統(tǒng)的可靠性協(xié)議包括提交協(xié)議、終結(jié)協(xié)議和恢復(fù)協(xié)議 提交協(xié)議：詳細(xì)說明了提交協(xié)議時如何被執(zhí)行的，它保持了分布式事務(wù)的原子性。 終結(jié)協(xié)議：在執(zhí)行一個分布式事物時， 其中一個站點失效了

50、， 我們希望其他站點也停止 該事務(wù)，終結(jié)協(xié)議是用來處理這種情況的。 恢復(fù)協(xié)議：一個站點失效了，終結(jié)協(xié)議確定可未失效站點如何處理該失效事件， 而恢復(fù) 協(xié)議確定失效站點重新啟動后，其進(jìn)程恢復(fù)他的狀態(tài)的過程。 6.4討論兩階段提交協(xié)議的終結(jié)協(xié)議和兩階段提交協(xié)議的恢復(fù)協(xié)議。 答：兩階段提交協(xié)議的終結(jié)協(xié)議：終結(jié)協(xié)議在協(xié)調(diào)者和參與者的定時器超時發(fā)揮作用， 超時發(fā)生在目的站點在期望的時間內(nèi)沒有從發(fā)送站點得到所期望的消息時。 處理超時的方法 依賴于失效發(fā)生的時間和失效的類型。 協(xié)調(diào)者可以再三種狀態(tài)中發(fā)生超時： 等待、提交和撤 銷。在后兩種狀態(tài)發(fā)生超時是按相同的方式處理的，所以只需考慮兩種情況： 等待狀態(tài)發(fā)生超

51、時時，協(xié)調(diào)者正在等待參與者的局部決定。 協(xié)調(diào)者不能單方面提交 事務(wù)，因為不滿足全局提交規(guī)則。然而，他可以決定全局撤銷事務(wù)，此時，他在日 志中寫入撤銷記錄，并向所有參與者發(fā)送“全局撤銷”消息。 在提交狀態(tài)或撤銷狀態(tài)發(fā)生超時時，協(xié)調(diào)者不能確定是否在所有參與者站點上本地 恢復(fù)管理程序都執(zhí)行完提交或撤銷過程。因此。協(xié)調(diào)者重復(fù)發(fā)出“全局提交”命令 或“全局撤銷”，命令給沒有響應(yīng)的站點，并等待確認(rèn)。 兩階段提交協(xié)議的恢復(fù)協(xié)議可分為三種情形： 協(xié)調(diào)者站點失效，參與者站點失效，還有 其他的附加情形。 協(xié)調(diào)者站點失效：1)協(xié)調(diào)者在初始狀態(tài)失效發(fā)生在協(xié)調(diào)者初始化提交過程之前， 因此，它將在恢復(fù)啟動時提交過程。 2)協(xié)調(diào)者在等待狀態(tài)失效時，協(xié)調(diào)者已經(jīng)發(fā) 送了 “準(zhǔn)備”命令，恢復(fù)時，協(xié)調(diào)者將從頭開始啟動提交過程，再次發(fā)送“準(zhǔn)備” 消息。3)協(xié)調(diào)者在提交狀態(tài)或撤銷狀態(tài)失效時，協(xié)調(diào)者可能已經(jīng)把它的決定通知 了參與者，并終結(jié)了事務(wù)。于是在恢復(fù)時如果它已經(jīng)收到所有的確認(rèn)消息，它就不 需要做任何事情。否則，就要啟動終結(jié)協(xié)議。 參與者站點失效：1) 一個參與者在初始狀態(tài)失效，在恢復(fù)時，該參與者應(yīng)該單方 面撤銷事務(wù)。2) 一個參與者在就緒狀態(tài)失效時，協(xié)調(diào)者已經(jīng)收到失效站點在失效 前發(fā)送的肯定性決定，在恢復(fù)時，失效站點的參與者認(rèn)為是在就緒狀態(tài)發(fā)生了超時， 于是啟動終結(jié)協(xié)議來處理該事務(wù)。 3) 一個