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

1、分布式數(shù)據(jù)庫習(xí)題第一章1.1 請用自己的語言定義下列分布式數(shù)據(jù)庫系統(tǒng)中的術(shù)語：全局/局部數(shù)據(jù)全局?jǐn)?shù)據(jù)是指參與全局應(yīng)用，可被多個站點(diǎn)上的應(yīng)用訪問的數(shù)據(jù)；局部數(shù)據(jù)是指只提供本站點(diǎn)的局部應(yīng)用所需要的數(shù)據(jù)。全局/局部用戶（應(yīng)用）在分布式數(shù)據(jù)庫系統(tǒng)中，一個用戶或一個應(yīng)用如果只訪問他注冊的那個站點(diǎn)上的數(shù)據(jù)稱為局部用戶（應(yīng)用）。如果訪問涉及兩個或兩個以上站點(diǎn)中的數(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ā)控制，實(shí)現(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）是指從各個站點(diǎn)的角度出發(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)系可以分為若干不相交的部分，每一部分稱為一個片段，分片模式定義片段以及全局關(guān)系到

3、片段的映像。分配模式分配模式定義片段的存放結(jié)點(diǎn)。根據(jù)選定的數(shù)據(jù)分布策略，定義各片段的物理存放站點(diǎn)，即定義片段映像的類型，確定分布式數(shù)據(jù)庫是冗余的還是非冗余的，以及冗余的程度。局部概念模式是全局概念模式的子集，對每個站點(diǎn)來說，在該站點(diǎn)上全部物理映像的集合就稱為該站點(diǎn)上的局部概念模式。1.2 采用分布式數(shù)據(jù)庫系統(tǒng)的主要原因是什么？分布式數(shù)據(jù)庫系統(tǒng)適合于單位分散的部門，允許各個部門將其常用的數(shù)據(jù)存儲在本地，實(shí)施就地存放本地使用，從而提高響應(yīng)速度，降低通信費(fèi)用。采用分布式數(shù)據(jù)庫的原因主要有兩方面：(1)集中式數(shù)據(jù)庫系統(tǒng)的不足：數(shù)據(jù)按實(shí)際需要已經(jīng)在網(wǎng)絡(luò)上分布存儲，如果再采用集中式處理，勢必造成附加成本和

4、通信開銷；應(yīng)用程序集中在一臺計算機(jī)上運(yùn)行，一旦該計算機(jī)發(fā)生故障，將會影響整個系統(tǒng)的運(yùn)行，可靠性不高；集中式處理導(dǎo)致系統(tǒng)的規(guī)模和配置都不夠靈活，系統(tǒng)的可擴(kuò)展性較差。(2)分布式數(shù)據(jù)庫系統(tǒng)的優(yōu)點(diǎn)：具有靈活的體系結(jié)構(gòu)；適應(yīng)分布式的管理和控制機(jī)構(gòu)；經(jīng)濟(jì)性能優(yōu)越；系統(tǒng)的可靠性高、可用性好；局部應(yīng)用的響應(yīng)速度快；可擴(kuò)展性好，易于集成現(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(2)按分布式數(shù)據(jù)庫系統(tǒng)的全局控制系統(tǒng)類型分類：全局控制集中型DDBS全局控制分散型DDBS全局控制可變型DDBS1.

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

6、加數(shù)據(jù)冗余度：在集中式數(shù)據(jù)庫中，盡量減少冗余度是系統(tǒng)目標(biāo)之一。而在分布式系統(tǒng)中卻通過冗余數(shù)據(jù)提高系統(tǒng)的可靠性、可用性和改善系統(tǒng)性能。(6) 事務(wù)管理的分布性：數(shù)據(jù)的分布性必然造成事務(wù)執(zhí)行和管理的分布性。即，一個全局事務(wù)的執(zhí)行可分解為在若干個站點(diǎn)上子事務(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ù)之間的邏輯相關(guān)性，但不同站點(diǎn)的用戶需要該關(guān)系中的元組可能不同。這就需要對這個關(guān)系進(jìn)行分割，并將分割后的片段存放在相應(yīng)的站點(diǎn)上。數(shù)據(jù)復(fù)制：當(dāng)一個分布式數(shù)據(jù)庫中用戶數(shù)量較大，地理分布

7、較廣，而且需要實(shí)時地訪問相同數(shù)據(jù)時可以采用數(shù)據(jù)復(fù)制技術(shù)，它通過將這些共享數(shù)據(jù)復(fù)制到位于不同地點(diǎn)的多個數(shù)據(jù)庫中，從而實(shí)現(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ù)合適的劃分方案，使用這種方案得到的片段作為分布式數(shù)據(jù)庫中數(shù)據(jù)的分配和存儲單位時，不但能夠減少應(yīng)用中的操作量，而且能夠?qū)τ趹?yīng)用具有最大可能的本地性，即使得各片段位于其使用最多的站點(diǎn)。關(guān)系的片段：對數(shù)據(jù)庫管理系統(tǒng)

