论文部分内容阅读
伴随互联网的快速发展,越来越多的数据以XML的形式描述、交换和存储。作为W3C推荐的XML查询语言,XQuery语言受到了越来越广泛的关注。XQuery语言与XML数据库的关系就如同SQL语言与关系数据库的关系一样。因此要想高效地实现XQuery语言,就需要一个强大如关系代数的XML查询代数系统。现有的XML查询代数更多地关注如何正确、完整地表达语义,保证了关系数据库中常见的逻辑优化能够应用于XML查询,并不能很好地满足XQuery语言所描述的多层嵌套查询的优化需求。为了更好的满足这一需求,本文提出了一种新的XML查询代数系统——FLW查询代数。该查询代数包含逻辑层代数和物理层代数两部分。逻辑层代数包含一组逻辑算子,这些算子用于表示查询计划的逻辑关系,不涉及实际的查询实现,可以作为查询计划的逻辑优化的基础。物理层包含一组物理算子,用于实现实际的查询操作,包含各种连接运算、筛选运算和结果枚举运算。本文还提出了用于FLW查询代数的数据模型——FLW实例树。这是一种树型结构的数据模型。相比XQuery规范中提出的XQuery数据模型(XDM),这种数据模型可以减少冗余的数据存储,减小查询中间结果的数据规模,并且更有利于高效的XML树模式查询技术的应用。最后,本文给出了基于FLW实例树结构,所有物理算子的实现方法。作者在SelabQuery XML查询引擎中实现了以上设计,并以SelabQuery中原本采用的XQA查询代数为参照,分别在XQA查询代数和FLW查询代数环境下运行了一组XQuery查询,记录了查询执行的时间和空间消耗。实验结果表明,对于多数据源的XQuery查询,采用FLW查询代数,查询时间明显少于XQA查询代数,并且查询内存占用也少于XQA查询代数。与XQA查询代数相比,FLW查询代数的优势非常明显。