XML查詢最小化研究.pdf

1、隨著越來越多的XML數(shù)據(jù)被存儲(chǔ)到數(shù)據(jù)庫中，XML數(shù)據(jù)的查詢效率顯得越來越重要。XML查詢效率與很多因素有關(guān)，其中一個(gè)重要的因素就是查詢本身的復(fù)雜程度和大小。一般來說，查詢?cè)綇?fù)雜，查詢規(guī)模越大，查詢響應(yīng)時(shí)間越慢。因此，如何在保持查詢?cè)獾耐瑫r(shí)降低查詢規(guī)模，是一個(gè)非常有價(jià)值的研究問題。 本文研究了XML查詢的最小化問題，即如何在保持查詢?cè)獾幕A(chǔ)上將查詢規(guī)模降至最小的問題，本文對(duì)于XML一個(gè)常用片段上的查詢的最小化做了一個(gè)比較系統(tǒng)而

2、全面的研究。 文章首先定義了一類查詢，稱為樹模式查詢(TreePatternQuery,TPQ)。這類查詢定義在一個(gè)常見的XPath片段之上，該片段含有child軸、descendant軸、descendant-or-self軸、節(jié)點(diǎn)測(cè)試和謂詞，在后來的擴(kuò)充當(dāng)中，還使得謂詞中能夠包含選擇條件和連接條件，并可以具有多個(gè)輸出節(jié)點(diǎn)。定義在這個(gè)XPath片段之上的樹模式查詢能夠表示大部分常見的XPath查詢，還能表示很多的XQuery查

3、詢的主干，因而具有一定的代表性。 不同的樹模式查詢具有不同的特征，最小化的途徑和方法也不一樣。本文采用兩種方法來對(duì)樹模式查詢進(jìn)行最小化，分別是基于刪除的方法和基于改寫的方法，這兩種方法互為補(bǔ)充，可以對(duì)大部分樹模式查詢有效地進(jìn)行最小化。 首先研究了基于刪除的查詢最小化策略，這種策略基于模擬的概念，通過刪除查詢中的冗余節(jié)點(diǎn)來達(dá)到最小化的目的。文章先討論了不考慮完整性約束時(shí)的最小化問題，提出了具體的復(fù)雜度為P算法。接著引入四種

4、常見完整性約束：孩子約束、后裔約束、雙親約束和兄弟約束，當(dāng)約束存在時(shí)，查詢往往能夠進(jìn)一步最小化，但是問題更加復(fù)雜。本文利用兩種技術(shù)來處理約束，即chase和增強(qiáng)模擬，通過對(duì)約束的幾種典型組合進(jìn)行分析，總結(jié)出了關(guān)于約束處理的一些啟發(fā)式結(jié)論，而且得出，無論約束如何存在，所研究片段上的樹模式查詢都可以在P的時(shí)間內(nèi)最小化。 然后研究了基于改寫的查詢最小化策略。這種策略針對(duì)一類特殊的樹模式查詢，即謂詞中含有節(jié)點(diǎn)標(biāo)識(shí)連接條件的樹模式查詢，該

5、類查詢中查詢條件往往可以進(jìn)一步簡(jiǎn)化，但是通過基于刪除的最小化策略無法最小化。基于改寫的最小化策略通過改寫和合并查詢中的某些條件，來消除查詢中的冗余，能夠有效對(duì)這類查詢進(jìn)行最小化。提出三個(gè)步驟來對(duì)查詢進(jìn)行改寫：構(gòu)造關(guān)系圖——推理——重構(gòu)，并討論了實(shí)現(xiàn)時(shí)的算法問題。對(duì)于這種策略，也討論了約束的應(yīng)用，提出利用路徑約束來輔助改寫，具有很好的效果。 最后研究了常見完整性約束的產(chǎn)生問題，這個(gè)問題是查詢最小化問題及很多其它問題的基礎(chǔ)和補(bǔ)充。提