8、中的關(guān)系進(jìn)行分割，將分割后得到的各部分元組，就稱為該關(guān)系的邏輯片段。關(guān)系的片段主要類型有：(1)水平片段：按一定的條件把全局關(guān)系的所有元組劃分成若干不相交的子集，每個子集為關(guān)系的一個片段。也是通過對一全局對象的實(shí)例(或元組)進(jìn)行選擇得到的子集構(gòu)。(2)垂直片段：把一個全局關(guān)系的屬性集分成若干子集，并在這些子集上做投影運(yùn)算，每個投影為垂直分片。也是通過將全局對象在其屬性子集上進(jìn)行投影得到的。(3)混合分片：將水平分片與垂直分片方式綜合使用則為混合分片。第二章2.1概述分布式數(shù)據(jù)庫系統(tǒng)的創(chuàng)建方法、方法特點(diǎn)和適用范圍。分布式數(shù)據(jù)庫系統(tǒng)的創(chuàng)建方法即分布式數(shù)據(jù)庫系統(tǒng)的實(shí)現(xiàn)方法，大致可分為兩種：組合法和重

9、構(gòu)法。(1)采用組合法創(chuàng)建分布式數(shù)據(jù)庫系統(tǒng)組合法也稱集成法，這是一種自底向上(bottomup)的創(chuàng)建方法。它是利用現(xiàn)有的計算機(jī)網(wǎng)絡(luò)和獨(dú)立存在于各個站點(diǎn)上的現(xiàn)存數(shù)據(jù)庫系統(tǒng)，通過建立一個分布式協(xié)調(diào)管理系統(tǒng)，將它們集成為一個統(tǒng)一的分布式數(shù)據(jù)庫系統(tǒng)。特點(diǎn)：這種方法由于是利用現(xiàn)存的網(wǎng)絡(luò)和現(xiàn)存的數(shù)據(jù)庫系統(tǒng)，僅僅需要建立一個分布式協(xié)調(diào)管理系統(tǒng)。因此，相對來說，如果該系統(tǒng)不是很大的話，其工作量可能會比較小，實(shí)現(xiàn)的周期會短些，花費(fèi)的人力、物力會少些，用戶也比較容易接受，因?yàn)樗欣诒Ｗo(hù)現(xiàn)有的投資。適用范圍：采用組合法的分布式數(shù)據(jù)庫系統(tǒng)往往是異構(gòu)或同構(gòu)異質(zhì)的分布式數(shù)據(jù)庫系統(tǒng)。(2)采用重構(gòu)法創(chuàng)建分布式數(shù)據(jù)庫系統(tǒng)

10、重構(gòu)法是根據(jù)系統(tǒng)的實(shí)現(xiàn)環(huán)境和用戶需求，按分布式數(shù)據(jù)庫系統(tǒng)的設(shè)計思想和方法，采用統(tǒng)一的觀點(diǎn)，從總體設(shè)計做起，包括各站點(diǎn)上的數(shù)據(jù)庫系統(tǒng)，重新建立一個分布式數(shù)據(jù)庫系統(tǒng)。特點(diǎn)：這種方法的優(yōu)點(diǎn)在于，可以按照統(tǒng)一的思想來考慮分布式數(shù)據(jù)庫系統(tǒng)中的各種問題，有效地解決分布式數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)一致性、完整性和可靠性。但是花費(fèi)的人力、物力會比較多，研制周期也比較長，系統(tǒng)建設(shè)的代價會比較大。在實(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)除包

11、括集中式數(shù)據(jù)庫設(shè)計中的目標(biāo)外，還要包括以下幾點(diǎn)：(1)分布式數(shù)據(jù)庫的本地性或近地性分布式數(shù)據(jù)庫系統(tǒng)中最重要的目標(biāo)(至少在使用廣域網(wǎng)的情況下，以及某些使用局域網(wǎng)的情況下)是盡量減少對網(wǎng)絡(luò)的利用，即盡可能減少站點(diǎn)之間的通信次數(shù)和通信量。所以,分布式數(shù)據(jù)庫設(shè)計中的一個主要原則是使數(shù)據(jù)和應(yīng)用實(shí)現(xiàn)最大程度的本地性。本地性的優(yōu)點(diǎn)不僅僅減少了遠(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)，其原因之一是因?yàn)榉植际綌?shù)據(jù)庫系統(tǒng)中存在數(shù)據(jù)的適當(dāng)冗余。(3)工作負(fù)荷分布分布式計算機(jī)系統(tǒng)的一個重要

