基于关系数据库引擎的XML索引技术

『 更新时间:2008-4-14 』『 字体:变小 变大 』『 作者:佚名 | 来源:互联网

XML(可扩展标记语言)已成为Web应用中数据表示和数据交换的标准,随着Internet的快速发展,尤其是电子商务,Web服务等应用的广泛使用,XML类型的数据成为当前主流的数据形式。因此XML数据的管理技术尤其是XML数据查询技术成为当前的研究热点。

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

万维网联盟于2007123XPath2.0XQuery1.0确定为推荐标准,结束了此前各种查询语言群雄逐鹿的局面。 基于此标准, 除传统厂商外,各科研机构纷纷提出了对XPathXQuery的实现(文献中提及的有十数种),其存储模型不同,查询算法各异,优化途径也各有所长,在这样的背景下,达梦数据库公司根据自身发展战略,也提出了自己的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的功能:当有新的查询要求处理时,首先在哈希表中搜索是否有满足的节点集合。但它对于带有元素值或属性值的查询表达式的处理效率较低。

[1] [2] 下一页

【点击数:】【发表评论】【加入收藏】【告诉好友】【打印此文】【关闭窗口

关文章

您的姓名:
评分等级:
1分 2分 3分 4分 5分
评论内容:
1、严禁发表危害国家安全、政治、黄色淫秽等内容的评论。
2、用户需对自己在使用金石网服务过程中的行为承担法律责任。
3、本站管理员有权保留或删除评论内容。
4、评论内容只代表网友个人观点,与本网站立场无关。
  • 金石网
  • | 设为首页 | 加入收藏 | 联系我们 | 版权申明 | 友情链接 | 站点地图 | 网站帮助 | 网站留言 | 广告服务 |
  • Copyright © 2001-2008 KingsNet.biz All Rights Reserved. 闽ICP备05026663号
  • 返回网站顶部