FLW查询代数物理实现方法的研究

• 作 者: 刘畅
• 机 构: 北京工业大学
• 出 处: 北京工业大学
• 发表日期: 2014年01期
• 关键词: XQuery XML查询代数 XML查询物理实现

伴随互联网的快速发展，越来越多的数据以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查询代数的优势非常明显。