12、特征是把工作負(fù)荷分布在網(wǎng)絡(luò)中的各個站點(diǎn)上。分布工作負(fù)荷的目的是充分利用每個站點(diǎn)計算機(jī)的能力和資源，以提高應(yīng)用執(zhí)行的平行程度，從而提高系統(tǒng)的性能。(4)存儲的能力和費(fèi)用數(shù)據(jù)庫的分布會受到各站點(diǎn)的存儲能力的影響。在網(wǎng)絡(luò)中可以有專門用于存儲數(shù)據(jù)的站點(diǎn)，也可以有完全不支持大容量存儲的站點(diǎn)。上述的設(shè)計目標(biāo)都要達(dá)到是非常困難的，因?yàn)檫@會使優(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)模式(也稱物理模式，描述概

13、念模式映射到存儲區(qū)域，并確定合適的存取方法)的設(shè)計。這兩個問題在分布式數(shù)據(jù)庫中變?yōu)槿帜Ｊ皆O(shè)計和每個站點(diǎn)的局部數(shù)據(jù)庫設(shè)計的問題，其中的關(guān)鍵是數(shù)據(jù)庫的全局模式應(yīng)如何劃分：并映射到合適站點(diǎn)上。這就產(chǎn)生了分布數(shù)據(jù)庫設(shè)計所特有的兩個新問題：數(shù)據(jù)的分片設(shè)計和片段的位置分配設(shè)計。分布式數(shù)據(jù)庫的分布設(shè)計要求確定數(shù)據(jù)的分片和片段的分配。分片是指把一全局對象(實(shí)體或關(guān)系)細(xì)分成若干邏輯片段的過程；分配是指把各片段映射到一個或多個站點(diǎn)的過程，片段是最合適的數(shù)據(jù)分配單位。2.6 數(shù)據(jù)分片應(yīng)遵守哪些基本原則？數(shù)據(jù)分片有哪些基本類型和方法？分片方法，必須遵守如下規(guī)則：若R=R1,R2,Rn滿足：1) 完整性(compl

14、eteness)條件:如果aCR則必aCRi,i=l,2,2)可重構(gòu)(reconstructed)條件：R=URi,(水平分片)或RqRi,(垂直分片)3)不相交(disjoint)條件：RinRj=。，iwj,i,j：=1,2,n(水平分片)RiARj=主鍵屬性，i,j=1,2,n(垂直分片)有兩種基本的數(shù)據(jù)分片方法：(1)使用水平分片方法得到水平片段，水平片段是通過對一全局對象的實(shí)例(或元組)進(jìn)行選擇得到的子集構(gòu)成。水平分片是對全局關(guān)系執(zhí)行“選擇”操作，把具有相同性質(zhì)的元組進(jìn)行分組，構(gòu)成若干個不相交的子集。水平分片的方法可歸為初級分片(primaryfragmentation)和導(dǎo)出分片(

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

16、接變得更加容易？試舉一例。全局關(guān)系的導(dǎo)出式水平分片不是以其自身的屬性性質(zhì)為基礎(chǔ)，而是從另一個關(guān)系的屬性性質(zhì)或水平片段推導(dǎo)出來的。采用導(dǎo)出分片可使片段與片段之間的“連接”(join)變得更容易。例：設(shè)全局關(guān)系SC(S#.C#,SCORE)S(S#,SNAMEAGESEX)若要將SC劃分為男生的各門課成績和女生的各門課成績。這就不可能從SC本身的屬性性質(zhì)來執(zhí)行選擇，必須從關(guān)系S的屬性性質(zhì)或水平片段來導(dǎo)出。definefragmentSC1asselectSC.S#,C#,SCOREfromSC,SwhereSC.S#=S.S#andSEX='MdefinefragmentSC2assele

17、ctSC.S#,C#,SCOREfromSC,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.S#fromSM)由此可見，使用導(dǎo)出式水平分片，使關(guān)系之間的連接變得更加容易。這是因?yàn)榭蓪⑦B接條件代之以子查詢，從而使它變?yōu)橐话愕呐袆e條件。2.8 采用D

18、ATAID-D方法的分布式數(shù)據(jù)庫設(shè)計與傳統(tǒng)的集中式數(shù)據(jù)庫設(shè)計在步驟和內(nèi)容上有什么不同？DATAID-D是作為集中式數(shù)據(jù)庫設(shè)計DATAID1方法論的擴(kuò)充而構(gòu)造的，后者分成四個階段：需求分析、概念設(shè)計、邏輯設(shè)計和物理設(shè)計。DATAID-D要求對其增加兩個階段：分布要求分析階段和分布設(shè)計階段1)分布要求分析階段：需要這一階段是為了收集關(guān)于分布的信息，如水平分片的劃分謂詞，每一應(yīng)用在各站點(diǎn)激活的頻率等。為了收集關(guān)于數(shù)據(jù)和應(yīng)用分布的信息，必須從概念設(shè)計階段的某些結(jié)果出發(fā)來收集關(guān)于分布要求。因此，分布要求分析階段將位于概念設(shè)計階段之后。2)分布設(shè)計階段：這一階段始于全局?jǐn)?shù)據(jù)庫模式的規(guī)格說明和所收集的分布要

