论文部分内容阅读
可扩展标记语言(eXtensible Markup Language,XML)已成为互联网环境中数据交换和共享的事实标准。由于基于互联网的电子商务、电子政务和社会服务等应用系统中XML数据的爆炸式增长,如何高效的实现对XML数据的查询成为当前XML数据处理领域的重要课题。XQuery语言是W3C组织为了标准化XML数据的查询处理提出的一种功能灵活强大的函数式XML数据查询语言。然而,不同于关系数据,XML数据的查询处理具有半结构化数据处理的特殊性,最突出的就是被认为是XML查询核心操作的XML树模式查询,即Twig查询。XML树模式查询频繁的出现在XQuery程序中,其查询效率对整个XQuery程序的执行效率有相当大的影响。而针对传统扁平化关系数据的查询处理和优化技术不能解决这一问题。因此,发展面向XQuery语言的XML树模式查询处理技术,不仅能使XQuery实现得益于高效的XML树模式查询技术,提高语言的实现效率,而且为XQuery语言实现技术和XML树模式查询技术的发展奠定了一定的理论基础,对推动XML处理技术的发展有着重要的理论指导和实际应用价值。 本文的研究主要包括面向XQuery语言的XML查询代数、XML树模式查询、支持XML树模式查询的中间语言及XML树模式识别方法四个方面。 首先,XQuery语言既是一种查询语言,又是一种函数式程序设计语言。因此XQuery语言的实现需要将数据库中查询代数技术与编译中的中间语言技术相结合,将XQuery程序翻译为一种查询代数表示的查询计划描述语言,以便于计算过程的表示、程序分析和代码优化。 其次,高效的XML树模式查询技术在XQuery语言中的应用受到越来越广泛的关注。然而,一个XQuery查询中往往包含多个标准XML树模式查询。通过增强XML树模式的描述能力并发展相应的匹配算法,就有机会将XQuery中零散存在的多个XML树模式查询进行合并,从而减少XML树模式查询的调用次数和可能存在的冗余匹配,节省时空开销,提高整个XQuery的查询效率。 再次,对XQuery语言应用树模式查询技术,就要求用形式化的方法对树模式查询进行表示,从而使得用于描述查询计划的中间语言支持对树模式查询的描述,同时需要发展专用的算子支持树模式查询技术在XQuery实现中的应用。 最后,为了使得更丰富的XQuery查询语义被包含在XML树模式查询中,就势必要分析查询计划,从中提取出XML树模式,并挖掘潜在的优化机会,最终生成一组完整且准确的XML树模式,参与整个XQuery查询的执行。 基于对上述四方面内容的研究,本文的主要创新性成果总结如下: (1)提出一套新型的面向XQuery语言的XML查询代数——FLW查询代数,包括一种新颖的数据模型,和一组基于该数据模型的代数算子。和现有工作相比,首先,作为FLW代数数据模型的一部分,FLW实例树结构提供了基于多层子查询结果的树型XML查询结果的组织、构造和访问方法,既能够保证在生成逻辑代数表示的查询计划时保留FLWOR查询中的各种迭代关系和连接关系,又不会在物理代数执行时保存不必要的冗余节点,减少了中间结果的空间开销;其次,算子的设计更多的考虑了FLWOR语句之间存在的各种连接关系,便于逻辑优化;最后,FLW查询代数算子的设计及树型中间结果组织方式为高效的树模式查询算法的使用提供了便利。 (2)提出一种新颖的增量式XML树模式查询处理方法,包括一种描述能力强的XML树模式IncTP,和一种高性能的增量式匹配算法IncTPList。和现有工作相比,首先,IncTP模式不仅能够描述多种结构约束、逻辑节点、通配符以及多种谓词,而且能够描述不同XQuery表达式间隐含的逻辑关系和依赖关系,使得更丰富的XQuery查询语义被包含在XML树模式查询中,并且得益于其高性能查询算法;其次,IncTPList算法以FLW实例树结构作为中间结果的组织形式,每个子查询结果对应一个FLW实例树结构,该算法能够同时实现对XML文档和FLW实例树的匹配,从而使得XQuery程序中内层XML树模式查询能够对能够在外层匹配结果上进行增量式的匹配,从而节省了时空开销。 (3)提出一种支持XML树模式的XQuery查询计划描述语言,并为其定义了详细的指称语义,统一了FLW代数、XML树模式以及增量式查询的表示方法;同时提出一组支持XML树模式查询的专用算子,以便将树模式查询操作组织成整个XQuery查询计划的一部分,支持XML数据处理的实现。语言的形式语义为XML树模式提供了形式化的表示方法,使得形式化方法可以用于分析树模式查询的行为特征,有助于验证XML查询的正确性,为代数的逻辑优化和XML树模式查询优化的实现提供了理论基础。 (4)提出一种功能强大的XML树模式识别方法ExtraTP,同时提出一种新型的XML树模式提升优化方法HoistTP。和现有工作相比,ExtraTP方法识别能力强,不仅解决了树模式识别受查询结果输出顺序限制的问题,且能够分析XQuery程序的嵌套结构,跨越多层嵌套的程序模块来分析相关的XML查询,提取并组装成一组包含逻辑关系及依赖关系的IncTP,因此能够覆盖更大的XQuery子集。HoistTP方法将某些特定情况下循环内部迭代调用多次的内部XML树模式查询提升为1次外部XML树模式查询,有效地提高了特定类型XQuery查询的效率。