XML索引

2024-10-23

XML索引（共4篇）

XML索引篇1

0 引言

由于XML数据的灵活性,自描述性好及可扩展性高,成为当前主流的数据形式,并成为Internet中进行数据交换和表示的标准。由于客观世界的复杂性,不确定性是数据常见的内在属性,因此不确定的信息是普遍存在的。通常不确定信息以概率值的形式在XML文件中表示。如何在连续不确定XML中建立索引实现快速高效的查询成为了当务之急。

索引是提高查询效率的有效途径,DataGuides[1]、1-index[2]、A(k)-index[3]、D(k)-index[4],都是其中典型的代表。但是这些索引结构有个共同的特点就是仅支持简单路径查询,不支持分支路径查询。文献[5]提出一种扁平结构索引F-index,能够快速过滤所有与查询无关的索引结点,进而过滤掉与查询无关的元素序列。在处理深度嵌套的复杂结构XML文档时具有很大的优势,但是这种索引结构仅适用于普通XML文档中的查询。文献[6]提到一种处理连续不确定数据的索引方法,这种方法通过对节点提前计算一些附加信息,在查询时通过这些信息过滤与查询无关的节点,最小化概率阈值查询中概率计算的次数。但是这种索引只适用连续不确定数据的查询处理,对于连续不确定XML文档没有实际应用。

在连续不确定XML中进行的查询,多数只需要知道取得某个值的概率是否超过了一个给定的阈值,即概率阈值查询。提出CPTI索引技术。首先扩展了结构索引F-index,建立了概率XML数据的扁平结构链表,此链表在原有的普通XML数据扁平结构链表的基础上又添加了结点状态(普通结点和分布式结点)和相应的概率信息,查询可直接在链表里进行,这种结构可快速的返回twig小枝的查询结果,并且可以确定节点的路径概率值(即从根节点到本节点的路径概率);其次建立了值索引,此索引在服从连续分布的叶子结点,记录了结点概率信息,查询时先根据此概率信息过滤掉一些与查询无关的叶子节点,减少叶子节点概率的计算。

1 CPTI索引

1.1 建立模型

一个PXML文档可表示成一棵树,记作T=(Vp,rp,Ep,tag)。其中:(1) Vp是结点的集合。(2) rp⊆Vp是树的根结点。(3) Ep是边的集合。(4) tag:VA→<name,value,valuetype>,给每个结点赋予一个三元字符串组,分别表示该结点的节点名、值和值的类型,如图1所示是包含mux和cont类节点的P-文档[7]。

1.2 CPTI结构索引

CPTI结构索引是一个链表,记录一个节点A和它的所有tag为B的后代节点的情况,链表结构如图2所示。图2(a)是链表表头,其中PC表示父子关系,AD表示祖先子孙关系,图2(b)为链表元素,此链表是在结构索引F-index链表元素的基础上增加了三个元素,Flag表示后代结点的类型,包含F、Fi、和Fm,F表示普通节点,Fi表示独立节点,Fm表示互斥节点;P表示后代节点的路径概率值,即从根节点到该节点的路径概率;CurrentNode表示对应的后代结点。

记录图1中所有非叶节点和它后代的可达性信息,建立了如图3所示的CPTI结构索引。其中Mo表示monitoring、Si表示sensori、Ms表示measures、Ti表示tempi。

1.3 CPTI值索引

1.3.1 正态分布的概念及特征

若连续型随机变量X的概率密度为 $f (x) = \frac{1}{\sqrt{2 π} σ} e^{- \frac{(x - μ)^{2}}{2 σ^{2}}}$ ,-∞<x<∞其中μ,σ(σ>0)为常数,则X服从参数为μ,σ2的正态分布或高斯分布,记为X～N(μ,σ2)。正态分布的概率密度曲线如图4所示,曲线关于X=μ对称。要使得落在区间(x1,x2)上的概率为p,则区间(x1,x2)存在三种可能情况:

${\begin{cases} x_{1} < X < x_{2} \\ - \infty < X < x_{R} \\ x_{L} < X < + \infty \end{cases}$

1.3.2 值索引

值索引是一个二维表结构,记录cont类节点概率值和对应区间关系的信息表,值索引结构如图5所示,P表示用户给定的概率值,0<P<1;|x2-x1|表示图4中关于X=μ对称的、概率为P的最短区间长度;xL、xR含义与图4中xL和xR含义相同。查询时,可根据此表信息过滤与查询无关的元素以减少处理元素的数目。

图1中叶子结点T服从正态分布N(μ,δ2),根据T的实际分布情况,计算得到一些信息,构成一个信息表,例如T2结点,设初值0.1,步长0.1,确定P值,并计算得到图6所示值索引。

图6 CPTI值索引实例

2 基于CPTI索引的查询处理过程

例如查询图1中温度在(28,31)范围内的概率P大于0.6的传感器s,如图7所示。使用CPTI结构索引查询图7中的Twig,利用CPTI值索引过滤不满足Temp在(28,31)的概率大于0.6这一条件的Twig。

2.1 CPTI结构索引查询Twig

CPTI结构索引查询步骤:

(1) 通过CPTI结构索引找到S-id的PC指针和S-T的AD指针,两指针同时推进,比较两个指针所指链表中AncestorNode是否相同,如果相同,则找到符合条件的小枝。如果不同,则继续推进,直到PC或AD为空。

(2) 根据链表元素P确定T的节点类型和路径概率。如果T的路径概率低于查询概率阈值将被过滤掉,否则保留。

根据以上策略,最终找到如图8所示三个小枝。

2.2 CPTI值索引过滤Twig

CPTI值索引过滤步骤:

(1) (a,b)是概率阈值查询的查询区间,P,x1,x2,xL,xR含义和图4中表示的含义相同,查询的概率为Pi=阈值概率/路径概率。本例中a=28,b=31,Pt=0.6/(T的路径概率)。

(2) 当 $| b - a | \leq | x_{2} - x_{1} |$ 时,T被过滤掉。

(3) 当 $| b - a | > | x_{2} - x_{1} |$ 时,如果a<x1<x2<b,则T满足条件;如果b≤xR,则T被过滤掉;如果a≥xL,T也被过滤掉。

(4) 其余情况均利用pdf进行计算。

根据以上过滤策略,只有T4符合条件。所以符合图7查询的只有S3[/id3]//T4。

3 实验分析

3.1 实验环境和数据集

本实验是在Dell Optiplex 380(2.93GHz),RAM 2GB,300G硬盘上运行,OS是Windows XP Professional SP-3。实验测试采用人工合成数据集。

3.2 测试及结果分析

本实验进行了两组测试。第一组测试中,数据集如表1所示,P文档逐渐增大,分别测试了没有索引存在、只有结构索引存在、结构索引和值索引都存在时的运行时间。结果如图9所示,从图中可以看出通过索引进行查询,查询时间大幅度地减少,并且发现,通过CPTI结构索引处理查询时,P文档越大,时间变化幅度越小,效率越高。

第二组测试中,P文档不变,44MB,只改变查询的概率值(P1～P9分别是0.1～0.9,步长0.1),测试了运行时间,如图10所示,从图中可以看出,概率值越大,运行时间越短,即概率值越大,通过CPTI索引查询的效率越高。

4 结语

本文在已有XML索引方法的基础上提出了CPTI索引结构,可以实现连续不确定XML的概率阈值查询,使用CPTI结构索引加速了Twig查询,通过CPTI值索引过滤Twig,进一步减少了查询时间。实验表明,效率较高。进一步的工作是对叶子节点服从任意分布的情况进行研究。

参考文献

[1]Goldman R,Widom J.DataGuides:Enabling query formulation andop-timization in semistructured databases[C]//Proc.of the 23rdInt'1Conf.on Very Large Data Bases(VLDB),Athens:Morgan Kaufman-nPublishers,1997:436-445.

[2]Milo T,Suciu D.Index structures for path expressions[C]//Proc.ofthe 7th Int'1 Conf.on Database Theory(ICDT),LNCS 1540,Jerusa-lem:Springer-Verlag,1999:277-295.

[3]Kaushik R,Sheony P,Bohannon P,et al.Exploiting localsimilarity forefficient indexing of paths in graph structured data[C]//Proc.of the18th Int'1Conf.on Data Engineering(ICDE),San Jose:IEEE Comput-er Society,2002:129-140.

[4]Chen Q,Lim A,Ong K W.D(k)-index:An adaptive structuralsummaryfor graph-structured data[C]//Proc.of the 2003 ACMSIGMOD Int'1Confon Management of Data(SIGMOD),San Diego:ACM Press,2003:134-144.

[5]He H,Yang J.Multiresolution indexing of XML for frequentqueries[C]//Proc.of the 20th Int'1 Conf.on Data engineering(ICDE),Bos-ton,IEEE Computer Society,2004:683-694.

[6]周军锋,孟小峰,蒋瑜,等.F-index:一种加速Twig查询处理的扁平结构索引[J].软件学报,2007,18(6):1429-1442.

[7]Kimelfeld B,Sagiv Y.Matching twigs in probabilistic XML[C]//VLDB'07,Vienna,Austria,2007.

XML索引篇2

XML是一种半结构化的数据, 能够良好地实现数据交换。而DTD (Document Type Definition) 采用了一系列正则表达式的形式, 它的语法分析器将这些正则表达式与XML文档内部的数据模式相匹配, 从而判别一个文档是否有效。因此如果XML文档中有任何信息不符合DTD的规定, 都不会通过。由于以数据为中心的XML文档结构具有极大的重复性, 考虑DTD在索引中的作用是提高索引效率的重要手段。为了避免在查询中多次且频繁的比较, 利用DTD可以有效地减少这种重复。在针对XML索引的研究工作中[1,2], 可以发现提高XML索引的效率需要考虑到索引方法的实际结构。

1问题定义及相关工作

1.1相关工作

XML文档中的元素之间是嵌套结构, 因此文档可以被描绘成一种树形结构且树中的结点被标记。XML文档索引的作用就是要将文档中的标记甚至内容映射成易于处理的表达方式。XML索引方案大致可以分为基于数字的编码索引和基于结构的编码索引。基于数字的编码方式可以通过比较直接确定出一棵树中祖先/后裔关系。

数字编码中应用最为广泛的为区域编码, 这包括Dietz编码[4], 该方法依靠前序遍历和后序遍历来确定结点之间的联系, 在查询中就可以利用确定的范围来进行结点的搜索, 本文的基础编码方案基于Dietz编码;Li-Moon方法[5], 利用数值对<order, size>来分别表示扩展的XML文档的前序遍历序号和后裔结点的数目范围;Zhang等人提出的Zhang编码, 利用先序遍历XML文档, 每一个结点在遍历时分别被访问两次并产生两个序号。这些方法利用区域编码有序的特点, 利用一个至少二元的数值对来表示每个结点, 需要大量额外的存储空间对索引进行存储。在区域编码对应的算法中, 都需要经历多次且频繁的比较, 显然将会降低查询效率。

其他的索引方法还包括Wang等人提出的PbiTree编码[7], 将XML树的中序遍历编码二进制化, 通过二进制串得到相应的树高、祖先结点的数字关系等。显然, 利用这种方法构建的PBi树可以仅仅根据编码就快速定位祖先/后裔关系。PbiTree使得在构建之初, 就必须建立一棵完全的二叉树与实际的XML文档进行对应, 但完全二叉树对应方法是一种静态的对应方法, 对于拥有众多子结点的某个结点来说, 二叉树的树高扩展将是无法估量的, 而这种编码的代价是巨大的。

1.2问题提出

基于结构的编码方案及其算法以XML文档的结构为中心, 将XML标签通过名称进行分组, 对查询根据标签字段进行拆分, 各自在XML文档中对应一系列的结果集, 再根据查询需要将各个结果集进行合并。本文所提出的方法中, 基于DTD的标记编码实际上就是标签对应, 它是根据DTD进行的动态标记法, 编码将根据DTD进行缩减。因此通过这种方法能同时满足以结构为中心和以数据为中心的XML文件的索引要求。

为了实现XML文档与DTD的标签相对应, 就需要考虑在DTD和XML中如何分别进行标签的索引建立。为了表现出DTD对XML文档的有效描述, 就必须找到一种适合结构标记索引的索引方法。因此在DTD的索引上, 考虑使用现有索引方法, 即Dietz编码。而在针对XML索引上, 则采用了一种全新的对照方法。

2对照标记索引方法

DTD的引入对XML文档结构的规范性提供了保证, 同时还可以提供对于XML文档大小、范围的限制。单一的XML文档难免出现诸如拼写偏差等妨碍正确信息显示的错误。因此, 将XML文档与其DTD文件进行对照标记, 可以在标记的同时有效地保证XML文档格式的规范性。当然, 对标记的纠正会涵盖予以错误与单纯拼写错误的区分问题, 本文假设XML文档中所有标记均可以按照DTD标记作出正确的对应。

定义1 (对照标记) XML文档树T的对照标记, 简称为CT (Contrast Tag) , 是一个二元组T={D, X}, 其中D表示DTD结点标记的集合, X表示T的结点标记的集合。其中:

1) X⊂D;