19、求，然后產(chǎn)生全局?jǐn)?shù)據(jù)的分片模式和片段的位置分配模式，分配模式描述了分配在各站點(diǎn)上的數(shù)據(jù)情況。2.9 考慮圖2.12所示的公司數(shù)據(jù)庫的分片和分布。假設(shè)該公司有三個計算機(jī)站點(diǎn)，站點(diǎn)B和C分別屬于部門2和3.現(xiàn)在希望在站點(diǎn)B和C上分別頻繁訪問EMPLOYEE和PROJECT表中有關(guān)工作在該部門的雇員和該部門管轄的項(xiàng)目信息。雇員信息主要是指EMPLOYEE表的NAME,ESSN,SALARY和SUPERSSN屬性。站點(diǎn)A供公司總部（部門1）使用，經(jīng)常存取為保險目的而記錄的DEPENDENT信息外，還定期地存取所有雇員和項(xiàng)目的信息。根據(jù)這些給出的要求，對COMPANY關(guān)系數(shù)據(jù)庫中關(guān)系進(jìn)行分片和分布。EM

20、PLOYEEFNAMEMINITLNAMEESSNBDATEADDRESSSEXSALARYSUPERSSNDNODEPARTMENTDNAMEDNOMGRSSNMGRSTARTDATEDEPT_LOCATIONDNODLOCATIONPROJECTPNAMEPNUMERPLOCATIONDNOWORKS_ONESSNPNOHOURSDEPENDENTESSNDEPENDENTNAME_SEXBDATERELATIONSHIP圖2.12COMPANY關(guān)系數(shù)據(jù)庫模式的一個可能的關(guān)系數(shù)據(jù)庫狀態(tài)（主碼用下標(biāo)線標(biāo)出）解：根據(jù)給出的要求，圖2.12中的整個數(shù)據(jù)庫可以被存儲在站點(diǎn)A。為了確定將要復(fù)制到站點(diǎn)

21、2和3上的片段，先根據(jù)DEPARTMENT的主碼DNO勺值進(jìn)行水平分片，然后基于外碼部門號（DNOX各導(dǎo)出的片段應(yīng)用至IJ關(guān)系EMPLOYEEPROJEC下口DEPT_LOCATIONS,再在剛才得至IJ的EMPLOYEE段上進(jìn)行垂直分片，得至IJ只含屬性NAME,ESSN,SALARY*SUPERSSNDNO兩片段。圖2.13給出了EMPD邪EMPD3勺混合分片，它包括了分別滿足條件DN0=2和DN0=3的EMPLOYEE組。類似地，PROJECT,DEPARTMENTDEPT-LOCATIONS按部門編號進(jìn)行水平分片，這些片段根據(jù)其相應(yīng)的部門號分別存儲在站點(diǎn)B和C上，如下圖所示。EMPD5

22、FNAMEMINITLNAMEESSNSALARYSUPERSSNDNOJohnBSimth123456789200003334455552FranisaTWong333445555100008886655552ReminiaKNaraya666884444150003334455552JoyeeAEnglish453453453200003334455552DEP5DNameDNOMGRSSNMGRSTARTDATEResearch23334455552003-05-22DEP5_LOC5DNOLOCATION2Bellaire2Sugarlnd2HoustenPROJS55PNAMEPNU

23、MBERPLOCAIONDNOProductX1Bellaire2Product丫2Sugarlnd2ProductZ3Housten2DEP5_LOCSESSNPNOHOURS123456789132.512345678927.5666884444340.0453453453120.0453453453220.0333445555210.0333445555310.03334455551010.03334455552010.0a）站點(diǎn)B上的對應(yīng)部門2的關(guān)系片段現(xiàn)在需要對WORKS_ON系進(jìn)行分片，并且確定哪些WORKS_ON段要存儲在站點(diǎn)B和C上口這時面臨這樣一個問題，WORKS_ON的屬性

