一種針對擴展xml樹型結構的查詢方法

2023-12-09 20:12:06

專利名稱：一種針對擴展xml樹型結構的查詢方法
技術領域：
本發明屬於信息技術領域中XML數據查詢技術，具體涉及一種對擴展的XML樹型結構的查詢方法。

背景技術：
隨著XML數據在商業、企業中的廣泛使用以及在交換信息中的流行，有效的處理XML數據查詢也變得越來越重要。一個XML查詢模式通常能用一個有根的標籤樹(或者是小枝樹)來表示。例如，圖1(a)為一個XPath查詢A[B][C]和一個相關的XML樹模型，此查詢用來找到有一個孩子結點B和C的所有結點。在圖(b)的查詢中，查詢結果是結點A1和A2。
對XML樹模型進行有效的匹配是XML查詢處理中的一個核心的操作。近幾年提出了多種有效地匹配XML樹的查詢方法，包括基於堆棧的查詢方法，但其即使在查詢結果很小的時候，輸出的中間結果也可能很大；還提出整體處理樹模型的方法TwigStack，它雖然能確保不輸出無用的中間查詢結果，但是只能處理含有祖先-後裔關係的查詢。還提出一些整體處理方法像TwigStackList，TSGeneric，iTwigJoin，TJFast，TwigStackList-Not等等，但依然存在以下的一些問題。
以前提出的XML樹模型查詢的方法只集中在有父子關係和祖先-後裔關係的查詢上。對於像XPath，XQuery查詢語言中用到的包含了通配符，負邊，有序約束的XML樹模型查詢的處理方法則很少。此發明將使用了負邊，通配符和有序約束的XML樹模型稱為擴展XML樹模型。圖2中有四個擴展XML樹模型。查詢(a)包括一個通配符結點」*」，它可以匹配XML資料庫中的任意單一結點。查詢(b)中包括一個負邊，用

表示。此查詢表示A有一個孩子B，但沒有孩子C。在XPath語言中，負邊可用布爾型函數」not」來表示。查詢(c)有一個有序約束，與一個XPath「//A/B[following-sibling::C]」相同。」＜」表示A的所有孩子結點是有序的。查詢(d)包含了通配符，負邊和有序約束。
以前提出的XML樹模型匹配方法並不能完全發揮出整體處理樹模型方法的最優性。當前面臨的問題是(1)如何識別能夠對查詢進行最優處理的查詢類；(2)對無法確保最優處理的查詢，如何有效的找到查詢結果。
以前提出的方法通過為樹模型中的所有結點找到匹配的元素而解決問題。但是，這在實際應用中是不需要的。以XPath「//A[B]//C」為例，只有元素C及其子樹是最後的結果。在先前的方法中，為了找到這個查詢結果，首先需要找到所有查詢結點的組合，並對這些返回結點進行處理，找到最終合適的結果，這就使得查詢過程中輸出許多與未返回結點相匹配的元素，這對最終結果是沒有用的。此發明中，提出一種新的方式來記錄映射關係並避免輸出未返回結點。
此發明針對可能包括父子關係，祖先-後裔關係，有序約束，負邊和通配符的擴展XML樹模型的查詢，提出新的查詢方法用來識別對查詢進行最優處理的大的查詢類。對擴展XML樹模型的查詢分為三類(1)查詢Q/，//，*是有父子關係，祖先-後裔關係和通配符的查詢；(2)查詢Q/，//，*，＜是有父子關係，祖先-後裔關係，通配符和有序約束的查詢；(3)查詢

是有父子關係，祖先-後裔關係，通配符，有序約束和負邊的查詢，如圖3所示。


