论文部分内容阅读
XML已经成为Intemet上数据交换的标准。XML不仅可以作为一个完整的文件传输，而且还有可以以一种串行数据流的方式传输。近年来，针对XML数据流的处理在研究领域引起了广泛的兴趣。XML流处理的挑战是如何能有效地处理巨量的针对XML数据流的查询集。这种查询通常是基于路径表达式的，如XPath、XQuery。
随着应用需求的增长，查询表达式也变得越来越复杂。我们发现，对于具有嵌套AND／OR谓词的复杂TwigPattem查询，目前还没有有效的处理方法。为此，我们开发了一个称为LeoXSQ的XML流处理系统。在LeoXSQ中，我们提出一种新的方法解决上述查询问题。围绕LeoXSQ，我们还开发了节点缓存管理组件和基于DTD的查询优化组件。本文的主要贡献概括如下：
1)提出一种新的方法处理具有嵌套AND／OR谓词的复杂twigpattern查询。在该方法中，将AND／OR谓词作为单独的抽象语法树来处理，利用基于运行时栈的算法，结合自顶向下与自底向上的过程，有效处理针对XML流的复杂twigpattem查询。
2)将所有twigpattem组合成单个可共享前缀的查询树，从而可以节省查询处理的空间与时间，并以输入的XML流顺序单遍处理所有的查询。通过对查询树中逻辑表达式进行公共子表达式的共享处理与短路计算，进一步提高了查询处性能。
3)提出了一种针对单个查询的基于语义链的缓存管理算法，并将其扩展并应用到前缀共享的多查询环境下。该算法能够以尽可能小的缓存空间处理递归嵌套文档与一对多关系文档。基于一种基于运行时栈的XML部分编码技术，来判断缓存节点间语义关系。这种方法只对进入运行时栈的节点编码，大大缩小了编码的范围。
4)分析影响XML流数据处理性能的关键因素。利用正则树文法和树自动机作为理论指导，阐述了使用DTD进行查询优化的方法。基于该方法，实现了查询优化组件。该组件在系统运行前进行预处理，不影响系统运行时的性能。