站长论坛

标题: 基于关系数据库引擎的XML索引技术 [打印本页]

作者: jinlj 时间: 2007-11-2 20:56
标题: 基于关系数据库引擎的XML索引技术
XML(可扩展标记语言)已成为Web应用中数据表示和数据交换的标准,随着Internet的快速发展,尤其是电子商务，Web服务等应用的广泛使用,XML类型的数据成为当前主流的数据形式。因此XML数据的管理技术尤其是XML数据查询技术成为当前的研究热点。

相比起关系型数据，XML有着各种各样的优点，但有个最大的缺陷就是它的效率。因为关系型数据文件中，数据的字段名只需出现一次即可，而XML数据文件中，元素名将反复出现，这必须会影响到查询的效率。为了尽可能的提高XML的查询效率，需要为XML类型提供了索引功能。

万维网联盟于2007年1月23日将XPath2.0和XQuery1.0确定为推荐标准，结束了此前各种查询语言群雄逐鹿的局面。基于此标准，除传统厂商外，各科研机构纷纷提出了对XPath和XQuery的实现(文献中提及的有十数种)，其存储模型不同，查询算法各异，优化途径也各有所长，在这样的背景下，达梦数据库公司根据自身发展战略，也提出了自己的XML查询引擎模型，目前，达梦的XML查询引擎正在紧张开发中，而对XML数据建立有效的索引是影响XML数据查询性能的重要因素。在深入分析当前已有的数据库产品的索引技术基础上为达梦XML查询引擎设计一种较为合理的索引结构，以使该引擎能发挥较优性能。

XML索引技术简介

目前，人们对XML的研究主要分为两个方面。一个是对XML这种半结构化数据的存储、查询和管理的的原生数据库，其中的数据和元数据完全采用XML结构表示，与其底层的数据存储格式(如对象模型、关系模型等)无关。另一个是它与关系数据库之间的相互转换，利用关系数据库的成熟技术对XML数据进行处理。由于后一个方向比较有现实意义，因此成了XML研究中的重点。

而除了存储方案之外，索引技术也是决定一个数据库系统最重要的因素之一。如果对XML文档不构建索引结构，那么针对XML数据的任何查询都很可能导致对整个文档树的遍历，随着XML数据集的增大，这种开销是不可忍受的。故此，对XML索引技术的研究具有较高的理论和实用价值。

虽然传统的索引技术经过长期的积累已经相对成熟，但是，这类索引技术针对的主要是根据值(而不是具有某种关系的模式)定位数据记录的功能，不太关注数据记录间的逻辑关系;而 XML 数据查询的基本特征就是根据模式特征(正则路径表达式形式描述的结构关系)的输入提取符合该模式的数据，所以，XML 索引的主要内容就是设计适用于模式匹配的技术。

XML索引分类

基于路径的XML索引

基于路径的索引是以XML树结构中节点的路径信息为基础，采取某种约简方式，使得约简后的树结构只维护不同的路径信息，而不会存在具有相同路径的两个节点。已经提出的这类索引有：DataGuides索引、Index Fabric索引、XML数据的自适应路径索引(Adaptive Path Index for XML Data， APEX )

Dataguides 索引是从根结点为起始的精练路径的一种结构摘要。边标签串联在一起形成的字符串路径在 Dataguides 中只描述一次。Dataguides 减少了遍历路径查询时所需的部分结点，它对从根部遍历 XML文档是有效的。但对于含有通配符的路径查询或对带有XPath标准中定义的descendant-or-self轴的路径查询要进行多次的连接操作，查询效率较低，并且存在数据冗余。

Index Fabric是在Patricia Trie树上发展而来的一种索引结构，它把到每个元素节点的每条标记路径都用一个字符串编码，再将这些编码值插入到Patricia Trie树中去，从而将按照路径方式对XML数据的查询转化为对字符串的查询。在查询时先将查询路径编码成字符串的形式，再在索引树中进行查找。Index Fabric索引优点是存储了XML数据的层次结构信息，统一处理了有模式和无模式信息情况下的XML数据的检索，并且使对XML数据的查询和更新所需要的时间与层次相关而不是与索引关键字的长度相关。Index Fabric索引的缺点在于丢失了元素节点间的结构关系，因为它只保留了有文本值的元素节点的信息。因此，与DataGuides索引类似，Index Fabric索引处理带有XPath标准中定义的descendant-or-self轴的部分匹配查询表达式效率不高。

