Partial Evaluation For Xquery Language

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.