一種基于樹狀邏輯式的ＸＭＬ查詢方法

(1.襄樊職業技術學院 信息技術系， 湖北 襄樊 441050；2.武漢大學 軟件工程國家重點實驗室， 武漢 430072；3.Carleton大學 計算機系， 加拿大 渥太華 K1S5B6)

摘 要：隨著XML在各類數據表示中的廣泛應用，XML文檔的查詢方法成為當前數據處理的一個重要問題。已有的研究如XPath和XQuery得到應用，但其查詢表現存在一些缺點需要改進。從模板匹配的角度出發，基于謂詞邏輯設計了樹狀邏輯表達式LXT。該表達式的特點是能以樹狀結構模板描述XML文檔查詢需求。在此基礎上，進一步探討了基于LXT表達式的XML文檔查詢方法，從數據的查詢過濾、結果的組織構造與含義等方面描述了利用LXT的特點設計XML查詢表現形式的基本思路。

關鍵詞：XML;查詢語言；邏輯；模板匹配

中圖分類號：TP311.1 文獻標志碼：A

文章編號：10013695(2009)02060803



XML query approach based on logic XML tree



ZENG Hong1，LI Xuhui2，LIU Mengchi2，3

(1.Dept. of Information Technology， Xiangfan Vocational Technical College， Xiangfan Hubei 441050， China；2.State Key Laboratory of Software Engineering， Wuhan University， Wuhan 430072， China；3.Dept. of Computer Science， Carleton University， Ottwa K1S5B6， Canada)

Abstract:With the wide application of XML in data representation and exchange， the query approach to XML document becomes a key problem in current data processing. Some studies such as XPath and XQuery had been adopted and applied， however， these works were still to be improved in query presentation.Following the idea of pattern matching，this paper designed a new logic tree expression called LXT which could present the XML query in a tree pattern. Further，discussed the XML approach to query XML document based on LXT expressions， including the features of filtering and constructing the query result，which illustrated the ideas of designing the XML query language with LXT. 

Key words:XML; query language; logic; pattern matching



XML目前已經成為網上數據描述和交換的標準，并已被廣泛應用于各種數據的表示（如各類文檔、設備日志乃至多媒體數據等）和標注。隨著信息技術的發展和網絡的普及，信息資源規模急遽增長，其中以XML文檔為主的半結構化數據資源占有比例不斷提高。以關系與對象模型為基礎的傳統數據查詢方法并不適于刻畫XML文檔的查詢需求，因此近年來XML文檔查詢方法成為數據處理領域的一個重要研究方向，其研究與應用成為相關研究領域所共同關注的熱點問題。

XML查詢方法的研究始于20世紀末。自本世紀初開始，數據庫和程序設計語言領域的研究者們分別從自身的研究背景和需要出發，陸續提出了多種XML文檔的處理與查詢方法，并以此為基礎設計了相應的XML處理與查詢語言。這些查詢方法基于不同的數據結構刻畫XML數據特點，并采用相應的處理方法提取所需的數據元素形成查詢結果。在這些XML查詢語言中，W3C所倡導的XQuery語言逐漸被接受，成為目前應用最廣的一種XML查詢語言。盡管當前XML查詢方法的研究已經取得了豐碩成果，但已有的研究仍然存在許多不盡如人意之處，促使研究者們不斷探索新的方法以更好地解決XML查詢的表現和處理等問題。

筆者在已有的研究基礎上提出了一種基于樹狀邏輯表達式的XML文檔查詢方法。該方法的主要優點是：利用邏輯形式描述XML查詢需求，并利用樹狀結構作為復合方式將簡單邏輯式合成復合邏輯樹形式，以此作為XML文檔模板（pattern），利用模板匹配（pattern matching）的思路進行XML文檔的查詢?；诖诉壿嬍降腦ML查詢表示具有語義簡單清晰、語法結構緊湊等特點，非常適合于構造聲明型XML查詢語言。

1 相關研究

XML查詢方法主要指各種對XML文檔進行搜索、匹配和轉換的方法，其研究成果主要以XML查詢語言形式表現。如前所述，目前研究者們已經設計了多種XML查詢處理語言或方法，包括Lorel、XQL、 XMLQL、TATL、TQL、Quilt、XDuce、XSLT、XPath、XQuery以及XTree等。這些語言相互關聯又有明顯區別。這里簡要介紹其中幾種較具代表性的研究方法。

