[發(fā)明專利]一種基于結(jié)構概要的數(shù)據(jù)恢復方法

有效

• 申請?zhí)枺?/td>: 201310100931.4
• 申請日: 2013-03-27
• 公開（公告）號: CN103136378A
• 公開（公告）日: 2013-06-05
• 發(fā)明（設計）人: 陳琳;陳海濤;夏冬;王奎
• 申請（專利權）人: 同方知網(wǎng)（北京）技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京天奇智新知識產(chǎn)權代理有限公司 11340
• 代理人: 劉黎明

技術領域

本發(fā)明涉及XML數(shù)據(jù)庫查詢領域，尤其涉及一種XML數(shù)據(jù)庫中基于結(jié)構概要的數(shù)據(jù)恢復方法。

背景技術

XML（Extensible?Markup?Language），即可擴展標記語言，是一種半結(jié)構化的數(shù)據(jù)格式。隨著互聯(lián)網(wǎng)技術的飛速發(fā)展，XML已經(jīng)成為基于Web應用的數(shù)據(jù)表示與交換的事實標準。XML的一些顯著特點是自描述、半結(jié)構化，層次嵌套結(jié)構。

XQuery/XPath是W3C標準化的XML數(shù)據(jù)查詢語言。XQuery是一個圖靈完整的程序設計語言，可以描述針對XML數(shù)據(jù)的豐富的處理邏輯。XPath可以認為是XQuery的一個子集，用于通過路徑模式，從XML數(shù)據(jù)中抽取匹配的數(shù)據(jù)。

Twig模式匹配是在半結(jié)構化數(shù)據(jù)中，利用樹模式進行匹配選擇數(shù)據(jù)的一種技術。Twig模式匹配被認為是XQuery/XPath的核心操作，通常被應用在XQuery/XPath引擎的實現(xiàn)中。Twig模式匹配的輸入是一個待匹配的模式樹，模式樹中的模式節(jié)點對應的數(shù)據(jù)節(jié)點流，輸出是符合模式的數(shù)據(jù)節(jié)點元組。為了加快Twig模式匹配算法的速度，目前現(xiàn)有技術可以從存儲和索引兩方面給予支持。

首先，在存儲方面，在XML數(shù)據(jù)庫中，基于節(jié)點的存儲方式可以提供對XML數(shù)據(jù)更細粒度的控制。一個XML文檔可以建模為一個樹形結(jié)構，樹的節(jié)點可以分為葉子節(jié)點和中間節(jié)點。因為XML數(shù)據(jù)實際存儲在葉節(jié)點中，中間節(jié)點可以認為是一個邏輯結(jié)構，所以采用只存儲葉節(jié)點數(shù)據(jù)的存儲方案可以提高數(shù)據(jù)存儲的空間性能，并能降低數(shù)據(jù)I/O。

其次，在索引方面，通常采用基于路徑的索引，以一條簡單路徑作為索引的定義形式，所謂簡單，即該路徑的描述形式是一條從根開始，到某個節(jié)點的路徑，在路徑上的節(jié)點中不涉及謂詞等復雜邏輯。基于路徑的索引可以加快對匹配某個簡單路徑的數(shù)據(jù)的訪問。這種索引通常被用來為Twig模式匹配算法提供輸入所需的節(jié)點數(shù)據(jù)流。

以上的存儲和索引技術方案提高了Twig模式匹配算法的性能。然而，在針對XML數(shù)據(jù)的查詢中，例如XPath，往往需要針對或者參考中間節(jié)點進行匹配選擇，而存儲和索引的對象都是XML數(shù)據(jù)的葉節(jié)點，路徑索引選取的也是路徑末端對應的葉節(jié)點，所以查詢的求值需要進行必要的數(shù)據(jù)恢復。

目前的數(shù)據(jù)恢復方案通常在存儲時對葉節(jié)點采用前綴編碼進行編碼，結(jié)合某些輔助的數(shù)據(jù)結(jié)構（例如結(jié)構概要），在Twig模式匹配時基于這些信息，對葉節(jié)點到根節(jié)點之間的所有數(shù)據(jù)進行恢復。這種方式在選擇恢復范圍時可以保證正確性，但會引入數(shù)據(jù)冗余，特別是有的數(shù)據(jù)中有重名節(jié)點出現(xiàn)的時候。

此外，如何選擇恢復的時機也是一個重要的問題。目前一般的處理方案是在Twig匹配時候，根據(jù)從路徑索引所獲取的葉節(jié)點進行恢復，然后再應用相應的Twig匹配算法。但是，這一恢復時機帶來了很大的復雜性。因為要準確確定路徑上的節(jié)點是否需要恢復，特別是在路徑上有重名的節(jié)點的情況，就必須對路徑上的節(jié)點就其是否滿足路徑結(jié)構進行考證，這個過程在恢復每個節(jié)點的過程中都是需要的，所以會嚴重影響數(shù)據(jù)恢復的效率。而不去準確地恢復中間節(jié)點，又勢必引入冗余節(jié)點，增加了算法處理的數(shù)據(jù)規(guī)模。

發(fā)明內(nèi)容

為解決上述中存在的問題與缺陷，本發(fā)明提供了一種基于結(jié)構概要的數(shù)據(jù)恢復方法，該方法是XML數(shù)據(jù)庫中存儲的內(nèi)容只有葉節(jié)點信息時，在基于路徑索引進行查詢時，重構所需要的中間節(jié)點數(shù)據(jù)的方法，所述技術方案如下：

一種基于結(jié)構概要的數(shù)據(jù)恢復方法，包括：

分析XML文檔樹數(shù)據(jù)，計算XML文檔樹葉節(jié)點對應的數(shù)據(jù)信息，并將所述葉節(jié)點數(shù)據(jù)信息進行存儲和索引；

將XPath查詢語句解析成Twig模式樹，分解模式樹拆分的簡單路徑，并標注感興趣的模式節(jié)點集；

記錄感興趣的模式節(jié)點序列集，并進行模式節(jié)點序列的合并；

根據(jù)記錄的感興趣的模式節(jié)點序列集，恢復與感興趣的模式節(jié)點序列集相匹配的數(shù)據(jù)節(jié)點集。

本發(fā)明提供的技術方案的有益效果是：

利用XML數(shù)據(jù)結(jié)構摘要信息和基于路徑的索引，在索引匹配與選取的過程中，恢復所需要的數(shù)據(jù)。從數(shù)據(jù)恢復范圍和數(shù)據(jù)恢復時機這兩方面對現(xiàn)有的方法進行了改進，可以正確、高效、準確地恢復所需要的數(shù)據(jù)，避免現(xiàn)有方法不準確，產(chǎn)生冗余等缺點。

附圖說明

圖1是基于結(jié)構概要的數(shù)據(jù)恢復方法流程圖；

圖2是XML數(shù)據(jù)示例圖；

圖3是樹模式查詢示例圖；

圖4是結(jié)構概要示例圖；

圖5是索引匹配過程示例圖；