2) ∀n∈V

$\exists C Τ = {< D i d, X i d > | D i d \in D, X i d \in X}$

实际上, 上述对照标记就是对T中的每个结点根据其对应的DTD赋予了一个数值对<Did, Xid>, 分别涵盖了DTD和XML文档中的结构标记。在实际索引的建立过程中, 则采用对结构标记建立数字编码的方式。针对标记的编码方式, 对于XML文档中的结点n产生数值对<Did, Xid>, Did代表DTD的前序遍历序号, Xid代表XML文档与DTD相对应标记的前序遍历序号。

图1和图2分别表示针对一个关于商品清单的DTD和XML。其中图1采取的是Dietz编码, 图2采取的是对照标记编码。

通过对照标记记录的XML文档树的结点具有相对统一的结构, 可以通过Did迅速找到具有相同标记的内容。这种对照标记的XML文档树, 节省了对结点标记的查询, 统一转换到对DTD的查询。

3实验

通过与XML的对照标记, 可以有效地通过DTD将XML文档进行合理的整合。根据DTD对XML文档进行结构上的标注和纠错。本文采取NetBeans IDE 6.0和JDOM 1.1作为开发平台, 对XML和DTD进行处理。不考虑对XML文档中的错误标记进行语法纠正, 并确保XML文档严格遵照DTD的文档格式要求。

