基于ＸＰａｔｈ的ＸＭＬ查詢優化

摘要：隨著XML作為Internet上數據表示和交換的標準，如何高效地進行XML數據的查詢己經變得越來越重要，許多XML查詢語言也隨之出現。這些查詢語言雖然種類繁多，但都有個共同特征：使用基于XPath數據模型下規則路徑表示來查詢XML數據。研究表明，當前的關系數據庫技術在處理規則路徑表示的查詢時通常效率不高。

文章在介紹了傳統的基于遍歷樹的方法的基礎上重點討論了基于路徑分解的查詢處理算法，并對選擇連接順序算法提出了基于動態規劃思想的改進。

關鍵詞：XPath；XML；查詢優化；動態規劃

中圖分類號：TP311文獻標識碼：A 文章編號：1009-3044(2008)28-0020-04

XML Query Optimization Based on XPath

XU Yi

(School of Software Engineering，Tongji University，Shanghai 201804，China)

Abstract: With the advent of XML as a standard for data representation and exchange on the Internet， querying XML data becomes more and more important. Several XML query Language have been proposed， and the common feature of the languages is the use of regular path expression based on XPath Data Model to query XML data. Research shows that the current relational database technology often inefficient when deal with the regular path expression.

This paper first introduce the traditional traversing tree algorithm， and then discuss the query parse algorithm which based on regular path expression， and optimize the structural join order by dynamic programming.

Key words: XPath; XML; query optimization; dynamic programming

1 引言

XML是由W3C開發的，主要目的是為了克服HTML缺乏結構和元數據信息的缺點，為Web信息的集成、交換建立一種新的靈活的機制。

它在以下幾個領域正改變著Web：

1) 簡化了數據交換。使用XML，每個實體可以創建單一的實用程序，該實用程序將該實體的內部數據格式轉換成XML，反之亦然。

2) XML支持智能代碼。因為可以使XML文檔結構化以標識每個非常重要的信息片段以及這些片段之間的關系，所以可以編寫無需人工干預就能處理這些XML文檔的代碼。

3)XML支持智能搜索。盡管搜索引擎這些年在穩步改進，但從搜索中得到錯誤的結果仍很常見。搜索 XML文檔會給一個好得多的結果集。

隨著XML數據的增多，如何對其進行高效的查詢時非常重要的，本文從XML的基本概念入手，著重對當前XML數據查詢的處理方法進行分析研究，并加以改進和優化，來進一步提高查詢處理效率。

2 XPath

談及XML數據查詢，就不得不談到XPath。作為XML數據查詢語言的核心部分，XPath用來對XML文檔的內容進行定位、檢索。XQuery和XPath公用的數據模型提供了XML文檔的樹形表示—節點樹。節點有七類，包括根節點、元素節點、屬性節點、文本節點、命名空間節點、處理指令節點、注釋節點。XPath的最主要構件路徑表達式就是通過這樣的節點樹來跟蹤路徑，識別出所有被路徑表達式檢索的節點。下面給出的是一個簡單的定位表達式：

/pub/book/author

定位路徑有兩種，分別是相對定位路徑和絕對定位路徑。每個定位路徑表達式都由一個或者多個定位步組成，每個定位步之間用正斜杠分開。絕對路徑以正斜杠開始，它從文檔的根節點開始定位路徑；而相對路徑則直接從某個定位步開始定位路徑。

XPath中用上下文節點集來描述定位路徑的求值過程是如何進行的。上下文節點集定義為：表達式中給定集確定的當前節點集。上下文定義為：正在處理的當前節點。

定位路徑表達式是求值過程是由定位步驟決定。定位步驟按順序(從左到右)一次一個地求值。每一個定位步驟都是對照上下文節點集中的節點進行求值的。第一個定位步驟是把上下文節點集中的每個節點當作上下文節點進行求值。 然后結果節點集被合并為新的節點集，這個節點集成為下一步操作的上下文節點集。這樣的處理在路徑的每一個定位步驟中持續進行。最后的定位步驟產生的節點集就是這個表達式的結果。

定位步包含三部分：

一個軸，它指定了定位步選擇節點與上下文節點之間的樹狀關系。XPath定義了13個軸。每個軸都有個方向，向前或者向后。

一個節點測試，它指定了定位步選擇的節點類型或者節點名。如果給定點的節點測試為真，則它保留在結果節點集中，否則將它從結果節點集中刪除。

零個或多個謂詞，它使用專有的謂詞表達式來進一步篩選定位步選擇的節點集合。

3 XML數據查詢處理方法

利用路徑表達式導航XML查詢是XML查詢語言的共同特點.目前對XML路徑表達式的計算有兩種方法:一種是基于樹遍歷的方法，另外一種是路徑連接方法。

3.1 基于遍歷樹的方法

