一種基於路徑信息的可擴展標記語言祖先後代索引方法

2023-05-26 02:36:26

專利名稱：一種基於路徑信息的可擴展標記語言祖先後代索引方法
技術領域：
本發明屬於計算機資料庫技術領域，特別涉及一種XML(可擴展標記語言， Extensible Markup Language)數據索引方法，具體涉及一種基於路徑信息來實現XML祖先 後代結構關係的數據索引方法。
背景技術：
隨著網絡數據的海量增長，網絡數據的格式越來越多樣，由於XML具有良好的可 擴展性以及自描述性，因此在當前hternet上，XML已經成為事實上的數據表示和數據交 換標準。在具體應用中，越來越多的應用系統採用XML標準格式來發表和交換數據。對於 XML查詢，現在已經有了標準的XML查詢語言XPath和XQuery，為了加速XPath和XQuery 查詢，需要對XML數據建立索引。XML文檔是一個樹形結構的文檔，在XPath和XQuery查詢中，一個比較困難的問題 就是解決XML文檔中祖先後代關係的結構查詢。如下面的查詢表達式book//editor直觀的辦法是對於book標籤節點和editor標籤節點分別建立對應的一個鍊表， 然後對這兩個鍊表中的元素進行嵌套循環一一匹配，這樣的算法的複雜度為0(N2)。一個更為精巧和典型的解決辦法是採用Siurug Al-Khalifa等人提出的 Structural Joins (結構連接)辦法來完成。結構連接算法對每一個XML元素進行編碼，其 編碼形式為(Docld, StartPos, EndPos, LevelNum)。對於兩個元素節點 Elementl (DocId 1, StartPos 1, EndPos 1, LevelNum 1)禾口 Element2 (Docld 2, StartPos 2, EndPos2, LevelNum2)。Elementl 和 Elementl 滿足祖先後代關係若且唯若DocIdl = DocId2, StartPosl EndPos2。在結果連接算法中，基本想法是對兩個標籤 節點鍊表按照(Docld，Startpos)進行排序，算法採用一個棧數據結構保留中間結果。之後又相繼提出很多算法來解決祖先後代結構連接問題，不過後來算法的核心思 想都是在Siurug Al-Khalifa等人提出一個棧加上XML元素標籤鍊表的基礎上加以改進。上面的各種算法在進行祖先後代關係查詢的時候，都需要為祖先標籤節點和後代 標籤節點建立一個鍊表，並且通常需要遍歷這兩個鍊表。另外，對於更加複雜的查詢諸如 A1ZVA2ZVAf An之類，結構連接算法通常是把它們分成A1//A2，A2//A3這樣的祖先後代對， 然後對這些運算結果進一步進行連接操作，效率比較低。

