XML路徑表達式的查詢優化技術

XML路徑表達式的查詢優化技術

　　摘要：XML查詢語言的共同特點是利用路徑表達式來導航XML文檔的查詢并返回指定路徑所能訪問到的節點集，因此路徑表達式的查詢優化是XML數據庫查詢優化的關鍵，本文詳細分析了當前路徑表達式查詢的幾種優化技術，指出了它們要解決的關鍵問題和主要技術特點。
　　
　　1　基本概念
　　
　　1.1　XML數據模型和XML數據模式
　　一個XML文檔樹是一個有序標簽樹(如果考慮元素之間的應用關系則以XML文檔的基本結構為圖)，每個節點與一個元素或值(文本)相對應，邊表示元素和子元素(或值)之間的嵌套關系。XML文檔的數據模式是一個有向圖，它為XML數據提供完整性約束。
　　1.2　XML數據的編碼方法
　　到目前為止處理路徑表達式查詢有兩種方法：一種是基于樹遍歷的方法，另一種不遍歷文檔樹就可以快速決定節點之間結構關系的方法，元素之間結構關系的確定主要依賴于有效的XML節點編碼方法。
　　1.2.1　基于區域的編碼方案
　　目前，最常用的編碼方法是區域編碼方法，最先使用區域編碼確定樹節點之間的結構關系的是Dietz。它給每個節點賦予一個(pre,post)編碼，其中，pre是節點的前序遍歷值，post是節點的后序遍歷值，對于任意兩個不同的節點x和y，x是y的一個祖先當且僅當x.pre　　文獻。給每個節點賦予一個(start,end)編碼，一個節點的start和end值是該元素的開始和結尾的絕對物理或邏輯位移，如果一個節點的編碼所覆蓋的區域被另一個節點的編碼所覆蓋的區域完全包含，則這個節點是另一個節點的后代節點。為適用于多個文檔查詢和父子關系的確定，還可以將元素的編碼擴展為(D，cid,start,end,levd)，Docid是文檔的標識符，Level是節點在文檔樹中的層數。文獻提出一種類似于區域編碼方案——擴展的前序和后代范圍編碼，其目是的為了支持數據的動態插入和刪除，每個節點被賦予一個(order，size)，order是節點的前序遍歷序號。size表示節點所覆蓋的范圍，它可以是任意一個大于該節點后代節點總數的整數值。
　　除了區域編碼以外還有另外一種相對區域編碼方，每個節點被賦予一個到其父節點的相對位移。這種編碼可以轉換成區域編碼，其主要缺點是為了確定節點的絕對位置查詢代價沿著查詢路徑從祖先節點到被查詢節點逐步增加。
　　1.2.2　基于前綴的編碼方法
　　不同于區域編碼方法，基于前綴的編碼方式保存路徑信息。在這種編碼方法中祖先后代關系和前綴子串的包含關系相對應。文獻提出了K-ary編碼，該方法通過增加虛節點把文檔看成一個完全k分樹，根據樹的層次遍歷順序給樹中的節點編碼，在這種編碼方法中節點的編碼帶有文檔的結構信息。類似于K-ary編碼，文獻提出了一種特殊的PBiTree編碼，這種編碼方案是通過增加虛擬節點將文檔樹嵌入到一個完全二叉樹中。這種編碼的優點是可以利用完全二叉樹的優良特性來計算節點間的結構關系。PBiTree中的虛擬節點起著—個占位符的作用，這樣有利于數據的動態更新，同時它們對查詢性能也有一定的影響。
　　1.3　XML數據索引
　　為了提高查詢的性能，許多專家和學者都致力于索引的研究與開發。目前提出的索引有兩種：一種是基于結構連接的索引；另一種是基于路徑的索引。基于結構連接的索引M首先將文檔樹中的所有節點以的形式進行分解后存儲在多張表中。這樣，當處理查詢//E1/E2/……/En時，對包含Ei(i=-1，…，m)的表按次序要進行多次連接操作得到查詢結果�；�于路徑的索引則是以文檔樹為基本數據結構，按照路徑將樹中的節點進行拆分、合并等操作，索引結構仍然是一個樹，使用這種索引處理查詢//El/E2/……/En時，基本上要遍歷整個索引樹才能得到結果。文獻提出了一種自適應的路徑索引結構，這種索引利用頻繁使用的路徑來改善查詢性能，并且這種索引可以隨著查詢工作量的不同而動態改變，從而有效地縮小了索引文件。
　　2　路徑表達式的查詢處理方式
　　
　　2.1　樹遍歷方法
　　最樸素的路徑訪問方法是樹遍歷的方法：一般采用自頂向下的方式遍歷文檔樹，使用該方法進行查詢時需要遍歷某元素通往葉子節點的所有可能路徑。為了減少樹遍歷的代價引入自底向上的方法，首先查找符合謂詞條件的所有原子節點，然后再尋找它們的父節點。這種方法一般情況下比較簡單、耗時較少。但對于符合謂詞條件的節點數目很大而符合路徑表達式的路徑很少時，這種遍歷方式的代價可能會高于自頂向下方式。一種折中的方法是同時按自頂向下和自底向上兩種方法進行遍歷，最后在路徑的某個中間位置匯合，從而得到查詢結果。當路徑上某節點的扇人度(在文檔中的)很大而符合謂詞條件的原子節點很少時，該方法可以達到最優。在這種方法中優化路徑表達式查詢的一個中心思想是設法縮小查詢范圍。使得不需要遍歷整個樹就可以獲得符合條件的查詢結果。
　　2.2　路徑分解法
　　這一種方法是目前用的比較多的，它的基本思路是將復雜的查詢路徑分解成簡單路徑，簡單路徑可以是由一個元素、一個謂詞條件或一個元素加一個謂詞條件，還可以是由兩個元素組成的路徑。首先計算這些簡單路徑表達式，再將每個簡單路徑表達式的計算結果連接起來。其本質確定節點間的結構關系(祖先后代或父子關系)，因此這種操作叫結構連接。像關系數據庫中的連接運算一樣，結構連接操作的代價非常昂貴，結構連接又是查詢處理的核心操作，因此在這種查詢處理模式中查詢優化的關鍵開發高效的結構連接算法，同時結構連接的順序也極大地影響著結構連接運算的性能。
　　
　　3　路徑表達查詢優化的一般方法
　　
　　3.1　路徑表達式的重寫優化
　　路徑表達式重寫優化的基本思想將復雜的、高代價的查詢路徑表達式轉換為簡單的、低代價的等價路徑表達式。查詢重寫技術的一般特征可以概括如下：①重寫優化發生在查詢解析之后查詢計劃生成之前；②重寫優化是將一個查詢轉換為一個等價的查詢；③要使用啟發式方法選擇查詢轉換方法，被選擇的查詢轉換方法能改善大多數查詢的執行性能；④查詢重寫的依據通常是查詢本身獲得信息、完整性約束或數據模式，而不考慮數據以及數據的存儲方式和數據的統計信息。
　　3.1.1　根據結構約束刪除冗余
　　最先研究路徑表達式最小化問題是和，文獻中只對不包括祖先后代邊“//”的簡單路徑表達式進行最小化，而文獻研究了不包含*的路徑表達式的最小化問題。其基本思想是將查詢中的路徑表示為查詢模式樹，根據給定的結構約束，逐步查詢模式樹中冗余路徑節點或冗余謂詞。
　　文獻對包含全部操作符{/,//[],*}的路徑表達式的最小化進行了研究，算法的基本思想是遞歸地從原模式樹中查找最小子模式并連接它們，證明了這是一個NP完全問題，同時，它還指出：在對路徑表達式分支個數和形狀加以一定限制的情況下。表達式最小化算法的復雜度可以達到多項式級。很顯然，在實際查詢中用戶不可能將查詢限制成一種特定形式的路徑表達式。

　　3.1.2　刪除路徑表達式中的固有冗余
　　文獻中提出了兩種優化策略：縮短路徑策略和補路徑策略�？s短路徑法是試圖用等價相對路徑取代絕對路徑，縮短路徑表達式本身，從而降低查詢的代價。這種方法利用元素的唯一訪問路徑、唯一父元素、關鍵祖先等幾個概念把絕對路徑表達式轉換為相對路徑表達式，這樣路徑表達式的查詢匹配就不再從根元素開始，從而縮短了路徑表達式查詢時間。如假定某查詢的絕對路徑表達式EIClE2C2E3…CnEn，如果UAP(E2)=C1E2，則可以用C2E3…CnEn代替EIClE2C2E3…CnEn。這里的關鍵問題確定唯一訪問路徑、唯一父元素和關鍵祖先。
　　在補路徑法中定義了互補路徑，相對于某元素的互補路徑是等價的，這樣就可以用補路徑替換原查詢。其基本思想是把用戶書寫的復雜的、代價高的查詢路徑表達式用一些簡單的、查詢代價低的互補路徑表達式來替代。這種策略的目的是減少連接次數和連接結果集的大小，因此怎樣確定查詢路徑的互補路徑并進行代價估算成為其關鍵問題。
　　3.1.3　刪除非冗余的通配符步
　　當在某條路徑中一個元素名未知或無關緊要時通常采用通配符。進行路徑匹配時，通配符需要和當前節點的所有子節點(或后代節點)匹配，由此可見，通配符的計算代價相當高。文獻中提出消除路徑表達式中的非冗余的通配符步，從而降低路徑表達式的計算代價。為了消除路徑中的通配符步，引入一個layer∞ds重寫有通配符的路徑表達式查詢，在形如child：：*/…/child*/ehild1：的查詢中，layer axis可以用來替代所有路徑通配步，從而把查詢等價地表示為Li::t1。這樣一方面縮短了路徑表達式，另一方面使得系統僅僅加載與查詢相關的XML數據，從而大大的優化了查詢。
　　3.2　基于樹遍歷的路徑查詢優化
　　基于樹遍歷的查詢優化要使用路徑索引縮小搜索范圍，這種優化方法的關鍵問題是要設計出有效合理的便于維護的路徑索引。DataGuides算得上是最早的路徑索引，也是路徑索引中最有影響力的代表。它采用了一種標簽路徑合并策略對文檔結構進行縮減，DmGuides中的每個節點都有一個目標集。這個目標集記錄了通過這個標簽路徑可訪問到的數據節點，這樣執行一個路徑查詢時只需要在Dataguides中查找該路徑，獲得的目標集即為滿足條件的查詢結果。當文檔的數據結構比較規則時Dataguides能很好地縮減文檔的結構，從而極大地改善查詢的性能。
　　文獻中提出了一種使用圖模式(Graph Schemas)縮小查詢范圍的方法。這里的圖模式也起著DataGuides的作用，但是它采用了合并同類邊的策略。圖模式中的節點叫狀態，每個狀態都對應一個狀態擴展，集即該狀態在文檔中所對應的節點集。在此基礎上文檔提出了兩種查詢優化策略：剪切查詢和使用狀態擴展集重寫查詢。剪切查詢是將查詢的搜索限制在僅與查詢結果有關的子樹上，后者則是將原查詢改寫為在圖模式上的查詢，兩種方法都使用非確定自動機為剪切工具。
　　不同于以上兩種方式，文獻提出了一種新的路徑查詢方法，該方法將XML文檔中的文本數據抽取出來單獨存儲，這樣文檔樹僅由帶標簽的元素或屬性組成，這樣的結構被叫做文檔的骨架(skeleton)。為了使大的文檔的骨架盡可能地放入內存中。這個樹骨架進一步通過共享的公共子樹被壓縮，被壓縮的樹骨架的每個節點與未壓縮樹的一組節點相對應，他們之間的對應關系用雙向相似關系表示。
　　3.3　基于路徑分解的查詢優化
　　結構連接是基于節點在NML文檔中的位置表示確定XML節點間的包含關系。給定一個祖先(或父)節點集合A和一個后代(或子)節點集合D，結構連接操作的任務就是要用高效的方法找到所有的節點對(ai,di)，其中ai是di的祖先(或父親)，ai、di分別是A、D中的元素。A、D可能來自索引掃描也可能是某個計算的中間結果。結構連接運算的代價非常昂貴，因此結構連接算法的好壞直接影響著查詢的效率，同時結構連接的順序也極大地影響著結構連接運算的性能。
　　3.3.1　結構連接算法
　　目前，已經提出的結構連接算法有兩種：排序合并[2，3,7,19]和劃分方法。排序合并法的主要特點是：①節點采用區域編碼確定節點間的結構關系；②要求輸入的數據集有序或在數據集上建立索引；③為了快速定位某類節點，可以利用元素索引、路徑索引或值索引。文獻中提出了一種多謂詞合并連接算法(MP-MGJN)，該算法需要多次掃描數據集；文獻中提出的ε－jion、εA－lion和κe-iion算法存在同樣的缺點。文獻提出了兩類算法：樹合并(Tree-Merge)算法和堆棧合并(stack-Tree)算法，前者是傳統數據庫合并連接的推廣，后者是一種基于堆棧的結構連接的算法，通過內存中保留一個棧結構來達到對輸入數據的一次掃描的目標。文獻對Stack-Tree算法做了改進，利用附加的索引跳過不需要參加連接的節點。堆棧合并算法(stack-Tree)既可以應用在XML的關系存儲系統中，也可以應用在原生XML系統中。
　　除了基于區域編碼的結構連接算法，文獻目中還針對它提出的PBiTree編碼提出了基于劃分的結構連接算法，其劃分策略有兩種：水平劃分和垂直劃分，分別按節點在樹中的高度和所在分支對數據集合的劃分，這種算法不要求輸入的數據有序或建立索引。結構連接算法在一定程度上依賴于節點的編碼方法，目前普遍使用的編碼方法是區域編碼。由于使用區域編碼可以快速確定節點間的包含關系，開發高效基于區域編碼的結構連接算法仍然是一個值得研究的課題。
　　3.3.2　結構連接的順序選擇
　　在結構連接中，無論采用什么樣的結構連接算法，結構連接的順序極大地影響著結構連接運算的性能，文獻使用簡單的代價估算模型提出了5種結構連接的順序選擇算法。其基本思想是使用動態規劃算法在整個解空間中搜索代價最小的連接計劃，當連接節點過多時解空間會發生組合爆炸，使用動態規劃算法進行搜索將會變得非常緩慢。為了加速搜索速度，在動態規劃算法中引入了各種不同的啟發式規則，這雖然極大地提高了搜索速度卻冒著一些可能丟失最優解的風險。結構連接順序選擇的目標是用較小的代價獲得最優的連接計劃，要實現這個目標還有待于新的結構連接順序選擇算法的提出。
　　
　　4　總結
　　
　　XML路徑表達式查詢優化技術是XML查詢優化的關鍵技術。文中概括了3種優化技術。重寫優化技術在查詢解析之后查詢計劃生成之前使用，其目的是消除路徑中的冗余步，把長的查詢路徑變為等價的短路徑，一方面在基于路徑分解查詢中減少連接次數和中間連接結果，另一方面在樹遍歷方法中也可以減少掃描的節點數，從而極大地優化了查詢性能�；�于樹遍歷的查詢優化和基于路徑分解的查詢優化則是在查詢計劃生成階段使用的。采用什么樣的優化技術主要取決于路徑表達式的處理方法。節點編碼技術和結構連接緊密相關，索引技術也是XML查詢優化的關鍵技術，在這些優化技術中很少使用到XML的數據模式(DTD或Schame)。在查詢中合理有效地使用數據模式將會給查詢優化帶來一片新的天地。

【XML路徑表達式的查詢優化技術】相關文章：

影視公司并購重組的路徑與效應08-21

民事審判錯案的國家救濟路徑04-29

論我國消費環境的優化05-11

金融貿易結構優化研討05-30

企業法律風險防范體系建立的原因及實現路徑08-06

教育供給側改革下大學英語教改路徑論文04-28

變電站接地網優化設計08-24

稅制改革、優化與稅收征管均衡發展06-01

商品期貨優化投資組合的實證檢驗08-26

電視新聞傳播中三網融合的規制路徑論文04-12