论文部分内容阅读
随着XML数据被广泛应用于互联网服务、信息集成等各个领域,针对XML数据的结构化查询,尤其是作为其核心操作的多分支查询,已经在研究领域成为一个热点话题。虽然在最近几年,为了高效地处理XML的结构化查询,大量的算法已经被提出,但是现有的算法却并没有对XML DTD文件和XML scheme文件进行充分得利用,而通过本文的工作可知,若能合理利用这两种文件,将能较大的提高XML结构化查询的效率。 本文基于北京大学数据库实验室的国家863高技术研究发展重大专项支持项目“无缝集成的关系-XML双引擎数据库管理系统研制及其示范应用”以及国家“核高基”重大专项课题“大型通用数据库管理系统与套件研发及产业化--XML数据管理技术研究与开发”,在深入调研国内外大量相关工作的基础上,提出了一种新的针对XML数据的查询处理方法。本文的主要贡献如下:⑴提出了一种基于路径同构和标签同名的概要树模型(包括概要树的相关定义和定理);⑵提出了两种概要树的构建方法:基于模板文件的概要树构建方法和基于实例数据的增量式概要树构建方法,并对这两种方法进行了深入的分析和比较;⑶在概要树模型的基础上,提出了一种新的编码方式,称为概要杜威编码,并提出了三种概要杜威编码的压缩方式。通过使用概要杜威编码,本文不仅可以对文档元素编码,也可以对查询路径进行编码;⑷提出了一种新的路径匹配算法(PathCheck算法)和一种新的分支匹配算法(TJumperJoin算法)。在查询处理过程中,它们只需要扫描与查询的叶子节点相关的元素,并且可以借助位操作完成路径匹配。此外,TJumperJoin算法还可以跳过大量与最终结果无关的元素;⑸实现了本文所提出的编码方法和查询算法,并在各种不同大小、不同种类的数据集上,通过大量的与其它同类方法的对比试验,对它们的效率进行了测试。