發明內容
本發明也是為了解決XML查詢語言XPath和XQuery中祖先後代關係查詢而提出， 不同於那些傳統算法，本發明基於XML解析中產生的路徑信息來進行祖先後代關係查詢。本發明採用的技術方案是設計並實現了一個新的XML結構信息索引XStrctldx。 算法對解析過的XML文檔每個節點存儲為(Key，Value)形式，其中Key為XML文檔的節點 標籤，Value包含了當前XML文檔節點的從父節點到根節點的路徑。對於這些XML文檔節點，在Key上面建立B+樹索引，在查詢過程中，對於指定的標籤，只需要判斷其對應的Value 中是否含有滿足條件的祖先節點即可。該索引主體採用B+樹數據結構，既可以很容易的嵌 入到關係型資料庫中，又可以在Native類型的XML資料庫中使用。本發明所需要存儲的具體節點信息如圖2所示，具體步驟如下步驟1解析XML文檔本發明首先需要對XML文檔進行解析，得到文檔節點的具體信息。對於XML文檔 解析有兩種方法，DOM解析與SAX解析。DOM是對XML文檔在內存中建立樹結構，這對系統 的資源消耗很大，一般說來，所建立的樹結構佔用的內存大小可能是文檔本身的幾倍到數 十倍。對於大型文檔可能根本沒法應用DOM解析。因此我們採用SAX解析。在SAX解析過程中，我們使用一個棧結構。在SAX解析中，會產生以下類型事件①文檔開始；②遇到元素節點開始標籤；③遇到元素節點結束標籤；④文檔結束。每當遇到元素節點開始標籤，即判斷是否對該標籤進行字典映射，也就是說把標 籤的字符流轉化成對應的數字ID。如果需要進行映射變換，即把該標籤轉化為數字ID，並 存儲到系統的數據字典中，然後把該數字ID入棧；如果不需要進行映射變換，直接把該數 字入棧，並且對該節點形成(Key，ValUe)對。其中Key即為該元素節點對應的數字ID，Value 是一個結構體，Value結構體包括當前節點從其父節點到根節點的路徑信息，以及指向該節 點具體存儲位置的指針。每當遇到元素節點的結束標籤，即判斷該標籤與棧頂元素是否是同一元素節點， 如果相同，則把棧頂元素彈出，否則不做操作。由於 XML 文檔的嵌套性質，即只有 ......</Elementl〉這種形式的文檔，沒有 ...... 形式的文檔，因此，在我們使用SAX文檔時，當解析某一個元素節點的時候，在從棧頂到棧底 的元素，正好對應了該元素從父節點到根節點元素。(因為在遇到開始標籤的時候壓棧，在 遇到結束標籤的時候彈棧，故有此特性)。在文檔結束的時候，文檔所有的元素節點解析完畢，每個元素節點都形成了我們 需要的(Key, Value)對。步驟2建立B+樹索引對於步驟1解析出來的每個(Key，Value)對，其實就對應了 XML文檔中的每個元 素節點，，需要把這些元素節點用B+樹索引起來。如果該算法應用於關係資料庫環境，那麼我們可以把我們的(Key，Value)對變成 關係資料庫系統中的表結構。該表有三個欄位，其模式為(CurrentN0de，Path，XP0inter)， CurrentNode欄位對應於我們(Key，Value)中的Key，PathInfo和XPointer組合對應於我 們(Key，Value)對中的Value結構體，其中I^thhf0為該節點的父親節點到根節點的路徑 信息，XPointer為一個指針，指向該節點所存儲的具體物理地址。B+樹索引的Key即建立 在(Key, Value)對中Key欄位上。如果該算法應用於Native XML資料庫環境，我們的每個(Key，Value)對在存儲的 時候要採用B+樹來進行索引，其中Key對應於B+樹中的索引鍵值，所對應的值即Value結 構體，Value結構體包括每個元素節點的從父親節點到根節點的路徑信息以及指向該節點 所存儲的具體物理地址信息。
無論是使用關係型資料庫來管理XML數據，還是採用Native系統來管理XML數 據，我們的索引都可以應用，並且整體都為B+樹作為索引。需要注意的是，雖然我們把步驟1和步驟2分開來寫，但是在實際實現中，每解析 一個元素節點，相應的就把這個節點按照通用B+樹算法插入到B+樹當中，在文檔解析完 成，一個完整的B+樹索引也就建立完畢。按照B+樹通用算法，我們的(Key，ValUe)對是聚 簇存儲的，也就是說相同的Key，他們的物理存儲結構是存儲在同一個磁碟塊或者相鄰的磁 盤塊上面。步驟1和步驟2介紹了結構索引生成算法，所對應的算法具體描述如下
權利要求
1. 一種基於路徑信息的可擴展標記語言祖先後代索引方法，其特徵在於包括以下步 驟步驟一解析XML文檔採用SAX解析，使用一個棧結構，在SAX解析中會產生以下類型事件 ①文檔開始；②遇到元素節點開始標籤；③遇到元素節點結束標籤；④文檔結束； 每當遇到元素節點開始標籤，即判斷是否對該標籤進行字典映射，如需要進行映射變 換，則將標籤的字符流轉化成對應的數字ID，並存儲到系統的數據字典中，然後把該數字 ID入棧；如不需要進行映射變換，直接把該數字入棧，並且對該節點形成(Key，Value)對； 每當遇到元素節點的結束標籤，即判斷該標籤與棧頂元素是否是同一元素節點，如果 相同，則把棧頂元素彈出，否則不操作；在文檔結束的時候，文檔所有元素節點解析完畢，每個元素節點都形成了(Key，ValUe)對；步驟二 建立B+樹索引存儲步驟一解析出來的每個(Key，Value)對，若該方法應用於關係資料庫環境， 則將(Key，Value)對變成關係資料庫系統中的表結構，該表有三個欄位，其模式為 (CurrentNode, Path, XPointer), CurrentNode 欄位對應於(Key, Value)對中的 Key, PathInfo和XPointer組合對應於(Key，Value)對中的Value結構體，其中PathInfo為該 節點的父親節點到根節點的路徑信息，XPointer為一個指針，指向該節點所存儲的具體物 理地址；若該方法應用於Native XML資料庫環境，存儲每個(Key，ValUe)對的時候要採用B+樹 算法來進行存儲，其中Key對應於B+樹中的索引鍵值，所對應的值即Value結構體，Value 結構體包括每個元素節點從父親節點到根節點的路徑信息以及指向該節點所存儲的具體 物理地址信息；步驟三使用B+樹索引進行祖先後代關係查詢對於A//D這類祖先後代關係查詢，先通過B+樹找到所有標籤名稱是D的節點，然後 對於每個節點，依次檢索該節點的Value結構，看看Value結構中的路徑信息是否包含A標 籤，如果該路徑信息包含了 A標籤，則說明這個D節點滿足查詢條件，通過Value結構中的 指針找到該D節點具體的物理存儲地址，找到查詢結果；對於A1ZVA2ZV-ZVAn這類複雜的路 徑查詢，先通過步驟2中的B+樹找到所有標籤名稱是An的節點，然後對於這些節點，依次 檢索該節點的Value結構，對於Value結構中的路徑信息，與路徑查詢中的A1ZVA2//…//Alri 進行匹配，即判斷KlIKI卜-1IKa是否是Value結構中的路徑的有序子集。
全文摘要
一種基於路徑信息的可擴展標記語言祖先後代索引方法，包括以下步驟步驟一解析XML文檔；步驟二建立B+樹索引；步驟三使用B+樹索引進行祖先後代關係查詢。本發明是一個實用的索引，基於計算機資料庫領域內的B+樹結構，該結構保證了在絕大多數情況下，採用索引都會比不採用索引查詢效率有很大的提高，該索引無論對於基於關係資料庫的XML資料庫管理系統還是基於Native存儲的XML資料庫管理系統，都易於實現；該結構實現簡單，只需要進行一次節點掃描，對於文檔的數據是否有數據傾斜狀況，都有很好的性能；還可以很好的處理A1//A2//…//An這類複雜的路徑查詢，避免了把長路徑分成若干個祖先後代對的做法，有效的實現了對索引節點一次掃描即可得到查詢結果。
文檔編號G06F17/30GK102043852SQ201010600979
公開日2011年5月4日 申請日期2010年12月22日 優先權日2010年12月22日
發明者劉輝林, 孫永佼, 張恩德, 趙相國 申請人:東北大學