XML查詢語言中所采用的比較普遍的文檔搜索和匹配方法是模板匹配方法。模板匹配的概念來自函數式程序語言，其基本思路是根據要處理的數據結構特點，將變量引入到數據結構中，以表示需要獲取的數據成分。由這些變量和相關常量形成的抽象數據結構就稱為模板。當目標數據實例被映射到模板上時，模板中的變量與目標數據實例中的相應數據元素綁定，從而實現數據的匹配，并可進行匹配數據的進一步轉換處理。

XML文檔處理最初僅引入了思路非常簡單的模板匹配方法。如XMLQL[1]語言中利用XML文檔片斷作為模板的數據結構，直接在一個XML元素中以變量代替子元素形成模板，并通過基本的數據合成方法進行匹配數據的轉換。原始的XML文檔模板匹配思路過于簡單，難以完成復雜的查詢，為此研究者們從不同角度深入探討了基于模板匹配的XML查詢方法。

程序語言領域的研究者們利用成熟的程序語言理論（如類型系統等）對XML文檔查詢處理進行了深入研究。以XDuce[2]、CDuce[3]等為代表的函數式XML處理語言引入了表現XML文檔結構特點的正規表達式類型系統，并基于該類型系統設計了具有典型函數式語言特點的模板及匹配方法。這些語言中模板的特點是基于類型構造并具有類型推導功能，因而XML數據在處理過程中始終能獲取其數據類型。

數據庫領域的研究者們對XML文檔的結構表示形式進行改進，設計了表現能力更強的模板。例如文獻[4]提出了一種樹狀XML結構XTree，利用一種嵌套的線性形式表示文檔的樹結構，使模板的表現形式更加緊湊。

另一種XML查詢方法則采用了函數式語言的基本思路，將整個查詢過程視為一個函數執行序列，其中有代表性的是XPath[5]和XQuery[6]。XPath采用了一種稱為軸(axis)的函數處理方法，從一組預定義的過濾函數中選擇若干函數形成一個步進式(step)函數管道，XML文檔通過這個函數管道后得到的處理結果即為查詢結果。XPath的處理形式單一，為增強其表達能力，XQuery在XPath的基礎上引入了FLWOR表達式，通過循環和嵌套將XPath的結果進行進一步的加工處理，從而表現復雜的查詢需求。

此外，還有一些交叉研究利用其他領域的理論方法（如進程演算、描述邏輯）對半結構化數據和XML數據的查詢表現進行了探討，其中較具代表性的研究如TQL[7]采用了一種基于Mobile Ambient演算的Ambient邏輯設計了適合XML文檔處理的半結構化數據查詢語言。本文所進行的研究工作就是在借鑒上述研究成果基礎上設計的一種新的基于邏輯的XML查詢表現方法。

2 LXT：XML樹狀邏輯式

本文所提出的新的XML查詢方法基于一種稱為LXT（logical XML tree）的樹狀XML邏輯表達式。筆者設計此邏輯表達式的初衷是針對XQuery語言表現復雜查詢時因XPath表現能力較弱而存在程序繁冗的情況，結合模板匹配與邏輯方法構造新的模板形式，以清晰表現復雜XML查詢需求。

如前所述，XQuery語言以XPath表達式為基礎。XPath表達式以一種線狀路徑形式表現基本的查詢要求，其實質是一個函數管道，其功能是將文檔通過若干步驟函數進行處理后得到過濾結果。例如表達式/bib/book[count(author)>1]就表明針對目標文檔依次經過求子元素函數child:bib、child:book以及過濾函數count(author>1)等構成的函數管道進行求值。XPath采用的這種函數管道形式有一個明顯的不足，即一個XPath表達式僅能與一個變量綁定，因此在表示復雜查詢時需要利用XQuery語言中的let和for等語句將XPath表達式的返回結果作進一步的處理。使用XQuery表現復雜查詢時，常需要頻繁使用let和for語句，使程序中出現過多的嵌套循環和不必要的變量綁定；同時，XQuery利用for循環來枚舉XPath的查詢結果數據實例，其默認采用的一次一個數據元組的處理方式與數據庫查詢處理通常所采用的一次一個數據集合的方式不符，因而導致查詢處理時的額外開銷。

