基于Schema的XML混合编码索引查询技术

夏　刚　刘林静　楼文高,2

1(上海理工大学光电信息与计算机学院　上海 200093)

2(上海商学院　上海 200235)



基于Schema的XML混合编码索引查询技术

夏刚1刘林静1楼文高1,2

1(上海理工大学光电信息与计算机学院上海 200093)

2(上海商学院上海 200235)

摘要Web中存在着越来越多的XML的文档，如何高效地从XML文档查询出有效信息已经成为当前在半结构化数据研究领域中的热点问题。针对XML文档节点进行编码和建立索引结构可以有效地提高查询速度，提出一种SBXHCI(Schema-Based XML Hybrid Coding Indexing)查询技术，该方法充分利用Schema信息对XML文档进行编码和构建索引。对创建索引所花费的时间和空间，查询响应的时间进行大量的实验分析，结果表明SBXHCI方法的编码机制降低了索引结构在时间和空间的资源消耗，并且在路径查询的响应速度有着显著的提高。

关键词SchemaXML路径表达式混合编码索引

QUERY TECHNOLOGY FOR SCHEMA-BASED XML HYBRID CODING INDEX

Xia Gang1Liu Linjing1Lou Wen’gao1,2

1

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China)2(Shanghai Business School,Shanghai 200235,China)

AbstractThere are more and more XML documents in Web, how to efficiently query the effective information from XML document has become the hot issue in the field of semi-structured data research at present. Aiming at that coding for XML document nodes and the establishment of index structure can improve the query speed effectively, this paper proposes an SBXHCI (schema-based XML hybrid coding index) query technology, it makes full use of Schema information to encode the XML documents and to build index. Then we carry out a great deal of experimental analysis on the index creation time, space and query response time. Results show that the encoding mechanism of SBXHCI method reduces the resource consumption of the index structure in time and space, and the response speed of path query has improved significantly.

KeywordsSchemaXMLPath expressionHybridcodingIndex

0引言

随着互联网的迅速发展，可扩展标记语言XML由于其良好的数据格式、丰富的数据表示能力及验证机制，已经成为Web中数据表示和交换的标准。XML在Web中广泛应用使得XML文档的结构变得越来越复杂和数据量越来越大，导航式的遍历显然已经不能满足查询所需的要求，对XML文档节点编码并建立索引可以快速有效地定位出需要访问的节点[1]，提高XML数据访问的查询效率。因此对XML数据建立索引是一个必要的手段，也成为了当前XML查询中研究的热点问题。

对XML文档建立索引，就是将具有相同标签的XML节点划分在同属一个索引节点类中[2]。目前，国内外对XML建立索引技术的研究取得了丰富的研究成果。例如，最早提出对XML文档建立索引的思想来源于文献[3]提出的基于结构概要的DataGuide索引方法，它的本质是一个确定自动机，能够根据绝对路径很好地给出响应查询，但却不能提供相对路径的查询。文献[4]提出带有分支路径查询的F&B索引，它可以快速地查询出带有分支路径的查询，但是F&B在构建索引时消耗的内存资源过大。文献[5,6]提出的基于元素、属性和结构的XISS索引，它将一个复杂的路径表达式分解成若干个简单路径，通过对XISS索引的访问来处理每个简单路径的查询处理得到满足结构关系的中间结果，最后对这些中间结果依次进行结构连接得到查询的最终的结果。但该方法对具有N个元素或者属性组成的路径查询表达式，XISS索引需要从XML文档中访问N组节点，并且至少需要N-1次结果的结构连接，因此会增加结构连接运算的时间。文献[7-9]都是基于DTD的XML索引方法DBXI，该方法能够很好地将DTD的结构信息保存到XML文档中元素和属性中，并且能够快速地访问到结果集。但该方法对XML文档使用区间编码的方法，这种编码对于分解后的简单路径查询存在着很多不相关的结果和结构连接运算相对复杂，并且对于DTD自身也存在着很多的缺陷性。文献[10,11]提出了基于Schema的SBXI索引方法，但这些方法中对XML文档也是使用区间编码的方法。

为了避免上述方法中存在的缺点，本文提出了一种基于XML Schema混合编码的索引方法SBXHCI，其优点在于：通过使用Schema，避免了DTD本身的多种缺陷；把Schema中的信息存入相应的XML文档中，可以快速地去除了不相关节点的访问，有效地减少结构连接次数，并能确保所有待查询节点都能被访问；根据前缀编码和区间编码各自的优点，对XML文档采用混合编码建立索引结构，这种编码方法可以快速地查询出待查询的节点和加快了结构连接的速度，从而提高查询效率和准确率。