基于遍歷樹的方法有兩種次序：top-down和bottom-up。下面以查詢表達式Q1:/city/school/class/student[@name=”Tom”]為例來說明。按top-down的次序來處理時，要順著所有開始于city節點的路徑，去查找是否有school的節點作為后代，這一步要對XML數據庫中的所有的city節點來執行， 這就意味著在XML樹中要遍歷從city節點到葉節點的每一條可能的路徑，如果city節點是根節點，那么整棵XML樹都必須被遍歷。按bottom-up的次序來遍歷可以降低遍歷的成本，對于同樣的查詢Q1來講，所有帶有屬性name值為”Tom”的student節點都要被搜索，從每一個這樣的student節點開始向上遍歷來確定是否存在class節點，然后再從每一個這樣的class節點向上遍歷來確定是否存在school節點作為祖先， 依次類推… 這種向上遍歷的方法在一般情況下較簡單、耗時較小，但對于符合條件的student節點數目很大，而class節點、school節點或city節點數目較小的情況，這種遍歷方式的成本可能會高于top-down方式。

一種折衷的處理方法是同時按照top-down 和bottom-up的次序進行遍歷，最終會在路徑的某個中間位置相遇，從而得出查詢結果。這種方法結合了top-down和bottom-up的優點，但它的高效性并不總能得到保證，下面改進的方法中采用了路徑分解和連接算法來處理，避免了多次遍歷樹。

3.2 基于路徑分解的查詢處理算法

Quanzhongli和Bongki Moon將規則路徑查詢表達式分解為以下五種基本表達式的組合。

1) 只由單一元素或單一屬性組成的表達式，如author、@year;

2) 由一個元素和一個屬性組成的表達式，如book[@year=2007];

3) 由兩個元素組成的的表達式，如chapter//title、book/@isbn;book[descendant::section]、book[chapter];

4) 一個子表達式的kleene閉包

5) 兩個子表達式的并集

對第1種情況可利用元素或屬性的索引直接得到結果，對第2、3、4種情況需分別需要采用EA-Join、EE-Join和KC-Join三個算法來進行中間結果的連接合并；第5 種情況可通過組合兩個中間結果或直接按文件分組來處理。

三個算法如下：

1) EA-Join算法 ( 用于元素集合和屬性集合的合并，對應于由一個元素和一個屬性組成的子表達式) :

輸入:{E1，…，Em}， Ei表示擁有相同文件標示符(did)的元素集

{A1，…，An}， Aj表示擁有相同文件標示符(did)的元素集

輸出:元素為(e，a)的集合，要求滿足a是e的屬性

//據文件標示符來分類合并集合{Ei} 和{Aj}

l :for each Ei and Aj with the same did do

//據孩子父母關系分類合并Ei和Aj

2 : for each e∈Ei and a∈Aj do

3 : if(e is a parent of a) then output(e，a)

end

end

2) EE-Join算法 ( 用于元素集合和屬性集合的合并，對應于由一個元素和一個屬性組成的子表達式)：

輸入:{E1，…，Em}和{F1，…，Fn}， Ei和Fj表示擁有相同文件標示符(did)的元素集

輸出:元素為(e，f)的集合，要求滿足e是f的屬性

//據文件標示符來分類合并集合{Ei} 和{Fj}

l :for each Ei and Fj with the same did do

//據孩子父母關系分類合并Ei和Fj

2 : for each e∈Ei and f∈Fj do

3 : if(e is an ancestor of f) then output(e，f)

end

end

3) kleene closure算法 ( 對應于求一個子表達式的kleene閉包) :

輸入:{E1，…，Em}， Ei表示一個XML文檔的一組元素

輸出: {E1，…，Em}的kleene閉包

//重復執行EE-Join算法

1:set i=1

2:set Kci ={E1，…，Em};

3:repeat

4:set I =i+1

5:set Kci=EE-Join(Kci-1， Kc1)

until (Kci is empty)

6:output union of Kc1 ，Kc2， ……， Kci-1;

4 XML數據查詢處理優化

路徑分解算法（見3.2節）在合并中間結果集時，由于各個集合中元素的個數不同，在采用不同的連接合并的次序的情況下，執行的開銷有很大不同。如果能夠選擇恰當的結構連接順序，將使原算法得到進一步的優化。因此如何應用動態規劃算法，使得在盡量小的搜尋空間里找到最好的方案是本節的主題。

4.1 動態規劃的基本思想

動態規劃算法的基本思路是用一個表來記錄所有已解決的子問題的答案，不管該子問題以后是否被用到，只要它被計算過，就將其結果填入表中，在需要時再找出，這樣就可避免大量的重復計算。

動態規劃算法通常用于求解具有某種最優性質的問題。這類問題中，可能會有許多可行解，每個解都對應一個值，我們希望找到最優值 ( 最大值或最小值)的那個解。設計一個動態規劃算法，通常可按以下幾個步驟進行:

1) 找出最優解的性質，并刻畫其結構特征。

2) 遞歸地定義最優值。

3) 以自底向上的方式計算出最優值。

4) 根據計算最優值時得到的信息，構造一個最優解。

用動態規劃算法通常只需要多項式時間，從而獲得較高的解題效率。

4.2 動態規劃算法的設計

