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

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

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

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

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

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

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