1、 目 录1 引言12 索引技术概论12.1 XML索引及其分类22.2 XML数据及XPath查询处理32.3 XML索引分类53 基于SQL SERVER2005的XML索引73.1 XML索引在Sql Server2005中的支持73.2 建立XML索引数据73.2.1 主索引83.2.2 次索引83.2.3 内容索引104 基于ORACLE 10G DB的XML索引114.1 什么是ORACLE XML数据库114.2 索引XML内容125 基于DB2 9 PUREXML的XML索引135.1 XML索引在DB2 9 pureXML中的支持135.1.1 XML索引的SQL函数类型145
2、.1.2 理解DB 2中XPath表达式7145.1.3 节点类型155.2 DB2 9 pureXML中的XML索引技术165.2.1 在路径中使用text()节点165.2.2 使用the UNIQUE关键词175.2.3 使用XML命名空间186 实验对比研究196.1 Sql Server 2005中的实验对比研究196.1.1 实验方法196.1.2 实验结果216.2Oracle 10g DB中的实验对比研究216.2.1 实验方法216.2.2 实验结果246.3 DB2 9 pureXML中的实验对比研究246.3.1 实验方法246.3.2 实验结果277 总结29致谢30参
3、考文献31主流DBMS提供的XML数据索引对比研究1 引言XML(Extensible Markup Language)，意为可扩展的标记语言，它是SGML的子集，是一套定义语义标记的规则，它也是一种元标记语言，即定义了用于定义其他与特定领域有关的、语义的、结构化的标记语言的句法语言。随着XML数据量的不断增长，要求更有效的数据管理能力和更快、更精确的查询。为了提高XML数据的查询效率，特别是结构查询的效率，要求有一种很有效的方法XML索引技术。 XML(最新的规范为2004 年的XML1.1)(extensible markup language),即可扩展的标记语言,是一套定义语义标记的规
4、范,其目标是能够定义计算机和人都能方便识别的数据类型.随着网络应用的快速发展,尤其是电子商务、Web服务等应用理念的进一步发展,使得XML类型的数据成为当前主流的数据形式.对XML据的管理也成为研究的热点.同时，随着互联网上XML文档的不断增多，对这些数据的使用越来越依赖于互联网搜索引擎强大的检索能力，对检索XML文档的搜索引擎的研究也就越迫切。如何将XML索引技术与现代主流关系数据库(ORACLE 10G, MICROSOFT SQL SERVER 2005和IBM DB2 9)技术结合起来，使得检索结果更为准确，也使得传输的数据量大大减小。2 索引技术概论 在讨论索引技术时，主要考虑两方面
5、的问题：一是索引的对象，既在什么数据上面建索引；二是索引的组织结构。下面分别讨论这两方面的问题。 在关系世界中，索引的对象很简单，就是元组的某一属性。这是因为在关系数据库里面，只有一种结构关系表，查询的时间直接查询表中的数据项。这种索引就是值索引。然而在XML数据库中，查询是多种多样的。有时是对XML文档中关键字的搜索，这类搜索可以用值索引来辅助；但是更多的是类似于XPath或XQuery那样的查询，这时搜索不仅涉及到值，还涉及到结构（如一个结点在文档树中的路径），因此，仅在某些值上建索引是不够的。在XML-enabled数据库里面，由于结构信息（如一个边的路径）往往分裂在几个表里面，因此无法
6、对路径建索引，查找特定路径的结点往往是通过几个表间的连接（称为structural join或containment query）来实现的，这也是XMLenabled数据库效率低下的原因之一。考虑到这些因素，一般的纯XML数据库都对多个对象建索引，主要有：值索引，即在属性值或结点内容上面建索引；结点名索引，即在结点标记上面建立索引；边或路径索引，即在XML文档树的边上面建立索引。 再看索引的组织形式。在关系数据库中，索引的组织形式主要是B+树及其变体。B+树结构的优点是：它是平衡的，因而对数据项的访问代价是基本确定的；它是扁平的，因而搜索的时候深度不是太深，访问的磁盘I/O不会太多；它是插入，
7、删除和查询时的效率都是较高的，因而综合性能是很好的。用B+树建立值索引毫无疑问是可行的，但是用它来管理XML文档的路径信息可能就不那么如意了。因为当XML文档的模式改变时，索引结构以及索引项可能都做较大调整，很明显这时维护B+树的代价是很高的。并且B+树对索引项的长度和索引项的数目是比较敏感的，如果要在大量长的而且重复较少的数据项上建立索引，B+树就会快速膨胀，从而导致访问时磁盘I/O的增加和更新时的繁琐，因而也不适合直接管理大量的路径信息。 另外一种常用的索引结构是哈希表。哈希表根据一个哈希函数快速将搜索键定位到某个桶（bucket）里面，如果桶中的记录不多就可以很快找到索引项，但是当索引项
8、过多是，桶的空间和数目会很快增长。此外，哈希表的性能取决于哈希函数的选择，一个糟糕的哈希函数同样可以导致索引性能低下，而在很多情况下，在知道索引项性质之前很难选择一个理想的哈希函数。因此哈希表也不一定适合于管理XML数据。 此外，还有一些传统的索引技术，如倒排列表（inverted list），但是它的作用范围很有限，一般用在文本搜索或关键字查询里面，所以只作为一个辅助索引。2.1 XML索引及其分类对XML数据建立有效的索引,是左右XML数据处理性能的重要因素.本节归纳目前XML索引技术的研究现状,将XML索引技术分为两大类:节点记录类索引(本身还可以分为3个小的类型)和结构摘要类索引.根据
9、XML数据查询处理效率以及XML数据修改对XML索引的要求,讨论了相关XML索引方法的优点和不足。2.2 XML数据及XPath查询处理3(a)Sample.xml(b)Sample.dtd图2-1 sample.xml和sample.dtd示例XML规范规定了XML数据必须满足的条件,其基本的形式是XML文档.从逻辑上讲,一个XML文档通常由5部分组成:声明、元素、注释、字符引用和处理指令,为叙述方便,统称为XML数据单元.XML数据内容的限制通常由XML模式(包括DTD和XMLSchema)来描述.图2-1为sample.xml文档及其DTD的示意.图中root为sample.xml的根,
10、它具有3个标签为a 的区段,而每一个a区段都嵌套一个以b 标签为标志的区段.当给定XML 文档时,该文档也就隐含地确定了其中所含的标记单元的顺序,称为XML顺序(XML ordering),这一概念在XML查询处理时是需要考虑的,即查询结果中的标记单元应当具有类似的顺序特征。为了从XML以及半结构化数据中获取所需要的信息,研究人员开发了许多查询语言,包括Lorel,XML-QL,XML-GL,Quilt,XPath,XQuery.它们共同的特征为:采用了正则路径表达式的形式,其本质是捕捉XML数据单元间的结构关系和内容.XPath是实现XML数据周游的基本语言,是XSLT,XQuery的基础.
11、它首先定义了XML数据的树形模型.图2-2即为图2-1的满足XPath数模型定义的XML树.图2-2中每个元素节点左侧的数字表示该节点在前序遍历XML 树形成的节点标签序列中的序号;右侧的数字表示该节点在后序遍历XML树形成的节点标签序列中的序号.由XPath的定义可以构建很复杂的查询语句,主要分为3个层次:线性路径表达式、分支路径表达式和路径树。图2-2 sample.xml对应的XML树当在XML文档类数据之上处理XPath查询时,借助于W3C定义的XML数据处理的两种接口规范,DOM(document object model)和SAX(simple API for XML),处理方式可
12、概括为:顺序读取XML 文档中的节点;如果该节点的路径满足XPath中定义的条件(包括结构关系、测试条件和谓词关系),那么该节点即为XPath查询语句的一个输出.这种基本的线性表达式查询语句的处理方式存在如下两个缺陷:(1) 只能采取周游的方式在XML文档中寻找满足查询语句结构关系的数据单元,即为了获取满足查询路径的结果,必须周游所有可能的数据单元的标签路径,效率不高。以图2-2为例,要想得到文本包含“c3 c4 c5 c6”的“c”节点,那么必须从根节点开始沿着rootabc 的路径到达.如果采取某种索引结构,可以直接定位到目标节点,将会大大提高查询的效率。(2) 对XML中标签路径相同的节
13、点,仍然需要重新遍历它们的路径.这个问题直接来自于(1)。同样以图2-2为例,如果目标节点是c,文档中存在3条相同标签路径的节点路径,而根据上述基本处理方式,为了搜索所有的c节点,必须对同样的路径都要遍历.那么,将同样路径的节点汇集到同一节点中,就可以提高搜索的效率。2.3 XML索引分类(1) 节点记录类索引节点记录类索引本质上即是将XML数据分解为数据单元的记录集合,同时在记录中保存该单元在XML数据中的位置信息.主要有两种获取位置信息的方法,一种是节点序号方法(node numbering method,有时也称为节点标签方法,node labeling method),另一种是节点路径
14、方法(node path method).对它们的研究占了XML数据处理研究文献中相当大的部分.根据路径信息表现形式的不同,节点记录类索引分为3大类:基于节点序号的索引、基于节点路径信息的索引和二者相结合的混合索引。节点序号的基本思想：这类索引中的位置信息是节点在某种遍历序列中的序号.对于一个XML文档,设计遍历XML文档的策略,遍历的最终结果表现为一个由节点组成的序列;相应地,节点的标签在序列中就有一个序号,该序号表明了节点间的次序关系,也能够反映节点间的结构关系,进而,就可以基于该序号信息捕获节点间的结构关系.节点序号类XML索引的基本思想是:基于XML文档设计某种遍历策略,得到由元素组成
15、的序列,节点的标签在序列中就具有唯一的次序,将序列与某指标集(最常用的就是自然数)建立一一映射的关系,对应序列中某个标签就有唯一的序号;对任意两个具有节点序号信息的节点,可以构建某种运算,该运算的结果可以表征节点间的结构关系,即(独立单元属性,位置信息)结构关系映射.根据标签序列生成方式的不同,目前研究文献中序号类索引可分为两种:基于标签有向树的遍历(如先序遍历和后序遍历)和基于字符流模型的顺序处理.根据映射指标集的不同,可分为赋以自然数、赋以局部编码和赋以素数的方式.在序列生成和节点序号赋值的基础上,可以构建不同形式的位置信息,进而形成不同的节点记录索引形式。节点路径的基本思想：节点的路径信息同样蕴含节点在XML数据中结构的信息:如果给定两节点的路径信息,同时预知两节点存在结构关系的情况下,就必然可以获知它们之间的结构关系.即节点A的标签路径包含节点B的标签路径,那么,在XML树中A和B之间一定具有祖先-子孙的结构关系,且B是A的祖先.所以,基于路径信息来获取节点的结构关系就成为另一组XML数据处理技术的思路来源,并演化出基于节点路径的XML索引.这类索引的核心技术是字符串的模式匹配.因而,这类索引记录数据的管理方法,有许多是来自于信息获取领域的。例如，Trie,Patrici
