论文部分内容阅读
由于其良好的可扩展性和灵活性,XML已经成为Web上数据表示和交换的标准,在各种应用中出现大量的XML形式的数据。作为一种半结构化数据,XML数据的高效处理带来了新的挑战。XML数据管理已经成为数据管理中一个重要的研究领域。XML数据管理中一个重要问题是如何对XML数据进行高效的查询处理。本文以XML数据的高效查询处理为目标,研究了树结构XML文档、图结构XML文档、XML数据流和基于XML的信息集成系统中的查询处理,主要研究成果如下:(1)提出了一整套支持树结构XML文档上路径查询高效处理的方法。具体的,提出树结构XML文档的磁盘存储结构。该存储结构有效地结合了结构索引、基于编码的连接操作以及树的遍历操作,支持复杂路径查询的高效处理。基于这种存储结构,提出了多种查询操作的实现方法。针对带有复杂结构和值约束的路径查询,提出了代价模型和基于代价模型的查询优化策略。实验结果表明这种查询处理方法有着很高的效率和可扩展性,查询优化策略可以快速有效地生成查询计划。(2)在图结构XML文档的查询处理方面,提出了子图查询和拓扑查询的处理方法。具体的,对DAG上的可达编码进行了扩展,使之能够支持有圈的图,并且提出了有效支持子图查询的编码存储方法。基于这种存储方法,提出了子图查询处理策略。这种策略能够高效地处理形式为一般图、包含可达关系的子图查询,经过简单的扩展,可以用来处理同时包含可达关系和连接关系的子图查询。实验结果表明本文提出策略能够高效地处理子图查询。提出了一种图结构XML文档上的新型查询―拓扑查询,并且给出了拓扑查询的高效处理算法。(3)在XML数据流的查询处理方面,首次提出了XML数据流上聚集查询的问题,对其给出了精确定义并提出了高效查询处理算法,既支持复杂的XPath表达式,又适用于多种类型的XML聚集,并且可用于基于SAX的XML文档上的聚集查询处理。分析和实验结果表明本文的提出算法具有很高的效率和可扩展性。(4)在基于XML的信息集成方面,本文对结果传输、返回结果合并与数据源选择这三个关键技术问题进行了研究。具体的,提出了两种对作为结果返回的XML数据片段进行缩减的策略。提出了基于XML的信息集成系统中XML数据片段的连接操作,用来描述多种情况下XML数据片段的连接,对这些连接操作提出了高效的实现算法。提出了用于数据源选择的索引结构,能够同时对数据源中值的信息和结构信息进行概要,从而为具有复杂结构和值约束的查询进行数据源选择。还提出了两种索引缩减策略。基于压缩和非压缩的索引结构,分别提出了有效的数据源选择方法。实验结果表明这种数据源选择方法有很好的精度和效率,索引缩减策略能够在不过多损失数据源选择性能的情况下有效地缩减索引。