基于樹模型的XML查詢匹配算法的設(shè)計(jì)與應(yīng)用

張 葉

(河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，南京 210098)

基于樹模型的XML查詢匹配算法的設(shè)計(jì)與應(yīng)用

張 葉

(河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，南京 210098)

在分析基于區(qū)間編碼的結(jié)構(gòu)連接算法Stack-Tree算法的基礎(chǔ)上，研究基于樹型模型的XML結(jié)構(gòu)編碼、XML查詢處理過程中路徑匹配等關(guān)鍵技術(shù)問題，并利用dom4j解析技術(shù)，基于Berkeley DB實(shí)現(xiàn)基于Stack-Tree算法的XML查詢?cè)拖到y(tǒng).實(shí)驗(yàn)結(jié)果表明本文設(shè)計(jì)的基于Stack-Tree算法的查詢系統(tǒng)在查詢時(shí)間，查詢準(zhǔn)確性以及全面性上能夠滿足對(duì)查詢系統(tǒng)的功能和性能要求.

XML；結(jié)構(gòu)化連接；結(jié)構(gòu)查詢；路徑匹配

XML又稱為可擴(kuò)展標(biāo)記語言，是由W3C組織于1998年2月發(fā)布的一種標(biāo)準(zhǔn).由于XML的組織結(jié)構(gòu)特征，關(guān)注XML的結(jié)構(gòu)特征成為查詢的關(guān)鍵因素之一.實(shí)際上任何一個(gè)XML文件是一種有序的樹型結(jié)構(gòu)，樹節(jié)點(diǎn)對(duì)應(yīng)于XML文件中的元素，一個(gè)樹節(jié)點(diǎn)的相對(duì)位置取決于它上下元素的位置.而結(jié)構(gòu)連接是實(shí)現(xiàn)數(shù)據(jù)庫系統(tǒng)XML文件查詢的關(guān)鍵.一種復(fù)雜的樹型模式可以分解為基本的二元結(jié)構(gòu)關(guān)系的集合，比如節(jié)點(diǎn)對(duì)間父親—孩子和祖先—子孫的關(guān)系.查詢模式匹配通過：1)根據(jù)XML文件匹配每一個(gè)二元結(jié)構(gòu)基本關(guān)系；2)集合返回這些基本匹配關(guān)系.

目前為止，結(jié)構(gòu)連接方法可以分為2類：一類是傳統(tǒng)的樹合并算法，一類是堆棧樹算法，這兩類算法首先將分支模式拆分為二元結(jié)構(gòu)關(guān)系，然后合并每一個(gè)二元結(jié)構(gòu)關(guān)系匹配后的結(jié)果[1].

1 模式樹與模式匹配

1.1 模式樹概念

本文工作以樹模型來表示XML.一個(gè)XML文檔是這樣一棵有根結(jié)點(diǎn)、有序的、帶標(biāo)簽的樹.樹的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)于XML文檔中的元素或者文本值，樹的邊表示元素—子元素或者元素—值關(guān)系，節(jié)點(diǎn)的標(biāo)簽由組成.XML文檔中同一層次節(jié)點(diǎn)的先后順序決定了這些節(jié)點(diǎn)在樹中的次序(文檔中這些節(jié)點(diǎn)的次序與樹節(jié)點(diǎn)的先序遍歷次序一致).

1.2 模式匹配

分支模式匹配方法主要分為2類：一類是基于拆分合并的方法； 另一類Holistic Join方法. 第一類方法分為兩個(gè)步驟：1)匹配分支模式中的所有二元結(jié)構(gòu)關(guān)系(Binary Structural Relationship)，如圖1(A)所示的分支模式可以拆分為圖1(B)所示的二元結(jié)構(gòu)關(guān)系；2)合并這些二元結(jié)構(gòu)關(guān)系的匹配結(jié)果.結(jié)構(gòu)連接兩種算法是基于拆分合并的.

圖1 分支模式及其對(duì)應(yīng)的二元結(jié)構(gòu)關(guān)系