1XML文档和模式

1.1XML文档模型

定义1XML文档树：一个XML文档T可以表示成一颗带有标签的有序树(V，E，Label，Root)。其中V表示文档中节点的有限集合，V=element∪attribut，element和attribute分别代表文档中的元素节点和属性节点；Root是文档树T中的根节点Root∈V；E=V×V是文档中有向边的集合；Label是文档中V到V的集合，既文档树中每个节点分别指明一个标签作为节点标识。下面给出了一个关于书架的XML文档简略片段，图1给出了对应的文档树的模型，其中椭圆形代表节点，三角形代表属性，矩形代表文本。

H.Cormen

E.Leierson

128.00

< publisher>China Machine Press

图1　书架的XML Schema文档示例

从图1中可以看出文档的根节点为bookshelf，它的子节点是由book元素组成，每个book节点都有一个属性id；节点集合及其边对应的关系都可以很容易从文档书中看出。

1.2XML模式

模式定义语言使XML文档遵循一定规则，可以有效地描述和确定出文档的特性，从而得到一个良构的XML文档。它不仅规定了XML文档中可以使用的元素和元素的数据类型，而且还定义了文档中元素出现的顺序和次数以及其节点的嵌套关系等。目前比较广泛使用的是DTD和XML Schema模型。

DTD使用一种特殊的语法来表示XML文档中的元素和属性，如表示bookshelf元素包含一个或者多个book元素，表示book元素的属性id是必须且只能出现一次。而Schema使用一种与XML文档相同的语法来定义XML文档的元素，如使用和来表示元素和属性。因此使用DTD模式比使用Schema模式来判断一个XML文档是否有效，必然会增加解析的时间开销。并且DTD相对于Schema还有着其他的缺点：DTD只提供字符串类型的数据，而Schema中提供了丰富的数据类型并且可以自定义数据类型，具有很好的可扩展性； DTD提供的约束限制仅有？(零或一个)、*(零或多个)和+(一个或多个)三种，而Schema还可以提供范围限制等。因此本文采用Schema模式限制约束XML文档并对XML建立索引。

定义2Schema摘要树：对于一个Schema文档可以映射成一个文档摘要树(V,children)(本文不考虑Schema结构中存在环的情况)，其中V表示文档中标签生成的节点集合，children表示一个元素映射到子元素上的映射集合。

2基于Schema索引的关键技术

2.1文档编码和索引结构

目前对XML文档常用的编码方法有基于区间编码[12,13]和基于前缀编码[14]：区间编码是对XML文档中的每个节点赋予一对整数值，父节点的编码区间包含其子节点和后代的编码区间；前缀编码是保存了XML文档节点的路径信息，任何父节点的编码都是其子节点和后代节点编码的前缀。本文充分利用两种编码的特点，分别对XML文档和Schema文档分别进行编码。

Schema编码：把Schema映射成一个摘要树，节点n的编码用(Code(n),Level(n),E/A)标识，其中Code(n)表示节点n的前缀编码，Level(n)表示节点n在摘要树中的层数，E/A表示节点是元素节点还是属性节点。

定理1给定一个有效的XML文档树T采用区间编码，则对T中任意两个节点m和n，若m是n的祖先节点的充分必要条件为Precode(m)·Order(m)是Precode(n)·Order(n)的一个前缀，其中Precode(m)表示节点m的前缀编码，Oeder(m)表示节点m的顺序码。

通过对Schema编码采用倒排索引建立一个Schema索引结构，在倒排索引中把关键词存储在一个索引文件中，使用指针链表指向关键词相关的文档，从而有效的完成倒排索引列表。如图2所示，本文把具有相同元素/属性的节点归并到一个索引中，这样可以通过在Schema索引中快速的访问指定元素/属性节点。

图2　Schema编码索引示例

