[發明專利]一種針對擴展XML樹型結構的查詢方法

無效

• 申請號: 200910222334.2
• 申請日: 2010-03-24
• 公開（公告）號: CN101763406A
• 公開（公告）日: 2010-06-30
• 發明（設計）人: 陸嘉恒
• 申請（專利權）人: 陸嘉恒
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬于信息技術領域中XML數據查詢技術，具體涉及一種對擴展的XML樹型結構的查詢方法。

背景技術

隨著XML數據在商業、企業中的廣泛使用以及在交換信息中的流行，有效的處理XML數據查詢也變得越來越重要。一個XML查詢模式通常能用一個有根的標簽樹(或者是小枝樹)來表示。例如，圖1(a)為一個XPath查詢A[B][C]和一個相關的XML樹模型，此查詢用來找到有一個孩子結點B和C的所有結點。在圖(b)的查詢中，查詢結果是結點A₁和A₂。

對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是一個選定的輸出結點。