基于拆分合并的方法根據(jù)是否使用緩存機(jī)制，可以分為直接歸并結(jié)構(gòu)連接和基于緩存的歸并結(jié)構(gòu)連接.前者主要有MPMGJN[2]算法和Tree-Merge[1]算法；后者主要有Stack-Tree-Desc[1]和Stack-Tree-Anc算法.這兩個(gè)算法基本思想是用棧存放嵌套祖先序列，在歸并過程中，通過動(dòng)態(tài)維護(hù)棧來避免重復(fù)查找.Stack-Tree相比于前者來說，可以避免重復(fù)查找，仍然需要維護(hù)每個(gè)二元結(jié)構(gòu)關(guān)系匹配后的中間結(jié)果.

2 系統(tǒng)總體方案

本系統(tǒng)主要分為前臺(tái)的用戶查詢和后臺(tái)的索引建立.后臺(tái)索引的建立主要是從數(shù)據(jù)庫中將數(shù)據(jù)取出經(jīng)過數(shù)據(jù)解析接口對(duì)數(shù)據(jù)進(jìn)行解析，將數(shù)據(jù)庫中的內(nèi)容解析成可以直接處理的格式，最后通過索引器對(duì)文檔建立索引.目標(biāo)是在分析當(dāng)今主流的XML結(jié)構(gòu)化查詢算法和技術(shù)的基礎(chǔ)上,研究基于樹型模型的XML結(jié)構(gòu)編碼、XML查詢處理過程中的匹配等技術(shù)問題，基于Berkeley DB實(shí)現(xiàn)相應(yīng)的XML查詢?cè)拖到y(tǒng).

因此，本次設(shè)計(jì)將系統(tǒng)設(shè)計(jì)流程分為四個(gè)模塊：解析，編碼，存儲(chǔ)，匹配.整個(gè)具體流程如圖2所示：

1)首先對(duì)XML進(jìn)行dom4j解析.使用DOM對(duì)XML文件進(jìn)行操作時(shí)，要解析文件，將文件分為獨(dú)立的元素、屬性和注釋等，然后以節(jié)點(diǎn)樹的形式在內(nèi)存中對(duì)XML文件進(jìn)行表示，就以通過節(jié)點(diǎn)樹訪問文檔的內(nèi)容，并根據(jù)需要修改文檔.

2)編碼：利用zhang編碼對(duì)XML所有節(jié)點(diǎn)進(jìn)行編碼；

3)將節(jié)點(diǎn)信息存儲(chǔ)到berkeley DB中.berkeley DB是一種嵌入式數(shù)據(jù)庫，主要研究berkeley DB的存儲(chǔ)機(jī)制.

4)研究匹配算法Stack-Tree算法.本文設(shè)計(jì)和實(shí)現(xiàn)了基于Stack-Tree算法的XML查詢?cè)拖到y(tǒng).在此基礎(chǔ)上，對(duì)基于Stack-Tree算法的XML查詢?cè)拖到y(tǒng)進(jìn)行實(shí)驗(yàn)分析.

3 系統(tǒng)實(shí)現(xiàn)

3.1 XML解析

XML是一種數(shù)據(jù)格式，每一種數(shù)據(jù)格式都需要一個(gè)解析器將其中的信息解析出來為你所用，XML當(dāng)然也不會(huì)例外.你可以用SAX或者DOM來構(gòu)建這種解析器.解析器包括兩種SAX(用于XML的簡(jiǎn)單API)和DOM(文檔對(duì)象模型).解析器會(huì)將文檔載入電腦的內(nèi)存中.一旦文檔被載入，可使用DOM或SAX對(duì)其數(shù)據(jù)進(jìn)行操作.

圖2 具體實(shí)現(xiàn)流程

本文使用Dom4j讀寫XML文檔，Dom4j是Document for Java的簡(jiǎn)稱，是用java解析dom文檔的組件.使用dom4j解析XML文檔的過程是這樣的，首先是將XML文檔轉(zhuǎn)換成dom4j樹之后，使用一致的編程模型來處理XML文檔.我們可以采用遞歸方法來獲取整份XML文檔里包含的信息.