XML编码：XML文档采用混合编码，每个节点的编码都包含前缀编码和区间编码信息。节点n编码为(Start(n),End(n),S_Code(n))。其中Start(n)和End(n)分别表示节点n的前序遍历和后续遍历值，S_Code(n)是节点n所对应的元素或者属性在Schema文档树中具有相同路径相同位置的节点前缀编码Code(n)，Level(n)表示节点n在XML文档树中的层数。因此，XML文档将Schema的前缀编码信息存入节点，通过使用S_Code(n)使得每个节点都包含了相应的Schema中的结构信息，这使得在SBXHCI可以直接判断出无效的路径表达式中，并且在结构连接运算中提供精确的定位和减少结构连接的次数。

定理2给定一个有效的XML文档树T采用区间编码，则对T中任意两个节点m和n，若m是n的祖先节点的充分必要条件为Start(m)

根据Schema索引可以建立一个XML文档索引结构，如图3所示。首先根据Schema摘要树先序遍历的节点建立一个目录，然后把XML文档中具有相同前缀编码的元素归并到一起，这样可以快速地定位某个节点的祖先节点，最后根据B+树将XML文档中具有相同元素/属性的节点归并到一个索引中。从XML编码可以看出，任意一个节点的前缀编码都包含了从根节点到该节点的简单路径信息。

图3　XML文档索引示例

一般实际的应用中，Schema文档和XML文档之间是多对多的关系。本文为了方便测试SBXHCI方法的效率，提出的索引技术是基于一个Schema文档对应一个XML文档的，因此在实际开发中，我们只需要在schema文档和XML文档编码过程中分别加入Schema_ID(n)和XML_ID(n)即可。

2.2路径查询语言

XML查询语言共同的特点是使用路径表达式在XML文档中导航到待查询节点并返回指定路径的节点集合，目前最常用的XML查询语言是XPath。XPath使用路径表达式来查找XML文档中的节点、节点集合、原子值等，节点是沿着路径选取的，它的基本语法为Step1/Step2/…/StepN，其中Step=Axis::Node_test[Predicate*]。轴Axis实际上是指一个方向，即查询是沿着选着的轴的方向移动，节点测试Node_test是指选着的节点类型或者是节点名，谓词Predicate对定位步选择的节点作更进一步的筛选。

一般情况下路径表达式为复杂路径，即表达式会存在多个谓词使得查询过程中存在多个分支几点。本文处理复杂路径的基本思想是路径分解的方法，即将复杂路径查询分解成若干个简单路径表达式，对每个简单路径查询的结果集进行连接得到需要查询的结果集。

2.3算法分析

SBXHCI查询文档分为四个步骤：建立索引，路径分解，与Schema索引匹配，与XML文档匹配。SBXHCI查询算法流程图如图4所示，具体算下如下：

(1) 建立索引。分别对Schema和XML文档建立索引，具体步骤可参见2.1节中的说明。为了减小索引空间，本文改进了Schema摘要树中前缀编码的方法，根据摘要树层次中最大的兄弟节点个数(记作bNode)来决定编码的长度1=[log2max(bNode)]，既每层的编码长度，从而减小了Schema编码中前序编码的Code(n)的长度。如图1中第三层节点中最大的兄弟节点为5，则可以用3位来表示每个节点的编号。

图4　SBXHCI查询算法流程图

(2) 路径分解。在进行路径表达式查询过程中将复杂路径分解为若干个简单路径的子查询，对于分解后含有目标节点的简单路径称为目标匹配路径，只含有一个谓词约束的简单路径称为条件匹配路径。例如一个复杂路径表达式a/b[c>d]/e/f[g=h]/i，可以分解为条件匹配路径a/b[c>d],b/e/f[g=h]和目标匹配路径f/i。

(3) 与Schema索引匹配。对分解后的子查询在Schema索引中进行有效性的验证，可以通过定理1来判断一个简单路径是否合法。如果子查询中存在Schema索引文档中无相匹配结构的路径信息，则说明待查询的路径表达式不合法，返回无查询结果。因为Schema中定义了XML文档遵循的规则，即XML文档中可以使用的元素和元素的数据类型，而且还定义了文档中元素出现的顺序和次数及其嵌套关系等， 如果在Schema中查询不到相应的路径信息，则在相应的XML文档中也不会存在此路径表达式的查询结果集。因为Schema文档的大小比XML文档的小的多，所以加快了对无效路径的查询效率。如果在Schema索引中有相应匹配的路径信息，则说明待查询的路径是一个合法的表达式。

(4) 与XML文档匹配可以根据待查询的路径表达式的复杂度分为两种情况：