24、沒有一個可以直接指明每個元組所屬的部門。實(shí)標(biāo)上WORKS_ON的每個元組與雇員e和項(xiàng)日P相聯(lián)系。我們既可以以e工作的部門也可以以管轄P的部門d'來分片WORKS_ON。如果對表WORKS_ON所有元組增加一個d_d'的限制，分片就會變得更加容易，即雇員只能為那些他所在部門管轄的項(xiàng)目工作。然而，在（用條件C圖2.12中的數(shù)據(jù)庫沒有給出這樣的限制。所以，對此可以先以雇員工作的部門表述）來分片WORKS_ON后進(jìn)一步以管轄雇員工作項(xiàng)目的部門來分片，如下圖所示。EMPD4FNAMEMINITLNAMESSNSALARYSUPERSSNDNOAhciaJZelaya99988777725

25、0009876543214JenniferSWallace987654321430008886655554AhmadVJabbar999887777250009876543214EMPD4FNAMEMINITLNAMEESSNSALARYSUPERSSNDNOJohnBSimth123456789200003334455552FranisaTWong333445555100008886655552ReminiaKNaraya666884444150003334455552JoyeeAEnglish453453453200003334455552DEP4DNameDNUMBERMGRSSNMGR

26、STARTDATEAdministr49876543212003-01-01DEP4_LOCSDNUMBERLOCATION4StatlandDEP4_LOCSESSNPNOHOURS3334455551010.09998877773030.09998877771010.09879879871035.0987987987305.09876543213020.09876543212015.0PROJS55PNAMEPNUMBERPLOCAIONDNOComputer10Statland4Newbener30Statland4b）站點(diǎn)B上的對應(yīng)部門4的關(guān)系片段在上圖中，片段G1,G2和G3的并集給

27、出了為部門2工作的雇員的所有WORKS_ON組。同樣地，片段G4,G5和G6的并集給出了為部門3的雇員的所有WORKS_ON組。另一方面，片段GI!LI'I和G7的并集給出了被部門2管轄的項(xiàng)目的所有WORKS_ON組。因此，可以把片段G1,G2,G3,G4和G的并集放到站點(diǎn)B上，把片段G5,G5,G6,G2和G8的并集放在站點(diǎn)C上，可以看到片段G2和G4在兩個站點(diǎn)上均被復(fù)制。這就清楚地論證了對于大型數(shù)據(jù)庫而言，數(shù)據(jù)的分片和分配是一個多么復(fù)雜的問題。第三章3.3 概述基于關(guān)系代數(shù)等價變換的查詢優(yōu)化算法的基本原理和實(shí)現(xiàn)步驟。基本原理：把查詢問題轉(zhuǎn)變?yōu)殛P(guān)系代數(shù)表達(dá)式，分析得到查詢樹（語法樹，

28、進(jìn)行從全局到片段的變換得到基于片段的查詢樹，然后利用關(guān)系代數(shù)變換規(guī)則的優(yōu)化算法，盡可能先執(zhí)行選擇和投影操作.這樣，一方面可以減少其后操作的操作量，另一方面可以減少操作次數(shù).對該查詢樹進(jìn)行優(yōu)化，從而達(dá)到查詢優(yōu)化的目的.實(shí)現(xiàn)步驟：1、將一個查詢問題轉(zhuǎn)換成關(guān)系代數(shù)表達(dá)式2、從關(guān)系代數(shù)表達(dá)式到查詢樹的變換：對一個關(guān)系代數(shù)表達(dá)式進(jìn)行語法分析，可以得到一顆語法書，即樹的葉子是已知的關(guān)系（或片段）、樹的結(jié)點(diǎn)是關(guān)系操作符、節(jié)點(diǎn)是按代數(shù)表達(dá)式中的操作順序組成的一組關(guān)系操作符。3、從全局查詢到片段查詢的變換：在具有分片透明性的系統(tǒng)中，這個變換的典型方法是：把基于全局關(guān)系的查詢樹中的全局關(guān)系名用其重構(gòu)該全局關(guān)系的各

29、片段名替換，變換成相應(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ù)量，從而減少站點(diǎn)間數(shù)據(jù)的傳輸量。適用情況：如果只需要一個關(guān)系中的一小部分元組參與和另一個關(guān)系連接的話，這是一個使數(shù)據(jù)傳輸量最小化的非常有效的方案。此時，丁半丁全，采用半連接方案是合適的。3.5 概述基于直接連接算法查詢優(yōu)化的基本原理和適用情形?；驹恚夯谥苯舆B接算法的查詢優(yōu)化處理中的站點(diǎn)依賴算法、分片和復(fù)制算法。站點(diǎn)依賴和數(shù)據(jù)復(fù)制算法，以及Hash劃分算法，主要是