與XPath相比，利用模板匹配的方法進行查詢要顯得相對簡單直觀。以文獻[4]所提出的XTree為例，一個形如/bib//book=>$b[author [last=> “Stevens”， first=>$f]， @year=>1992， publisher=> “Addison Wesley”]的XTree表達式形成了一個XML文檔結構模板，該模板表示一個由祖先節點元素bib、后代節點元素book以及book的子元素author、publisher和屬性year等構成的樹狀XML文檔結構，通過指定author元素的子元素last為Stevens、year屬性為1992以及publisher元素為Addison Wesley，查詢與此相匹配數據中author的子元素first和book元素，并將其分別綁定到變量$f和$b。

利用模板匹配進行查詢的優點在于，可以同時綁定多個變量，從而使查詢表現得更加緊湊清晰（如文獻[4]對XTree和XPath的查詢表現進行了比較），以此為基礎設計的XML查詢語言通常具有典型QL語言的形式，具有簡便易用的優點。然而已有的基于模板匹配的XML查詢方法并未得到廣泛應用，其主要原因在于：a）現有的XML模板結構通常僅描述XML文檔元素間的相對位置結構關系，如XTree能同時描述元素間層次關系和兄弟關系，但復雜查詢通常更注重元素所滿足的邏輯條件，僅刻畫XML文檔結構特點的模板不具備足夠的表達能力；b）利用模板匹配方法得到的數據需要以合適的方式組織和轉換形成最終結果，才能滿足用戶的最終需求，但現有的研究在組織和轉換數據的形式上還有欠缺。

LXT是一種基于一階邏輯的樹狀XML模板，它在語法結構上參考了其他模板匹配方法和邏輯方法的特點，其基本形式是一組由“元素名=>內容”形式的模板通過“[]”“，”“||”等連接符構成的復合模板，元素名和內容均可用常量或變量代替，并允許一部分缺省以表示通配情況。對于一個元素的內容相關的模板被包含在一對“[”“]”中，并且“[]”可以嵌套，以表示樹狀結構。LXT中，一個模板表示一個聲明存在指定元素的謂詞命題，其中變量能被相應的數據取代以使該謂詞為真。這種基于邏輯的模板語義使人們能夠完全從邏輯的角度去考慮查詢的表述，而不是像以往的基于文檔結構的模板那樣僅能允許指定待匹配文檔的結構特點。同時，為了表示文檔結構特點，LXT也引入了常用的“/”“//”等符號表示父子和祖先—后代節點關系。例如，LXT模板表達式bib/book[author=>$a， title=> “XML Specification”， //publisher] 表示bib元素下存在滿足下列條件的book子元素：該元素中存在author子元素其內容且以$a表示，存在內容為“XML Specification”的title子元素，以及存在publisher后代元素。

LXT模板表達式引入了三個常見的邏輯操作符“與”“或”“非”。與操作符以“，”表示，或操作符以“||”表示，非操作符則以“not”表示。上面的LXT模板中，book元素的各個子元素的相關模板以“，”間隔，表示各子模板謂詞之間是邏輯與關系。例如，LXT模板book[author=>$a， editor=>$e]表示book元素中既存在author子元素（綁定到變量$a）又存在editor子元素（綁定到$e），因此該命題的一個證明可由一個author和editor子元素對構成，綁定到($a，$e)上。而LXT模板book[author=>$a || editor=>$e]則表示book元素中存在author子元素（綁定到變量$a）或存在editor子元素（綁定到$e），該命題的一個證明可由一個author或editor子元素構成，分別綁定到$a或$e上。非操作符“not”既可以表示模板命題的否命題，也可以表示對具體值的否定。例如not(/name=>value)表示文檔中不存在一個name=>value模板的實例，而name=>not(value)表示存在元素name的內容不為value。

LXT模板可以利用各種邏輯操作符表達相當復雜的查詢邏輯。例如，如果需要查詢滿足要求的book元素，使其內容中沒有名為“W.Steven”的作者，并且至少有一個姓為“Smith”或“Green”的作者，則其對應的LXT模板可以為/bib/book=>$b[not(/author[last=>“Stevens”，first=> “W.”])， author[last=>( “Smith”||“Green”)]]。

3 基于LXT的XML查詢方法

