分布式數(shù)據(jù)庫總結(jié)

分布式數(shù)據(jù)庫總結(jié)分布式數(shù)據(jù)庫系統(tǒng)及其應(yīng)用復(fù)習(xí)大綱第一章分布式數(shù)據(jù)庫系統(tǒng)概述1、理解分布式數(shù)據(jù)庫系統(tǒng)的特點(diǎn)分布式數(shù)據(jù)庫系統(tǒng)的定義：分布式數(shù)據(jù)庫系統(tǒng)，通俗地說，是物理上分散而邏輯上集中的數(shù)據(jù)庫系統(tǒng)。分布式數(shù)據(jù)庫系統(tǒng)使用計(jì)算機(jī)網(wǎng)絡(luò)將地理位置分散而管理和控制又需要不同程度集中的多個(gè)邏輯單位(通常是集中是數(shù)據(jù)庫系統(tǒng))連接起來，共同組成一個(gè)統(tǒng)一的數(shù)據(jù)庫系統(tǒng)。分布式數(shù)據(jù)庫系統(tǒng)的特點(diǎn)：1物理分布性：數(shù)據(jù)不是存放在一個(gè)站點(diǎn)上2邏輯整體性：是與分散式數(shù)據(jù)庫系統(tǒng)的區(qū)別3站點(diǎn)自治性：是與多處理機(jī)系統(tǒng)的區(qū)別4數(shù)據(jù)分布透明性5集中與自治相結(jié)合的控制機(jī)制6存在適當(dāng)?shù)臄?shù)據(jù)冗余度7事務(wù)管理的分布性2、能夠按照不同標(biāo)準(zhǔn)描述分布式數(shù)據(jù)庫系統(tǒng)的分類按局部數(shù)據(jù)庫管理系統(tǒng)的數(shù)據(jù)模型分類：同構(gòu)性(homogeneous)(分為同構(gòu)同質(zhì)型和同構(gòu)異質(zhì)型)DDBS和異構(gòu)性(heterogeneous)DDBS按分布式數(shù)據(jù)庫系統(tǒng)的全局控制系統(tǒng)類型分類：全局控制集中型DDBS，全局控制分散型DDBS，全局控制可變型DDBS。3、理解分布式數(shù)據(jù)庫中數(shù)據(jù)的獨(dú)立性和分布透明性所謂數(shù)據(jù)獨(dú)立性是指用戶或用戶程序使用分布式數(shù)據(jù)庫如同使用集中式數(shù)據(jù)庫那樣，不必關(guān)心全局?jǐn)?shù)據(jù)的分布情況，包括全局?jǐn)?shù)據(jù)的邏輯分片情況、邏輯片段站點(diǎn)位置的分配情況，以及各站點(diǎn)上數(shù)據(jù)庫的數(shù)據(jù)模型等。也就是說，全局?jǐn)?shù)據(jù)的邏輯分片、片段的物理位置分配，各站點(diǎn)數(shù)據(jù)庫的數(shù)據(jù)模型等情況對(duì)用戶和用戶程序透明。所以，在分布式數(shù)據(jù)庫中分布獨(dú)立性也稱為分布透明性。分布透明性包括三個(gè)層次：分片透明性（完全分布透明性）：映像2位置透明性（中級(jí)分布透明性）：映像3局部數(shù)據(jù)模型透明性（低級(jí)分布透明性）：映像4無分布透明性：異構(gòu)數(shù)據(jù)第二章分布式數(shù)據(jù)庫系統(tǒng)設(shè)計(jì)1、理解分布式數(shù)據(jù)庫的設(shè)計(jì)目標(biāo)分布式數(shù)據(jù)庫設(shè)計(jì)的目標(biāo)1分布式數(shù)據(jù)庫的本地性或近地性2控制數(shù)據(jù)的適當(dāng)冗余3工作負(fù)荷分布4存儲(chǔ)的能力和費(fèi)用 2、理解水平分片的定義、分類和應(yīng)用水平分片是對(duì)全局關(guān)系執(zhí)行“選擇操作”，把具有相同性質(zhì)的元組進(jìn)行分組，構(gòu)成若干個(gè)不相交的子集。水平分片的方法可歸為初級(jí)分片和導(dǎo)出分片兩類。初級(jí)分片：以關(guān)系自身的屬性性質(zhì)為基礎(chǔ)，執(zhí)行“選擇”操作，將關(guān)系分為若干個(gè)不相交的片段。例子2.1S（S#，SNAME,AGE,SEX）DefinefragmentS1asselect*fromwheresex=’M’DefinefragmentS2asselect*fromwheresex=’F’導(dǎo)出分片：全局關(guān)系的導(dǎo)出分片不是以其自身的屬性性質(zhì)為基礎(chǔ)，而是從另一個(gè)關(guān)系的屬性性質(zhì)或水平片段推導(dǎo)出來的。采用導(dǎo)出分片可片可使片段與片段之間的“連接”變得更容易。例2.3設(shè)全局關(guān)系SC(S#,C#,GRADE),S(S#,SNAME,AGE,SEX)若要將$。劃分為男生的各門課成績和女生的各門課成績，這就不可能從SC本身的屬性性質(zhì)來執(zhí)行選擇，必須從關(guān)系S的屬性性質(zhì)或水平片段來導(dǎo)出。DefinefragmentSC1asselectSC.S#,C#,GRADEfromSC,SwhereSC.S#=S.S#andSEX=’M’DefinefragmentSC2asselectSC.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.S#fromSM)3、理解垂直分片的定義和應(yīng)用一個(gè)全局關(guān)系的垂直分片是通過“投影”操作把它的屬性分為若干組。確定一個(gè)全局關(guān)系R的垂直分片需要根據(jù)應(yīng)用以“同樣方式”（例如具有相同的使用頻率）訪問的屬性來進(jìn)行分組。例2.4全局關(guān)系EMP（E#，NAME，SAL，TEL，MAGNUM，DEPT），主碼為E#。主要應(yīng)用有：集中在站點(diǎn)3上的管理性應(yīng)用要求查詢雇員的：NAME，SAL，TEL；和從其他站點(diǎn)發(fā)出的應(yīng)用要求查詢雇員的：NAME，DEPT，MAGNUM。解：如果使用垂直分片：EMP1CE#，NAME，SAL，TEL）和EMP2CE#，MAGNUM，DEPT）則NAME屬性只屬于一個(gè)片段，對(duì)于上述的應(yīng)用，必須進(jìn)行連接操作和非本地訪問。如果使用垂直群集：EMP1（E#，NAME，SAL，TEL）和EMP2（E#，NAME，MAGNUM，DEPT）則對(duì)于上述應(yīng)用，不需要執(zhí)行連接操作，且可實(shí)現(xiàn)較好的本地性。4、能夠描述分片的基本原則完備性原則：要把所有的數(shù)據(jù)映射到各個(gè)片斷中可重構(gòu)原則：關(guān)系分片后的各個(gè)片斷可重構(gòu)整個(gè)關(guān)系不相交原則：關(guān)系分片后的各個(gè)片斷不能重疊5、掌握數(shù)據(jù)片斷分配的分類和常用方法分配的簡化模型有：讀代價(jià)、寫代價(jià)、存儲(chǔ)代價(jià)和目標(biāo)函數(shù)。常用方法：非冗余分配設(shè)計(jì)方法（包含最佳適應(yīng)法和其他方法）和冗余分配的設(shè)計(jì)方法（包含所有得益站點(diǎn)法和附加復(fù)制法）6、掌握最佳適應(yīng)法和所有得益站點(diǎn)法的基本特點(diǎn)最佳適應(yīng)法是對(duì)每一種分配方式進(jìn)行估算，然后選擇最佳的站點(diǎn)。這種方法不考慮把一個(gè)片段與一個(gè)相關(guān)片段放在同一站點(diǎn)的“相互”影響。特點(diǎn)：將片斷陌分配到訪問Ri次數(shù)最多的那個(gè)站點(diǎn)上Bij二ZkFkj*Nki所有得益站點(diǎn)法：首先確定非復(fù)制為題的解，然后在全部站點(diǎn)中確定一組站點(diǎn)，給這組站點(diǎn)中的每一個(gè)站點(diǎn)分配片斷的一個(gè)副本，這樣做所得到的好處要比為此而付出的費(fèi)用合算。特點(diǎn)：將片斷Ri的副本分配到所有得益站點(diǎn)j上Bij二EkFkj*Rki-c*EkEj?#jFkj*Uki如果Bij>0，則站點(diǎn)j是得益站點(diǎn)，放置Ri的一個(gè)副本7、能夠描述DATAID-D方法設(shè)計(jì)分布式數(shù)據(jù)庫的各個(gè)階段需求分析，概念設(shè)計(jì)，分布要求分析，全局邏輯設(shè)計(jì)，分布設(shè)計(jì)，局部邏輯設(shè)計(jì)，局部物理設(shè)計(jì)。邏輯設(shè)計(jì)分為全局邏輯設(shè)計(jì)和局部邏輯設(shè)計(jì)8、能夠根據(jù)給出的條件對(duì)關(guān)系進(jìn)行具體分片，給出正確的限定關(guān)系上邊的例子。第三章分布式數(shù)據(jù)庫系統(tǒng)中的查詢處理和優(yōu)化1、掌握分布式數(shù)據(jù)庫查詢的分類局部查詢、遠(yuǎn)程查詢和全局查詢2、理解關(guān)系代數(shù)運(yùn)算的交換率？U1(U2(R))=U2(U1(R))條件：U1U2是選擇操作時(shí)總成立，U1U2是投影操作時(shí)要求其屬性集合相等U1與U2是投影和選擇操作時(shí)：nA1,?An(oF(R))=。F(nA1,?An(R))的條件是F中的屬性是A1,?.An的子集。R8s=S8RRXS二SXRrus二surrns二snrr工s乂？s工RR-S乂？S-R3、掌握直接連接優(yōu)化算法的分類利用站點(diǎn)依賴信息的算法，分片與復(fù)制算法，站點(diǎn)依賴和數(shù)據(jù)復(fù)制結(jié)合算法，Hash劃分算法4、 掌握半連接運(yùn)算見P83-84例子5、 掌握半連接和直接連接查詢優(yōu)化算法的區(qū)別取決于數(shù)據(jù)傳輸和局部處理的相對(duì)費(fèi)用；如果傳輸費(fèi)用是主要的，采用半連接；如果本地費(fèi)用是主要的，采用直接連接，6、理解Hash劃分算法的特點(diǎn)1數(shù)據(jù)傳送量是R;2索引方面，比片段復(fù)制算法更低，3每個(gè)站點(diǎn)的連接數(shù)據(jù)量同站點(diǎn)依賴7、能夠描述基于半連接算法查詢優(yōu)化的基本原理和步驟基本原理是在傳到另一個(gè)站點(diǎn)做連接前，消除與連接無關(guān)的數(shù)據(jù)，減少做連接操作的數(shù)據(jù)量，從而減小傳輸代價(jià)步驟：1計(jì)算每種半連接方案的代價(jià)，并從中選擇一種最佳方案2選擇傳輸代價(jià)最小的站點(diǎn)，計(jì)算采用全連接的方案的代價(jià)3比較兩種方案，確定最優(yōu)方案8、 能夠描述基于關(guān)系代數(shù)等價(jià)變換的查詢優(yōu)化算法原理、算法實(shí)現(xiàn)步驟原理：1查詢問題一一〉關(guān)系代數(shù)表達(dá)式2分析得到查詢樹3進(jìn)行全局到片段的變換得到基于片段的查詢樹4利用關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化算法，盡可能先執(zhí)行選擇和投影操作算法：1連接和合并盡可能上提(樹根方向)2選擇和投影操作盡可能下移(葉子方向)實(shí)現(xiàn)步驟：轉(zhuǎn)換一：1查詢問題一一〉關(guān)系代數(shù)表達(dá)式。2轉(zhuǎn)換二：關(guān)系代數(shù)表達(dá)式一一〉查詢樹。3轉(zhuǎn)換三：全局查詢樹分拆成片段查詢樹。4優(yōu)化：利用關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化算法，優(yōu)化查詢樹，進(jìn)而優(yōu)化查詢9、 能夠根據(jù)提供的條件完成分片和復(fù)制算法應(yīng)用，通過計(jì)算判斷哪個(gè)關(guān)系保持分片最優(yōu)P88例3-6考試第四章分布式數(shù)據(jù)庫中的事務(wù)管理和恢復(fù)1、 掌握事務(wù)的四大特性原子性(Atomicity)，一致性(Consistency)，持久性(Durability).隔離性(Isolation)2、 能夠描述兩階段提交協(xié)議的工作流程兩階段提交協(xié)議的基本思想是：將本地原子性提交行為的效果擴(kuò)展到分布式事務(wù)，保證了分布式事務(wù)提交的原子性，并在不損壞Log的情況下，實(shí)現(xiàn)快速故障恢復(fù)，提高DDB系統(tǒng)的可靠性.2PC把事務(wù)的提交過程分為兩個(gè)階段：第一階段：表決階段，目的是形成一個(gè)共同的決定首先，協(xié)調(diào)者給所有參與者發(fā)送“準(zhǔn)備''消息，進(jìn)入等待狀態(tài)其次，參與者收到“準(zhǔn)備”消息后，檢查是否能夠提交本地事務(wù)如能，給協(xié)調(diào)者發(fā)送“建議提交”消息,進(jìn)入就緒狀態(tài)如不能，給協(xié)調(diào)者發(fā)送“建議撤銷”消息，可以單方面撤銷第三，協(xié)調(diào)者收到所有參與者的消息后，他就做出是否提交事務(wù)的決定，只要有一個(gè)參與者投了反對(duì)票，就決定撤銷整個(gè)事務(wù)，發(fā)送“全局撤銷”消息給所有參與者，進(jìn)入撤銷狀態(tài)否則，就決定提交整個(gè)事務(wù)，發(fā)送“全局提交''消息給所有參與者，進(jìn)入提交狀態(tài)第二個(gè)階段：執(zhí)行階段，實(shí)現(xiàn)表決階段的決定，提交或者撤銷3、掌握事務(wù)故障的分類分布是數(shù)據(jù)庫的故障分布是數(shù)據(jù)庫的故障分為站點(diǎn)故障和通信故障。站點(diǎn)故障包括事務(wù)故障、系統(tǒng)故障和介質(zhì)故障。事務(wù)故障包括計(jì)算溢出。完整性被破壞、操作員干預(yù)、輸入或輸出出錯(cuò)等。通信故障分為報(bào)文故障和網(wǎng)絡(luò)分割故障。4、掌握分布式數(shù)據(jù)庫事務(wù)執(zhí)行的控制模型的分類分為三類：主從模型，三角模型，層次控制模型5、理解日志文件的特點(diǎn)日志文件保存到磁盤上。日志Log：記錄所有對(duì)DB的操作事務(wù)標(biāo)識(shí)：每個(gè)事務(wù)給定一個(gè)具有惟一性的標(biāo)識(shí)符Log記錄項(xiàng)：[start_transaction,T][write_item,T,x,I日值，新值][read_item,T,x][mit,T][abort,T]寫動(dòng)作：寫Log比寫數(shù)據(jù)優(yōu)先Log存儲(chǔ)：一般存在盤上，還會(huì)定期備份到磁帶上6、理解分布式數(shù)據(jù)庫數(shù)據(jù)更新常見方法多站點(diǎn)數(shù)據(jù)更新、主文本更新法、快照方法7、理解故障恢復(fù)時(shí)檢查點(diǎn)知識(shí)檢查點(diǎn)(Checkpoint):設(shè)置一個(gè)周期性(時(shí)間/容量)操作點(diǎn)a)LogBuffer內(nèi)容寫入匚og數(shù)據(jù)集b)寫檢查點(diǎn)Log信息：當(dāng)前活動(dòng)事務(wù)表，每個(gè)事務(wù)最近一次Log記錄在Log文件中的位置c)DBBuffer內(nèi)容寫入DBd)將本次檢查點(diǎn)Log項(xiàng)在Log文件中的地址記入“重啟動(dòng)文件”8、能夠描述兩階段提交協(xié)議的特點(diǎn)：2PC協(xié)議的重要特點(diǎn)：1允許參與者單方面撤銷事務(wù)2一旦參與者確定了提交或撤銷協(xié)議，它就不能再更改它的提議3當(dāng)參與者處于就緒狀態(tài)時(shí)，根據(jù)協(xié)調(diào)者發(fā)出的消息種類，它可以轉(zhuǎn)換為提交狀態(tài)或者撤銷狀態(tài)4協(xié)調(diào)者根據(jù)全局提交規(guī)則做出全局終止決定5協(xié)調(diào)者和參與者可能進(jìn)入互相等待對(duì)方消息的狀態(tài)，使用定時(shí)器，保證退出消息等待狀態(tài)第五章分布式數(shù)據(jù)庫中的并發(fā)控制1、理解封鎖的基本準(zhǔn)則1事務(wù)T在執(zhí)行任何read_item(x)操作之前，必須先執(zhí)行read_lock(x)或者write_lock(x)操作2事務(wù)T在執(zhí)行任何write_item(x)操作之前，必須先執(zhí)行write_lock(x)操作3如果事務(wù)T執(zhí)行read_lock(x)操作,數(shù)據(jù)項(xiàng)x必須沒有加鎖或者已經(jīng)加了讀鎖，否則事務(wù)T的這個(gè)操作不能進(jìn)行4如果事務(wù)T執(zhí)行write_lock(x)操作,數(shù)據(jù)項(xiàng)x必須沒有加鎖，否則事務(wù)T的這個(gè)操作不能進(jìn)行5事務(wù)T在完成所有read_item(x)和write_item(x)操作之后，必須執(zhí)行unlock(x)操作6如果事務(wù)T已經(jīng)持有數(shù)據(jù)項(xiàng)x上的一個(gè)讀鎖或者一個(gè)寫鎖，那么它不能再執(zhí)行read_lock(x)操作7如果事務(wù)T已經(jīng)持有數(shù)據(jù)項(xiàng)x上的一個(gè)讀鎖或者一個(gè)寫鎖，那么它不能再執(zhí)行write_lock(x)操作8如果事務(wù)T沒有持有數(shù)據(jù)項(xiàng)x上的一個(gè)讀鎖或者一個(gè)寫鎖，那么它不能執(zhí)行unlock(x)操作2、理解基于時(shí)標(biāo)的并發(fā)控制方法并發(fā)控制方法包含全局時(shí)標(biāo)和局部時(shí)標(biāo)3、掌握死鎖檢測(cè)的方法分類局部死鎖：僅在一個(gè)站點(diǎn)上發(fā)生的死鎖全局死鎖：涉及多個(gè)站點(diǎn)的死鎖（即等待圈由多個(gè)站點(diǎn)組成）4、理解一致性調(diào)度和可串行化調(diào)度的特點(diǎn)一致性調(diào)度：調(diào)度可以使得數(shù)據(jù)庫從一個(gè)一致性狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€(gè)一致性狀態(tài)，則稱調(diào)度為一致性調(diào)度可串行化調(diào)度：如果一個(gè)調(diào)度等價(jià)于某個(gè)串行調(diào)度，則該調(diào)度稱為可串行化調(diào)度。也就是說，該調(diào)度可以通過一系列非沖突動(dòng)作的交換操作使其成為串行調(diào)度5、能夠描述死鎖發(fā)生的四個(gè)必要條件：會(huì)考試互斥條件：事務(wù)請(qǐng)求對(duì)資源的獨(dú)占控制等待條件：事務(wù)已持有分配給它的資源，又去申請(qǐng)并等待別的資源非搶占條件：直到資源被持有它的事務(wù)釋放前，不可能將資源強(qiáng)制從持有它的事務(wù)奪去循環(huán)等待條件：存在事務(wù)互相等待的等待圈6、能夠列舉并發(fā)控制算法悲觀并發(fā)控制法和樂觀并發(fā)控制法悲觀并發(fā)控制法有基于封鎖的算法、基于時(shí)標(biāo)排序的算法和混合算法。樂觀的方法也可分為基于封鎖或基于時(shí)標(biāo)排序的算法。第六章分布式數(shù)據(jù)庫中的可靠性1、理解可靠性和可用性的含義與關(guān)系可靠性：指數(shù)據(jù)庫在一給定時(shí)間間隔內(nèi)不產(chǎn)生任何失敗的概率。它強(qiáng)調(diào)數(shù)據(jù)庫的正確性，要求數(shù)據(jù)庫正確運(yùn)行。通常用來描述不可修復(fù)的系統(tǒng)?？捎眯裕簭?qiáng)調(diào)的是當(dāng)需要訪問數(shù)據(jù)庫時(shí)，它是可用的。指在給定的時(shí)間點(diǎn)系統(tǒng)可以正常運(yùn)行的概率。通常用于描述那些可以修復(fù)的系統(tǒng)。兩者關(guān)系：通常認(rèn)為構(gòu)建可用性的系統(tǒng)比可靠性的系統(tǒng)容易。兩者是統(tǒng)一的，可靠性高的系統(tǒng)可用性自然是好的。兩者又是矛盾的，增加錯(cuò)誤風(fēng)險(xiǎn)的情況下，可提高可用性;采用太謹(jǐn)慎的策略會(huì)降低可用性2、理解兩階段提交協(xié)議如何轉(zhuǎn)為三階段提交協(xié)議2PC中的狀態(tài)：C（提交）狀態(tài)是可提交狀態(tài)，其它為不可提交狀態(tài)。Ready狀態(tài)是不可提交狀態(tài)。Wait狀態(tài)是不可提交狀態(tài)。它們都侵犯了非阻斷協(xié)議的充要條件，從而考慮改變2PC,使其滿足非阻斷協(xié)議條件。在Wait和mit之間，或者在Ready和mit之間加入另一種狀態(tài)作為緩沖狀態(tài)，從而有了3PC協(xié)議3、掌握