并行XML數(shù)據(jù)庫(kù)分片與查詢(xún)技術(shù)研究.pdf

1、由于XML在網(wǎng)絡(luò)上的廣泛應(yīng)用,它已經(jīng)成為Internet上新的數(shù)據(jù)交換標(biāo)準(zhǔn),同時(shí)也為數(shù)據(jù)庫(kù)科研工作者帶來(lái)了新的挑戰(zhàn).隨著XML數(shù)據(jù)規(guī)模急劇膨脹,查詢(xún)處理日趨復(fù)雜,單處理機(jī)環(huán)境由于I/O和主存限制,整體處理能力存在著極限.并行XML數(shù)據(jù)庫(kù)系統(tǒng)的出現(xiàn)為大型超大型XML文檔的高效處理提供了有效解決方案.在并行數(shù)據(jù)庫(kù)系統(tǒng)中,數(shù)據(jù)分片是影響并行數(shù)據(jù)庫(kù)整體性能的重要因素.一些研究結(jié)果表明,尤其在無(wú)共享體系結(jié)構(gòu)中,數(shù)據(jù)分片結(jié)果與并行數(shù)據(jù)庫(kù)系統(tǒng)性能是密

2、切相關(guān)的.并行數(shù)據(jù)庫(kù)研究者已經(jīng)提出了很多種經(jīng)典的數(shù)據(jù)分片策略.在并行關(guān)系數(shù)據(jù)庫(kù)中,主要有一維數(shù)據(jù)劃分方法和多維數(shù)據(jù)劃分方法,一維數(shù)據(jù)劃分方法包括Round-Robin,Hash,Range和Hybrid-Range-Partition,多維數(shù)據(jù)劃分方法包括k-d-B-Tree,hB-Tree和X-Tree等.在并行對(duì)象數(shù)據(jù)庫(kù)中,各對(duì)象之間通過(guò)指針任意引用,對(duì)象之間拓?fù)浣Y(jié)構(gòu)呈圖狀,因此并行對(duì)象數(shù)據(jù)庫(kù)中分片算法都是圖分片算法.該文首先介紹了

3、根據(jù)不同分片粒度,符合XML自身特點(diǎn)和XML查詢(xún)特點(diǎn)的并行數(shù)據(jù)庫(kù)物理分片策略:基于路徑模式的路徑實(shí)例平衡分片(Path Schema BasedPath Instances Balancing-PSPIB)策略,和攜帶父親信息的孩子節(jié)點(diǎn)輪循(NodeRound Robin-NRR)策略.PSPIB分片策略,以路徑模式為分片粒度,將XML文檔中屬于同一個(gè)路徑模式的路徑實(shí)例分配到并行系統(tǒng)的不同處理機(jī)上.NRR分片策略,以元素節(jié)點(diǎn)類(lèi)型為分片粒

4、度,根據(jù)元素節(jié)點(diǎn)類(lèi)型的定義將元素節(jié)點(diǎn)實(shí)例按照輪循的方式分配到不同處理機(jī)上.然后,我們提出了三種基于工作負(fù)載均衡的并行XML分片策略:元素工作量平衡分片算法,部分拷貝數(shù)據(jù)分片算法和基于工作負(fù)載均衡媒介節(jié)點(diǎn)數(shù)據(jù)分片策略.基于這幾種分片策略設(shè)計(jì)的并行XML查詢(xún)?cè)拖到y(tǒng),提供多種支持并行的索引結(jié)構(gòu),支持XQuery查詢(xún)語(yǔ)言.使用XMark Benchmark的大量測(cè)試結(jié)果表明,各種分片策略在不同的要求下具有良好的加速比和縮放比性能.同時(shí),在該文