从编码长度上考虑, 对照标记法具有简短的标记长度。通过利用不同索引方法与对照法比较的编码长度和结构关系检测如表1所示。

根据以上六种编码方式建立索引和使用对照标记方法建立索引, 对XML文档进行查询操作, 文档属性和查绚语句如表2、表3所示。

采用前六种编码方式对XML文档XMLDoc1.XML建立索引后, XPath表达式Q1和Q2对XMLDoc1.XML进行查询操作, 查询效率时间比对图如图3所示。

采用前6种编码方式对XML文档XMLDoc2.XML建立索引后, XPath表达式Q3和Q4对XMLDoc2.XML进行查询操作, 查询效率时间比对图如图4所示。

如图4所示, 由于通过对照标记记录的XML文档树的结点具有相对统一的结构, 可以通过Did迅速找到具有相同标记的内容。这种对照标记的XML文档树, 节省了对结点标记的查询, 统一转换到对DTD的查询。查询效率高于采用其他编码方式建立的索引。

4未来工作

由于XML索引的实现需要查询方法的有力支持, 因此针对该方法的查询工作是未来着手的工作之一。其次, 由于利用了DTD对于XML文档进行整理, 在XML文档中出现标记错误时, 可以根据DTD进行标记的修改。但在这个过程中需要考虑到语义的模糊匹配。

参考文献

[1] Chien SY, Vagena, Zhang D, et al.Efficient Structural Joins on Indexed XML Documents[C]// Proc.of the 28th VLDB, HongKong, China, 2002:263-274.

[2]Jiang Haifeng, Wang Wei, Lu Hongjun, et al.Holistic Twig Joins on In-dexed XML Documents[C]//Proc.the 29thVLDB, Berlin, Germany, 2003:273-284.

[3]Al-Khalifa S, Jagadish HV, Koudas N, et al.Structural joins:A primi-tive for efficient XML query pattern matching[C]//Proc.of the IEEEICDE, 2002.

