时态xml索引研究

《时态xml索引研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中山大学博士学位论文时态XML索引研究姓名：汤娜申请学位级别：博士专业：计算机软件与理论指导教师：汤庸20080520中山大学博士学位论文时态XML索引研究专业：计算机软件与理论博士生：汤娜指导老师：汤庸教授摘要目前Web应用的支撑技术大多局限于静态和快照式，但是)(ML文档的结构和内容随着时间的流逝不断变化，引入“时态表达"后，时态XML本身就能够记录xML文档的一系列修改痕迹，它提供了一种高效可行的XML版本管理方案。另一方面，由于“传统关系模型”的灵活性差以及“SQL语言’’的可扩展性低等原因，至今还没有解决如何在已有的商业数据库系统中全面支持时态的有效可

2、行的方案。和传统的关系模型和SQL相比，xML和XQue巧能够更好地支持时态信息表达和时态查询。无论是XML数据文档需要处理随时间变迁带来的一系列问题，还是传统时态数据库需要在商业化进程中寻找新的契机，XML文档的版本管理和内容的时态查询正在成为下一代web信息系统中重要的应用。但目前对时态)【ML的研究主要集中于“数据模型"和“查询机制"，集中在逻辑层如何用)(ML来描述时态信息，比较少关于时态)(ML的物理存储和索引的研究。目前在时态)(ML索引方面所做工作或者无法适用于大的时态)(ML文档，或者索引的空间代价较高且查询效率不高。本文研究了时态ⅪⅥL的数据模

3、型，以及基于此数据模型创建了索引模型，通过创建索引优化了基于时间的查询。本文所做的主要工作和贡献包括：论文提出了一个时态Ⅺ订L数据模型，该模型将一个时态XML文档建模成一个带有有效时间边标记的有向无环图。提出了基于父节点和入边有效时间的前缀编码方案。并探讨和实现了四种将该数据模型映射到一个具体的时态XML文档的映射方案。并通过实验定性定量地分析了四种映射方案及其适用场合。论文基于时态XML数据模型，引入节点问的基于时态等价的等价关系和基于时态偏序的拟序关系，创建了一个索引模型VTempⅪ讧LIndex。此模型按照路径模式PaⅡ儿abel分为若干个模式类，所有符合

4、某个路径模式的从根到叶节点的路径会放在这个类中，每个路径模式类按照路径从根节点到叶节点分层形成层节点，每个层节点的基本特征是具有二重嵌套的索引框架，即在由时态等中山大学博士学位论文价关系确定的等价类中进一步建立由时态偏序关系确定的拟序关系，使得针对有效时间区间的二维(有效时间的开始时间，有效时间的结束时间)查找变成了一维的查找，查找的效率得到了大大提高。论文首次基于A1len的13种时间区间／点的关系，设计了针对时态XML文档值和结构的查询和更新的算法，并通过理论分析对比了没有经过节点时态过滤优化的查询算法和采用节点时态过滤优化的查询算法的效率。本文还提出了一种

5、采用前缀编码结合hashmap的方法大大地提高了祖先，子孙匹配效率。论文按照VTempxMLIndex应用实现的基本思路，设计和实现了基于VTempXMLIndex索引模型的查询和更新算法，并通过和目前时态XML索引中性能较好的算法相比，实验结果表明，基于VTempXMLIndex的时态查询和更新算法是可行的和高效的，能适于数据量多达50M的情况，而且随着数据文档的增大，查询时间的增长趋势也是线性的。而且本算法随着查询语句含有的时态约束越多过滤掉的节点越多时，查询效率越高。关键字：时态查询，时态数据模型，文档映射，时态)【T小。索引，时态等价关系，时态偏序关系I

6、V学位论文使用授权声明本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。学位论文作者签名：i≯岬日期：沙g年厂月∞日IX翩躲f确日期：办髫年争月即日中山大学博士论文第l章绪论第1章绪论§1．1引言随着网络和Internet的发展，数据交换的能力已成为新的应用系统的一个重要的要求。随着信息共享和数据交换的范围不断扩大，传统

7、的关系数据库也面临着挑战。一方面数据库技术的应用是建立在数据库管理系统基础上的，数据库属于高端应用，需要昂贵的价格和运行环境；各数据库管理系统之间的异构性及其所依赖操作系统的异构性，严重限制了信息共享和数据交换范围；数据库技术的语义描述能力差，大多通过技术文档表示，很难实现数据语义的持久性和传递性，而数据交换和信息共享都是基于语义进行的，在异构应用数据交换时，不利于计算机基于语义自动进行正确数据的检索与应用。1．1．1XML的时态驱动可扩展的标记语言EXtensibleMarkupLanguage()(ML)同HTML类似，都是一种基于标记的标记语言，它继承了S

8、GML的大部分功能，却使