30、使得連接操作的數(shù)據(jù)傳送量?。ㄗ詈檬菬o數(shù)據(jù)傳送）和負(fù)載均衡，從而達(dá)到優(yōu)化的目的。使用情形：直接連接查詢優(yōu)化的算法有四種，通過比較，站點(diǎn)依賴算法的數(shù)據(jù)傳送量最?。▽?shí)際上沒有），連接數(shù)據(jù)量最小切利用索引，因而能獲得最佳性能。其次是Hash劃分算法，最后是片段和復(fù)制算法。盡管如此，站點(diǎn)依賴算法只有在給出適當(dāng)?shù)目捎谜Z義信息時才使用;Hash劃分算法要求相對均勻的數(shù)據(jù)分布來得到良好的性能，最壞的情況下，兩個關(guān)系可能被映射到同一個站點(diǎn)，而達(dá)不到負(fù)載均衡；在某個關(guān)系已經(jīng)復(fù)制在包含其他關(guān)系片段的站點(diǎn)中，可在本地立即進(jìn)行無數(shù)據(jù)傳送處理，這種場合下使用分片和復(fù)制算法要好于Hash劃分算法。在高速的局域網(wǎng)中，本地處理

31、的代價也必須考慮在內(nèi)，那么使用全連接是比較合適的。此時，查詢優(yōu)化策略就是去確定選擇執(zhí)行全連接的最佳方法。3.6 設(shè)有關(guān)系R,S,T如圖3.13所示。(1)計算連接RooSooTo(2)計算半連接R2SaR,ST,TaR,"S,R8TABC235536168346535268BCD356359683596416584DEI669878856389圖3-13(1)RooS>oTABCDEI235669168389535669268389(2)R8sABC235168535268S8RBCD356359683S8TBCD356683596416T8R為空FET為空T8SDEI6693

32、893.7 如果習(xí)題3.6中的三個關(guān)系R,S,T分別位于三個不同的站點(diǎn)X,Y,乙若采用基于半連接算法計算連接RmS8T,請選擇使得傳輸代價最少的連接執(zhí)行的站點(diǎn)和確定半連接序列。假設(shè)每個屬性域長度均為1B,考慮所有的半連接力殺半連接P得益費(fèi)用傳送屬性P1R0°S2/31/3*3*62*5S.BS.CP2S0°R1/21/2*3*62*4R.BR.CP3S0°T2/31/3*3*61*3T.DP4T°°S1/21/2*3*61*4S.D1、選擇得益高于P2進(jìn)行優(yōu)化，得到新的R,S',T,并對受到影響的方案重新計算得意和費(fèi)用。新的R,S

33、9;,T如下：PS3TP年O3/5-6g5-*6?8-3-對受到影響的方案重新計算得益和費(fèi)用力殺半連接P得益費(fèi)用傳送屬性P1RooS'2/31/3*3*62*5S'.BS'.CP2s0°R1/21/2*3*62*4R.BR.CP3S'0°T2/31/3*3*61*3T.DP4T°°S'1/21/2*3*61*4S'.D2、選擇得益最高的P4進(jìn)行優(yōu)化，彳#到新的R,S',T',并對受到影響的方案重新計算得益和費(fèi)用。新的R,S',T'如下:對受到影響的方案重新計算得益和費(fèi)用力殺半

34、連接P得益費(fèi)用傳送屬性P1RooS'2/31/3*3*62*5S'.BS'.CP2S0°R1/21/2*3*62*4R.BR.CP3S'0°T2/31/3*3*61*3T.DP413s1/21/23614s.D3、依口11或者2的方法得到新的R',S',T'如下：A*S川35r3*6*t】"8p3,4-6/a3a5-2,6叩A(chǔ)5種6。9r3-R=S=T'AB*C2"3p5小1卡6戶的5p3/5卡2G6a8cD*3卡5-63卡5卡9632對受到影響的方案進(jìn)行重新計算得益和費(fèi)用得到:力殺半連接P

35、得益費(fèi)用傳送屬性P1RooS'2/31/3*3*62*5S.BS.CP2SooR1/21/2*3*62*4R.BR.CP3S'0°T2/31/3*3*61*3T.DP4i0°S1/21/2*3*61*4S.D4、選擇得益最高的P3進(jìn)行優(yōu)化，得到X,Y,Z站點(diǎn)上最終的R',S',T'.X,Y,Z站點(diǎn)上最終的R',S',T'如下:A/B2/3/5/1<6爐5戶542,6484B+-A5-6/6戶8/De16戶69/條9r所以選擇各站點(diǎn)做連接的代價:X站點(diǎn)代價=2*3+2*3=12Y站點(diǎn)代價=4*3+2*3=1

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