將節(jié)點(diǎn)信息保存在Node.java中，結(jié)構(gòu)如下：

private int id;//節(jié)點(diǎn)編號(hào)

private String name; //節(jié)點(diǎn)名稱

private int start; // 節(jié)點(diǎn)起始位置

private int end;//節(jié)點(diǎn)結(jié)束位置

private int level;//節(jié)點(diǎn)所在層數(shù)

private String text;//節(jié)點(diǎn)內(nèi)容

在設(shè)計(jì)中，首先對(duì)使用SAXReader來解析XML文檔，采用先序遍歷方法來獲取整份XML文檔里包含的信息.

SAXReader saxReader = new SAXReader();//使用SAXReader來解析XML文檔

document = saxReader.read(new File(filename));//讀取XML文件，獲得document對(duì)象.

3.2 節(jié)點(diǎn)編碼

本系統(tǒng)的設(shè)計(jì)，節(jié)點(diǎn)編碼是基于zhang編碼實(shí)現(xiàn)的.下面介紹一下zhang編碼的規(guī)則.

Zhang編碼：這種編碼規(guī)則給XML文檔中每一個(gè)結(jié)點(diǎn)賦予一個(gè)三元組.對(duì)樹T的所有結(jié)點(diǎn)進(jìn)行先序遍歷，每一個(gè)結(jié)點(diǎn)在遍歷樹時(shí)分別被訪問兩次并產(chǎn)生兩個(gè)序號(hào).一次是在遍歷該結(jié)點(diǎn)的所有后裔結(jié)點(diǎn)之前訪問該結(jié)點(diǎn)，并產(chǎn)生該結(jié)點(diǎn)的序號(hào)begin；另一次是在遍歷完該結(jié)點(diǎn)的所有后裔結(jié)點(diǎn)后再一次訪問該結(jié)點(diǎn)，并產(chǎn)生該結(jié)點(diǎn)的另一個(gè)序號(hào)end；level是節(jié)點(diǎn)的層次.基于該編碼判斷兩個(gè)元素u，v間的結(jié)構(gòu)關(guān)系的方法如下：

1) u是v的祖先結(jié)點(diǎn)當(dāng)且僅當(dāng)u.begin < v.begin && u.end > v.end.

2) u是v的父親結(jié)點(diǎn)當(dāng)且僅當(dāng)u是v的祖先并且u.level = v.level -1.

3) u在v的左邊當(dāng)且僅當(dāng)u. end < v. begin.

節(jié)點(diǎn)編碼具體流程如圖3所示.

3.3 節(jié)點(diǎn)編碼設(shè)計(jì)與存儲(chǔ)

Berkeley DB所管理數(shù)據(jù)的邏輯組織單位是若干個(gè)獨(dú)立或有一定關(guān)系的數(shù)據(jù)庫，每個(gè)數(shù)據(jù)庫由若干記錄組成，這些記錄全都被表示成(key，value)的形式.如果把一組相關(guān)的(key，value)對(duì)也看作一個(gè)表的話，那么每一個(gè)數(shù)據(jù)庫只允許存放一個(gè)table，這一點(diǎn)不同于一般的關(guān)系數(shù)據(jù)庫.實(shí)際上，在Berkeley DB中所提到的“數(shù)據(jù)庫”，相當(dāng)于一般關(guān)系數(shù)據(jù)庫系統(tǒng)中的表；而“key/data”對(duì)相當(dāng)于關(guān)系數(shù)據(jù)庫系統(tǒng)中的行(rows)；Berkeley DB不提供關(guān)系數(shù)據(jù)庫中列直接訪問的功能，而是在“key/data”對(duì)中的data項(xiàng)中通過實(shí)際應(yīng)用來封裝字段(列).

