分布式數(shù)據(jù)庫中垂直分片算法研究.pdf

1、計(jì)算機(jī)網(wǎng)絡(luò)的日益發(fā)展和普及以及跨地域分布的企業(yè)組織機(jī)構(gòu)使得數(shù)據(jù)的存儲(chǔ)和應(yīng)用越來越分布化。分布式數(shù)據(jù)庫(Distributed Database)技術(shù)就是在這種環(huán)境下應(yīng)運(yùn)而生的。基于這種技術(shù)的系統(tǒng)可靠性、可用性和時(shí)間響應(yīng)方面較傳統(tǒng)的集中式數(shù)據(jù)庫系統(tǒng)有更多的優(yōu)越性，因此在實(shí)際中有著更廣泛的應(yīng)用。 在分布式數(shù)據(jù)庫應(yīng)用中片段劃分是一個(gè)非常重要的問題，它直接影響后續(xù)工作中的數(shù)據(jù)分配，進(jìn)而影響系統(tǒng)的最終運(yùn)行效率和可靠性。 因?yàn)榉植际?/p>

2、數(shù)據(jù)庫系統(tǒng)中事務(wù)通常情況下并不是存取關(guān)系中的所有數(shù)據(jù)，而是存取關(guān)系的子集，因此，分布式數(shù)據(jù)庫系統(tǒng)就存在數(shù)據(jù)的劃分問題，即數(shù)據(jù)的邏輯分割(分片)問題。通過將關(guān)系中的數(shù)據(jù)劃分成若干個(gè)不相交的子集，可以減少事務(wù)的存取代價(jià)。分布式數(shù)據(jù)庫設(shè)計(jì)的主要目標(biāo)之一就是數(shù)據(jù)處理的本地化，即將關(guān)系中的數(shù)據(jù)分成若干個(gè)互不重疊的子集(垂直分片的主鍵除外)，然后再按照一定的分配策略將各個(gè)片段分配到相應(yīng)的站點(diǎn)上，這樣使得數(shù)據(jù)盡可能存放在對(duì)它們有存取要求的事務(wù)所在的站

3、點(diǎn)上，從而減少遠(yuǎn)程訪問所需的通信代價(jià)，并且通過分片和分配，可以并發(fā)執(zhí)行事務(wù)。 數(shù)據(jù)分片的基本類型包括水平分片和垂直分片兩種方式，水平分片是將關(guān)系中的元組劃分為若干個(gè)不相交的子集，而垂直分片則是將關(guān)系中的屬性劃分為若干個(gè)不相關(guān)的子集，本文僅討論數(shù)據(jù)垂直分片的問題。 怎樣合理地對(duì)關(guān)系中的屬性劃分，這是數(shù)據(jù)垂直分片設(shè)計(jì)要考慮的根本問題。數(shù)據(jù)垂直分片問題對(duì)提高整個(gè)應(yīng)用系統(tǒng)運(yùn)行效率、數(shù)據(jù)的可用性、DDB的效率和可靠性都有很大的影響

4、。如何使關(guān)系劃分得當(dāng)，使整個(gè)系統(tǒng)的運(yùn)行效率提高，國內(nèi)外專家和學(xué)者一直致力于基于分布式數(shù)據(jù)庫的數(shù)據(jù)垂直分片的研究。由于其復(fù)雜性，一直還沒有找到一個(gè)兼顧代價(jià)和性能的最優(yōu)通用的數(shù)據(jù)垂直分片方法。 雖然大量的研究學(xué)者也提出了一些分片模型和算法，但是大多數(shù)模型和算法非常復(fù)雜難于理解或者計(jì)算工作量太大，因而很難應(yīng)用于實(shí)際環(huán)境。本論文主要在現(xiàn)有的研究基礎(chǔ)上，分析總結(jié)各類垂直分片算法的優(yōu)缺點(diǎn)和局限性，主要對(duì)文獻(xiàn)<'[7]>中提出的基于事務(wù)的垂直

5、分片算法的不完善之處進(jìn)行擴(kuò)充改進(jìn)，提出了一種分片過程中計(jì)算節(jié)點(diǎn)估算代價(jià)的方法。該算法首先歸納出垂直分片算法所需的統(tǒng)計(jì)信息，然后確定以事務(wù)對(duì)磁盤的I/O次數(shù)為代價(jià)公式。 算法第一步是事務(wù)一屬性矩陣的獲取，通過對(duì)從后臺(tái)數(shù)據(jù)庫表中讀取的事務(wù)查詢語句的動(dòng)態(tài)分析，獲取每個(gè)事務(wù)存取的屬性集；第二步就是在此基礎(chǔ)上進(jìn)行分片工作，按照事務(wù)的訪問頻率依次選擇每一個(gè)事務(wù)，構(gòu)造當(dāng)前節(jié)點(diǎn)的T分片(從根結(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑所包含事務(wù)存取的所有屬性)，計(jì)算該