a) 如果查询路径为简单路径，即查询路径为目标路径，则可以直接根据路径的目标节点在Schema摘要树中找到对应的S_Code(n)值，从而在XML文档的索引中直接获取到待求的XML节点；

b) 如果查询路径为复杂路径，可以将查询路径分解为若干个分支路径集合{bPath}和一个包含目标节点的目标路径TPath。如果{bPath}包含两条及两条以上的路径集合，首先从{bPaht}依次取出两条路径找出叶子节点的前缀编码S_Code(i)，并找出对应的Schema摘要树中的相同的前缀编码Code(i)，使用“与”操作计算出相邻路径中节点的最长的前缀编码，循环操作{bPath}既可以得到分支路径结果集bResult；如果{bPath}只包含一条路径，则直接可以求出bResult。最后使用同样的方法对bResult和tPath进行连接，得到待求的XML节点。具体算法如下所示：

输入：分支路径集合{bPaht}，目标路径tPath

输出：待求的XML节点集Result

if({bPath},length>2){

for each bPathi→bPath{

//获取bPaht中叶节点对应的前缀编码Code(i)

Code(i)=GetPreCode(bPathi)

Code(i+1)=GetPreCode(bPathi+1)

//获取相邻路径的最长前缀编码，Align先根据编

//码层次获得其编码长度然后使用与操作连接

MaxCode(i)=Align(Cod(i)&Code(i+1));

}

//获取分支路径结果集bResult

}

else{

Code(1)=GetPreCode(bPath1);

bResult=Code(Code(1));

}

Result=Align(bResult&tPath);

3实验及其分析

为了测试和评估本文提出SBXHCI查询系统中的混合索引方法性能和查询效率，本文使用了Java语言实现SBXHCI查询系统。实验运行在一台CPU主频为2.3 GHz双核，内存大小为4 GB，操作系统为Windows 7电脑上。实验采用的数据有两种：第一种是广泛应用于XML测试的DBLP数据，它的特点是结构简单，树的深度不高；第二种是XML基准数据库XMark，它包含了复杂的树形记录结构。本文实验中忽略了XML数据中的空格，并且所有的实验都是经过多次实验所取得稳定的平均结果值。表1表示两种不同数据及的特征。

表1　表示两种不同数据及的特征

根据实验的可行性和可获得性，本文选取文献[6]中的XISS方法、文献[8]中DBXI方法、文献[11]中SBXI方法三种具有代表性的方法和本文提出的SBXHCI方法进行分析和比较测试。

3.1构建索引的时间和空间比较

衡量一种索引机制的性能可以从以下三个方面来考察：① 创建索引所花费的时间；② 存储索引所需的空间；③ 查询响应消耗的时间。创建索引所花费的时间越短，消耗的存储空间越少，查询响应的时间越短，则说明索引的性能越好。图5分别表示不同方构建索引的时间和空间比较。

从图5(a)中可以看出，不管是结构相对简单的DBLP文档，还是相对复杂的XMark文档，SBXHCI方法建立索引所需的时间都是最小的。原因是解析Schema与解析XML文档使用相同的解析器，相对于解析DTD时减小了消耗的时间，加快了索引的构建，因此使用Schema构建索引的方法SBXHCI和SBXI所消耗的时间小于使用DTD构建索引的方法DBXI。

从图5(b)中可以看出，XISS构建索引消耗的空间最小，原因是XISS在构建索引的过程中只对XML文档中每个节点赋予一个二元组(pre，post)编码，并没有包含模式信息，因此构建索引使用的空间最小；对于结构相对简单的DBLP文档，SBXHCI方法建立索引所需空间则比DBXI和SBXI要小，而对于结构相对复杂的XMark文档，SBXHCI方法建立索引所需空间则比DBXI和SBXI要大，虽然本文优化了前缀编码标识节点的位数，但在构建索引的过程中比区间编码使用了更多的存储空间，因此SBXHCI方法在构建XMark索引过程中比DBXI方法使用了更多的存储空间。

图5　不同方法建立索引所需时间和空间消耗对比

3.2查询响应时间的比较

为了测试文档索引的查询响应时间，本文针对表1中数据2-DBLP和数据4-XMark两种数据集，分别给出了4种具有代表性的路径表达式查询语句，如表2所示。其中D1-D5是关于DBLP的查询表达式，X1-X4是关于XMark的查询表达式，D1和X1是不包含谓词的简单路径查询，D2和X2是含有谓词的简单路径查询，D3和X3是含有谓词的复杂路径查询，D4、D5和X4是错误路径查询。查询响应时间实验结果如图6所示。

