论文部分内容阅读
由于互联网技术的快速发展,我们可以通过它来发布和获取各式各样的信息。所以,为了充分且有效地表示网络上丰富的数据,W3C组织提出了将XML作为互联网上信息共享的格式。XML由于具有半结构化描述特性和很容易被扩展等特点,目前被广泛地用在互联网上数据的描述与交换,并逐渐作为事实上的标准。为此,高效的XML数据查询成为使用XML的必然要求。为了对XML数据的查询与处理等操作进行标准化,W3C组织提出了一种标准的XML数据查询语言——XQuery。其最核心的操作是Twig查询,又被称为树模式查询。所以,设计一种高效的Twig查询算法已经成为研究的热点。经过了几年对Twig查询的研究,已经出现了一些比较常见的Twig查询算法,如:基于结构连接的MPMGJN算法、基于整体匹配的TwigStack算法及其衍生算法Twig2Stack、避免层次栈这种复杂数据结构的TwigList算法、进一步减少中间结果产生的TreeMatch算法等。其中,TreeMatch算法由于极大程度上减少了中间结果的产生,被认为是最好的Twig查询算法之一。然而,在TreeMatch算法的核心操作getNext中,存在不少仅依赖Twig查询模式的计算。当getNext调用次数很多时,这种冗余的重复计算会严重影响TreeMatch算法的性能。为了进一步改进TreeMatch算法,提高TreeMatch算法对XML数据的查询性能,本文提出了一种基于部分求值和热踪编译的Twig查询优化方法,该方法以Twig查询模式作为不变量进行部分求值,把查询请求翻译成一种Twig查询机指令序列,避免了查询过程中对Twig查询模式的重复计算;并且针对这种查询机指令序列的解释过程,利用热踪编译技术进行了优化,以提高查询机指令序列的执行效率。对比试验说明基于部分求值和热踪编译的优化方法能够将Twig查询效率提高了20%到60%。