[4] Bruno N, Koudas N, Srivastava D.Holistic Twig Join:Optimal XML Pattern Matching[C]//Proc.of 21st ACM SIGMOD, Madison, USA, 2002 , 6:310-321.

[5]Paul F.Dietz.Maintaining order in a linked list[C]//Proc.14thAnnu-al ACMSymposiumon Theory of Computing, San Francisco, USA, 1982 (5) :122-127.

[6]Li Q, Moon B.Indexing and querying XMLdata for regular path expres-sions[C]//Proc.of 27thVLDB, Rome, Italy, 2001:361-370.

XML索引篇3

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

对XML文档建立索引,就是将具有相同标签的XML节点划分在同属一个索引节点类中[2]。目前,国内外对XML建立索引技术的研究取得了丰富的研究成果。例如,最早提出对XML文档建立索引的思想来源于文献[3]提出的基于结构概要的Data Guide索引方法,它的本质是一个确定自动机,能够根据绝对路径很好地给出响应查询,但却不能提供相对路径的查询。文献[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文档采用混合编码建立索引结构,这种编码方法可以快速地查询出待查询的节点和加快了结构连接的速度,从而提高查询效率和准确率。

1 XML文档和模式

1. 1 XML文档模型

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

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

1. 2 XML模式

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

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

定义2 Schema摘要树: 对于一个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索引中快速的访问指定元素/属性节点。

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 ) < Start( n ) 且End( n ) < End( m ) 。若m是n的父节点充分必要条件是m是n的祖先节点且Level( m ) + 1 =Level( n ) 。

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

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

2. 2 路径查询语言

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

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

2. 3 算法分析

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

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

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

输入:分支路径集合{b Paht},目标路径t Path

输出:待求的XML节点集Result

3 实验及其分析

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

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 所示。

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

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

4 结语

XML索引篇4

XML文档版本管理的目的是不仅可以让使用者操作最新版本的XML文档,还可以快速获取旧版本的XML文档,对XML文档版本发展过程进行追踪。目前已提出的XML文档版本管理技术有Diff-based[1]、Timestamps-based[2]等方法。

Diff-based方法的主要概念都是利用edit-script语法(insert, delete, update,move)来记录同一份XML文档不同版本之间的变化。不管Diff-based方法经过怎样的发展,仍然无法突破直接任意地获取XML文档版本的限制。

文献[2]以Timestamps-based方法为基础,提出了以时间戳与数值范围为XML文档版本中每个结点进行编码。但没有讨论如何明确定义结点数值范围中的间距值range,也没有说明当新的XML文档版本加入时,例如新增、删除和修改XML文档,原来XML文档结点的数值范围应该如何调整。

1多版本XML文档及编码方法

文献[3]提出了多版本XML文档的概念。多版本XML文档是将原始版本及其后续版本的差异整合成一个XML 文档,并且设计出新的numbering schema,给予XML树状结构的每个结点两种范围的编码:空间上的数值范围(startpos :endpos)和时间上的生存周期(vstart :vend)。图1是一个多版本XML文档的例子(版本1-3),图中标出了每个结点的编码。

版本1只有books结点和左分支的book结点,这些结点一直到版本3依然保留,因此每个节点的(vstart :vend)都是(1 :3),版本2增加了右边的book结点及4个子结点,因此这些结点的vstart是2,这些结点在第三个版本中继续保留,唯独删除了book结点的第三个子结点author,因此该author结点的vend是2,其他结点的vend均为3 。

新的numbering schema实际上是区间编码的一种扩展,存在如下关系:

(1) 可利用时间范围(vstart :vend)来撷取满足特定版本的结点。如要撷取版本v的结点a,只需满足a.vstart<v<a.vend条件即可。

(2) 可利用数值范围判断两个结点之间的结构关系。如给定的两结点u,v,如果u是v的祖先,当且仅当u.startpos<v.startpos<u.endpos。

2编码的维护

首先给出插入子树的四种情形,如图3所示。三角形代表要插入的子树。根据插入子树在原文档中有无左右子树,可以划分为四种情形。我们注意到,当在文挡中插入内容,原文挡的所有结点的数值范围需重置,进而会导致索引文件内容以及结构的调整,这样的效能无疑是低下的,下面讨论插入一个子树时结点编码更改最小化的方法。