因此，將節(jié)點(diǎn)信息存儲(chǔ)到數(shù)據(jù)庫Berkeley DB中采用鍵值對(duì)(key，value)的形式，其中key指id 代表節(jié)點(diǎn)順序編號(hào)，value代表各屬性之和，表示如下：

String key = node.getId()+"";

String value=node.getName()+"@"+node.getStart()+"@"+node.getEnd()+"@"+

node.getLevel()+"@"+node.getText();

本文的工作采用Berkeley DB[3]來存儲(chǔ)XML的節(jié)點(diǎn)編碼，Berkeley DB能夠很好地支持XML節(jié)點(diǎn)的檢索[4].XML節(jié)點(diǎn)編碼后的以(key，value)的形式存儲(chǔ)在Berkeley DB中.其中key是節(jié)點(diǎn)的編號(hào)，value是節(jié)點(diǎn)在XML文檔中的所有屬性.[5]

new BDBTest().insert(MyData.Nlist);//將遍歷結(jié)果保存到數(shù)據(jù)庫

圖3 節(jié)點(diǎn)編碼流程

3.4 基于樹模型的Stack-Tree連接算法

Stack-Tree連接算法輸入對(duì)象是AList[a1,a2,a3,…]和DList[d1,d2,d3,…],分別表示XML樹中謂詞匹配祖先-子孫關(guān)系連接(ai,dj)節(jié)點(diǎn)的集合.ai,dj都是節(jié)點(diǎn)的編碼元素,而AList,DList中的元素分別按(docID,startPos)從小到大順序排列.這里算法分析都是假設(shè)AList,DList都是已經(jīng)得到的有序的輸入隊(duì)列.

Stack-Tree方法包含兩個(gè)算法Stack-Tree-Anc和Stack-Tree-Desc，但他們分別實(shí)現(xiàn)了連接結(jié)果按祖先或后裔有序.本文主要采用算法Stack-Tree-Anc.

在文獻(xiàn)[1]中提出Stack-Tree連接算法的主要思想:當(dāng)發(fā)現(xiàn)AList中的當(dāng)前節(jié)點(diǎn)是當(dāng)前棧頂節(jié)點(diǎn)的子孫時(shí)，堆棧AList中此節(jié)點(diǎn).堆棧始終是祖先節(jié)點(diǎn)的序列，在棧中的每一個(gè)節(jié)點(diǎn)是它棧底元素的子孫.這時(shí)，如果DList中當(dāng)前節(jié)點(diǎn)是棧頂元素的子孫，它就是棧中所有堆棧元素的子孫節(jié)點(diǎn).而如果AList中下一個(gè)元素不是棧頂元素的子孫則再?zèng)]有元素是當(dāng)前棧頂元素的的子孫，也可以保證DList中當(dāng)前節(jié)點(diǎn)不是棧外其他的節(jié)點(diǎn)的子孫.

Stack-Tree-Anc算法的outputList的輸出序列按照AList中元素的順序輸出所有的基本關(guān)系序列(ai,dj) (j=1,2,3,…).

對(duì)于AList中的當(dāng)前節(jié)點(diǎn)a和DList中的當(dāng)前節(jié)點(diǎn)d.如果a和d是棧頂元素的子孫且a.begind.begin (此時(shí) AList中不存在d的祖先)則當(dāng)前棧中所有元素與d輸出；如果a和d不是棧頂元素的子孫，則出棧.重復(fù)，直至Alist或Dlist為空.

Stack-Tree-Anc算法是用棧來存放一個(gè)嵌套的祖先節(jié)點(diǎn)序列，為實(shí)現(xiàn)按照祖先有序輸出結(jié)果，棧中每個(gè)元素維護(hù)了兩個(gè)列表self-list和inherit-list，其中self-list用來存放臨時(shí)該節(jié)點(diǎn)的連接結(jié)果，inherit-list用來存放該節(jié)點(diǎn)的所有子孫節(jié)點(diǎn)繼承來的連接結(jié)果，直到棧底元素出棧時(shí)才能依次輸出兩個(gè)列表中的結(jié)果.連接過程中，對(duì)于AList中的當(dāng)前節(jié)點(diǎn)a和DList中的當(dāng)前節(jié)點(diǎn)d.如果a和d是棧頂元素的子孫且a.begind.begin (此時(shí) AList中不存在d的祖先)將棧底和d輸出，并將除棧底外其他棧元素和d添加到該棧的self-list中；如果a和d不是棧頂元素的子孫，則出棧頂元素.如果棧為空則將棧頂元素的inherit-list輸出，否則將棧頂元素的inherit-list和self-list添加到當(dāng)前棧頂元素的inherit-list.