在LXT的基礎上，本文進一步設計了XML文檔的一般查詢表現方法。基于LXT的查詢分為查詢數據和構造結果兩部分。

3.1 查詢數據 

LXT提供了一種基本的樹狀邏輯表示形式，可從邏輯的角度刻畫XML查詢要求，但其表達能力仍然不足以描述一般情況下的查詢需求。一方面，一個LXT表達式僅針對一個數據源設計，當需要對多個數據源之間關系需要滿足的復雜查詢描述其限定條件時，需要額外的輔助描述方法以刻畫多數據源的關系；另一方面，LXT是一種簡單的謂詞邏輯，需要對其進行擴展，通過引入量詞使其具備完整的一階邏輯表達能力。為解決此問題，本文設計了基于LXT的XML數據查詢方法。

基于LXT的XML數據查詢由一組LXT表達式和一個條件子句where構成。各LXT表達式之間以“，”分隔，這些LXT表達式的匹配過程相互獨立，其相互之間的關系由where子句進一步限定。例如：

doc(“book.xml”)/book=>$b[author=>$a， title=>$t]， doc(“doc.xml”)/doc=>$d[author=>$a1， title=>$t1]

表示兩個數據源分別為“book.xml”和“doc.xml”的LXT表達式，需要分別了解兩個文檔中的book和doc元素及其author和title子元素的情況。當需要進一步限定條件以建立兩個文檔之間的關系時可以引入where子句。Where子句由一組包含變量的邏輯式構成。Where邏輯式與LXT邏輯式有明顯區別：首先，where邏輯式的變量是已經在前面的LXT中出現過的變量，稱為綁定變量，這些變量指稱LXT中其對應的匹配元素或值。其次，where邏輯式由常見的布爾運算和算術布爾運算如“and”“or”“not”“imply““=”“>”等構成，而非采用LXT的樹狀結構。利用where子句的邏輯式，一方面可以進一步限定LXT表達式的匹配值應滿足的條件，另一方面可以將多個表達式通過匹配變量之間的關系進行連接。例如，在上例中加入where $a1=$a2，即可將兩個LXT表達式通過author元素值自然連接。

此外，where邏輯式除了簡單的算術布爾表達式，還引入了全稱量詞foreach 和存在量詞forsome，因此引入where子句后，可通過LXT表達式和where子句利用一階邏輯表現多數據源上的復雜查詢需求，并可在邏輯式中引入合適的輔助函數形成實用的數據查詢方法。例如，一個比較完整的數據查詢如下：

doc(“book.xml”)/book=>$b[author=>$a， title=>$t]，doc(“doc.xml”)/doc=>$d[author=>$a1， title=>$t1]where $a=$a1 and(foreach $t1， strcontain($t， “Unix”))

顯然，該查詢表示限定book和doc元素中的author子元素具有相同值，并且book元素的title子元素中含有“Unix”。

3.2 構造結果 

LXT表達式僅能從數據源中提取出若干匹配值，而where子句通過邏輯條件可對這些匹配值進一步過濾。如何將這些最終得到的匹配值有效組織起來，以構造出符合用戶需要的查詢結果，是構造基于LXT的查詢方法需要解決的另一個重要問題。

從結果構造的形式與含義兩個方面來進行結果構造。從結果構造的形式方面，采用樹狀結構模板來構造結果。具體的構造方法仍然采用“元素名=>內容”作為基本的模板形式，利用括號“[”“]”包含同屬于一個父元素的各子元素，并通過“[ ]”的嵌套表示結果的樹狀結構。例如，對于一個LXT表達式book=>[author=>[first=>$f， mid=>$m， last=>$l]， title=>$t]，其查詢結果由各book元素的author子元素的first、mid和last等子元素值以及title子元素值分別綁定到$f、$m、$l、$t上構成?？梢曰诖瞬樵兘Y果，利用一個樹狀構造模板book=>[author=>[first=>$f， last=>$l]， title=>$t]，將其中的$f、$l、$t組織起來形成一個僅包含first和last子元素的author元素，并進一步將其與title元素結合成為構造結果的book元素的內容。