为此，APEX[14]引入了依赖于XML数据查询分布的信息:将经常出现的XML查询语句对应的标签节点预先保存在一个哈希结构中。它的作用类似于Cache的功能:当有新的查询要求处理时，首先在哈希表中搜索是否有满足的节点集合。但它对于带有元素值或属性值的查询表达式的处理效率较低。

作者: jinlj 时间: 2007-11-2 20:56
基于节点的索引

基于节点的索引本质上即是将XML数据分解为数据单元的记录集合，同时在记录中保存该单元在XML数据中的位置信息。与基于路径的索引不同，基于节点的索引打破了必须通过标签路径查找节点这一限制，将XML数据分解成规范形式的节点记录。由于保存了节点的位置信息，而且能够很好地结合到成熟的关系数据库管理系统中，因此它是目前应用最广泛的一种索引。

根据对位置信息的编码方式不同，基于节点的索引一般可以分为一下几类：

1 基于前缀的索引

基于前缀的索引主要是根据Dewey[12]编码生成的索引，文献[13]的 ORDPATH 编码采用的也是类似的方法,并给出了压缩 ORDPATH的方法，该方法已应用于SQL Server 2005的索引组织中。

前缀编码的基本思想是直接将一个节点的双亲节点的编码作为该节点编码的前缀，对于前缀编码，要判断一个节点v是否另一个节点u的后裔，只要判断u的编码是否v的编码的前缀。前缀编码索引的一个重要性质是它们的字典有序：以节点r为根的子树中的任意一个节点u，它的前缀编码c(u)大于（小于）它的左兄弟子树（右兄弟子树）中所有节点的前缀编码。因此，基于前缀的索引不仅能够有效地支持包含关系的运算，而且能够有效地支持文档位置关系的计算。

2. 基于区间编码的索引

对于区间编码索引,树T中的每一个结点被赋予一个区间编码[begin,end],满足:一个结点的区间编码包含它的后裔结点的区间编码.也就是说，树T中的节点u是节点v的祖先，当且仅当start(u)<start(v) and end(v)<end(u)。两个节点的区间编码之间的关系为：它们要么完全不相交，要么完全包含。

第一个区间编码方案是Dietz编码,树T中的每一个结点被赋予一个具有先序遍历序号和后序遍历序号的二元组<pre,post>.由于树T中的一个祖先结点u在先序遍历(后序遍历)中必然出现在它的后裔结点v之前(之后),因此, 节点u和v是祖先/后裔关系,当且仅当pre(u)<pre(v)且post(v)<post(u).因此,树T中的任意两个结点之间的祖先/后裔关系的检测(即包含检测)能够在常数时间内被计算(即两次比较运算).对于该编码方案,pre或post均可以作为结点

另一个区间编码索引的典型例子是XISS索引，它为每个节点赋予一个数字对<order，size>，其中order为扩展的前序编码，size为节点的子孙的范围。对一棵文档树中的任意节点X和Y，当且仅当order(x)<order(Y)≤order(X) + size(x)，则X是Y的一个祖先。

XISS索引通过将原始查询语句分解为子表达式。然后分别针对这些子表达式实现查询，最后对这些中间结果进行联结获得查询结果集。从而能较好地支持含通配符的查询语句。不过，它是对每一个中间结果进行联结后得到最终查询结果。虽然这样一种方法的确能够解决所有的通配符问题，可是，这种中间结果的联结很有可能是非常耗时的，特别是对于长路径的简单表达式。

两种索引机制的比较

基于路径的索引主要基于节点合并的策略，通过节点等价、路径等价等技术，得到比原始文档小得多的索引结构，它的结构仍然是树型的，所以在处理查询时，基本上仍须遍历整个索引树才能得到结果。基于路径的索引可以很好地支持简单路径表达式的查询，但是对于正则路径表达式，它效果不是很理想。

基于节点的索引通过编码技术索引每一个节点，节点之间的结构关系通过编码可以在常数时间内确定它可以很好地支持正则路径表达式，但是对于长的路径表达式，尤其是在查询产生的中间结果很多的时候，节点索引的连接操作代价高昂。

基于路径的索引和基于节点的索引各有优缺点，但可以优势互补。目前在实际应用中，基于节点的索引应用更为广泛，研究得也比较成熟，因此，达梦公司有关XML索引结构研究主要以基于节点的索引为主，并适当参考基于路径的索引加以改进。

欢迎光临站长论坛 (http://tzlink.com/bbs/)