3.5 實(shí)驗(yàn)結(jié)果評(píng)價(jià)與分析

本實(shí)驗(yàn)設(shè)計(jì)了基于Stack-Tree匹配算法的查詢系統(tǒng)，為了更好地展現(xiàn)zhang編碼的準(zhǔn)確性，特地設(shè)計(jì)了一般Xpath查詢與基于zhang編碼查詢的對(duì)比,通過結(jié)果的對(duì)比來確定基于zhang編碼查詢的完整性，正確性.

為了驗(yàn)證實(shí)驗(yàn)的有效性，我們?cè)趯?shí)驗(yàn)的時(shí)候?qū)ML文檔多次查詢，通過對(duì)系統(tǒng)的查詢結(jié)果和查詢時(shí)間的計(jì)算，可以得到不同路徑下查詢所用時(shí)間，見表1.

表1 查詢所用時(shí)間

Xpath查詢路徑一般Xpath查詢時(shí)間/s論文實(shí)現(xiàn)查詢時(shí)間/s/SigmodRecord/issue0．20．3/SigmodRecord/issue/volume0．41．5/SigmodRecord//volume0．31．6/SigmodRecord/issue/articles/article0．42．6/SigmodRecord/issue/articles/article/title0．54．3

實(shí)驗(yàn)分析表明，使用Tree-Merge算法實(shí)現(xiàn)了簡(jiǎn)單查詢的查詢系統(tǒng)要求，通過實(shí)驗(yàn)結(jié)果可以看出查詢結(jié)果正確，與Xpath在準(zhǔn)確性上達(dá)到了一致，在查詢結(jié)果的完整性上是一致的.

[1] AL-KHALIFA S, JAGADISH H V, KOUDAS N,etal. Structural Joins:A Primitive for Efficient XML Query Pattern Matching [C]//San Jose, CA: IEEE, 2002,141-152.

[2] ZHANG C NAUGHTON J, DEWITT D,etal. On supporting containment queries in relational database management systems [C]//New York: 2001 ACM SIGMOD international conference on Management of data, 2001.425-436.

[3] BERKELEY D B. http://www.oracle.com/technetwork/products/berkeleydb/over-view/index.html, 2012.

[4] LI Q Z, MOON B. Indexing and querying XML data for regular path expressions [C]// San Francisco: the 27th VLDB International Conference on Very Large Databases,2001.361-370.

[5] 賈曉芬，趙佰亭，周孟然，等.采用圓投影和序貫相似檢測(cè)的圖像匹配技術(shù)[J].哈爾濱商業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2015，31(2)：232-236，241.

Design and application of XML query matching algorithms based on tree model

ZHANG Ye

(Hohai University, School of Computer and Information, Nanjing 210098, China)

In this paper, XML structure coding based on tree model and the path matching in XML query processing were studied on the basis of analyzing the connection algorithm Stack-Tree algorithm based on interval coding structure. A XML query prototype system based on a Stack-Tree algorithm was realized using dom4j analytical techniques on the basis of Berkeley DB. Experimental results showed that the query time, query accuracy and comprehensiveness of the query system based on Stack-Tree algorithm in this paper could satisfy the function and performance requirement of the query system.

XML; structural join; structure query; path matching

2014-06-23.

張 葉(1989-)，女，碩士，研究方向：數(shù)據(jù)管理、云計(jì)算.

TP311

A

1672-0946(2015)03-0354-04