论文部分内容阅读
在计算机软件应用领域,增量计算(Incremental Computation)有广泛的应用基础。然而增量计算的实现通常需要复杂的算法设计与艰苦的软件维护,从而限制了此类计算机应用系统的发展与普及,因此增量计算的实现迫切需要程序自动生成工具的支持。另一方面,由于XML被普遍应用于实现异构信息和异构平台的数据交换和数据共享,而XQuery又被W3C组织提出作为XML数据查询的标准,越来越多的应用采用XQuery语言实现XML数据计算,因此研究XQuery查询优化技术成为现在的研究热点。本研究发展了一种基于XQuery的增量计算程序自动生成技术,可对采用XQuery语言描述的计算程序进行程序变换,自动生成能够响应与此计算相关的数据变化的增量更新程序代码,依据前次计算结果得到新的计算结果,且令此增量更新代码的执行效率优于重新执行此计算的效率。首先,本研究提出了一个基于XQuery的增量计算程序自动生成方法。作为一个通用增量计算方法,此方法既能响应XML数据更新实现查询型增量计算,也能响应输入数据的更新实现计算型增量计算。此方法应用范围广,能够处理带有分支和自定义函数的XQuery计算,对于无法处理的程序结构,使用探索查询实现增量计算从而保证方法的通用性;生成的增量更新程序用XQuery语言描述,可以用任意XQuery引擎执行。其次,针对XQuery语言的特点,提出基于双向分析的增量更新代码生成技术。此技术采用自底向上的反向更新传播分析和自顶向下的正向结构构造分析实现增量更新代码生成。此技术可以处理带有分支和自定义函数的XQuery计算,不需要XML数据提供索引和Schema的支持,且无辅助信息存储,通用性强。再次,为支持增量更新代码生成,提出了XPath更新区域分析方法实现XPath变更区域的捕获。此分析方法不仅能够响应XML数据更新以捕获变更区域,也可以响应输入数据的更新捕获变更区域,支持除“//*”以及反向轴之外的所有XPath表达式。此方法生成的变更区域不仅用于实现基于双向分析的增量更新代码生成技术实现增量更新程序的代码生成,也能用于实现XPath计算结果的增量维护。最后,本研究研制一个新型的XQuery物化视图增量维护系统。此系统作为一个分布式系统中实现高性能的XML数据查询的新型软件工具,应用基于XQuery的增量计算程序自动生成方法,响应后台数据库变化,异步增量维护XQuery物化视图。此系统采用三层架构使之更容易地适应分布式数据处理。为提升系统效率,提出XML数据更新合并算法和增量计算程序合并算法来提升系统效率。