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

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

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

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

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