37、上的投影兀D(T);把結(jié)果送到站點(diǎn)X;(4)在站點(diǎn)Y上計算半連接，設(shè)其結(jié)果為S',則S'=S8T;結(jié)果送到站點(diǎn)X;(5)在站點(diǎn)X上計算半連接，得到最后結(jié)果3.8設(shè)某公司的雇員關(guān)系為employee(name,address,salary,plant-number),按plant-number水平分片這個關(guān)系，每個片段都有兩個副本：一個副本存放在NewYork站點(diǎn)，另一個副本存放在工廠的站點(diǎn)。請為在Toronto站點(diǎn)提出的下列查詢設(shè)計一個好的處理策略。(1)找出Boce廠的所有雇員。(2)找出所有雇員的平均工資。(3)找出在如下每個站點(diǎn)工資最高的雇員姓名：Toronto,Edmo

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

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

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

41、日志中。如果在規(guī)定時間內(nèi)協(xié)調(diào)者收到了所有參與者“就緒”的信息，則將做出提交的決定，否則撤銷。第二階段：執(zhí)行階段，目的是實(shí)現(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)日志信息可以脫機(jī)保存。4.8 為什么說兩階段提交協(xié)議在不丟失運(yùn)行日志信息的情況下，可從任何故障恢復(fù)？因?yàn)樵趫?zhí)行過程中維護(hù)了事務(wù)日志，記錄了執(zhí)行恢復(fù)所需要的信息。4.9 在分布式數(shù)據(jù)庫系統(tǒng)中對多副本數(shù)據(jù)的更新通常采用什么方法？快照方

42、法的優(yōu)點(diǎn)和缺點(diǎn)是什么？答：對多副本數(shù)據(jù)更新通常有主文本更新法、移動主文本法和快照方法?？煺辗椒ǖ膬?yōu)點(diǎn)是：可完成復(fù)雜的查詢，而又不阻止更新；不必考慮數(shù)據(jù)的輔文本，只關(guān)心每一數(shù)據(jù)的主文本和在這些主文本上定義的任意多個快照；避免了某些并發(fā)控制的開銷，又便于復(fù)雜查詢完成，可提高系統(tǒng)可用性?？煺辗椒ǖ娜秉c(diǎn)是：快照為了與主文本保持同步，不許定時刷新，快照是一個制度關(guān)系,其中數(shù)據(jù)只能讀而不能寫，對更新操作無效。第五章5.2描述分布式事務(wù)的可串行化理論的一些定義：事務(wù)、沖突操作、并發(fā)調(diào)度、串行調(diào)度、一致性調(diào)度、兩個調(diào)度等價、可串行化調(diào)度。事務(wù)：在分布式系統(tǒng)中，事務(wù)是一個分布式操作的序列，被操作的數(shù)據(jù)分布在不同

43、的站點(diǎn)上。沖突操作：如果兩個操作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í)行均有Ti<Tj,即事務(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)度?？纱谢{(diào)度：如果一個調(diào)度等價于某個串行調(diào)度，則該調(diào)度稱為可串行調(diào)度。兩個調(diào)度等價：沖突等價以及視圖等價。5.5什么是兩階段封鎖協(xié)議？它如何保證可串行性？為什么人們經(jīng)常更愿意采用嚴(yán)格兩階段封鎖和嚴(yán)酷兩階

44、段封鎖？兩階段封鎖協(xié)議：一個事務(wù)所有的封鎖操作（讀寫）都在第一個解鎖操作之前，則該事務(wù)遵守兩階段封鎖協(xié)議。這樣一個事務(wù)被分成兩個階段：上升階段（成長階段）：只能獲取新鎖，而不能釋放已有的鎖收縮階段（衰退階段）：只能釋放已有的鎖，而不能獲得新鎖保守2PL要求事務(wù)在開始執(zhí)行前就持有所有它要訪問的數(shù)據(jù)項(xiàng)上的鎖。嚴(yán)格2PL事務(wù)提交或撤銷之前，絕對不釋放任何一個寫鎖；在事務(wù)結(jié)束時，同時釋放所有的鎖。嚴(yán)酷2PL事務(wù)在提交或撤銷之前，不能釋放任何一個鎖。如何保證可串行性：如果事務(wù)T稍后必須封鎖數(shù)據(jù)項(xiàng)Y,哪么在它使用完數(shù)據(jù)項(xiàng)X之后，獲得數(shù)據(jù)項(xiàng)丫之前，不可以釋放數(shù)據(jù)項(xiàng)X上的鎖。因此T必須一直持續(xù)有X的鎖，直到該

45、事務(wù)需要讀或?qū)懙乃袛?shù)據(jù)項(xiàng)都被他自己封鎖，然后，T才可以釋放X上的鎖。透明合適，即時T已經(jīng)完成X,另一個要訪問X的事務(wù)也可能會被強(qiáng)制等待。同樣對于數(shù)據(jù)項(xiàng)Y,如果T封鎖了Y則其他事務(wù)也要等待。因此就保證了可串行性。為什么人們經(jīng)常更愿意采用嚴(yán)格兩階段封鎖和嚴(yán)酷兩階段鎖，因?yàn)樵趪?yán)格兩階段封鎖中事務(wù)T在提交或撤銷之前，絕對的不釋放任何一個排他鎖；在事務(wù)結(jié)束時，同時釋放所有鎖。因此，除非事務(wù)T已經(jīng)提交，否則，任何其他的事務(wù)都不可以讀或?qū)懹墒聞?wù)T所寫的數(shù)據(jù)項(xiàng)，從而產(chǎn)生了一個對可恢復(fù)性而言的調(diào)度。改變有數(shù)據(jù)處理器所發(fā)出的操作命令不分，這對于僅當(dāng)操作被提交或撤銷時保證鎖的什那市很必要的。而在嚴(yán)酷2PL中，事務(wù)