举例说明:如图4(a)所示,在结点<2,4>和<5,7>之间插入一子树(结构如图4 (b) 所示),这属于情形一:插入的子树有左右兄弟子树。此时插入子树的根结点的startpos值应该满足在区间[Left.endPos,right.startPos]内,即[[4],5]内,才能保证结点之间的结构关系,而此区间的间距仅为1,因此有些文献提出在编码时给所有结点的区间编码都乘以一个系数,从而预留出一定的空间,但问题是,对插入子树的规模我们无法预测,如果插入子树过大,即使预留空间也没有用,我们采用浮点数给子树编码,具体方法是:先给子树相对编码,相对编码结果如图4 (b)所示,然后再将子树中所有结点的编码都乘以一个系数,我们称之为相对因子,相对因子取0.1,0.01,0.001等这样的小数。取值时必须满足其与插入子树的根结点的endpos值的乘积小于1,此例中,子树的根结点的endpos值为4,因此相对因子的值为0.1,最后再将子树中所有结点的编码加上左区间的值,此例中左区间的值为4,从而完成对子树的编码,如图4(c)。这样可以保证原来的文档中所有结点编码的数值部分不需要重置。情形二:插入子树的根结点的startpos值应该满足在区间[Left.endPos,P.endPos]内。情形三:插入子数的根结点的startpos值应该满足在区间[P.startPos,right.startPos]内。情形四:插入子树的根结点的startpos值应该满足在区间[P.startPos,P.endPos]内。情形二、三、四给子树编码的方法与情形一相同,只是其中的一个参数(左区间的取值)不同。

3新的索引机制

我们将从索引文件内容和索引文件结构两方面来讨论新的索引机制。

文献[3]用关系数据库来存储多版本文件至少有两个缺点:(1)无法利用XML数据自身的特点,如结构化、自描述性等,在处理XML数据时需经过多级复杂的转换;(2)对结构查询不具有优势,对如图5这样存在祖先、子孙复杂嵌套的多版本文件,无法避免冗余连接。(篇幅所限,图5中我们只标记出结点的(vstart :vend),而数值范围由线段的长短标记,如果有结点没有标出时间生存周期,表示该结点继承其祖先的生存周期)。

本文提出的新的索引机制能较好地解决上述两个问题。新的索引机制可以用在纯XML数据库中,同时能支持多版本XML文档的结构查询。索引文件的内容是将文档中具有相同名称的结点存储在一起形成一个列表,列表保存每个结点的四元组编码。以图5为例,该文档索引文件内容如下:

A:<1,21,1,10>,<2,4,2,8>,<5,9,1,7>,<6,8,1,7>,<7,7,1,7>,<10,15,1,8>,<11,13,1,8>,<12,12,1,8>,<14,14,1,8>,<16,20,1,9>,<17,19,1,9>,<18,18,1,9>,<35,37,1,9>

D:<3,3,2,7>,<22,24,1,10>,<23,25,1,10>,<24,24, 1,10>,<26,30, 1,10>,<27,29,1,10><28,28,1,10>, <31,33,1,10>,<32,32,1,10>,<36,36,1,9>

通过b+树来组织每个名称列表。根据b+树的插入算法,将每个list中的结点按照startpos值由小到大插入一棵b+树,这种索引结构将加速查询。

本文提出的索引机制和XISS有些相似,但也有本质的不同。XISS用<order,size>来标记每一个结点,仅仅能够判断结点之间的结构关系,但是不支持多版本文档,我们沿用XISS最根本的思想,但用新的numbering schema来代替<order,size>的结点编码机制,就可以在不恢复版本的前提下,利用索引直接快速地撷取特定版本的结点,为多版本XML文档的结构连接奠定了基础。

4查询

结构连接是XML查询的核心操作,受到了专家和学者的关注。目前提出的许多结构连接算法都不支持多版本的XML文档。文献[4]叙述的anc_desc_b+算法效率比较高,该算法对alist和dlist列表分别顺序扫描一次就可以完成连接。下面我们来扩展该算法,使其支持多版本XML文档的查询,通过算法分析看出,该算法在处理祖先—后代复杂嵌套的情况时能利用索引的B+树结构跳过并不参与连接的结点,避免了许多冗余的连接步骤。

