XML索引编码（共4篇）
XML索引编码 篇1
0引言
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
实际上, 上述对照标记就是对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.
[7] Zhang C, Naughton J, Dewitt D, et al.On Support containment queries and keyword search in RDBS[C]//Proc.of 20th ACM SIGMOD, New York, USA, 2003, 3:391-402.
XML索引编码 篇2
随着互联网的迅速发展,可扩展标记语言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索引编码 篇3
现在传统的方式是使用DOM或SAX协议对XML文档进行操作, DOM是建立文档树来访问XML数据, 建立树的过程会花费很大的系统开销, 对于较大的XML文档, 这种方式会很大程度上降低系统的性能, 即使使用SAX协议访问, 也是顺序方式查找XML文档, 还是很难满足日益发展的Web服务的要求。当数据量很大时必须找到一种新的方式来提高查询的效率, 人们已经开始着手研究Native XML数据库 (NXD) 并取得了一定的成就, Native XML数据库是一种新的数据库技术, 是一个完整的数据库系统, 有着传统数据库的各种功能和组件, 如今NXD的技术还在研究中, 一些机制还不是很完善。该文利用NXD的思想, 保持XML文档的原格式, 并建立索引来提高查询效率, 针对一种特定情形下的数据查询基于XML文档的存储结构建立索引机制, 这里要处理的是图书查询系统的图书信息, 针对常见的查询建立索引, 使用关系数据库来保存索引, 加快查询效率的提高。
1 图书查询系统应用分析
首先, 分析一下图书查询系统常用的查询有哪些种类, 针对这些应用来建立索引。
1) 用户要求返回具有某种属性的书目列表。这是最常用的查询方式, 几乎绝大部分查询都是这种类型的查询, 如题名检索、作者检索、主题词检索、出版社检索等, 我们为题名检索和出版社检索为例。
问题一:查询书名为“我的童年”的书目列表。
问题二:查询“清华大学出版社”出版的书目列表。
2) 返回一类书目的列表。这里可能是某一类书中的一个子类, 如一个网页设计的入门者, 他只是想浏览网页设计方面的书籍, 并不是确定要找哪一本书。
问题三:查询类别名为“网页制作”的书目列表。
3) 返回具有某一属性的书本的其他属性列表。这种应用很少, 但也存在, 如想要查找在清华大学出版社出书的作者列表。
问题四:查询出版社为“清华大学出版社”的书目作者列表。
2 建立索引
根据实际的应用给要查询的文档建立索引, 一个书店或者图书馆里的书目是众多的, 所以我们的XML文档也是非常庞大的, 因此已经不可能用DOM或SAX来访问了, 我们也不使用XED (XML-Enabled DBMS) 的方式, 把数据都存储在关系数据库中, 然后转换成XML格式。我们采用了一种折中的方法, 依然使用原始的XML文档方式来存储数据, 但把检索中会用到的数据另外存储到关系数据库中, 这样在查询的过程中使用的是关系数据库系统, 效率比较好, 而最终读取的结果又会依赖XML文档。将XML文档中的一部分内容读取出来, 这样我们查询得到的结果依然是XML格式, XML的优势同样能够得到发挥。其具体结构如图1:
从关系数据库到XML文档, 其实是一个定位过程, 如果不通过关系数据库建立索引, 我们可能是顺序方式查找需要的信息, 现在把查询过程中用到的信息存储在关系数据库中的表中了, 我们需要将这些表 (可能不止一个表) 关联到XML文档中的某个特定的位置, 这样才能减轻查询的负担, 常用的做法是利用XML文档的行号来实现。我们通过例子来看, 附表是一个图书信息文档, 其书目分为两大类, 文学类和计算机类, 在计算机类中又有子类网页制作, 从结构上来说已经是有点复杂了, 存在一个子类结构, 我们看一下《亲密接触ASP.Net》这本书, 这本书的信息是从
现在来建立下一个表, 考虑到第一类应用, 也是几乎绝大部分的查询方式, 这一类查询强调某本书的一个子元素或属性, 而这些元素或属性正好是XML文档里的路径。由此引入路径表:path_list, 见表2。把XML文档中出现的所有路径存储到表中, 这样我们要查询时可能从该表中选择正确的路径进行查询, 例如要查询书名时, 可以在path属性里匹配字符串“/catalog (/category) +/book/name”即可, 这里的字符串是用正则表达式表示的, 其中“/category”在path里可以出现多次, 但至少出现一次。
表2只是存储了XML文档中的所有路径, 至于路径下的内容才是查询时用到的主要信息。单有这个路径是不行的, 必须再引入一个表来存储XML文档中每个元素或属性的值, 即value_list表, 见表3。value_list表存储了路径和值, 在查询的时候可以依照路径查询, 而最终得到的结果是某本书或某些书的列表, 而这些信息可以通过book_list来获得, 这要求在value_list表中再存储一个book_id来定位到某一本书,
对于第一类的书目, 包括子类别, 需要单独存储出来, 以保证分类查询时的效率, 因此再加入一个表:category_list, 见表4, 这个表能确保分类查询时快速返回结果。
value_list、category_list两个表这里没有设主键, 实际应用时应添加主键。
3 执行查询
通过上面的四个表, 我们建成了图书目录XML文档的索引, 这里并不是把信息存储在一个表中, 而是分开建立索引, 以利于询和实现XML优势, 现在来执行前面提到的三类应用。第一类应用中, 对问题一, 首先从path_list表中查询合适的路径, 也就是配前面说到的字符串, 得到1和13两个path_id符合, 然后从value_list表中查询这两个path_id且value字段为用户给定的“我的年” (或者以“我的童年”为子串的字符串) 的记录, 返回book_id值, 最后从book_list表中得到其内容在XML文档中的位置, 定位XML文档中返回最终结果。主要用到以下的SQL语句:
SELECT start_pos, end_pos FROM book_list WHERE book_id IN (SELECT book_idFROM value_listWHER (path_id=‘1‘ORpath_id=‘13‘) AND value LIKE‘我的童年‘)
第二类问题通过category_list表就可以解决, 书目种类毕竟是少数, 数据量不会很大, 在这个表中查询要找的信息应该很方便问题三执行的SQL语句:
SELECT start_pos, end_pos FROM category_list where category_name=‘网页制作’
第三类应用比较少, 这种查询不需要返回书本信息, 需要操作的是value_list和path_list两个表, 重复查询value_list就可以得结果。这里我们为了简单起见, 只查询没有子类结构的情形。问题四的查询SQL语句为:
SELECT value
FROM value_list
WHERE path_id=’14’AND book_id IN
(SELECT book_idFROM value_listWHERE path_id=‘15‘AND value=‘清华大学出版社‘)
4 结束语
本文简单介绍了图书查询系统XML文档的一种索引建立方法, 它是针对查询这种特殊的应用设计实现的, 利用关系数据库来建立索引, 但最终的数据还是保存在XML文档中, 索引中建立了路径表, 能够支持XPath查询的实现。这种索引机制适用网上书店系统, 图书馆检索系统等, 只提供给用户查询, 不提供修改, 执行修改和更新的是图书管理员, 而且面向单一应用, 用特定的表实现, 效率较高。在有新的应用时, 我们可以建新的表机制来实现需求。这种索引能大大提高查询效率, 但存在一些不足, 由于是对查询建立的索引机制, 在多用户频繁更新数据的情形下, 系统需要重建索引, 会大大提高系统需求。
摘要：该文针对XML, DOM和SAX协议操作大文档的缺陷, 将技术成熟的关系数据库索引机制应用于图书书目查询系统, 从而实现对XML文档的快速查询。
关键词：XML,关系数据库,索引
参考文献
[1]Arzucan Ozgur, Taflan I Gundem.Efficient Indexing Technique for XML-based Electronic Product Catalogs[J].Electronic Commerce Re search and Applications, 2006 (5) :66-77.
[2]王宏宇.基于Native—XML数据库倒排索引算法研究[J].情报科学, 2006, 24 (7) :84-88.
[3]李素清, 陶世群.一种基于关键词的XML文档查询算法[J].计算机工程与应用, 2012, 48 (5) :138-142.
[4]赵雄峰.一种高效检索XML文档的倒排索引技术[J].电脑知识与技术, 2010, 6 (30) :8429-8431.
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数据索引技术论文05-31
索引结构06-22
电子索引07-06
资源索引09-21
空间数据索引06-18
网络索引相关问题08-21
文件柜索引06-01
索引和视图实验报告07-13
中国社会科学引文索引09-06
推手-中英文影评+电影情节索引05-28