發明內容
此發明中首先提出最優查詢類，然後針對擴展XML樹模型，提出一種新的整體查詢方法。通過此方法獲得含有通配符查詢(Q/，//，*)的結果，並經過擴展，使得能夠處理包含有序約束(Q/，//，*，＜)和負邊(

)的查詢。
具體介紹如下 1.擴展XML樹模型的查詢Q 一個XML資料庫D通常用一個有根的，用標籤表示的樹來模擬，元素標籤和屬性被映射到樹的結點上，用邊表示直接的嵌套關係。以下用「結點」表示一個查詢結點，用「元素」表示D中的一個數據元素。
擴展XML樹的查詢Q中的結點包括元素標籤，屬性和字符數據。用「*」表示通配符，用來匹配任意的單一樹元素。其中有四種查詢邊，它們是(正邊，負邊)和(父子邊，祖先-後裔邊)之間的結合。比如在圖2(b)中，(A，B)是一個正的父子邊，(A，C)是一個負的父子邊。用符號

表示負邊；有兩種查詢結點有序結點和無序結點。用「＜」表示有序結點關係。比如，圖2(c)和(d)中的結點A是有序結點。在每個擴展樹模型查詢中，有一個或多個結點被選為輸出結點，用下劃線表示。例如，在圖2(a)中，C是一個選定的輸出結點。
給定一個有n個選定輸出結點的擴展XML樹查詢Q和一個XML資料庫D。與查詢Q的匹配用從Q中的結點到D中元素的映射表示，並使得滿足(i)查詢結點類型(比如標籤名稱)能被相應的資料庫元素滿足並且通配符」*」能匹配任意單一資料庫元素。(ii)查詢結點間的正邊(包括正的父子邊和正的祖先-後裔邊)能被相應的資料庫元素滿足；(iii)在不存在相應的資料庫元素時，負邊(包括負的父子邊和負的祖先-後裔邊)能被滿足；(iv)每個有序結點的孩子的順序關係被相應的資料庫元素滿足。比如，圖4展示了從一個擴展XML樹模型到一個文檔樹中的映射關係。
定義最優查詢類如下 最優查詢類若且唯若一個查詢Q中的父子關係發生在以下邊E上時，查詢Q是最優查詢類的子類。
(1)給定Q中任意的輸出結點q，E是路徑中從q到root的邊；或者 (2)令E＝(a，b)則a是一個有序的結點，b是a的第一個孩子結點；或者 (3)E是一個負邊。
對於滿足最優查詢類條件的查詢，查詢的具體方法如下介紹。
2.獲得查詢Q/，//，*結果的方法 在後面的敘述中，將此發明中的查詢方法稱為TreeMatch。
2.1數據結構 Tq與每個查詢結點q相關的輸入列表。列表中包含有相同名稱q的XML元素的擴展前綴編碼，所有元素根據文檔順序進行排序，這些元素用eq表示。每個列表有一個指針，可以通過單向的移動來以升序瀏覽一遍所有的元素。每個列表中的標籤只能被讀取一次。
Sq與每個分支查詢結點q(不是每個查詢結點)相關的集合。集合中的每個元素eq用一個三元組表示(label，bitVector，outputList)。label是eq的擴展前綴編碼，bitVector用來判斷當前元素在文檔中是否有合適的孩子或者後裔元素。bitVector(eq)的長度與q的孩子結點的數量是相等的。給定一個結點qc∈children(q)，若且唯若文檔中有一個元素eqc使得eq與eqc也滿足q與qc的查詢關係，bitVector(eq，qc)＝「1」。outputList中含有可能對最後查詢結果有貢獻的元素。對Sq集合中的每個元素eq，(i)如果bitVector(eq)中值全為1，則eq就一定能匹配以q為根結點的子樹。(ii)若且唯若eq匹配整個樹查詢，每個元素e∈outputList(eq)都是查詢結果。
例1圖5舉例說明了一個文檔中的查詢結點A的集合SA。SA中有兩個元素。由於A1(「0」)只有一個孩子B1，沒有孩子元素能與C匹配，因此bitVector(A1)＝」10」.相對比而言，bitVector(A2)＝」11」，由於A2(「0.1」)有兩個孩子B2和C1，且滿足查詢中的父子關係。由於在bitVector(A2)中所有的值都為1，因此對輸出結點B來說，B2(「0.1.0」)一定是一個查詢結果。
2.2Q/，//，*的查詢方法 步驟A1在查詢結點q的列表Tq中定位能與對應的根-葉路徑模式相匹配的第一個元素。
步驟A2如果Tq尚未到表尾， 步驟A2-1遞歸的尋找最高分支結點的下一個葉結點。如果該葉結點是輸出結點，則將可能匹配的元素插入到outputlist中。
步驟A2-2讀取該葉結點的列表T中的下一個元素。
步驟A2-3更新該葉結點的集合S。
步驟A2-4處理與查詢模式相匹配的下一個元素，循環步驟A2； 步驟A3輸出查詢結果。清空集合中的所有元素。
3.獲得有序查詢Q/，//，*，＜結果的方法 擴展上述的TreeMatch方法來支持有有序約束的查詢。
3.1數據結構 擴展後的Sq集合中的每個元素eq用一個五元組表示。minChild(eq)和maxChild(eq)的長度與q的孩子的數量相等。假設q1，…，qn是查詢中q的有序孩子結點。給定一個minChild(eq)中的元素

