XQuery语言的部分求值技术

摘要

XQuery是W3C组织提出的一种功能强大的XML数据查询语言。随着XML数据的广泛应用，XML日益成为Internet上数据交换的标准化的数据存储格式，导致XML格式数据的数据量和查询计算复杂性的增加，提高XQuery语言的查询效率的需求日益迫切，而部分求值技术是用于提高程序运行效率的一种程序变换技术，对XQuery查询程序进行部分求值处理能够有助于提高该程序的运行效率，缓解XML数据查询处理日益复杂与提高性能要求之间的矛盾。因此，研究针对于XQuery查询语言的部分求值技术不仅扩大了部分求值技术的应用领域，对于XML数据库技术、XQuery语言查询技术的发展在程序理论和实际应用上都有着重要的意义。 xQuery语言部分求值技术的研究主要包括引用敏感性分析、绑定时间分析和程序例化技术等三个方面。 在XQuery程序部分求值过程中，由于XQuery的语言特征和处理对象XML数据的特殊性，基于节点重构的XQuery语言部分求值方法在进行XML数据的常量折叠时会带来语义丢失，为此本文提出了一种新颖的程序分析技术——引用敏感性分析。通过使用引用敏感性分析，使得XQuery语言部分求值中能够有效地避免因对这种常量折叠所带来的副作用，保证了XQuery语言部分求值的精度。 由于引用敏感性分析的引入，使得要判断出一个表达式是否能够被例化或滞留就不能够仅仅凭借静态参数的指定信息和程序本身的静态不变量，还必须参考引用敏感性分析提供的相关信息。因此，与传统的部分求值不同，需要在XQuery语言部分求值中的绑定时间分析中参考引用敏感性分析的结果来重新确认其最终的绑定时间状态以保证其能够在例化阶段中进行正确的处理。 XQuery程序例化技术的研究主要包括程序例化实现方法的研究以及面向不同应用环境的编译时刻例化和运行时刻例化两种例化方式的研究。针对XQuery语言不同于一般函数式语言的语言结构和数据模型，研究了各种控制结构和XML操作的程序例化方法。同时，考虑到XQuery语言应用中，普遍采用动态生成数据查询命令的特点，在实现了编译时刻程序例化的基础上，发展了运行时刻程序例化技术，使得使用者有可能依据程序执行中不变量进行程序自动例化，产生高性能的查询程序。 基于上述的研究，实现了针对XQuery语言的部分求值系统——XQPE。XQPE系统是目前第一个针对于XQuery程序的自动化部分求值系统，扩展了部分求值技术的应用领域。此外，本文研究了相应的XQuery部分求值技术的应用技术，包括有：基于XQuery语言部分求值的动态编译技术和XQJ应用框架。这使得XQuery语言部分求值技术能够直接应用于实用的编程环境中，提高XQuery程序的执行效率，并且对XQuery语言部分求值技术的应用与发展也有推动作用。 本文的主要创新性成果如下： 1)提出了一种引用敏感性分析，用于发现和标记可能导致语义丢失的表达式，从而正确地判断出针对哪些表达式的计算结果可以采用XML文档重构的常量折叠方法，从而保证基于已知信息的、不涉及反向轴等特定运算的表达式计算都可以在部分求值阶段完成；进而扩展了传统上的绑定时间分析，使其不仅根据程序不变量等其它静态信息来标记表达式，而且参考引用敏感分析的结果来最终确定表达式的绑定时间状态，从而提高绑定时间分析的精度，扩大程序中部分求值的范围。 2)提出了一种XQuery语言的程序例化方法，扩展了传统的函数式语言程序例化方法；针对FLWOR表达式、XML文档对象模型和xQuery数据模型等语言结构，提供专用的程序例化策略；采用4种函数例化模式来控制备个函数调用表达式的例化方式；并且针对不用应用需求设计了两种例化方式：编译时刻例化和运行时刻例化，扩大了XQuery语言部分求值技术的应用范围。 3)基于上述XQuery语言的部分求值技术，研制了第一个支持XQuery程序自动例化的部分求值系统——XQPE，它支持XQuery程序编译时刻例化和运行时程序例化两种例化方式，拓展了部分求值技术的应用领域。 4)面向基于XQJ接口的XQuery查询程序，发展了一种新型的基于xQuery语言部分求值的动态编译机制，将XQuery程序运行时刻例化技术成功地运用于XQJ接口的实现，有效地提高了这种基于XQJ的XQuery应用程序的执行效率。

目录

文摘

英文文摘

声明

第1章 绪 论

1.1 课题背景

1.2 研究的目的和意义

1.3 课题来源

1.4 本文的工作

第2章 XOuery语言与部分求值技术

2.1 XQuery语言的基础概念

2.1.1 XQuery语言的文法

2.1.2 XQuery语言的数据模型

2.1.3 XQuery语言的特点

2.1.4 XQuery语言的研究现状

2.2 部分求值技术基础概念

2.2.1 部分求值的基本原理-Kleene的s—η-n理论

2.2.2部分求值技术的相关定义

2.2.3部分求值技术的分类

2.2.4部分求值技术的研究现状

2.3 存在的问题与机遇

2.4 本章小结

第3章 引用敏感性分析

3.1 基于文档重构的XQuery语言部分求值中的新问题

3.2 引用敏感性分析

3.2.1 引用敏感性分析状态

3.2.2引用敏感性分析的方法

3.2.3 引用敏感性分析的时空复杂度分析

3.2.4引用敏感性分析示例

3.3 相关工作

3.4 本章小结

第4章 绑定时间分析

4.1 XQuery语言部分求值实现策略的选择

4.2 XQuery语言部分求值中的两阶段BTA

4.2.1 绑定时间分析状态

4.2.2函数展开例化模式

4.2.3动态分支标记

4.2.4第一阶段的绑定时间分析

4.2.5第二阶段的绑定时间分析

4.2.6绑定时间分析的时空复杂度

4.2.7绑定时间分析示例

4.3 相关工作

4.4 本章小结

第5章 程序例化

5.1 XQuery语言部分求值中的例化处理

5.1.1程序例化方法

5.1.2程序例化的时空复杂度分析

5.2 不同应用环境下的例化方式

5.2.1编译时刻例化

5.2.2运行时刻例化

5.3 例化示例

5.4 相关工作

5.5 本章小结

第6章 部分求值系统与XQJ应用框架

6.1 XQuery语言部分求值系统——XQPE

6.1.1 XQPE的系统结构

6.1.2 XQPE的对外接口

6.1.3 实验与结果分析

6.2 基于部分求值的XQJ应用框架

6.2.1 XQJ

6.2.2 基于XQuery语言部分求值的动态编译

6.2.3 XQJ应用框架

6.3 实验与结果分析

6.4 本章小结

结论

论文的主要工作

论文中的主要创新点

今后工作展望

参考文献

附 录

攻读博士期间所发表的学术论文及申请的专利

致谢