4.1算法

自定义的两个过程version_of_demand(a)和nextnode(a)是算法扩展的基础。version_of_demand(a)能返回a结点是否是符合版本的结点;而nextnode(a)过程返回a列表中下一个符合版本条件的a结点。扩展后的Anc_Desc_B+_MV算法如下:

Anc_Desc_B+_MV(alist,dlist,v)

输入:两个参与连接的列表Alist和Dlist,要获取的XML文档的版本整数V

输出:按后代有序的连接结果output

1. Let a,d be the first elements of alist and dlist;

2. While (not at the end of alist or dlist) do

3. If (a is an ancestor of d) then

4. Locate all elements in alist that are ancestors of d and version_of_demand(a) and push them into stack;

5. Let a be the last element pushed;

6. output d as a descendant of all elements in stack;

7. D=nextnode(d)

8. Else if (a.end<d.begin) then

9. If (ancestor stack is not empty) then

10. Pop all stack elements which are before d;

11. Let 1 be the last element popped;

12. Else 1=a;

13. Let a be the element in alist having the smallest begin that is larger than 1.end and version_of_demand(a); /*利用B+树定位/

14. Else

15. Output d as a descendant of all elements in stack;

16. If (ancestor stack is empty ) then

17. Let d be the element in dlist having the smallest begin that is larger than a.begin and version_of_demand(d)

18. Else

19. D=nextnode(d)

20. Endif

21. Endif

22. endwhile

4.2查询

简要说明算法的执行过程,以图5为例,如果查询版本2的a//d,则执行过程如图7所示。可以看出,参加连接的祖先结点仅为<a1,a2,a13>,后代结点仅为<d1,d10>,利用新的索引机制,避免了连接中的冗余操作。上述查询还隐藏着另一层意义,一般的XML文档版本管理问题中,若要查询某个版本的内容,需先恢复版本。而本文所述方法不需要恢复版本就能直接进行查询,原因是(startpos :endpos)和(Vstart:Vend)具有时间和空间的概念。

Step1:压a1进栈 Step2:压a2进栈Step3:输出(a1,d1)(a2,d1) Step4:弹a1出栈,弹a2出栈Step5:a13进栈 Step6:输出(a13,d10)Step7:弹a13出栈

5总结

多版本XML文档的研究是XML研究领域相对独立的一个研究方向,目前主要由加州大学洛杉矶分校和台湾嘉义大学从事这方面的研究,国内此项研究尚处于起步阶段。不同于以往研究,在改进编码方式的基础上,本文针对多版本XML文档提出了一种新的索引机制,在文档频繁更改的时候,多版本文档结点的数值编码不需要重置,索引文件内容和索引文件结构的更新也是局部而有限的。更为重要的是,该索引机制的提出对多版本XML文档的存储和查询提供了新的思路:文档的存储不再需要依托关系型数据库;在不需要恢复版本的情况下,扩展后的结构连接算法也能够对任意版本的文档作高效的结构查询。

摘要：首先对XML文档的编码方式作了改进,提出了用浮点数对插入子树进行编码的方法,新的编码方法能较好地支持XML文档的插入更新,在此基础上提出了支持多版本XML文档的新的索引机制,最后扩展了一个经典的结构化连接算法使之不仅能支持多版本XML文档的查询,而且还能较好地避免连接过程中的冗余操作。对XML的版本管理,尤其是在索引和查询优化方面提供了一些新的思路。

关键词：XML,索引,多版本XML,结构化连接

参考文献

[1]Marian Abiteboul S,Cobena G,Mignet L.Change-centric management of versions in an XMLwarehouse.Proc.of the27th VLDB,Rome,Ita-ly,2001,9.

[2]Chien S Y,Tsotras VJ,Zaniolo C,Zhang D.Storing and Querying Mul-tiversion XML Documents using Durable Node Numbers.Proc.of WISE,2001.

[3]蔡政霖.XML文档版本管理.http://datf.iis.sinica.edu.tw/Pa-pers/2003datfpapers.

【XML索引】推荐阅读：

XML索引编码09-26

XML数据索引技术论文05-31

索引结构06-22

电子索引07-06

资源索引09-21

空间数据索引06-18