基于序列化的高效XML查詢算法.pdf

1、由于可擴展標記語言(eXtensibleMarkupLanguage,XML)具有結(jié)構(gòu)簡單、自表達、可擴展性強等諸多優(yōu)點,近幾年越來越多的企業(yè)和互聯(lián)網(wǎng)應(yīng)用使用XML作為數(shù)據(jù)表示、數(shù)據(jù)存儲和數(shù)據(jù)交換的格式。在所有XML相關(guān)的應(yīng)用中,如何進行XML數(shù)據(jù)上的查詢處理則是工業(yè)界和學術(shù)界最為關(guān)注的課題之一。特別是如何回答海量XML文檔上的結(jié)構(gòu)化查詢(StructuredQuery)請求,一直是研究的熱點問題。現(xiàn)有的很多查詢算法,都是通過分解-連接

2、(Split-Join)操作的方式,把復雜的結(jié)構(gòu)查詢拆成若干個簡單路徑查詢分別處理,并把中間結(jié)果連接起來得到最終結(jié)果的方法。但是,這類方法往往效率不高,主要原因在于復雜查詢拆成多個簡單路徑查詢,分別處理這些簡單路徑查詢所得到的中間結(jié)果集往往較大,多個集合的連接操作更是需要耗費大量的時間,所以連接操作往往成為整個查詢系統(tǒng)的性能瓶頸。雖然通過設(shè)計一些索引結(jié)構(gòu)和堆棧操作,能夠有效地提高連接操作的性能,但無法從根本上解決結(jié)構(gòu)連接(Structu

3、redJoin)的性能瓶頸問題?；谛蛄谢牟樵兎椒◤膹氐妆苊膺B接操作的目的出發(fā),通過把XML文檔和結(jié)構(gòu)化查詢請求轉(zhuǎn)換成符合特定格式的序列,并且通過序列匹配的方式來回答結(jié)構(gòu)化查詢,從而把復雜的結(jié)構(gòu)查詢作為一個整體進行處理,避免連接操作,提高了系統(tǒng)的查詢性能。然而,由于XML文檔的半結(jié)構(gòu)數(shù)據(jù)特性和序列的一維數(shù)據(jù)特性之間的不兼容性,現(xiàn)有基于序列化的查詢系統(tǒng)往往不能達到最優(yōu)的性能。本文提出了一種新的基于序列化的XML查詢算法——LEO方法,該

4、方法通過深入分析序列化方法中的幾個基本問題,提出了兩個重要的概念:靈活地序列化XML文檔和靈活地進行查詢序列匹配的策略。首先,在序列化過程中,本文提出了一種靈活的序列化策略,該策略通過對文檔進行適當?shù)木幋a,以支持對所得LEO序列中的元素進行任意排列的操作,從而可以按照文檔集中各元素出現(xiàn)的頻率對序列元素進行排列,使得所得各序列之間具有最長的共有前綴,以縮小所建立的trie-樹索引的空間耗費。本文提出了一種泛化編碼技術(shù),通過對文檔集進行適當

5、地預處理并建立一棵超樹,以擴展范圍編碼得到序列化步驟中必須的三元組編碼。泛化編碼技術(shù)是LEO序列化步驟中最關(guān)鍵的一個部分。其次,對于查詢過程中的序列匹配算法,本文提出了一種靈活的匹配策略,該策略摒棄現(xiàn)有序列化方法中自左至右的匹配順序,而是根據(jù)查詢序列中各元素的選擇度決定匹配的順序,從而解除了序列順序和匹配順序的耦合性。在此基礎(chǔ)上,我們通過預處理查詢請求,制定最優(yōu)的查詢計劃(QueryPlan),保證整個查詢過程中的搜索空間達到最小,最終

6、取得最優(yōu)的查詢性能。通過以上兩種新的文檔序列化策略和查詢序列匹配算法,本文提出的LEO方法能夠高效地處理各種查詢。通過實驗比較,在不同的標準數(shù)據(jù)集上對多種查詢請求進行測試,LEO序列化方法比現(xiàn)有的其它序列化方法在查詢時間和磁盤I/O操作上都有了很大的性能提高;而同樣地,在比較多個序列化的索引結(jié)構(gòu)時,LEO方法中所建立的索引結(jié)構(gòu)也具有最優(yōu)的空間性能。另外,與其他非序列化的基于磁盤的XML索引方法相比,本文提出的索引和查詢也都有更優(yōu)的表現(xiàn)。