- 相關(guān)推薦
XML路徑表達(dá)式的查詢優(yōu)化技術(shù)
摘要：XML查詢語(yǔ)言的共同特點(diǎn)是利用路徑表達(dá)式來(lái)導(dǎo)航XML文檔的查詢并返回指定路徑所能訪問(wèn)到的節(jié)點(diǎn)集，因此路徑表達(dá)式的查詢優(yōu)化是XML數(shù)據(jù)庫(kù)查詢優(yōu)化的關(guān)鍵，本文詳細(xì)分析了當(dāng)前路徑表達(dá)式查詢的幾種優(yōu)化技術(shù)，指出了它們要解決的關(guān)鍵問(wèn)題和主要技術(shù)特點(diǎn)。
1 基本概念
1.1 XML數(shù)據(jù)模型和XML數(shù)據(jù)模式
一個(gè)XML文檔樹是一個(gè)有序標(biāo)簽樹(如果考慮元素之間的應(yīng)用關(guān)系則以XML文檔的基本結(jié)構(gòu)為圖)，每個(gè)節(jié)點(diǎn)與一個(gè)元素或值(文本)相對(duì)應(yīng)，邊表示元素和子元素(或值)之間的嵌套關(guān)系。XML文檔的數(shù)據(jù)模式是一個(gè)有向圖，它為XML數(shù)據(jù)提供完整性約束。
1.2 XML數(shù)據(jù)的編碼方法
到目前為止處理路徑表達(dá)式查詢有兩種方法：一種是基于樹遍歷的方法，另一種不遍歷文檔樹就可以快速?zèng)Q定節(jié)點(diǎn)之間結(jié)構(gòu)關(guān)系的方法，元素之間結(jié)構(gòu)關(guān)系的確定主要依賴于有效的XML節(jié)點(diǎn)編碼方法。
1.2.1 基于區(qū)域的編碼方案
目前，最常用的編碼方法是區(qū)域編碼方法，最先使用區(qū)域編碼確定樹節(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系的是Dietz。它給每個(gè)節(jié)點(diǎn)賦予一個(gè)(pre,post)編碼，其中，pre是節(jié)點(diǎn)的前序遍歷值，post是節(jié)點(diǎn)的后序遍歷值，對(duì)于任意兩個(gè)不同的節(jié)點(diǎn)x和y，x是y的一個(gè)祖先當(dāng)且僅當(dāng)x.pre 文獻(xiàn)。給每個(gè)節(jié)點(diǎn)賦予一個(gè)(start,end)編碼，一個(gè)節(jié)點(diǎn)的start和end值是該元素的開始和結(jié)尾的絕對(duì)物理或邏輯位移，如果一個(gè)節(jié)點(diǎn)的編碼所覆蓋的區(qū)域被另一個(gè)節(jié)點(diǎn)的編碼所覆蓋的區(qū)域完全包含，則這個(gè)節(jié)點(diǎn)是另一個(gè)節(jié)點(diǎn)的后代節(jié)點(diǎn)。為適用于多個(gè)文檔查詢和父子關(guān)系的確定，還可以將元素的編碼擴(kuò)展為(D，cid,start,end,levd)，Docid是文檔的標(biāo)識(shí)符，Level是節(jié)點(diǎn)在文檔樹中的層數(shù)。文獻(xiàn)提出一種類似于區(qū)域編碼方案——擴(kuò)展的前序和后代范圍編碼，其目是的為了支持?jǐn)?shù)據(jù)的動(dòng)態(tài)插入和刪除，每個(gè)節(jié)點(diǎn)被賦予一個(gè)(order，size)，order是節(jié)點(diǎn)的前序遍歷序號(hào)。size表示節(jié)點(diǎn)所覆蓋的范圍，它可以是任意一個(gè)大于該節(jié)點(diǎn)后代節(jié)點(diǎn)總數(shù)的整數(shù)值。
除了區(qū)域編碼以外還有另外一種相對(duì)區(qū)域編碼方，每個(gè)節(jié)點(diǎn)被賦予一個(gè)到其父節(jié)點(diǎn)的相對(duì)位移。這種編碼可以轉(zhuǎn)換成區(qū)域編碼，其主要缺點(diǎn)是為了確定節(jié)點(diǎn)的絕對(duì)位置查詢代價(jià)沿著查詢路徑從祖先節(jié)點(diǎn)到被查詢節(jié)點(diǎn)逐步增加。
1.2.2 基于前綴的編碼方法
不同于區(qū)域編碼方法，基于前綴的編碼方式保存路徑信息。在這種編碼方法中祖先后代關(guān)系和前綴子串的包含關(guān)系相對(duì)應(yīng)。文獻(xiàn)提出了K-ary編碼，該方法通過(guò)增加虛節(jié)點(diǎn)把文檔看成一個(gè)完全k分樹，根據(jù)樹的層次遍歷順序給樹中的節(jié)點(diǎn)編碼，在這種編碼方法中節(jié)點(diǎn)的編碼帶有文檔的結(jié)構(gòu)信息。類似于K-ary編碼，文獻(xiàn)提出了一種特殊的PBiTree編碼，這種編碼方案是通過(guò)增加虛擬節(jié)點(diǎn)將文檔樹嵌入到一個(gè)完全二叉樹中。這種編碼的優(yōu)點(diǎn)是可以利用完全二叉樹的優(yōu)良特性來(lái)計(jì)算節(jié)點(diǎn)間的結(jié)構(gòu)關(guān)系。PBiTree中的虛擬節(jié)點(diǎn)起著—個(gè)占位符的作用，這樣有利于數(shù)據(jù)的動(dòng)態(tài)更新，同時(shí)它們對(duì)查詢性能也有一定的影響。
1.3 XML數(shù)據(jù)索引
為了提高查詢的性能，許多專家和學(xué)者都致力于索引的研究與開發(fā)。目前提出的索引有兩種：一種是基于結(jié)構(gòu)連接的索引；另一種是基于路徑的索引�；诮Y(jié)構(gòu)連接的索引M首先將文檔樹中的所有節(jié)點(diǎn)以的形式進(jìn)行分解后存儲(chǔ)在多張表中。這樣，當(dāng)處理查詢//E1/E2/……/En時(shí)，對(duì)包含Ei(i=-1，…，m)的表按次序要進(jìn)行多次連接操作得到查詢結(jié)果�；诼窂降乃饕齽t是以文檔樹為基本數(shù)據(jù)結(jié)構(gòu)，按照路徑將樹中的節(jié)點(diǎn)進(jìn)行拆分、合并等操作，索引結(jié)構(gòu)仍然是一個(gè)樹，使用這種索引處理查詢//El/E2/……/En時(shí)，基本上要遍歷整個(gè)索引樹才能得到結(jié)果。文獻(xiàn)提出了一種自適應(yīng)的路徑索引結(jié)構(gòu)，這種索引利用頻繁使用的路徑來(lái)改善查詢性能，并且這種索引可以隨著查詢工作量的不同而動(dòng)態(tài)改變，從而有效地縮小了索引文件。
2 路徑表達(dá)式的查詢處理方式
2.1 樹遍歷方法
最樸素的路徑訪問(wèn)方法是樹遍歷的方法：一般采用自頂向下的方式遍歷文檔樹，使用該方法進(jìn)行查詢時(shí)需要遍歷某元素通往葉子節(jié)點(diǎn)的所有可能路徑。為了減少樹遍歷的代價(jià)引入自底向上的方法，首先查找符合謂詞條件的所有原子節(jié)點(diǎn)，然后再尋找它們的父節(jié)點(diǎn)。這種方法一般情況下比較簡(jiǎn)單、耗時(shí)較少。但對(duì)于符合謂詞條件的節(jié)點(diǎn)數(shù)目很大而符合路徑表達(dá)式的路徑很少時(shí)，這種遍歷方式的代價(jià)可能會(huì)高于自頂向下方式。一種折中的方法是同時(shí)按自頂向下和自底向上兩種方法進(jìn)行遍歷，最后在路徑的某個(gè)中間位置匯合，從而得到查詢結(jié)果。當(dāng)路徑上某節(jié)點(diǎn)的扇人度(在文檔中的)很大而符合謂詞條件的原子節(jié)點(diǎn)很少時(shí)，該方法可以達(dá)到最優(yōu)。在這種方法中優(yōu)化路徑表達(dá)式查詢的一個(gè)中心思想是設(shè)法縮小查詢范圍。使得不需要遍歷整個(gè)樹就可以獲得符合條件的查詢結(jié)果。
2.2 路徑分解法
這一種方法是目前用的比較多的，它的基本思路是將復(fù)雜的查詢路徑分解成簡(jiǎn)單路徑，簡(jiǎn)單路徑可以是由一個(gè)元素、一個(gè)謂詞條件或一個(gè)元素加一個(gè)謂詞條件，還可以是由兩個(gè)元素組成的路徑。首先計(jì)算這些簡(jiǎn)單路徑表達(dá)式，再將每個(gè)簡(jiǎn)單路徑表達(dá)式的計(jì)算結(jié)果連接起來(lái)。其本質(zhì)確定節(jié)點(diǎn)間的結(jié)構(gòu)關(guān)系(祖先后代或父子關(guān)系)，因此這種操作叫結(jié)構(gòu)連接。像關(guān)系數(shù)據(jù)庫(kù)中的連接運(yùn)算一樣，結(jié)構(gòu)連接操作的代價(jià)非常昂貴，結(jié)構(gòu)連接又是查詢處理的核心操作，因此在這種查詢處理模式中查詢優(yōu)化的關(guān)鍵開發(fā)高效的結(jié)構(gòu)連接算法，同時(shí)結(jié)構(gòu)連接的順序也極大地影響著結(jié)構(gòu)連接運(yùn)算的性能。
3 路徑表達(dá)查詢優(yōu)化的一般方法
3.1 路徑表達(dá)式的重寫優(yōu)化
路徑表達(dá)式重寫優(yōu)化的基本思想將復(fù)雜的、高代價(jià)的查詢路徑表達(dá)式轉(zhuǎn)換為簡(jiǎn)單的、低代價(jià)的等價(jià)路徑表達(dá)式。查詢重寫技術(shù)的一般特征可以概括如下：①重寫優(yōu)化發(fā)生在查詢解析之后查詢計(jì)劃生成之前；②重寫優(yōu)化是將一個(gè)查詢轉(zhuǎn)換為一個(gè)等價(jià)的查詢；③要使用啟發(fā)式方法選擇查詢轉(zhuǎn)換方法，被選擇的查詢轉(zhuǎn)換方法能改善大多數(shù)查詢的執(zhí)行性能；④查詢重寫的依據(jù)通常是查詢本身獲得信息、完整性約束或數(shù)據(jù)模式，而不考慮數(shù)據(jù)以及數(shù)據(jù)的存儲(chǔ)方式和數(shù)據(jù)的統(tǒng)計(jì)信息。
3.1.1 根據(jù)結(jié)構(gòu)約束刪除冗余
最先研究路徑表達(dá)式最小化問(wèn)題是和，文獻(xiàn)中只對(duì)不包括祖先后代邊“//”的簡(jiǎn)單路徑表達(dá)式進(jìn)行最小化，而文獻(xiàn)研究了不包含*的路徑表達(dá)式的最小化問(wèn)題。其基本思想是將查詢中的路徑表示為查詢模式樹，根據(jù)給定的結(jié)構(gòu)約束，逐步查詢模式樹中冗余路徑節(jié)點(diǎn)或冗余謂詞。
文獻(xiàn)對(duì)包含全部操作符{/,//[],*}的路徑表達(dá)式的最小化進(jìn)行了研究，算法的基本思想是遞歸地從原模式樹中查找最小子模式并連接它們，證明了這是一個(gè)NP完全問(wèn)題，同時(shí)，它還指出：在對(duì)路徑表達(dá)式分支個(gè)數(shù)和形狀加以一定限制的情況下。表達(dá)式最小化算法的復(fù)雜度可以達(dá)到多項(xiàng)式級(jí)。很顯然，在實(shí)際查詢中用戶不可能將查詢限制成一種特定形式的路徑表達(dá)式。
3.1.2 刪除路徑表達(dá)式中的固有冗余
文獻(xiàn)中提出了兩種優(yōu)化策略：縮短路徑策略和補(bǔ)路徑策略。縮短路徑法是試圖用等價(jià)相對(duì)路徑取代絕對(duì)路徑，縮短路徑表達(dá)式本身，從而降低查詢的代價(jià)。這種方法利用元素的唯一訪問(wèn)路徑、唯一父元素、關(guān)鍵祖先等幾個(gè)概念把絕對(duì)路徑表達(dá)式轉(zhuǎn)換為相對(duì)路徑表達(dá)式，這樣路徑表達(dá)式的查詢匹配就不再?gòu)母亻_始，從而縮短了路徑表達(dá)式查詢時(shí)間。如假定某查詢的絕對(duì)路徑表達(dá)式EIClE2C2E3…CnEn，如果UAP(E2)=C1E2，則可以用C2E3…CnEn代替EIClE2C2E3…CnEn。這里的關(guān)鍵問(wèn)題確定唯一訪問(wèn)路徑、唯一父元素和關(guān)鍵祖先。
在補(bǔ)路徑法中定義了互補(bǔ)路徑，相對(duì)于某元素的互補(bǔ)路徑是等價(jià)的，這樣就可以用補(bǔ)路徑替換原查詢。其基本思想是把用戶書寫的復(fù)雜的、代價(jià)高的查詢路徑表達(dá)式用一些簡(jiǎn)單的、查詢代價(jià)低的互補(bǔ)路徑表達(dá)式來(lái)替代。這種策略的目的是減少連接次數(shù)和連接結(jié)果集的大小，因此怎樣確定查詢路徑的互補(bǔ)路徑并進(jìn)行代價(jià)估算成為其關(guān)鍵問(wèn)題。
3.1.3 刪除非冗余的通配符步
當(dāng)在某條路徑中一個(gè)元素名未知或無(wú)關(guān)緊要時(shí)通常采用通配符。進(jìn)行路徑匹配時(shí)，通配符需要和當(dāng)前節(jié)點(diǎn)的所有子節(jié)點(diǎn)(或后代節(jié)點(diǎn))匹配，由此可見，通配符的計(jì)算代價(jià)相當(dāng)高。文獻(xiàn)中提出消除路徑表達(dá)式中的非冗余的通配符步，從而降低路徑表達(dá)式的計(jì)算代價(jià)。為了消除路徑中的通配符步，引入一個(gè)layer∞ds重寫有通配符的路徑表達(dá)式查詢，在形如child：：*/…/child*/ehild1：的查詢中，layer axis可以用來(lái)替代所有路徑通配步，從而把查詢等價(jià)地表示為L(zhǎng)i::t1。這樣一方面縮短了路徑表達(dá)式，另一方面使得系統(tǒng)僅僅加載與查詢相關(guān)的XML數(shù)據(jù)，從而大大的優(yōu)化了查詢。
3.2 基于樹遍歷的路徑查詢優(yōu)化
基于樹遍歷的查詢優(yōu)化要使用路徑索引縮小搜索范圍，這種優(yōu)化方法的關(guān)鍵問(wèn)題是要設(shè)計(jì)出有效合理的便于維護(hù)的路徑索引。DataGuides算得上是最早的路徑索引，也是路徑索引中最有影響力的代表。它采用了一種標(biāo)簽路徑合并策略對(duì)文檔結(jié)構(gòu)進(jìn)行縮減，DmGuides中的每個(gè)節(jié)點(diǎn)都有一個(gè)目標(biāo)集。這個(gè)目標(biāo)集記錄了通過(guò)這個(gè)標(biāo)簽路徑可訪問(wèn)到的數(shù)據(jù)節(jié)點(diǎn)，這樣執(zhí)行一個(gè)路徑查詢時(shí)只需要在Dataguides中查找該路徑，獲得的目標(biāo)集即為滿足條件的查詢結(jié)果。當(dāng)文檔的數(shù)據(jù)結(jié)構(gòu)比較規(guī)則時(shí)Dataguides能很好地縮減文檔的結(jié)構(gòu)，從而極大地改善查詢的性能。
文獻(xiàn)中提出了一種使用圖模式(Graph Schemas)縮小查詢范圍的方法。這里的圖模式也起著DataGuides的作用，但是它采用了合并同類邊的策略。圖模式中的節(jié)點(diǎn)叫狀態(tài)，每個(gè)狀態(tài)都對(duì)應(yīng)一個(gè)狀態(tài)擴(kuò)展，集即該狀態(tài)在文檔中所對(duì)應(yīng)的節(jié)點(diǎn)集。在此基礎(chǔ)上文檔提出了兩種查詢優(yōu)化策略：剪切查詢和使用狀態(tài)擴(kuò)展集重寫查詢。剪切查詢是將查詢的搜索限制在僅與查詢結(jié)果有關(guān)的子樹上，后者則是將原查詢改寫為在圖模式上的查詢，兩種方法都使用非確定自動(dòng)機(jī)為剪切工具。
不同于以上兩種方式，文獻(xiàn)提出了一種新的路徑查詢方法，該方法將XML文檔中的文本數(shù)據(jù)抽取出來(lái)單獨(dú)存儲(chǔ)，這樣文檔樹僅由帶標(biāo)簽的元素或?qū)傩越M成，這樣的結(jié)構(gòu)被叫做文檔的骨架(skeleton)。為了使大的文檔的骨架盡可能地放入內(nèi)存中。這個(gè)樹骨架進(jìn)一步通過(guò)共享的公共子樹被壓縮，被壓縮的樹骨架的每個(gè)節(jié)點(diǎn)與未壓縮樹的一組節(jié)點(diǎn)相對(duì)應(yīng)，他們之間的對(duì)應(yīng)關(guān)系用雙向相似關(guān)系表示。
3.3 基于路徑分解的查詢優(yōu)化
結(jié)構(gòu)連接是基于節(jié)點(diǎn)在NML文檔中的位置表示確定XML節(jié)點(diǎn)間的包含關(guān)系。給定一個(gè)祖先(或父)節(jié)點(diǎn)集合A和一個(gè)后代(或子)節(jié)點(diǎn)集合D，結(jié)構(gòu)連接操作的任務(wù)就是要用高效的方法找到所有的節(jié)點(diǎn)對(duì)(ai,di)，其中ai是di的祖先(或父親)，ai、di分別是A、D中的元素。A、D可能來(lái)自索引掃描也可能是某個(gè)計(jì)算的中間結(jié)果。結(jié)構(gòu)連接運(yùn)算的代價(jià)非常昂貴，因此結(jié)構(gòu)連接算法的好壞直接影響著查詢的效率，同時(shí)結(jié)構(gòu)連接的順序也極大地影響著結(jié)構(gòu)連接運(yùn)算的性能。
3.3.1 結(jié)構(gòu)連接算法
目前，已經(jīng)提出的結(jié)構(gòu)連接算法有兩種：排序合并[2，3,7,19]和劃分方法。排序合并法的主要特點(diǎn)是：①節(jié)點(diǎn)采用區(qū)域編碼確定節(jié)點(diǎn)間的結(jié)構(gòu)關(guān)系；②要求輸入的數(shù)據(jù)集有序或在數(shù)據(jù)集上建立索引；③為了快速定位某類節(jié)點(diǎn)，可以利用元素索引、路徑索引或值索引。文獻(xiàn)中提出了一種多謂詞合并連接算法(MP-MGJN)，該算法需要多次掃描數(shù)據(jù)集；文獻(xiàn)中提出的ε－jion、εA－lion和κe-iion算法存在同樣的缺點(diǎn)。文獻(xiàn)提出了兩類算法：樹合并(Tree-Merge)算法和堆棧合并(stack-Tree)算法，前者是傳統(tǒng)數(shù)據(jù)庫(kù)合并連接的推廣，后者是一種基于堆棧的結(jié)構(gòu)連接的算法，通過(guò)內(nèi)存中保留一個(gè)棧結(jié)構(gòu)來(lái)達(dá)到對(duì)輸入數(shù)據(jù)的一次掃描的目標(biāo)。文獻(xiàn)對(duì)Stack-Tree算法做了改進(jìn)，利用附加的索引跳過(guò)不需要參加連接的節(jié)點(diǎn)。堆棧合并算法(stack-Tree)既可以應(yīng)用在XML的關(guān)系存儲(chǔ)系統(tǒng)中，也可以應(yīng)用在原生XML系統(tǒng)中。
除了基于區(qū)域編碼的結(jié)構(gòu)連接算法，文獻(xiàn)目中還針對(duì)它提出的PBiTree編碼提出了基于劃分的結(jié)構(gòu)連接算法，其劃分策略有兩種：水平劃分和垂直劃分，分別按節(jié)點(diǎn)在樹中的高度和所在分支對(duì)數(shù)據(jù)集合的劃分，這種算法不要求輸入的數(shù)據(jù)有序或建立索引。結(jié)構(gòu)連接算法在一定程度上依賴于節(jié)點(diǎn)的編碼方法，目前普遍使用的編碼方法是區(qū)域編碼。由于使用區(qū)域編碼可以快速確定節(jié)點(diǎn)間的包含關(guān)系，開發(fā)高效基于區(qū)域編碼的結(jié)構(gòu)連接算法仍然是一個(gè)值得研究的課題。
3.3.2 結(jié)構(gòu)連接的順序選擇
在結(jié)構(gòu)連接中，無(wú)論采用什么樣的結(jié)構(gòu)連接算法，結(jié)構(gòu)連接的順序極大地影響著結(jié)構(gòu)連接運(yùn)算的性能，文獻(xiàn)使用簡(jiǎn)單的代價(jià)估算模型提出了5種結(jié)構(gòu)連接的順序選擇算法。其基本思想是使用動(dòng)態(tài)規(guī)劃算法在整個(gè)解空間中搜索代價(jià)最小的連接計(jì)劃，當(dāng)連接節(jié)點(diǎn)過(guò)多時(shí)解空間會(huì)發(fā)生組合爆炸，使用動(dòng)態(tài)規(guī)劃算法進(jìn)行搜索將會(huì)變得非常緩慢。為了加速搜索速度，在動(dòng)態(tài)規(guī)劃算法中引入了各種不同的啟發(fā)式規(guī)則，這雖然極大地提高了搜索速度卻冒著一些可能丟失最優(yōu)解的風(fēng)險(xiǎn)。結(jié)構(gòu)連接順序選擇的目標(biāo)是用較小的代價(jià)獲得最優(yōu)的連接計(jì)劃，要實(shí)現(xiàn)這個(gè)目標(biāo)還有待于新的結(jié)構(gòu)連接順序選擇算法的提出。
4 總結(jié)
XML路徑表達(dá)式查詢優(yōu)化技術(shù)是XML查詢優(yōu)化的關(guān)鍵技術(shù)。文中概括了3種優(yōu)化技術(shù)。重寫優(yōu)化技術(shù)在查詢解析之后查詢計(jì)劃生成之前使用，其目的是消除路徑中的冗余步，把長(zhǎng)的查詢路徑變?yōu)榈葍r(jià)的短路徑，一方面在基于路徑分解查詢中減少連接次數(shù)和中間連接結(jié)果，另一方面在樹遍歷方法中也可以減少掃描的節(jié)點(diǎn)數(shù)，從而極大地優(yōu)化了查詢性能�；跇浔闅v的查詢優(yōu)化和基于路徑分解的查詢優(yōu)化則是在查詢計(jì)劃生成階段使用的。采用什么樣的優(yōu)化技術(shù)主要取決于路徑表達(dá)式的處理方法。節(jié)點(diǎn)編碼技術(shù)和結(jié)構(gòu)連接緊密相關(guān)，索引技術(shù)也是XML查詢優(yōu)化的關(guān)鍵技術(shù)，在這些優(yōu)化技術(shù)中很少使用到XML的數(shù)據(jù)模式(DTD或Schame)。在查詢中合理有效地使用數(shù)據(jù)模式將會(huì)給查詢優(yōu)化帶來(lái)一片新的天地。
【XML路徑表達(dá)式的查詢優(yōu)化技術(shù)】相關(guān)文章：
影視公司并購(gòu)重組的路徑與效應(yīng)08-21
民事審判錯(cuò)案的國(guó)家救濟(jì)路徑04-29
論我國(guó)消費(fèi)環(huán)境的優(yōu)化05-11
金融貿(mào)易結(jié)構(gòu)優(yōu)化研討05-30
企業(yè)法律風(fēng)險(xiǎn)防范體系建立的原因及實(shí)現(xiàn)路徑08-06
教育供給側(cè)改革下大學(xué)英語(yǔ)教改路徑論文04-28
變電站接地網(wǎng)優(yōu)化設(shè)計(jì)08-24
稅制改革、優(yōu)化與稅收征管均衡發(fā)展06-01