表2　实验中的查询路径表达式

图6　查询响应时间

从图6中可以看出，对于无效路径的查询，DBXI、SBXI和SBXHCI三种方法都可以快速的判断出无查询结果。在XML文档建立索引中有效的利用了模式信息，都是先从相应的模式信息中进行匹配，无需查询XML文档，可以直接判断出无效查询，因此大大降低无效路径的查询响应时间。

对于有效路径的查询，SBXHCI方法相对于其他三种方法明显的降低了查询响应时间。对于XISS查询具有N个元素组成的路径查询时，需要N-1次的结果结构连接，因此查询响应消耗的时间最大；DBXI和SBXI方法都是采用区间编码建立索引，在结构连接算法的性能低于采用前缀编码的索引；而SBXHCI采用混合编码索引的机制，在结构连接中去除了不相关节点的连接操作，减少了结构连接次数，加快了结构的连接运算，这使得查询效率得到更进一步的提高，优于其他三种方法。

4结语

本文提出了一种基于Schema混合编码的索引查询技术SBXHCI，充分利用Schema信息并将Schema编码信息引入到XML文档节点编码中，对XML文档综合利用混合编码建立索引。这种编码方法充分利用了区间编码的可以快速访问节点的优点和前缀编码的可以加快结构连接运算的优点，并且在结构连接中去除了不相关节点的连接操作，可以快速地访问到查询结果。通过实验结果表明SBXHCI方法的索引结构在时间和空间方面都有较大的提高，并且可以有效地提高文档的查询速度。但目前对XML文档查询研究工作还存在众多的问题，如没有考虑XML的存在的“参考”属性，这使得XML文档对应一个图形结构而不是一个简单的树形结构，从而处理起来更加复杂，这需要在将来的工作中进一步的提高。

参考文献

[1] 孟小峰,王宁,王小峰.XML查询优化研究[J].软件学报,2006,17(10):2069-2086.

[2] 季玉梅.一种基于XML模式的XML索引技术[D].北京:北京工业大学,2013.

[3] Goldman R,Widom J.DataGuides:Enabling Query Formulation and Optimization in Semistructured Databases[C]//Proceedings of the 23rd International Conference on Very Large Data Bases,1997:436-445.

[4] Wang W,Jiang H,Wang H,et al.Efficient processing of XML Paht queries using the disk-based F&B Index[C]//Proceeding of the 31st Interational Conference on Very Large Data Bases,Trondheim,Norwey,2005:145-156.

[5] Li Q,Moon B.Indexing and querying XML data for regular path expressions[C]//Proceeding of the 27th International Conference on Very Large Data Bases,Roma,Italy,2001:361-370.

[6] 王锦,何先波,贺春林.改进的XISS索引技术的仿真研究[J].计算机科学,2012,39(1):148-151.

[7] 路燕,张亮,段起阳,等.一种基于DTD的XML索引方法[J].计算机研究与发展,2005,42(1):30-37.

[8] 满慎江,陈近森,郭希娟,等.面向XML文档检索的索引技术[J].小型微型计算机系统,2008,29(1):89-92.

[9] Che D,Ling T,Hou W.Holistic boolean-twig pattern matching for efficient XML query processin[J].IEEE Trans on Knowledge and Data Engineering,2012,24(11):2008-2024.

[10] 肖芳桥.基于模式的XML索引技术研究[D].济南:山东大学,2010.

[11] 邹为伟,宋余庆,耿飙,等.基于Schema的XML索引方法研究[J].计算工程,2011,37(6):74-76.

[12] 万常选,刘云生,许升华,等.基于区间编码的XML索引结构的有效结构连接[J].计算机学报,2005,28(1):113-127.

[13] 庄灿伟,冯少荣,林子雨,等.XML动态区间编码方法[J].软件学报,2012,23(3):582-593.

[14] 万里勇.基于索引技术的XML查询优化研究[D].长沙:中南大学,2012.

中图分类号TP311

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.02.008

收稿日期：2014-06-04。上海高校知识平台“上海商贸服务知识服务中心”建设项目(ZF1226)。夏刚，硕士生，主研领域：软件工程，数据挖掘，人工智能。刘林静，硕士生。楼文高，教授。