從結果構造的含義方面，需要在進一步規范對LXT表達式的匹配值組織結構基礎上確定結果構造方法的實際含義。LXT表達式模板對其中的各種變量之間的位置關系進行了描述。當模板與數據源相匹配時，其結果實際上構成了一棵由變量匹配值組成的樹。例如，對于LXT表達式/doc/book[author=>$a， title=>$t]，其作為邏輯命題的證明可由($a， $t)對給出；而當該表達式與數據源doc(“book.xml”)匹配時，文檔中所有的合法($a，$t)匹配值對都可看成是該LXT邏輯式的一個證明實例。因此，對于一個構造樹book[author=>$a， title=>$t]，每一個($a，$t)匹配值對均可以生成一個新的book元素。

但是這些匹配值$a、$t本身仍然存在一定的空間位置關系，該位置關系由LXT表達式所指定。在此例中，顯然可知本屬于同一個book元素下的author子元素和title子元素所對應的$a和$t自然形成一個集合，并與其他book元素下的($a，$t)匹配值自然區分。因此，所有的($a， $t)匹配實例根據其具體位置構成了一個由author和title元素內容按照原始文檔中的元素間父子和兄弟關系形成的樹。為表示其樹狀結構，可引入一個集合符號“{ }”，例如{$a}表示一個book元素下的所有author子元素的內容，而{{$a}， {$t}}則可將一個book元素下的所有author和title子元素聚合起來，使其相對保持原始文檔中對應元素內容的位置關系。因此，可以用構造樹book=>{[author=>{$a}， title=>{$t}]}的形式來構造一個保持原始文檔中book、author、title三者相對位置關系的新文檔。

3.3 進一步的工作

上述方法僅僅討論了基于LXT進行查詢表現的一些基本思路，本文沿此思路對數據查詢和結果構造進行了深入的探討，基本完成了包括子查詢、遞歸、分組等多種實用查詢手段的表示。以這些工作為基礎，本文設計了基于LXT的新的XML查詢語言XTQ[8]，并利用上述的查詢結果樹給出了語言的操作語義[9]，實現了語言核心內容的原型系統。目前筆者正進一步完善語言的設計與實現工作。

4 結束語

XML作為目前應用最廣泛的數據描述與交換標準，其文檔查詢方法是數據管理領域的一個重要問題。本文從模板匹配的角度出發，基于一階邏輯設計了樹狀邏輯表達式LXT。該表達式的特點是能以嵌套樹狀結構模板描述XML文檔查詢需求。在此基礎上，本文進一步探討了基于LXT表達式的XML文檔查詢方法，從數據的進一步查詢過濾、結果的組織構造與含義等方面描述了利用LXT的特點設計XML查詢表現形式的基本思路。目前筆者按此思路設計了一個XML查詢語言XTQ，并正進一步完善其語言和原型系統。

參考文獻：

［1］

DEUTSCH A，FERNANDEZ M，FLORESCU D，et al.XML-QL:a query language for XML[EB/OL].(1998-08-19).http://www.w3.org/TR/1998/Note-xml-ql-19980819.

［2］HOSOYA H，PIERCE B.XDuce:a typed XML processing language[J].ACM Trans on Internet Technology，2003，3(2):117-148.

［3］BENZAKEN V，CASTAGNA G，FRISCH A.CDuce:an XML-centric general-purpose language[C]//Proc of ICFP.2003:51-63.

［4］CHEN Zhuo， LING T W，LIU Meng-chi，et al.XTree for dec larative XML querying[C]//Proc of the 9th International Conference on DASFAA.2004:100-112.

［5］BOAG S，CHAMBERLIN D，FERNANDEE M，et al.XQuery 1.0:an XML query language[EB/OL].(2007).http://www.w3.org/TR/xquery/. 

［6］BERGLUND A，BOAG S，CHAMBERLIN D，et al.XML path language (XPath) 2.0[EB/OL].(2007).http://www.w3.org/TR/xpath20/.

［7］CARDELLI L，GHELLI G.TQL:a query language for semistructured data based on the ambient logic[J].Mathematical Structures in Computer Science，2004，14:285-327. 

［8］LI Xu-hui，LIU Meng-chi.Design issues of XTQ language[C]//Proc of CIT 2008.[S.l.]：IEEE CS Press， 2008.

［9］LI X，LIU M.Formal semantics of core XTQ， technical[EB/OL].(2008-01-20)[2008-04-20].http: //www.sklse.org:8080/XTQ.

08040963