和maxChild(eq)中的


是比元素

(如果存在的話)大的最小元素，

是比元素

(如果存在的話)小的最大元素。因此，

是eq的最左邊的孩子，

是最右邊的孩子。
例2如圖6中的查詢和文檔。表I展示了minChild和maxChild屬性的值。當瀏覽B1和C1時，由於C1在B1之前，因此，不會將C1作為一個minChild插入，因為C1不比B1大。只有當瀏覽到C2時，才將C2插入到minChild中，當B2和C3被瀏覽時，它們分別是B結點和C結點的maxChild。

表I 3.2 Q/，//，*，＜的查詢方法 對TreeMatch進行擴展，只對其中的兩步有所變化 步驟B1對Q/，//，*的查詢方法進行擴展，在更新集合S時，還包括更新minChild和maxChild值。
步驟B2在判斷元素是否為可能匹配的元素時，對其有序性進行了判斷。
4.獲得查詢

結果的方法 擴展TreeMatch方法來支持查詢中的有序約束和負邊。
4.1數據結構 集合S中添加屬性negBitVector用來記錄關於負邊的匹配信息。給定一個結點qc是q的一個負的孩子，若且唯若在文檔中沒有元素

使得eq和

滿足q和qc之間的查詢關係，negBitVector(eq，qc)＝」0」。因此，q的所有負的孩子結點是否滿足條件，只需要看所有孩子的negBitVector是否為」0」。
4.2

的查詢方法 對Q/，//，*，＜的查詢方法進行擴展，只對其中的兩步有所變化 步驟C1對Q/，//，*，＜的查詢方法進行擴展，在更新集合S時，還包括更新negBitVector的值。
步驟C2在判斷元素是否為可能匹配的元素時，考慮到查詢中的負邊，對該negBitVector值進行了判斷。



