论文部分内容阅读
由于网络技术的不断发展,web服务、电子商务的广泛应用,XML已成为网络应用中数据表示和数据交换的标准。XML表示数据的同时,还携带了数据的语义,可以作为一种中间格式,为所有平台所使用。XML数据库技术已得到较为深入的发展,取得许多优秀的学术成果。而时间作为商业应用中的一个重要元素,引入到XML数据中具有实际意义,可用于表示数据的有效时间。时态XML数据库就是对XML数据库进行扩展,增加对时态属性的支持,可以跟踪历史数据,或恢复数据到任一时刻的状态。国内外对时态XML数据库关注越来越多。随时间推移,数据不断增多,对查询处理的性能要求越来越高。与非时态XML数据库一样,如何建立高效的索引成为时态XML数据技术的重要问题。在时态XML索引领域,较多是在时态XML文档更新时产生一个新版本,需要遍历不同的版本才能完成查询处理,影响查询处理性能。另一些则注重借鉴非时态XML数据库的索引技术,对其进行扩展,在索引的构建,查询和维护中分别增加对时态的支持。非时态XML索引大致分为结构摘要类和结点记录类索引。它们的构造思想对处于起步阶段的时态XML索引技术有很好的启发作用。本文中使用的时态XML模型是将不同有效时间的数据存放在同一个文档,而不是将数据按时间划分版本分开保存。针对这种时态XML文档的特点,本文提出一种新的时态XML索引技术TFIX。它的基本思想是在处理查询时,只在文档中可能包含查询结果的部分进行搜索,避免遍历整个文档。对于大的时态XML文档,本文首先枚举出所有深度为K的子文档片,K是索引的参数且为整数,以特征向量来表征每一个文档片,计算出各个文档片的特征向量并作为键值插入到B+树中建立索引。索引在处理查询时,同样将小枝查询看作是一棵查询树,计算出特征向量,以此在B+树进行匹配,查找出所有可能包含查询结果的子文档片集,最后只在这个中间结果集中进行简单遍历即可得到最终结果集。本文所使用的特征向量包含如下几个分量:文档片根结点名称、文档图对应矩阵的最大最小特征值和根结点有效时间。它是基于图论中的基本结论和时态XML文档自身的性质提出来的。本文详细讨论了TFIX索引的构造、查询和维护的算法过程,并通过实验对比,验证索引的性能。本文的创新之处在于,提出一个特征向量并利用它的筛选作用,减少查询时需要遍历的范围,提高索引的查询处理性能。这种思路与结点记录类和结构摘要类索引的构造思想有所区别,但在TFIX索引构造过程中也借鉴了计算结构摘要的理论,提出适合本索引的双拟概念。实验结果表明TFIX索引具有较突出的查询性能。