【作者】 苏航；

【导师】 廖湖声；

【作者基本信息】 北京工业大学 ， 计算机应用技术， 2009， 博士

【摘要】 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应用程序的执行效率。更多还原

【Abstract】 XQuery, designed by the W3C XML Query Working Group, is a powerful functional query language for querying a broad spectrum of XML information sources. With the emergence of XML as the de facto standard for data representation and exchange on the web in recent years, the data volumes and querying complexity for XML data are growth accordingly. The partial evaluation is a program transformation technique that can be used to do optimization for programs to improve their executing performance, and it can also be used to improve the executing performance for XQuery programs, which is a way to reduce the conflict between the high executing performance requirement and the low executing performance deduced by the high complexity representation of data querying. So, XQuery partial evaluation technique is the significant research filed for the XML database technique, and it extends the research and application fields of partial evaluation technique.Our research of XQuery partial evaluation technique mainly includes 3 parts: reference-sensitivity analysis, binding-time analysis and XQuery program specialization technique.For the characteristics of XQuery language and XML data, the semantic of a node value may be lost or be changed when doing the constant-unfolding on the node in the processing of XQuery partial evaluation based on constructor-operation. So, we investigate a novel program analysis technique, called the reference-sensitivity analysis, to solve the side-effect problem. With the helping of reference-sensitivity analysis, we can own a high precision XQuery partial evaluation.Owing the introducing of reference-sensitivity analysis, only relying on static configurations and invariants in a program is not enough to do the judgment that if an expression can be specialized or not. Do not like the binding-time analysis in traditional partial evaluation, the binding-time analysis for XQuery partial evaluation should also refer to the information given by reference-sensitivity analysis to make the final correct binding-time decision for every expression.XQuery program specialization technique mainly includes: the program specializing rules and the application environment oriented specialization techniques that includes the compile-time specialization technique and run-time specialization technique. Owing the difference between XQuery on program syntax structure and the data model with other functional languages, we investigate the specialization methods for the various control structures and XML data operations in XQuery programs. And, in the application field of XQuery, the dynamically generated query is widely adopted, so we developed the run-time specialization technique on the basis of the realization of compile-time specialization. The run-time specialization finishes specializations automatically according to the invariants in XQuery programs and generates high performance programs correspondingly.Based on above researches, XQPE, a first automatic partial evaluation system for XQuery, is developed. It extends the application field for partial evaluation technique. Furthermore, the dynamic compilation technique and the XQJ application framework have also been developed. Both of these can be used in practical programming development to improve the efficiency of XQuery programs and to promote the application and development for XQuery partial evaluation technique.The primary innovative productions of this paper are shown as follows.1) It investigates the reference-sensitivity analysis. The method is used to find out and annotate the expression, whose value may lose its original semantic after being encoded in residual program. It helps us to make the judgment which expression’s result can be done constant-folding for being encoded in residual program by using constructor-operation. And this ensures the computing of expressions, which are static and not related to reverse-axis, can be finished in the phase of partial evaluation. Moreover, the binding-time analysis also is extended that it does not only annotate expressions’ binding-time analysis states according to the static information, e.g. the static invariants, but also accords to the results given by reference-sensitivity analysis. These methods increase the precision binding-time analysis and extend the scope of partial evaluation used in XQuery program.2) It investigates a specializing method for XQuery program, and extends specializing method for the traditional functional language; it gives the specializing method for FLWOR expression, for XML data model and for XQuery syntax structure; it uses 4 function-specializing modes to control the specializing for every function-call; and it provides two specializing way, the compile-time specializing and the run-time specializing, to extends field of application for XQuery partial evaluation technique.3) A first automatic partial evaluation system for XQuery, called XQPE, is developed, it supports both the compile-time specialization and the run-time specialization for XQuery programs, and this system extends the fields of application for partial evaluation technique. 4) A dynamically compilation mechanism based on run-time specialization of XQuery partial evaluation is developed, and it is used in the realization of XQJ interface. This mechanism can availably improve the executing efficiency of XQJ interface.更多还原