一個XPath語句通常被建模成為一個樹，這種查詢也被稱為樹模式查詢。一個查詢的求解過程為：從初始查詢數開始，每次處理樹中的一條邊，即將相連的兩個節點進行連接，連接的結果用一個新的節點表示，并替代原樹中的2個節點。每次連接的時候都會減少一個節點，產生一個新的樹。當最后的樹只包含一個節點的時候，整個求解過程便告結束。圖1給出了一個查詢樹求解的例子。

■

圖1 使用動態規劃時的查詢樹求解圖

查詢數的求解圖實際上是一個有向無環圖。圖中所有類似于AB的聚集點成為狀態節點，每個查詢數稱為一個狀態，從一個查詢樹變換到另一個查詢樹的過程稱為移動。從初始狀態開始經過k步移動后到達的狀態被稱為k層狀態。只有當第k層所有狀態產生后才能移動到第k+1層。因而查詢樹的求解過程就是從初始狀態出發，經過n次移動到達結束狀態的過程，n為初始查詢樹中邊的數目。在這n次移動過程中經過的路徑就給出了連接的計劃即連接的順序。比如：S00-S10-S24-S31表示連接的順序為：先連接節點A和B，在將中間結果和D連接，最后與C連接。現在的問題是，要選擇一條路徑，使得按照該順序連接的總體代價最小。

如果將每一步的連接代價作為狀態樹每個邊的權，則這個問題上實際就是經典的求最小路徑問題。把最短路徑問題的動態規劃算法應用到這里，就變成了連接順序求解的動態規劃策略。其過程為：從初始狀態出發，每次進行一步移動。移動到第k層時，可能得到多個狀態，而且每個狀態又可能從多個路徑轉換而來。這些路徑的代價不一樣，只保留其中代價最小的那條路徑。然后從第k層狀態出發，移動到下一層，并按同樣的方法選擇最佳路徑。這樣到最后得到的路徑便是最短路徑，也是最優的連接順序。

DijkstraShortestPathes算法:

輸入:具有非負權值的簡單無向加權圖G，以及G的一個特殊頂點v：

輸出:對于G中每個頂點u，輸出標記D[u]，滿足D[u]是G中從v到u的距離

//初始化

1:set D[v]=0;

2:for G中每個頂點u ≠ v do

set D[u]=+ ∞;

//設優先隊列Q包含G中所有的頂點，利用D標記作為關鍵字

3:while Q 非空 do

//把一個新頂點u從Q中加入到初始化為空集的集合C中

set u = Q.removeMin();

for u 的每個鄰接頂點Z且Z在Q中 do

//對邊(u，z)進行松弛過程

if D[u] + w(u，z) < D[z] then

set D[z] = D[u] + w(u，z);

改變Q中頂點Z的關鍵字

算法運行時間分析：

反復向Q中插入帶有初始關鍵字的所有頂點，所需時間為O（nlogn），如果利用自底向上的構造堆，則所需時間為O(n)在while循環中，從頂點Q中刪除頂點u所需時間為O（nlogn），對于依附于頂點u的邊，執行松弛過程的時間為O(dev(v)logn)總時間為Σv∈G（1+dev（v））logn即：總運行時間為O（（n+m）logn）

4.3 幾種查詢處理算法的比較

基于遍歷樹的處理方法比較直觀，但祖先后代關系的判斷需要多次對樹進行遍歷，特別對查詢路徑較長的情況將耗費較多時間，效率不高。路徑分解法處理時將長的查詢表達式分成五種基本子表達式，處理完每個子表達式后，再將中間結果集合按照具體算法進行合并，得出原查詢表達式的結果，此方法節省了時間，提高了效率。在此基礎上，動態規劃算法對此路徑分解法進一步優化，在進行合并中間結果集前先確定出合并的最優次序，減少了計算量，提高了效率。

5 小結

隨著XML作為Internet上數據表示和交換的標準，如何高效地進行XML數據的查詢己經變得越來越重要，本文對規則路徑表示下XML數據的查詢處理算法進行了分析研究，其中重點討論了基于XPath的查詢表達式的分解、中間結果集的合并算法等，主要工作如下:基于動態規劃的思想，設計出具體算法，在進行中間結果集合并之前，先求出合并的最優次序，大大降低了合并結果集的計算量，提高了查詢處理效率，實現了對路徑分解算法的進一步優化。

事實上，對于一個復雜的查詢來說，上述算法的搜索空間依然很大，還有進一步優化的空間，這也是后續的研究方向。

參考文獻：

[1] Li Q，Moon B.Indexing and Querying XML Data for Regular Path Expression[A].In: Apers PMG et al Eds. Proceedings of the 27th VLDB International Conference on Very Large Database.[C] Rome， Italy. September 11-14，2001.San Francisco: Morgan Publishers，2001:361-370.

[2] Wu Y，Patel J M，Jagadish H V.Structural Join Order Selection for XML Query Optimization[A].In: Casati F et al Eds. Proceedings of the 19th IEEE ICDE International Conference on Data Engineering.[C] Bangalore， India. March 5-8， 2003. Los Alamitos: IEEE Computer Society，2003:443-454.

[3] World Wide Web Consortium. XML Path Language(XPath) Version 1.0. [S].W3C Recommendation.16 November，1999.