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