圖1XML樹查詢以及文檔。
圖2擴展XML樹模型查詢的例子。_表示查詢的輸出結點 圖3擴展XML樹模型的三類查詢例子。
圖4擴展XML樹模型到一個文檔樹的映射關係。
圖5示例介紹集合S中各屬性的取值。
圖6一個有序XML樹模型查詢的例子。
圖7包括通配符的查詢(Q/，//，*)的示例。
圖8各類查詢所需要用到的隨機數據。
圖9基於DBLP(Q7-Q9)和TreeBank(Q10-Q13)數據的查詢. 圖10隨機數據中保證最優性需要緩衝的元素的數量。
圖11各查詢方法的比較。
圖12主存變化時的性能和I/O花費的比較. 圖13包含通配符，有序約束和負邊的查詢(

)。
圖14基於DBLP和TreeBank數據的各類查詢。
圖15擴展XML樹模型查詢方法流程圖。
圖16a為包括通配符的查詢方法TreeMatch的實現流程圖；b為a方法中的兩個過程的具體實現。c為尋找下一個待處理結點的過程。
圖17擴展TreeMatch，實現包括通配符，有序約束的查詢方法的流程圖。
圖18擴展TreeMatch，實現包括通配符，有序約束和負邊的查詢方法的流程圖。

具體實施例方式 此發明的實現是對擴展XML樹結構查詢方法的實現。具體包括查詢中包含了通配符，有序約束和負邊的查詢方法的實現。
1.查詢Q/，//，*方法的實現 步驟A1在查詢葉結點的列表Tq中定位能與個別的根-葉路徑模式相匹配的第一個元素。
步驟A2如果尚未到達Tq的表尾，則繼續步驟A2-1，否則，進入步驟A3. 步驟A2-1通過遞歸找到最高分支結點的下一個葉子結點fact。
步驟A2-2如果fact是一個輸出結點，則在與fact的最近祖先分支結點f相關的集合Sf中添加可能匹配的當前元素，判斷是否可能匹配是根據Sf中的元素與列表

當前的元素所對應的bitVector值是否為1，即兩個元素的關係是否與查詢中的關係相同，如果相同即值為1，則將當前元素填入到Sf中。
步驟A2-3讀取列表

中的下一個元素。
步驟A2-4更新該葉結點的集合 步驟A2-4-1根據當前瀏覽過的元素清空集合。
步驟A2-4-2將可能匹配的元素e添加到集合S中，並設置正確的bitVector值。
步驟A2-4-3如果fact結點不是根結點而且元素e的bitViector＝」1...1」，則遞歸的更新e的祖先集合。由於e的插入，祖先結點的bitVector值不斷更新。
步驟A2-5處理與查詢模式相匹配的下一個元素，循環步驟2. 步驟A3清空所有的相關集合 步驟A3-1對與每個查詢結點(葉結點除外)相關的集合Sq中的元素，如果bitVector中各個值都為1，而且如果此時該結點是一個輸出結點，則將當前元素插入到該結點的最近祖先分支結點的集合中；如果此時該結點是一個最高分支結點，而它的集合S中只有一個元素，就輸出outputlist中的所有元素。如果有多個元素，則將元素與它的最近祖先分支結點對應的元素的outputlist中的所有元素進行合併。
步驟A3-2將集合S中的元素全部刪除。
對步驟A2-1中的尋找下一個葉子結點的方法，具體步驟如下(輸入一個結點n，返回一個葉結點) 步驟A2-1-1如果當前結點是葉結點，則返回n； 步驟A2-1-2如果n有最近的後裔分支結點ni，即ni是一個分支結點或者葉子結點而且是一個後裔結點，從n到ni的路徑上不存在其他的分支結點或葉子結點。如果存在ni，則對每個ni進入步驟A2-1-3處理，否則進入步驟A2-1-4。
步驟A2-1-3包括 步驟A2-1-3-1將ni作為當前結點，尋找ni的下一個葉子結點fi。
步驟A2-1-3-2如果ni是一個分支結點並且ni對應的集合

非空，則返回fi；否則，進入下一步。
步驟A2-1-3-3如果ni是分支結點，則將

中的最大元素賦值給e。否則，令e為列表

中的當前元素。返回e的祖先a的一個集合。
步驟A2-1-3-4在上一步返回的集合中，找最大的元素，賦值給ei. 步驟A2-1-4求ei中的最深的元素emax. 步驟A2-1-5對每個n的最近後裔分支結點ni，如果存在元素e屬於步驟A2-1-3返回的集合中，但e不是emax的祖先元素，即當前元素不能參與到其他列表的後續解，則返回當前結點fi。
步驟A2-1-6找到所有返回的fi中最小的結點fmin，fi不是一個輸出結點。
步驟A2-1-7進入步驟A2-1-3，其中ni是指nmin，即步驟A2-1-6中的返回的最小結點。
步驟A2-1-8對步驟A2-1-7得到的集合中的每個元素，如果該元素是emax的祖先元素，則將e插入集合Sn中。
步驟A2-1-9返回最小結點fmin。
例3考慮圖1中的數據和查詢。A是一個單一的輸出結點。首先，讀取B1和C1.由於A1隻有一個孩子結點B1和一個後裔結點C1(沒有孩子結點)，將A1插入到SA集中，並且bitVector(A1)＝」10」(查看表II)。接著，當瀏覽結點B2和C1時，由於A2有兩個孩子結點B2和C1，將A2添加到集合中並且bitVector(A2)＝」11」。然後，當瀏覽C2時，由於A1也有一個孩子C2，因此更新bitVector(A1)為」11」。最後，清空SA集合，並輸出outputlists中的兩個元素A1和A2。與先前的方法TwigStack和TJFast相比，此方法用bitVector準確的記錄匹配的結果。如果沒有元素C2，則不能輸出A1。

表II 例4利用圖7中的查詢和文檔查看此方法。表III展示了當前訪問的元素，集合S以及相應的輸出元素。查詢中有兩個分支結點。當TreeMatch讀取E2時，遞歸的更新C1和A2的bitVector。最後算法輸出{B1，B2}作為最後的結果。

表III 2.查詢Q/，//，*，＜方法的實現 實現的步驟同Q/，//，*方法相比，區別是，對步驟A2-2中判斷元素是否為可能匹配的元素部分，重新進行實現 步驟B1假設Q中q的孩子結點按序為q1，….qn。
如果當前元素

比前一個結點的元素的編碼大，即而且當前元素比後一個結點的元素的編碼小，即而且該元素與Sf中的元素的bitVector值為1，即兩元素滿足查詢中的關係，則將該元素添加到集合Sf中。
步驟B2在步驟A2-4的更新葉結點相關的集合時，除了要設置bitVector值，還需要設置minChild和maxChild值。
此方法擴展的目的是處理查詢的過程中，考慮與查詢兄弟結點相匹配的元素之間的有序關係，然後進行查詢。
3.查詢

的實現。
擴展前面的方法來支持查詢中的有序約束和負邊。
步驟C1在步驟B1中判斷元素是否為可能匹配的元素部分，重新進行實現如果當前元素

比minChild(eq，qi-1)大，比maxChild(eq，qi+1)小，而且該元素與Sf中的元素的bitVector值為1，同時negBitVector值為「0」，則將該元素添加到集合Sf中。
步驟C2在步驟B2的更新葉子結點相關集合時，需要根據當前元素設置適當的的negBitVector值 實驗效果 實驗使用CPU為奔騰IV1.7G，內存為768M的計算機。
實驗數據 在JDK1.4上用文件系統來存儲，實現上述的方法。實驗基於真實數據集和人工數據集。人工數據集隨機產生。數據集中有7個標籤，A，B，C，...F，G，標籤依此統一分配。真實的數據集是DBLP和Treebank，保證了結構的複雜性。TreeBank的遞歸結構是深的(平均深度7.8，最大深度36). 表IV總結了數據集的特點。
表IV 與以前提出的四個方法TwigStack，TJFast，OrderedTJ，和TwigStackListNot進行比較，來評價此方法。選擇這四個方法是由於與TreeMatch相似，TJFast和TwigStack是兩個整體小枝模式匹配方法，但他們不能處理有有序約束或者負邊的查詢。而OrderTJ是一個能夠處理有序的XML樹模式的整體小枝查詢方法，但是不能處理有負邊的查詢。TwigStackListNot是針對有負邊的查詢而提出的，但是無法處理有序的查詢。只有本發明中的TreeMatch方法能有效處理包含有序約束，負邊以及通配符的查詢。
實驗結果 (1)查詢類Q/，//，*的實驗結果 實驗中所有的查詢所需要的隨機數據集在圖8中可找到。圖8中同時展示了每個查詢的最優性。對DBLP和TreeBank的數據在圖9中展示。限制主存的情況第一個實驗中，不允許TreeMatch中的outputlist在主存中緩存任何元素。這樣，任意添加到outputlist中的元素應該輸出到硬碟中。對主存大小的需求是相當小的。這個實驗的目的是模擬文檔很大但可用主存很小的應用。表V展示了輸出元素的數量和最後查詢結果的數量。用三個不同大小的隨機文檔來做實驗。特別是D1有100k個結點，D2有500K，D3有1M個結點。從表V可看出對大多數的查詢，每個輸出元素都不屬於最後的結果，在這個意義上講TreeMatch中是最優的。唯一的例外是Q3和Q6，不能確保其最優性。Q6對D1和D2是最優的，但僅對D3有略微的次優性。由於文檔D3比D1和D2大，使得D3展示出了D1和D2隱藏的次優性。

表V輸出元素的數量，D1有100K結點，D2有500K結點，D3有1M結點 主存很大的情況第二個實驗，允許outputlist在主存中緩存所有的元素。這個實驗的目的是模擬可用主存比較大，以至文檔的一大部分可緩存在主存中的應用。圖10(a)展示了需要被緩存來確保TreeMatch最優性的元素的最大數量。一個明顯的結果是Q3和Q6需要緩存許多元素，而其他的查詢僅需要緩存數量非常小的元素。
當與先前的方法TwigStack和TJFast進行比較時，TreeMatch方法的優勢更加明顯。在圖11(a)和(b)比較三個方法的性能。顯然，TreeMatch比TwigStack和TJFast更好，對所有的查詢，在執行時間上達到了20％-95％的改善。
為了測試TreeMatch方法是否有能力完全利用現有的主存空間，我們通過改變主存的大小而得到不同的輸出元素的數量來進行比較。通過圖12(b)和(c)，我們可看出此方法的性能。在這個實驗中，選擇了Q1和Q6，由於Q1是TreeMatch的最優查詢，而Q6是次優的。實驗結果顯示了TreeMatch方法輸出元素的數量總是比TwigStack和TJFast輸出的少。特別是，對Q1，隨著可用主存大小的增加，TwigStack和TJFast輸出元素的數量呈線性減少，這是由於TwigStack和TJFast在主存中緩存了中間結果，減少了中間結果的輸出。但是TreeMatch方法輸出元素的數量保持相同，總是等於最後結果的大小。這個實驗結果說明TreeMatch總是能夠利用已有的內存空間，從而減少輸出中間結果，達到很高的查詢效率。
(2)查詢類

的實驗結果 查詢中包含了有序約束，負邊和通配符。實驗所用的查詢如圖13和14所示。

表VI有序查詢的輸出結點數量與有用結點數量 用三個大小不同的隨機文檔進行實驗。表VI顯示了輸出結點的數量和最後查詢結果的數量，其中不允許TreeMatch中的outputlist在主存中緩存任意的元素。對所有最優的查詢(Q15-Q19)，輸出結果的數量與最後的結果相等。
基於DBLP和TreeBank，用圖1 4中的查詢進行實驗。在圖11(c)和12(a)中顯示了執行時間。由於Q14-Q16，Q20-Q22是基於有序查詢的，比較TreeMatch和OrderedTJ。此外，Q17，Q18，Q23，Q24有負邊，因此比較TreeMatch與TwigStackListNot。在所有的實驗的查詢中，TreeMatch比先前提出的方法有更好的性能。主要由於TreeMatch方法有更大的最優查詢類。對查詢Q19和Q25，由於兩個查詢包含了通配符，負邊和有序約束，因此只有TreeMatch能夠得到如此複雜的查詢結果。以上實驗使用了一個相對較小的緩存空間，預期此方法能夠通過擴展使得對當前機器上的甚至是千兆(Gigabytes)的XML數據進行處理。
最後，此發明針對以前的整體查詢方法所無法解決的通過輸出一些不確定的元素避免在主存受限時丟失有用解的問題，通過識別最優查詢類，然後對最優查詢類中所包括的三種查詢，即Q/，//，*，Q/，//，*，＜和

提出了新的解決方法。此方法不僅能最優的處理更多的查詢而且避免了輸出無用的中間結果。而對於不滿足最優查詢類的查詢模式，雖然一些與查詢結果無關的中間結果會輸出，但是與以前提出的方法相比，此方法能利用主存空間的緩存，使得輸出更少的中間結點。而能處理更多的最優查詢類的優勢也是值得注意的。
基於以上優點，本發明提出的針對擴展XML樹型結構的查詢方法可應用於XML資料庫的查詢處理，尤其是XPath，XQuery等查詢語言中，以及其他對XML信息進行查詢處理的系統中。
此外，對於本領域的普通技術人員來說可顯而易見的得出其他優點和修改。因此，具有更廣方面的本發明並不局限於這裡所示出的並且所描述的具體說明及示例性實施例。因此，在不脫離由隨後權利要求及其等價體所定義的一般發明構思的精神和範圍的情況下，可對其做出各種修改。
權利要求
1.一種針對擴展XML樹型結構的查詢方法，其特徵在於，提出擴展XML樹模型是指包含了通配符，有序約束和負邊的XML樹模型。
2.一種針對擴展XML樹型結構的查詢方法，其特徵在於，實現的具體步驟如下
A.基於擴展前綴編碼，通過使用與分支查詢結點相關的集合S保存可能匹配的元素，通過記錄映射關係，輸出最終匹配的包含通配符的查詢的結果。
B.通過在S中添加元素的屬性值，記錄元素之間的有序關係，輸出最終匹配的包含通配符和有序約束的查詢的結果。
C.在S中添加關於負邊的屬性值，使得此方法可處理包含通配符，有序約束以及負邊的查詢。
3.根據權利要求2所述的方法，其特徵在於，所述的包含通配符的查詢(Q/，//，*)方法的實現如下
步驟A1在查詢結點q的列表Tq中定位能與對應的根-葉路徑模式相匹配的第一個元素。
步驟A2如果Tq尚未到表尾，
步驟A2-1遞歸尋找最高分支結點的下一個葉結點。
步驟A2-2如果該葉結點是輸出結點，則將可能匹配的元素插入到該葉結點的最近祖先分支結點的相關集合S中。
步驟A2-3讀取該葉結點的相關列表T中的下一個元素。T中包含與查詢結點有相同名稱的所有元素，元素按照文檔順序排序。
步驟A2-4更新該葉結點的集合S。S中元素用表示。分別表示元素的擴展前綴編碼，記錄當前處理元素與S中元素的關係是否符合孩子或後裔關係，記錄最可能的輸出結果。
步驟A2-5處理與查詢模式相匹配的下一個元素，循環步驟A2；
步驟A3輸出查詢結果。清空集合中的所有元素。
4.根據權利要求2所述的方法，其特徵在於，所述的包含通配符以及有序約束的查詢(Q/，//，*，＜)的實現方法是在對Q/，//，*的查詢方法進行擴展的基礎上實現的
步驟B1對Q/，//，*的查詢方法進行擴展，在判斷元素是否為可能匹配的元素時，同時對元素之間的有序性進行判斷。
步驟B2在更新集合S時，S中的元素用
表示。minChild與maxChild值記錄元素的有序關係。
5.根據權利要求2所述的方法，其特徵在於，所述的包含通配符，有序約束以及負邊的查詢
的實現方法是在對Q/，//，*，＜的查詢方法進行擴展的基礎上實現的
步驟C1對Q/，//，*，＜的查詢方法進行擴展，在判斷元素是否為可能匹配的元素時，考慮到查詢中的負邊，對negB計Vector值進行了判斷。
步驟C2在更新集合S時，S中的元素用表示negBitVector記錄關於負邊的匹配信息。
全文摘要
本發明屬於信息技術領域XML數據查詢技術，具體涉及對一種擴展的ZML樹型結構的查詢方法。針對當前所提出的查詢方法的問題，即由於主存的限制不得不輸出一些不確定元素，以及能處理的最優查詢類範圍較小的問題，本發明提出一種新的整體方法，能夠處理含有父子關係，祖先-後裔關係，通配符，有序約束和負邊的查詢。通過利用與分支查詢結點相關的集合S來保存可能匹配的元素，並記錄映射關係，當元素匹配查詢模式時，輸出最終的查詢結果。此方法不僅能最優的處理更多的查詢類，而且使得中間結果大大減少，同時避免了無用結果的輸出。通過實驗表明，此方法在性能，輸出結點數量上都有優勢，而且在主存空間變化時，此方法仍具有明顯的最優性。
文檔編號G06F17/30GK101763406SQ20091022233
公開日2010年6月30日 申請日期2010年3月24日 優先權日2010年3月24日
發明者陸嘉恆 申請人:陸嘉恆