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应用程序的执行效率。
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.
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应用程序的执行效率。
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.
引文
1 T. Bray, J. Paoli, C. M. Sperberg-McQueen, et al. Extensible Markup Language (XML) 1.0, 2006
2 G. Feinberg. Native XML database storage and retrieval. Linux Journal. 2005, (137):7
3 H. V. Jagadish, S. Al-Khalifa, A. Chapman, et al. TIMBER: A native XML database. The VLDB Journal. 2002, 11(4): 274~291
4 A. M. Weiner, C. Mathis and T. Horder. Rules for query rewrite in native XML databases. In Proceedings of the 2008 EDBT Workshop on Database Technologies for Handling XML information on the Web, Nantes, France, 2008, DataX '08, (261): 21~26
5 K. Win, W. Ng and E. Lim. An Architectural Framework for Native XML Data Management. In Proceedings of the 2003 international Conference on Cyberworlds, Washington, DC, USA. IEEE Computer Society, 2003: 302
6 N. Zhang. Query Processing and Optimization in Native Xml Databases. Doctoral Thesis. University of Waterloo. 2006:20~31
7 S. Boag, D. Chamberlin, M. Fernandez, et al. XQuery 1.0: An XML Query Language. http://www.w3.org/TR/xquery, 2008
8 PLAN-X 2006, http://palnx2006.ens.fr
9 PLAN-X 2007, http://www.plan-x-2007.org
10 XIME-P 2006, http://www.ximep-2006.org
11 XIME-P 2007, http://research.yahoo.com/workshops/ximep-2007
12 G. Buratti, D. Montesi. A data model and an algebra for querying XML documents. The 17th International Conference on Database and Expert Systems Applications, Krakow, 2006,Washomgtpm, DC, USA, IEEE Computer Society: 482-486
13 S. Wang, E. A. Rundensteiner and M. Mani, Optimization of Nested XQuery Expressions with Orderby Clauses. 2nd International Workshop on XML Schema and Data Management, 2005
14孟小峰,罗道峰,蒋瑜,王宇,OreintXA:一种有效的XQuery查询代数,软件学报,2004,15(11):1648~1660
15 H. V. Jagadish, L. V. S. Lakshmanan. TAX: A tree algebra for XML. Internationl Workshop on Data Bases and Programming Languages (DBPL), Rome, 2002, 2397:148~164
16 N. May, S. Helmer, G. Moerkotte. Nested queries and quantifiers in an ordered context. In Proceedings of the 20th International Conference on Data Engineering, 2004:239~250
17 X. Li, G. Agrawal, Parallelizing XQuery In a Cluster Environment, In Proceeding of the 10th International Database Engineering and Applications Symposium, Delhi, 2006, 291~294
18 P. Bothner, Compiling XQuery to Java bytecodes, XIME-P 2004
19拜朝峰,林琳,黄林鹏等.部分计值综述.计算机科学, 2004, 31(4): 163-165
20 N. D. Jones, C. K. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. International Series in Computer Science, Prentice Hall International, 1993
21 L. Beckman, A. Haraldson, O. Oskarson, et al. A Partial Evaluator and its Use as a Programming Tool. Artificial Intelligence Journal, 1976, 7:319-357
22 Y. Futamura. Partial evalution of computer process--An approach to a compiler-compiler. Higher Order Symbol Computer, 1999, 12(4):381~391
23 A. Haraldsson. A partial evaluator and its use for compiling iterative statements in LISP. In Proceedings of the 5th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, Tucson. POPL '78. ACM, New York, 195~202
24 A. Haraldsson. A Program Manipulation System Based On Partial Evaluation, Informatics Laboratory, Linkoeping University, Ph.D. Thesis, 1977
25 N. D. Jones, P. Sestoft and H. Sondergaard. An experiment in partial evaluation: The generation of a compiler generator. In Rewriting Thechniques and Applications. Springer-Verlag, LNCS,1985, 202:124~140
26 N. D.Jones, P. Sestoft and H.Sondergaard. Mix: A self-applicable partial evaluator for experiments in compiler generation. Lisp and Symbolic Computation, 1988, 1(3/4):9~50
27 C. Consel, J. L. Lawall and A. L. Meur. A tour of tempo: A program specializer for the C language. Research Report, LaBRI, April 2003: 1299~1303
28 U. P. Schultz, J. L. Lawall and C Consel. Automatic program specialization for Java. ACM Trans. Program. Language Systems, ACM Press, 2003, 25(4):452~499
29 D. McNamee, J. Walpole, C. Pu, et al. Specialization tools and techniques for systematic optimization of system software. ACM Transactions on Computer Systems, 2001, 19(2):217~251
30侯忆铭,孙永强. Java字节代码程序的部分计值,上海交通大学学报, 2002, 36(9):1301~1303
31李渊洁,侯忆铭,孙永强.类JVML在线部分计值器的正确性证明,上海交通大学学报, 2002, 36(9):1298~1300
32李航,宋立彤,金成植. LISP语言的增量式部分求值器.软件学报,1996, 7(8):492~498
33陆卫东,金成植.高阶函数式语言的部分求值器.软件学报, 1996, 7(11):634~640
34宋立彤,金成植.函数式语言的部分求值技术.软件学报,1996,7(5): 306~313
35廖湖声,童兆丰,王众.面向对象程序设计语言的绑定时间分析技术.软件学报, 2003, 14(3):415~421
36高红雨,廖湖声,王众.一个基于部分求值的Java动态优化系统.计算机科学. 2003, 30(11):145~147
37吴晶,廖湖声.实现函数式语言部分求值器的约束时间分析,计算机工程与科学, 1997, 19(1):48~52
38 A. Novoselsky. Partial Evaluation of XML Queries for Program Analysis. United States, US 2007/0294678 A1. 2007
39 M. Fernandez, A. Malhotra, J. Marsh, et al. XQuery 1.0 and XPath 2.0 Data Model (XDM). http://www.w3.org/TR/xpath- datamodel, 2007
40 H. Katz. An introduction to XQuery: A look at the W3C’s proposed standard for an XML query language. September, http://www-900.ibm.com/developerworks/ cn/xml/x-xquery/. 2003
41 D. Draper, P. Fankhauser, M. Fernandez, et al. XQuery 1.0 and XPath 2.0 Formal Semantics. http://www.w3.org/TR/xquery-semantics/, 2007
42 M. Fernandez, J. Simeon, D. Suciu, P. Wadler. A data model and algebra for XML query. http://www.cs.bell-labs.com/wadler/topics/xml.html# algebra, 1999
43 C. Consel and O. Danvy. Partial evaluation: Principles and perspectives. In Proceedings of the ACM-SIGPLAN Symposium on Principles of Programming Languages, Charleston, ACM, 1993:493~501
44 S.Kleene. Introduction to Metamathematics. D.van Nostrand, Princeton, New Jersey, 1952
45 K. Godel. Uber formal unentscheidbare Sotze der Principia Mathematica und verwandter Systeme, I. Monatshefte for Mathematik und Physik, 1931, 38:173~198
46 A. P. Ershov, Mix computation in the class of recursive program schemata’, Acta Cybernetica, 1978, 4(1):19~23
47 A. P. Ershov, Mixed computation: Potential applications and problemsfor study, Theoretical Computer Science, 1982, 18:41~67
48 A.P.Ershov, On the partial computation principle, Information Processing Letters,1977, 6(2):38~41
49 D.Bjorner, N.D. Jones, A.P.Ershov, et al. Partial Evaluation and Mixed Computation. Proceedings of the IFIP Tc2 Workshop, Gammel Avernaes, Denmark, 1987. Elseier Science, 1987, 167~185
50 C. K. Gomard, A self-applicable partial evaluator for the lambda calculus: Correctness and pragmatics, ACM Transactions on Programming Languages and Systems, 1992, 14(2):147~172
51 J.Hannan and D.Miller, From operational semantics to abstract machines, In 1990 ACM Conference on Lisp and Functional Programming, Nice, 1990. New York, ACM, 1990: 323-332
52 L. Paulson, Compiler generation from denotational semantics, in B.Lorho(ed.), Methods and Tools for Compiler Construction, Cambridge University Press, 1984, 219-250
53 E. Ruf and D. Weise, Opportunities for Online Partial Evaluation, Computer Systems Laboratory, Stanford University, Technical Report CSL-TR-92-516, 1992
54 RUF. Topics in online partial evaluation. Stanford Univ., California, Technical Report CSL-TR-93-563, 1993
55 S. Thibault and C. Consel. A framework of application generator design. In Proceedings of the Symposium on Software Reusability, Boston, 1997. Software Engineering Notes, 1997, 22(3):131~135
56 J. Palsberg, M. I. Schwartzbach. Binding-time analysis: Abstract interpretation versus type inference, In Proceeding of the Fifth IEEE International Conference on Computer Languages, Toulouse, 1994. IEEE Computer Society Press, 1994:289-298
57 C. Consel. Polyvariant binding-time analysis for applicative languages. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-BasedProgram Manipulation, Copenhagen, 1993. New York, ACM, 1993:66-77
58 K. Davis. Higher-order binding-time analysis. In Proceedings of the 1993 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, Copenhagen, 1993. New York, ACM, 1993:78-87
59 S. Hunt, D. Sands. Binding time analysis: a new PERspective. SIGPLAN Note, 1991, 26(9):154-165
60 C. Consel and O. Danvy. Partial evaluation: Principles and perspectives. In Proceedings of the ACM-SIGPLAN Symposium on Principles of Programming Languages, Charleston, 1993. New York, ACM, 1993:493~501
61 L. Hornof, J. Noye. Accurate binding-time analysis for imperative languages: Flow, context, and return sensitivity. In Proceedings of the 1997 ACM SIGPLAN Symposium on Patial Evaluation and Semantics-Based Program Manipulation, Amsterdam, 1997. New York, ACM, 1997:63~73
62 C. Consel, L. Hornof, F. Noel, et al. A uniform approach for compile-time and run-time specialization. Lecture Notices in Computer Sciences, 1996, 1110:54~72
63 T. B. Knoblock, E. Ruf. Data specialization. In Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, 1996. New York, ACM, 1996:215~225
64 V. Turchin. The concept of a supercompiler. ACM Transactions on Programming Language and Systems, 1986, 8(3):292-35
65 E. N. Volanschi, C. Counsel, G. Muller, et al. Declarative specialization of object-oriented programs. SIGPLAN Notes, 1997, 32(10):286-300
66 U. P. Schultz and J. L. Lawall, C. Consel, et al. Towards Automatic Specialization of Java Programs. Lecture Notes In Computer Science, 1999, 1628:367-390
67 B. Moura. Bridging the Gap between Functional and Imperative Languages. PhD thesis, University of Rennes I, 1997
68 O. Agesen. Concrete type inference: delivering object-oriented applications. Ph.D thesis, Stanford University, 1996
69 O. Agesen and U. Hlzle. Type Feedback vs. Concrete Type Analysis: A Comparison of Optimization Techniques for Object-Oriented Languages. Technical Report TRCS
95-04, Computer Science Department, University of California, Santa Barbara, March 1995
70 T. Wang and S.Smith. Precise constraint-based type inference for Java. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP’01), 2001, 2072:99~117
71苏航,廖湖声, XQuery语言的部分求值技术的研究,计算机工程与科学, 2006, 28(A2):160~162
72 D.Peterson, S. Gao, A. Malhotra, et al. W3C XML Schema Definition Language (XSD) 1.1Part2: Datatypes. http://www.w3.org/TR/xmlschema 11-2 /, 2008
73 Query Test Suite http://www.w3.org/XML/Query/test-suite/, 2008
74 L. Hornof, J. Noy'e, and C. Consel. Effective specialization of realistic programs via use sensitivity. In: Proceedings of the Fourth International Symposium on Static Analysis, SAS'97, Lecture Notes in Computer Science, Paris, France, 1997, 1302:293~314
75 R. Davies. A temporal-logic approach to binding-time analysis. In Symposium on Logic in Computer Science, New Brunswick, 1996. Washington, DC, USA, IEEE Computer Society Press, 1996:184-195
76 H.S. Liao, Z.F. Tong, Z. Wang. A technology of binding time analysis for object-oriented programming languages. Journal of Software, 2003, 14(3):415~421
77 A. J. Glenstrup, N. D. Jones: Termination analysis and specialization-point insertion in offline partial evaluation. ACM Transction. Programming. Language Systems, 2005, 27(6): 1147~1215
78 J. Brauburger, J. Giesl. Termination analysis for partial functions. Lecture Notices on Computer Sciences, 1996, 1145:113~127
79 Y. Futamura, Z. Konishi, R. Glück. WSDFU: program transformation system based on generalized partial computation, The essence of computation: complexity, analysis, transformation, 2002:258~378
80 P. Sestoft. The structure of a self-applicable partial evaluator. Lecture Notices in Computer Sciences, 1986, 217:236~256
81 M. Sperber. Self-Applicable Online Partial Evaluation, Lecture Notices in Computer Sciences,1996, 1110:465~480
82 K. Asai. 2002. Binding-time analysis for both static and dynamic expressions. New Generation Computing. 2002, 20(1):27~51
83 K. Malmkjar. Program and data specialization: Principles, applications, and self-application. Master's thesis, DIKU, Computer Science Department, University of Copenhagen, August 1989
84 R. Glück and N. D. Jones. Automatic program specialization by partial evaluation: an introduction. Software Engineering in Scientific Computing. 1996:70~77
85崔敏惠,戴桂兰,王生原,张素琴,动态编译技术研究,计算机科学2004, 31(7):113~117
86 H. Masuhara, Y. Sugita, A. Yonezawa. Dynamic Compilation of a Reflective Language Using Run-Time Specialization. Principles of Software Evolution, 2000: 128~137
87 H. Masuhara, A. Yonezawa. Run-time Bytecode Specialization: A Portable Approach to Generating Optimized Specialized Code. Lecture Notices in Computer Sciences, 2001, 2053:138~154
88 F. Noel, L. Hornof, C. Consel, et al. Automatic, Template-Based Run-Time Specialization Implementation and Experimental Study. In Proceedings of the 1998 international Conference on Computer Languages, Chicago, 1998. Washington, DC,IEEE Computer Society, 1998:132~142
89 U. P. Schultz. Partial evaluation for class-based object-oriented languages. Lecture Notes in Computer Science, 2001, 2053:173--197
90 U. Schultz, J. Lawall, C. Consel, and G. Muller. Specialization patterns. In Proceedings of the 15 th IEEE International Conference on Automated Software Engineering, Grenoble, France, 2000. Washington, DC, IEEE Computer Society, 2000:197~206
91 J. Carette, M. Kucera. Partial evaluation of Maple. In Proceedings of the 2007 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, New York, 2007. New York, ACM, 2007:41~50
92 C. Consel. A Tour of Schism: A Partial Evaluation System for Higher-Order Applicative Language. In Proceedings of the 1993 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, New York, 1993. New York, ACM, 1993:145~154
93 M. Leuschel, S. Craig, M. Bruynooghe et al. Specializing Interpreters using Offline Partial Deduction. Lecture Notices in Computer Sciences, 2004, 3049:341~376
94 Hang Su, Husheng Liao. XQPE: A Partial Evaluation System for XQuery, In: 32nd Annual IEEE International Computer Software andApplications Conference, Turku, Finland, 2008. Washington, DC, IEEE Computer Society, 2008:347~354
95 Jan-Eike Michels. XQuery API for Java(TM) (XQJ) 1.0 Specification. http://jcp.org/en/jsr/detail?id=225, 2007
96 J Auslander, M. Philipose, C. Chambers, et al. Fast, Effective Dynamic Compilation. ACM SIGPLAN Notices, 1996, 31(5):149-159
97 B. Grant, M. Mock, M. Philipose, et al. DyC:An Expressive Annotation-Directed Dynamic Compiler for C. Theoretical Computer Science, 2000, 248:1~2
98 C. Krintz.Coupling On-Line and Off-Line Profile Information to Improve Program Performance.ACM International Conference Proceeding Series, 2003, 37:69~78
99 Michal C, etal. Practicing JUDO:Java Under Dynamic Optimizations. ACM International Conference Proceeding Series, 2000, 37:69~78 13~26
100 M. Mock, C. Chambers, S. J. Eggers. Calpa: a tool for automating selective dynamic compilation. In Proceedings of the 33rd Annual ACM/IEEE international Symposium on Microarchitecture, Monterey, 2000. New York, ACM press, 2000:291~302
2 G. Feinberg. Native XML database storage and retrieval. Linux Journal. 2005, (137):7
3 H. V. Jagadish, S. Al-Khalifa, A. Chapman, et al. TIMBER: A native XML database. The VLDB Journal. 2002, 11(4): 274~291
4 A. M. Weiner, C. Mathis and T. Horder. Rules for query rewrite in native XML databases. In Proceedings of the 2008 EDBT Workshop on Database Technologies for Handling XML information on the Web, Nantes, France, 2008, DataX '08, (261): 21~26
5 K. Win, W. Ng and E. Lim. An Architectural Framework for Native XML Data Management. In Proceedings of the 2003 international Conference on Cyberworlds, Washington, DC, USA. IEEE Computer Society, 2003: 302
6 N. Zhang. Query Processing and Optimization in Native Xml Databases. Doctoral Thesis. University of Waterloo. 2006:20~31
7 S. Boag, D. Chamberlin, M. Fernandez, et al. XQuery 1.0: An XML Query Language. http://www.w3.org/TR/xquery, 2008
8 PLAN-X 2006, http://palnx2006.ens.fr
9 PLAN-X 2007, http://www.plan-x-2007.org
10 XIME-P 2006, http://www.ximep-2006.org
11 XIME-P 2007, http://research.yahoo.com/workshops/ximep-2007
12 G. Buratti, D. Montesi. A data model and an algebra for querying XML documents. The 17th International Conference on Database and Expert Systems Applications, Krakow, 2006,Washomgtpm, DC, USA, IEEE Computer Society: 482-486
13 S. Wang, E. A. Rundensteiner and M. Mani, Optimization of Nested XQuery Expressions with Orderby Clauses. 2nd International Workshop on XML Schema and Data Management, 2005
14孟小峰,罗道峰,蒋瑜,王宇,OreintXA:一种有效的XQuery查询代数,软件学报,2004,15(11):1648~1660
15 H. V. Jagadish, L. V. S. Lakshmanan. TAX: A tree algebra for XML. Internationl Workshop on Data Bases and Programming Languages (DBPL), Rome, 2002, 2397:148~164
16 N. May, S. Helmer, G. Moerkotte. Nested queries and quantifiers in an ordered context. In Proceedings of the 20th International Conference on Data Engineering, 2004:239~250
17 X. Li, G. Agrawal, Parallelizing XQuery In a Cluster Environment, In Proceeding of the 10th International Database Engineering and Applications Symposium, Delhi, 2006, 291~294
18 P. Bothner, Compiling XQuery to Java bytecodes, XIME-P 2004
19拜朝峰,林琳,黄林鹏等.部分计值综述.计算机科学, 2004, 31(4): 163-165
20 N. D. Jones, C. K. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. International Series in Computer Science, Prentice Hall International, 1993
21 L. Beckman, A. Haraldson, O. Oskarson, et al. A Partial Evaluator and its Use as a Programming Tool. Artificial Intelligence Journal, 1976, 7:319-357
22 Y. Futamura. Partial evalution of computer process--An approach to a compiler-compiler. Higher Order Symbol Computer, 1999, 12(4):381~391
23 A. Haraldsson. A partial evaluator and its use for compiling iterative statements in LISP. In Proceedings of the 5th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, Tucson. POPL '78. ACM, New York, 195~202
24 A. Haraldsson. A Program Manipulation System Based On Partial Evaluation, Informatics Laboratory, Linkoeping University, Ph.D. Thesis, 1977
25 N. D. Jones, P. Sestoft and H. Sondergaard. An experiment in partial evaluation: The generation of a compiler generator. In Rewriting Thechniques and Applications. Springer-Verlag, LNCS,1985, 202:124~140
26 N. D.Jones, P. Sestoft and H.Sondergaard. Mix: A self-applicable partial evaluator for experiments in compiler generation. Lisp and Symbolic Computation, 1988, 1(3/4):9~50
27 C. Consel, J. L. Lawall and A. L. Meur. A tour of tempo: A program specializer for the C language. Research Report, LaBRI, April 2003: 1299~1303
28 U. P. Schultz, J. L. Lawall and C Consel. Automatic program specialization for Java. ACM Trans. Program. Language Systems, ACM Press, 2003, 25(4):452~499
29 D. McNamee, J. Walpole, C. Pu, et al. Specialization tools and techniques for systematic optimization of system software. ACM Transactions on Computer Systems, 2001, 19(2):217~251
30侯忆铭,孙永强. Java字节代码程序的部分计值,上海交通大学学报, 2002, 36(9):1301~1303
31李渊洁,侯忆铭,孙永强.类JVML在线部分计值器的正确性证明,上海交通大学学报, 2002, 36(9):1298~1300
32李航,宋立彤,金成植. LISP语言的增量式部分求值器.软件学报,1996, 7(8):492~498
33陆卫东,金成植.高阶函数式语言的部分求值器.软件学报, 1996, 7(11):634~640
34宋立彤,金成植.函数式语言的部分求值技术.软件学报,1996,7(5): 306~313
35廖湖声,童兆丰,王众.面向对象程序设计语言的绑定时间分析技术.软件学报, 2003, 14(3):415~421
36高红雨,廖湖声,王众.一个基于部分求值的Java动态优化系统.计算机科学. 2003, 30(11):145~147
37吴晶,廖湖声.实现函数式语言部分求值器的约束时间分析,计算机工程与科学, 1997, 19(1):48~52
38 A. Novoselsky. Partial Evaluation of XML Queries for Program Analysis. United States, US 2007/0294678 A1. 2007
39 M. Fernandez, A. Malhotra, J. Marsh, et al. XQuery 1.0 and XPath 2.0 Data Model (XDM). http://www.w3.org/TR/xpath- datamodel, 2007
40 H. Katz. An introduction to XQuery: A look at the W3C’s proposed standard for an XML query language. September, http://www-900.ibm.com/developerworks/ cn/xml/x-xquery/. 2003
41 D. Draper, P. Fankhauser, M. Fernandez, et al. XQuery 1.0 and XPath 2.0 Formal Semantics. http://www.w3.org/TR/xquery-semantics/, 2007
42 M. Fernandez, J. Simeon, D. Suciu, P. Wadler. A data model and algebra for XML query. http://www.cs.bell-labs.com/wadler/topics/xml.html# algebra, 1999
43 C. Consel and O. Danvy. Partial evaluation: Principles and perspectives. In Proceedings of the ACM-SIGPLAN Symposium on Principles of Programming Languages, Charleston, ACM, 1993:493~501
44 S.Kleene. Introduction to Metamathematics. D.van Nostrand, Princeton, New Jersey, 1952
45 K. Godel. Uber formal unentscheidbare Sotze der Principia Mathematica und verwandter Systeme, I. Monatshefte for Mathematik und Physik, 1931, 38:173~198
46 A. P. Ershov, Mix computation in the class of recursive program schemata’, Acta Cybernetica, 1978, 4(1):19~23
47 A. P. Ershov, Mixed computation: Potential applications and problemsfor study, Theoretical Computer Science, 1982, 18:41~67
48 A.P.Ershov, On the partial computation principle, Information Processing Letters,1977, 6(2):38~41
49 D.Bjorner, N.D. Jones, A.P.Ershov, et al. Partial Evaluation and Mixed Computation. Proceedings of the IFIP Tc2 Workshop, Gammel Avernaes, Denmark, 1987. Elseier Science, 1987, 167~185
50 C. K. Gomard, A self-applicable partial evaluator for the lambda calculus: Correctness and pragmatics, ACM Transactions on Programming Languages and Systems, 1992, 14(2):147~172
51 J.Hannan and D.Miller, From operational semantics to abstract machines, In 1990 ACM Conference on Lisp and Functional Programming, Nice, 1990. New York, ACM, 1990: 323-332
52 L. Paulson, Compiler generation from denotational semantics, in B.Lorho(ed.), Methods and Tools for Compiler Construction, Cambridge University Press, 1984, 219-250
53 E. Ruf and D. Weise, Opportunities for Online Partial Evaluation, Computer Systems Laboratory, Stanford University, Technical Report CSL-TR-92-516, 1992
54 RUF. Topics in online partial evaluation. Stanford Univ., California, Technical Report CSL-TR-93-563, 1993
55 S. Thibault and C. Consel. A framework of application generator design. In Proceedings of the Symposium on Software Reusability, Boston, 1997. Software Engineering Notes, 1997, 22(3):131~135
56 J. Palsberg, M. I. Schwartzbach. Binding-time analysis: Abstract interpretation versus type inference, In Proceeding of the Fifth IEEE International Conference on Computer Languages, Toulouse, 1994. IEEE Computer Society Press, 1994:289-298
57 C. Consel. Polyvariant binding-time analysis for applicative languages. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-BasedProgram Manipulation, Copenhagen, 1993. New York, ACM, 1993:66-77
58 K. Davis. Higher-order binding-time analysis. In Proceedings of the 1993 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, Copenhagen, 1993. New York, ACM, 1993:78-87
59 S. Hunt, D. Sands. Binding time analysis: a new PERspective. SIGPLAN Note, 1991, 26(9):154-165
60 C. Consel and O. Danvy. Partial evaluation: Principles and perspectives. In Proceedings of the ACM-SIGPLAN Symposium on Principles of Programming Languages, Charleston, 1993. New York, ACM, 1993:493~501
61 L. Hornof, J. Noye. Accurate binding-time analysis for imperative languages: Flow, context, and return sensitivity. In Proceedings of the 1997 ACM SIGPLAN Symposium on Patial Evaluation and Semantics-Based Program Manipulation, Amsterdam, 1997. New York, ACM, 1997:63~73
62 C. Consel, L. Hornof, F. Noel, et al. A uniform approach for compile-time and run-time specialization. Lecture Notices in Computer Sciences, 1996, 1110:54~72
63 T. B. Knoblock, E. Ruf. Data specialization. In Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, 1996. New York, ACM, 1996:215~225
64 V. Turchin. The concept of a supercompiler. ACM Transactions on Programming Language and Systems, 1986, 8(3):292-35
65 E. N. Volanschi, C. Counsel, G. Muller, et al. Declarative specialization of object-oriented programs. SIGPLAN Notes, 1997, 32(10):286-300
66 U. P. Schultz and J. L. Lawall, C. Consel, et al. Towards Automatic Specialization of Java Programs. Lecture Notes In Computer Science, 1999, 1628:367-390
67 B. Moura. Bridging the Gap between Functional and Imperative Languages. PhD thesis, University of Rennes I, 1997
68 O. Agesen. Concrete type inference: delivering object-oriented applications. Ph.D thesis, Stanford University, 1996
69 O. Agesen and U. Hlzle. Type Feedback vs. Concrete Type Analysis: A Comparison of Optimization Techniques for Object-Oriented Languages. Technical Report TRCS
95-04, Computer Science Department, University of California, Santa Barbara, March 1995
70 T. Wang and S.Smith. Precise constraint-based type inference for Java. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP’01), 2001, 2072:99~117
71苏航,廖湖声, XQuery语言的部分求值技术的研究,计算机工程与科学, 2006, 28(A2):160~162
72 D.Peterson, S. Gao, A. Malhotra, et al. W3C XML Schema Definition Language (XSD) 1.1Part2: Datatypes. http://www.w3.org/TR/xmlschema 11-2 /, 2008
73 Query Test Suite http://www.w3.org/XML/Query/test-suite/, 2008
74 L. Hornof, J. Noy'e, and C. Consel. Effective specialization of realistic programs via use sensitivity. In: Proceedings of the Fourth International Symposium on Static Analysis, SAS'97, Lecture Notes in Computer Science, Paris, France, 1997, 1302:293~314
75 R. Davies. A temporal-logic approach to binding-time analysis. In Symposium on Logic in Computer Science, New Brunswick, 1996. Washington, DC, USA, IEEE Computer Society Press, 1996:184-195
76 H.S. Liao, Z.F. Tong, Z. Wang. A technology of binding time analysis for object-oriented programming languages. Journal of Software, 2003, 14(3):415~421
77 A. J. Glenstrup, N. D. Jones: Termination analysis and specialization-point insertion in offline partial evaluation. ACM Transction. Programming. Language Systems, 2005, 27(6): 1147~1215
78 J. Brauburger, J. Giesl. Termination analysis for partial functions. Lecture Notices on Computer Sciences, 1996, 1145:113~127
79 Y. Futamura, Z. Konishi, R. Glück. WSDFU: program transformation system based on generalized partial computation, The essence of computation: complexity, analysis, transformation, 2002:258~378
80 P. Sestoft. The structure of a self-applicable partial evaluator. Lecture Notices in Computer Sciences, 1986, 217:236~256
81 M. Sperber. Self-Applicable Online Partial Evaluation, Lecture Notices in Computer Sciences,1996, 1110:465~480
82 K. Asai. 2002. Binding-time analysis for both static and dynamic expressions. New Generation Computing. 2002, 20(1):27~51
83 K. Malmkjar. Program and data specialization: Principles, applications, and self-application. Master's thesis, DIKU, Computer Science Department, University of Copenhagen, August 1989
84 R. Glück and N. D. Jones. Automatic program specialization by partial evaluation: an introduction. Software Engineering in Scientific Computing. 1996:70~77
85崔敏惠,戴桂兰,王生原,张素琴,动态编译技术研究,计算机科学2004, 31(7):113~117
86 H. Masuhara, Y. Sugita, A. Yonezawa. Dynamic Compilation of a Reflective Language Using Run-Time Specialization. Principles of Software Evolution, 2000: 128~137
87 H. Masuhara, A. Yonezawa. Run-time Bytecode Specialization: A Portable Approach to Generating Optimized Specialized Code. Lecture Notices in Computer Sciences, 2001, 2053:138~154
88 F. Noel, L. Hornof, C. Consel, et al. Automatic, Template-Based Run-Time Specialization Implementation and Experimental Study. In Proceedings of the 1998 international Conference on Computer Languages, Chicago, 1998. Washington, DC,IEEE Computer Society, 1998:132~142
89 U. P. Schultz. Partial evaluation for class-based object-oriented languages. Lecture Notes in Computer Science, 2001, 2053:173--197
90 U. Schultz, J. Lawall, C. Consel, and G. Muller. Specialization patterns. In Proceedings of the 15 th IEEE International Conference on Automated Software Engineering, Grenoble, France, 2000. Washington, DC, IEEE Computer Society, 2000:197~206
91 J. Carette, M. Kucera. Partial evaluation of Maple. In Proceedings of the 2007 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, New York, 2007. New York, ACM, 2007:41~50
92 C. Consel. A Tour of Schism: A Partial Evaluation System for Higher-Order Applicative Language. In Proceedings of the 1993 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, New York, 1993. New York, ACM, 1993:145~154
93 M. Leuschel, S. Craig, M. Bruynooghe et al. Specializing Interpreters using Offline Partial Deduction. Lecture Notices in Computer Sciences, 2004, 3049:341~376
94 Hang Su, Husheng Liao. XQPE: A Partial Evaluation System for XQuery, In: 32nd Annual IEEE International Computer Software andApplications Conference, Turku, Finland, 2008. Washington, DC, IEEE Computer Society, 2008:347~354
95 Jan-Eike Michels. XQuery API for Java(TM) (XQJ) 1.0 Specification. http://jcp.org/en/jsr/detail?id=225, 2007
96 J Auslander, M. Philipose, C. Chambers, et al. Fast, Effective Dynamic Compilation. ACM SIGPLAN Notices, 1996, 31(5):149-159
97 B. Grant, M. Mock, M. Philipose, et al. DyC:An Expressive Annotation-Directed Dynamic Compiler for C. Theoretical Computer Science, 2000, 248:1~2
98 C. Krintz.Coupling On-Line and Off-Line Profile Information to Improve Program Performance.ACM International Conference Proceeding Series, 2003, 37:69~78
99 Michal C, etal. Practicing JUDO:Java Under Dynamic Optimizations. ACM International Conference Proceeding Series, 2000, 37:69~78 13~26
100 M. Mock, C. Chambers, S. J. Eggers. Calpa: a tool for automating selective dynamic compilation. In Proceedings of the 33rd Annual ACM/IEEE international Symposium on Microarchitecture, Monterey, 2000. New York, ACM press, 2000:291~302