46、T在提交或撤銷之前，不鞫釋放任何一個鎖，因此比嚴(yán)格兩階段鎖更容易實(shí)現(xiàn)。第六章6.3 概述分布式可靠性協(xié)議的組成以及它們各自的使用范圍。答：分布式數(shù)據(jù)庫系統(tǒng)的可靠性協(xié)議包括提交協(xié)議、終結(jié)協(xié)議和恢復(fù)協(xié)議提交協(xié)議：詳細(xì)說明了提交協(xié)議時如何被執(zhí)行的，它保持了分布式事務(wù)的原子性。終結(jié)協(xié)議：在執(zhí)行一個分布式事物時，其中一個站點(diǎn)失效了，我們希望其他站點(diǎn)也停止該事務(wù)，終結(jié)協(xié)議是用來處理這種情況的?；謴?fù)協(xié)議：一個站點(diǎn)失效了，終結(jié)協(xié)議確定可未失效站點(diǎn)如何處理該失效事件，而恢復(fù)協(xié)議確定失效站點(diǎn)重新啟動后，其進(jìn)程恢復(fù)他的狀態(tài)的過程。6.4 討論兩階段提交協(xié)議的終結(jié)協(xié)議和兩階段提交協(xié)議的恢復(fù)協(xié)議。答：兩階段提交協(xié)議的終

47、結(jié)協(xié)議：終結(jié)協(xié)議在協(xié)調(diào)者和參與者的定時器超時發(fā)揮作用，超時發(fā)生在目的站點(diǎn)在期望的時間內(nèi)沒有從發(fā)送站點(diǎn)得到所期望的消息時。處理超時的方法依賴于失效發(fā)生的時間和失效的類型。協(xié)調(diào)者可以再三種狀態(tài)中發(fā)生超時：等待、提交和撤銷。在后兩種狀態(tài)發(fā)生超時是按相同的方式處理的，所以只需考慮兩種情況：等待狀態(tài)發(fā)生超時時，協(xié)調(diào)者正在等待參與者的局部決定。協(xié)調(diào)者不能單方面提交事務(wù)，因?yàn)椴粷M足全局提交規(guī)則。然而，他可以決定全局撤銷事務(wù)，此時，他在日志中寫入撤銷記錄，并向所有參與者發(fā)送“全局撤銷”消息。在提交狀態(tài)或撤銷狀態(tài)發(fā)生超時時，協(xié)調(diào)者不能確定是否在所有參與者站點(diǎn)上本地恢復(fù)管理程序都執(zhí)行完提交或撤銷過程。因此。協(xié)調(diào)者

48、重復(fù)發(fā)出“全局提交”命令或“全局撤銷”，命令給沒有響應(yīng)的站點(diǎn)，并等待確認(rèn)。兩階段提交協(xié)議的恢復(fù)協(xié)議可分為三種情形：協(xié)調(diào)者站點(diǎn)失效，參與者站點(diǎn)失效，還有其他的附加情形。 協(xié)調(diào)者站點(diǎn)失效：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é)議。 參與者站點(diǎn)失效：1)一個參與者在初始狀態(tài)失效，在恢復(fù)時，該參與者應(yīng)該單方面撤銷事務(wù)。2)一個參與者在就緒狀態(tài)失效時，協(xié)調(diào)者已經(jīng)收到失效站點(diǎn)在失效前發(fā)送的肯定性決定，在恢復(fù)時，失效站點(diǎn)的參與者認(rèn)為是在就緒狀態(tài)發(fā)生了超時，于是啟動終結(jié)協(xié)議來處理該事務(wù)。3)一個參與者在提交狀態(tài)或撤銷狀態(tài)失效，在恢復(fù)時，參