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