（计算机应用技术专业论文）xquery语言的部分求值技术.pdf

摘璎 摘要 x q u e r y 是w 3 c 组织提出的一种功能强大的x m l 数据查询语言。随着x m l 数据的广泛应用，x m l 日益成为i n t e r n e t 上数据交换的标准化的数据存储格式， 导致x m l 格式数据的数据量和查询计算复杂性的增加，提高x q u e r y 语言的查 询效率的需求日益迫切，而部分求值技术是用于提高程序运行效率的一种程序变 换技术，对x q u e r y 查询程序进行部分求值处理能够有助于提高该程序的运行效 率，缓解x m l 数据查询处理日益复杂与提高性能要求之间的矛盾。因此，研究 针对于x q u e r y 查询语言的部分求值技术不仅扩大了部分求值技术的应用领域， 对于x m l 数据库技术、x q u e r y 语言查询技术的发展在程序理论和实际应用上 都有着重要的意义。 x q u e r y 语言部分求值技术的研究主要包括引用敏感性分析、绑定时间分析 和程序例化技术等三个方面。 在x q u e r y 程序部分求值过程中，由于x q u e r y 的语言特征和处理对象x m l 数据的特殊性，基于节点重构的x q u e r y 语言部分求值方法在进行x m l 数据的 常量折叠时会带来语义丢失，为此本文提出了一种新颖的程序分析技术引用 敏感性分析。通过使用引用敏感性分析，使得x q u e r y 语言部分求值中能够有效 地避免因对这种常量折叠所带来的副作用，保证了x q u e r y 语言部分求值的精度。 由于引用敏感性分析的引入，使得要判断出一个表达式是否能够被例化或滞 留就不能够仅仅凭借静态参数的指定信息和程序本身的静态不变量，还必须参考 引用敏感性分析提供的相关信息。因此，与传统的部分求值不同，需要在x q u e r y 语言部分求值中的绑定时间分析中参考引用敏感性分析的结果来重新确认其最 终的绑定时间状态以保证其能够在例化阶段中进行正确的处理。 x q u e r y 程序例化技术的研究主要包括程序例化实现方法的研究以及面向不 同应用环境的编译时刻例化和运行时刻例化两种例化方式的研究。针对x q u e r y 语言不同于一般函数式语言的语言结构和数据模型，研究了各种控制结构和 x m l 操作的程序例化方法。同时，考虑到x q u e r y 语言应用中，普遍采用动态 生成数据查询命令的特点，在实现了编译时刻程序例化的基础上，发展了运行时 刻程序例化技术，使得使用者有可能依据程序执行中不变量进行程序自动例化， 产生高性能的查询程序。 基于上述的研究，作者实现了针对x q u e r y 语言的部分求值系统x q p e 。 x q p e 系统是目前第一个针对于x q u e r y 程序的自动化部分求值系统，扩展了部 分求值技术的应用领域。此外，本文研究了相应的x q u e r y 部分求值技术的应用 技术，包括有：基于x q u e r y 语言部分求值的动态编译技术和x q j 应用框架。这 北京t 业人学t 学博十学位论文 使得x q u e r y 语言部分求值技术能够直接应用于实用的编程环境中，提高x q u e r y 程序的执行效率，并且对x q u e r y 语言部分求值技术的应用与发展也有推动作用。 本文的主要创新性成果如下： 1 )提出了一种引用敏感性分析，用于发现和标记可能导致语义丢失的表达 式，从而正确地判断出针对哪些表达式的计算结果可以采用x m l 文档重构的常 量折叠方法，从而保证基于已知信息的、不涉及反向轴等特定运算的表达式计算 都可以在部分求值阶段完成；进而扩展了传统上的绑定时间分析，使其不仅根据 程序不变量等其它静态信息来标记表达式，而且参考引用敏感分析的结果来最终 确定表达式的绑定时间状态，从而提高绑定时间分析的精度，扩大程序中部分求 值的范围。 2 1 提出了一种x q u e r y 语言的程序例化方法，扩展了传统的函数式语言程 序例化方法：针对f l w o r 表达式、x m l 文档对象模型和x q u e r y 数据模型等语 言结构，提供专用的程序例化策略；采用4 种函数例化模式来控制各个函数调用 表达式的例化方式；并且针对不用应用需求设计了两种例化方式：编译时刻例化 和运行时刻例化，扩大了x q u e r y 语言部分求值技术的应用范围。 3 1基于上述x q u e r y 语言的部分求值技术，研制了第一个支持x q u e r y 程序 自动例化的部分求值系统一一x q p e ，它支持x q u e r y 程序编译时刻例化和运行 时程序例化两种例化方式，拓展了部分求值技术的应用领域。 4 ) 面向基于x q j 接口的x q u e r y 查询程序，发展了一种新型的基于x q u e r y 语言部分求值的动态编译机制，将x q u e r y 程序运行时刻例化技术成功地运用于 x q j 接e l 的实现，有效地提高了这种基于x q j 的x q u e r y 应用程序的执行效率。 关键词x q u e r y ；程序分析和变换；部分求值；绑定时间分析；动态编译 a b s t f a c t a b s t r a c t x q u e r y , d e s i g n e db yt h ew 3 cx m lq u e r yw o r k i n gg r o u p ，i sap o w e r f u l f u n c t i o n a lq u e r yl a n g u a g ef o rq u e r y i n gab r o a ds p e c t r u mo fx m li n f o r m a t i o ns o u r c e s w i t ht h ee m e r g e n c eo fx m la st h ed ef a c t os t a n d a r df o rd a t ar e p r e s e n t a t i o na n d e x c h a n g eo nt h ew e bi nr e c e n ty e a r s ，t h ed a t av o l u m e sa n dq u e r y i n gc o m p l e x i t yf o r x m ld a t aa r eg r o w t ha c c o r d i n g l y t h ep a r t i a le v a l u a t i o ni sap r o g r a mt r a n s f o r m a t i o n t e c h n i q u et h a tc a l lb eu s e dt od oo p t i m i z a t i o nf o rp r o g r a m st oi m p r o v et h e i re x e c u t i n g p e r f o r m a n c e ，a n di tc a na l s ob eu s e dt oi m p r o v et h ee x e c u t i n gp e r f o r m a n c ef o r x q u e r yp r o g r a m s ，w h i c hi saw a y t or e d u c et h ec o n f l i c tb e t w e e nt h eh i g he x e c u t i n g p e r f o r m a n c er e q u i r e m e n ta n dt h el o we x e c u t i n gp e r f o r m a n c ed e d u c e db yt h eh i 曲 c o m p l e x i t yr e p r e s e n t a t i o no fd a t aq u e r y i n g s o ，x q u e r yp a r t i a le v a l u a t i o nt e c h n i q u e i st h es i g n i f i c a n tr e s e a r c hf i l e df o rt h ex m ld a t a b a s et e c h n i q u e ，a n di te x t e n d st h e r e s e a r c ha n da p p l i c a t i o nf i e l d so fp a r t i a le v a l u a t i o nt e c h n i q u e o u rr e s e a r c ho fx q u e r yp a r t i a le v a l u a t i o nt e c h n i q u em a i n l yi n c l u d e s3p a r t s ： r e f e r e n c e - s e n s i t i v i t y a n a l y s i s ，b i n d i n g t i m ea n a l y s i s a n d x q u e r yp r o g r a m s p e c i a l i z a t i o nt e c h n i q u e f o rt h ec h a r a c t e r i s t i c so fx q u e r yl a n g u a g ea n dx m ld a t a ，t h es e m a n t i co fan o d e v a l u em a yb el o s to rb ec h a n g e dw h e nd o i n gt h ec o n s t a n t u n f o l d i n go nt h en o d ei nt h e p r o c e s s i n go fx q u e r yp a r t i a l e v a l u a t i o nb a s e do n c o n s t r u c t o r - o p e r a t i o n s o ，w e i n v e s t i g a t e an o v e lp r o g r a m a n a l y s i st e c h n i q u e ，c a l l e d t h er e f e r e n c e s e n s i t i v i t y a n a l y s i s ，t os o l v et h es i d e - e f f e c tp r o b l e m w i t ht h eh e l p i n go fr e f e r e n c e s e n s i t i v i t y a n a l y s i s ，w ec a no w n ah i 曲p r e c i s i o nx q u e r yp a r t i a le v a l u a t i o n o w i n gt h ei n t r o d u c i n go fr e f e r e n c e s e n s i t i v i t ya n a l y s i s ，o n l yr e l y i n go ns t a t i c c o n f i g u r a t i o n sa n di n v a r i a n t si nap r o g r a mi sn o te n o u g ht od ot h ej u d g m e n tt h a ti fa n e x p r e s s i o nc a nb es p e c i a l i z e do rn o t d on o tl i k et h eb i n d i n g - t i m ea n a l y s i si n t r a d i t i o n a lp a r t i a le v a l u a t i o n ，t h eb i n d i n g t i m ea n a l y s i sf o rx q u e r yp a r t i a le v a l u a t i o n s h o u l da l s or e f e rt ot h ei n f o r m a t i o ng i v e nb yr e f e r e n c e s e n s i t i v i t ya n a l y s i st om a k e t h ef i n a lc o r r e c tb i n d i n g t i m ed e c i s i o nf o re v e r ye x p r e s s i o n x q u e r yp r o g r a ms p e c i a l i z a t i o nt e c h n i q u em a i n l y i n c l u d e s ：t h ep r o g r a m s p e c i a l i z i n gr u l e sa n dt h ea p p l i c a t i o ne n v i r o n m e n to r i e n t e ds p e c i a l i z a t i o nt e c h n i q u e s t h a ti n c l u d e st h ec o m p i l e - t i m es p e c i a l i z a t i o nt e c h n i q u ea n dr u n t i m es p e c i a l i z a t i o n t e c h n i q u e o w i n gt h ed if f e r e n c eb e t w e e nx q u e r yo np r o g r a ms y n t a xs t r u c t u r ea n d t h e d a t am o d e lw i t ho t h e rf u n c t i o n a ll a n g u a g e s ，w ei n v e s t i g a t et h es p e c i a l i z a t i o nm e t h o d s i i l 北京t 业大学t 学博十学位论文 f o rt h ev a r i o u sc o n t r o ls t r u c t u r e sa n dx m ld a t ao p e r a t i o n si nx q u e r y p r o g r a m s a n d i nt h ea p p l i c a t i o nf i e l do fx q u e r y , t h e d y n a m i c a l l yg e n e r a t e dq u e r yi sw i d e l ya d o p t e d ， s ow ed e v e l o p e dt h er u n t i m es p e c i a l i z a t i o nt e c h n i q u eo nt h eb a s i so ft h e r e a l i z a t i o n o fc o m p i l e - t i m es p e c i a l i z a t i o n t h er u n t i m es p e c i a l i z a t i o nf i n i s h e ss p e c i a l i z a t i o n s a u t o m a t i c a l l ya c c o r d i n gt ot h ei n v a r i a n t si nx q u e r yp r o g r a m sa n dg e n e r a t e sh i g h p e r f o r m a n c ep r o g r a m sc o r r e s p o n d i n g l y b a s e do na b o v er e s e a r c h e s ，x q p e ，af i r s ta u t o m a t i cp a r t i a le v a l u a t i o ns y s t e mf o r x q u e r y , i sd e v e l o p e d i te x t e n d st h ea p p l i c a t i o nf i e l df o rp a r t i a le v a l u a t i o nt e c h n i o u e f u r t h e r m o r e ，t h ed y n a m i cc o m p i l a t i o nt e c h n i q u ea n dt h ex q ja p p l i c a t i o nf r a m e w o r k h a v ea l s ob e e nd e v e l o p e d b o t ho ft h e s ec a nb eu s e di n p r a c t i c a lp r o g r a m m i n g d e v e l o p m e n tt oi m p r o v et h ee f f i c i e n c yo fx q u e r yp r o g r a m sa n dt op r o m o t et h e a p p l i c a t i o na n dd e v e l o p m e n tf o rx q u e r yp a r t i a le v a l u a t i o nt e c h n i q u e t h e p r i m a r yi n n o v a t i v ep r o d u c t i o n so ft h i sp a p e ra r es h o w na sf o l l o w s 1 ) i ti n v e s t i g a t e st h er e f e r e n c e s e n s i t i v i t ya n a l y s i s t h em e t h o di su s e dt of i n d o u ta n da n n o t a t et h ee x p r e s s i o n , w h o s ev a l u em a yl o s ei t s o r i g i n a ls e m a n t i ca f t e r b e i n ge n c o d e di nr e s i d u a lp r o g r a m i th e l p su st om a k et h ej u d g r n e n tw h i c h e x p r e s s i o n sr e s u l tc a nb ed o n ec o n s t a n t f o l d i n gf o rb e i n ge n c o d e di nr e s i d u a l p r o g r a mb yu s i n gc o n s t r u c t o r - o p e r a t i o n a n dt l l i se n s u r e st h e c o m p u t i n go f e x p r e s s i o n s ，w h i c ha r es t a t i ca n dn o tr e l a t e dt or e v e r s e a x i s ，c a nb ef i n i s h e di nt h e p h a s eo fp a r t i a le v a l u a t i o n m o r e o v e r , t h eb i n d i n g t i m ea n a l y s i sa l s oi se x t e n d e dt h a t i td o e sn o to n l ya n n o t a t ee x p r e s s i o n s b i n d i n g - t i m ea n a l y s i ss t a t e sa c c o r d i n gt ot h e s t a t i ci n f o r m a t i o n ，e g t h es t a t i ci n v a r i a n t s ，b u ta l s oa c c o r d st ot h er e s u l t sg i v e nb y r e f e r e n c e s e n s i t i v i t ya n a l y s i s t h e s em e t h o d si n c r e a s et h ep r e c i s i o nb i n d i n g t i m e a n a l y s i sa n de x t e n dt h es c o p eo f p a r t i a le v a l u a t i o nu s e di nx q u e r yp r o g r a m 。 2 ) i t i n v e s t i g a t e sas p e c i a l i z i n gm e t h o df o rx q u e r yp r o g r a m ，a n de x t e n d s s p e c i a l i z i n gm e t h o df o rt h et r a d i t i o n a lf u n c t i o n a ll a n g u a g e ；i tg i v e st h es p e c i a l i z i n g m e t h o df o rf l w o r e x p r e s s i o n ，f o rx m l d a t am o d e la n df o rx q u e r ys y n t a xs t r u c t u r e ； i tu s e s4 f u n c t i o n - s p e c i a l i z i n gm o d e st oc o n t r o lt h es p e c i a l i z i n gf o re v e r y f u n c t i o n 。c a l l ；a n di tp r o v i d e st w os p e c i a l i z i n gw a y , t h ec o m p i l e t i m es p e c i a l i z i n ga n d t h er u n - t i m es p e c i a l i z i n g ，t oe x t e n d sf i e l do f a p p l i c a t i o nf o rx q u e r yp a r t i a le v a l u a t i o n t e c h n i q u e 。 3 ) af i r s ta u t o m a t i cp a r t i a le v a l u a t i o ns y s t e mf o rx q u e r y , c a l l e dx q p e ，i s d e v e l o p e d ，i ts u p p o r t s b o t ht h ec o m p i l e t i m e s p e c i a l i z a t i o n a n dt h er u n t i m e s p e c i a l i z a t i o nf o rx q u e r yp r o g r a m s ，a n dt h i ss y s t e me x t e n d st h ef i e l d so fa p p l i c a t i o n f o rp a r t i a le v a l u a t i o nt e c h n i q u e i v a b s tr a c t 4 1a d y n a m i c a l l yc o m p i l a t i o nm e c h a n i s mb a s e do nr u n t i m es p e c i a l i z a t i o no f x q u e r yp a r t i a le v a l u a t i o ni sd e v e l o p e d ，a n di ti su s e di nt h er e a l i z a t i o no fx q j i n t e r f a c e t h i sm e c h a n i s mc a na v a i l a b l yi m p r o v et h ee x e c u t i n ge f f i c i e n c yo fx q j i n t e r f a c e k e y w o r d sx q u e r y ；p r o g r a ma n a l y s i s a n dt r a n s f o r m a t i o n ；p a r t i a l e v a l u a t i o n ； b i n d i n g t i m ea n a l y s i s ；d y n a m i cc o m p i l a t i o n v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：堇丝日期：塑z ：! ：! f 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：导师签名：日期：) 叼，5 - ；1 第1 审绪论 拿。 一m 1 ：i 皇皇曼曼曼曼皇曼 1 1 课题背景 第1 章绪论 x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 【1 | ，即可扩展的标记语言，是一套定义 语义标记的规范，其目标是能够定义计算机和人都方便识别的数据类型。随着网 络应用的快速发展，符合x m l 规范的数据( 称为x m l 数据) 已经大量存在于 当前的信息社会，尤其是电子商务、w e b 服务、数字图书馆等应用理念的进一步 发展，使得x m l 日益成为i n t e r n e t 上数据交换的标准化的数据存储格式。 随着x m l 日益成为网络上的信息描述和信息交换事实上的标准，x m l 技术 随之也在当前的i t 环境中扮演着越来越重要的角色，但x m l 又同时给人们带 来了不小的麻烦，其缘由就在于x m l 数据模型与传统的关系模型之间存在着较 大的区别：关系模型是以关系( 表) 、属性( 列) 为基础，而x m l 数据模型则 是以节点( 元素、属性、备注等) 和节点间存在着的相互关系( 文档序) 为基础 的，其特点有：x m l 数据是自描述的，内容与结果混杂在一起；x m l 数据具有 嵌套层次；x m l 数据是有序的。因此与传统的查询需求相比，对x m l 数据的 查询具有如下特点：以长路径表达式为查询的核心，路径复杂，包含分支结构； 嵌套的查询表达，查询表达式中加入编程语言的嵌套和条件判断思想：查询对象 和返回结果类型的不确定。来自数据结构和查询需求者两个主要方面的问题导致 原有的基于关系和面向对象数据库的查询处理和查询优化技术均不能够适应 x m l 数据的查询需要。 目前，对x m l 查询优化的研究正在成为热点问题。虽然现有的一些商业数 据库系统扩充了处理x m l 数据的功能，它们利用现有数据库成熟的技术，把 x m l 查询要求转变为数据库查询表达，由查询引擎优化查询表达并执行，再将 查询的结果转变为x m l 数据。这种方法在一定程度上解决了查询复杂性的要求， 但是多级的转换带来的问题是效率的降低和查询语义的混淆。因此，如何高效地 共享、搜索和管理企业产生的大量x m l 文档和消息，是数据库领域的厂商们所 面临的巨大挑战。目前一种新的数据库技术，原生x m l 数据库( n x d ，n a t i v e x m l d b m s ) 也己崭露头角【2 儿3 1 ，它打破了传统的关系型数据库一统天下的局面， 为数据库技术的研究提供了一次良好的发展契机。与关系数据库显著不同的是， 在n x d 中直接支持x m l 查询语言来处理x m l 数据相关查询【4 】【5 】【6 】，而不是转 换成s q l 或者o q l ，因此x m l 数据查询语言的查询效率对于n x d 的查询效率 有着至关重要的影响。作为x m l 标准的主要制定机构，w 3 c ( w o r l dw i d ew e b c o n s o r t i u m ) 成立了x m l 查询工作组，其任务是创建一种灵活的查询语言来实 北京丁业大学工学博一 j 学位论文 现从x m l 文档中查询数据，具体目标是：为x m l 文档建立一个数据模型、基 于该数据模型的一组查询运算符以及建立在这些查询运算符操作之上的查询语 言。虽然x s l t 和x p a t h 可以在一定程度上满足上述需求，但是其书写的复杂程 度和功能的不完善使其远远不能达到人们的要求。人们需要的是一种类似于s q l 语言的、简单且易于编写的x m l 数据查询语言。鉴于此，w 3 c 的x m l 查询工 作组制定出了x m l 查询语言x q u e 巧语言的规范1 7 j 。 x q u e r y 是w 3 c 提出的以x m l 为抽象数据模型的查询语言规范，是一种功 能强大的x m l 数据查询语言，它提供了一系列的数据类型和控制结构的编程环 境，适用于查询各种类型的x m l 数据源，并能够从其中选择并提取数据，进而 把查询出的结果按照用户的需求组织成新的x m l 文档结构。x q u e r y 还是一种 强类型的函数式程序设计语言，丰富且功能强大的运算符和函数库使得用户能够 方便的进行程序设计，并且函数式语言其本身具有良好的代数基础，尤其是在使 用部分求值用技术时，任意提前或推迟某些表达式的计算不会影响整个程序的语 义。s q l 语言是对建立在关系代数基础上的数据表进行操作的语言，而x q u e r y 语言则是对建立在x q u e r y 数据模型上的x m l 数据进行查询的语言，随着x m l 的广泛应用，x q u e r y 极有可能成为“x m l 中的s q l ”。近年来，x q u e r y 语言的 研究得到了广泛的重视，在a c m 计算机语言专业委员会s i g p l a n 每年举行 p o p l 国际会议期间都举行x m l 程序设计语言方面的p l a n x 专题研讨会【8 】【9 】； 在a c m 数据管理专业委员会s i g m o d 每年举行的s i g m o d p d o s 会议期间也 都举行x q u e r y 语言方面的x i m e p 专题研讨会【l o 】【1 l 】。 在x q u e r y 语言的研究领域中，语法功能的扩展和实现技术是主要的研究方 向。其中，x m l 查询优化技术的研究已经吸引了全世界主要发达国家的研究者， 包括：美国w o r c e s t e r 学院、m i c h i g a n 大学、o h i o 州立大学、加州大学、华盛顿 大学、英国爱丁堡大学等，还有德国、日本、新西兰、巴西的科研院所；以及国 内北京大学、中科院软件所、复旦大学、人民大学、浙江大学和华中科技大学等 科研院所。这些研究针对x m l 半结构数据及其查询方法的特点，从查询代数和 连接算法等各个方面，研究提高x m l 查询性能的方法【1 2 】 1 3 】【1 4 】【1 5 】【1 6 】。近年来， 又出现了x q u e r y 并行实现技术【1 7 】、x q u e r y 字节码编译技术【1 引。例如，美国 w o r c e s t e r 学院r a i n b o w 、r a i n d r o p 等科研项目，分别研究了x q u e r y 引擎 以及面向x m l 数据流的x q u e r y 实现技术，发展了x a t 查询代数、面向关系库 的x m l 查询、语义缓存、物化视图增量维护等技术。 部分求值( p a r t i a le v a l u a t i o n ) 也被称为程序例化【l 9 】【20 1 ，是用于自动程序生 成和编译优化的一种程序变换技术，即在给定部分输入参数的情况下对程序进行 转换约简，完成程序中只依赖给定参数的计算从而产生滞留程序，当滞留程序作 用在其余参数后，产生与原来程序作用在全部参数一样的结果。部分求值能够通 2 第】章绪论 过程序运行的环境和程序自身所包含的一些己知条件对程序进行例化，生成更加 高效的程序代码。随着软件工程及软件复用技术的不断发展，可重用性、兼容性、 可扩充性、可互操作性已经成为软件设计的发展方向，这样可以大大减少重复开 发，提高软件开发的效率，但同时也造成软件结构的复杂化及性能的下降，而部 分求值技术有助于解决这一问题。 部分求值理论出现于上世纪7 0 年代【2 1 】【2 2 】【2 3 】【2 4 】【2 5 】，作为一种新型的软件自动 化技术为软件开发提供了一种不同于传统的算法优化与编译优化的通用的程序 优化方法和软件工具。利用程序的部分求值技术，软件系统能够根据特定的运行 环境，调整软件自身的程序结构和数据结构，完成程序优化，从而有效地解决复 杂软件系统中常见的功能与性能的矛盾，达到高度的自适应性。自8 0 年代中期 研制出第一个能实际运用的部分求值器以来【2 5 】 2 6 】，美国、荷兰、法国、日本和 俄罗斯( 前苏联) 都开展了部分求值及其应用技术的研究，研究方向从静态部分 技术逐步进入动态部分求值的实现技术及其应用框架的研究，从函数式语言、逻 辑型语言、过程型语言转入面向对象语言、并行程序设计语言部分求值技术的研 究。在部分求值的应用方面，人们已经在操作系统、动态编译、多媒体应用和图 形学领域取得了研究成果，目前代表性的工作包括：丹麦c o p e n h a g e n 大学n j o n e s 研究组最早实现了c 语言部分求值系统c m i x 2 0 】；法国i r i s a 大学c o n s e l 研究组开发了支持c 语言动态例化( r u n t i m es p e c i a l i z a t i o n ) 的部分求值系统 t e m p o 和支持j a v a 程序静态部分求值的j s p e c 系统2 7 】【2 8 1 ，并且将部分求值技术 应用于自适应软件组件( a d a p t a b l es o f t w a r ec o m p o n e n t s ) 和领域专用语言( d o m a i n s p e c i f i cl a n g u a g e ) 的研究；美国o r e g o n 科技研究生院c a l t o np u 研究组将部分求 值技术应用于操作系统和多媒体应用系统的研究【2 9 1 ，探讨了提高系统性能、q o s 和安全性的方法。 在国内，上海交通大学开展了部分求值理论与实践的研究，包括对象型入演 算、j a v a 字节码程序部分求值技术【3 0 】【3 1 】。吉林大学开展了程序设计语言部分求 值及其在编译自动生成应用的研究，包括绑定时间分析( b i n d i n gt i m ea n a l y s i s ) 等 过程型语言和面向对象语言部分求值的实现技术【3 2 】【3 3 1 【3 4 1 。北京工业大学也进行 过j a v a 语言和函数式语言部分求值实现技术及其在增量计算自动生成和视频图 象播放方面的应用基础研究【3 5 】【3 6 】【3 7 】。 1 2 研究的目的和意义 如何能提高程序语言的执行效率是程序语言编译技术这个研究领域内的重 要研究课题，虽然有x q u e r y 这个强大的语言来提供对于x m l 格式数据查询的 支持，但是由于x m l 的广泛应用，这必然导致x m l 格式数据的数据量和查询 北京1 = 业大学t 学博i j 学位论文 复杂度的增加，使得x q u e r y 不得不面对x m l 数据密集型计算和描述相应的密 集型计算算法，这势必要求各个x q u e r y 的支持引擎提供更高的查询效率。此外， 国内外绝大多数x m l 查询优化的研究者都把目光放在了x m l 查询代数，x m l 查询策略和x m l 物理存储优化等领域，而很少有将x q u e r y 视为一个程序开发 语言来进行优化，因此提出利用部分求值技术对x q u e r y 查询进行优化，该技术 能够与常见的x m l 查询优化技术，函数式语言优化技术达到优势互补，从不同 的角度提高x q u e r y 程序的运行效率。此外，通过研究和实现x q u e r y 语言的部 分求值技术和相应的部分求值器，将部分求值技术的应用领域扩展到x m l 数据 处理领域中，不但提高了这种软件自动化技术的应用价值，而且为开发x m l 数 据处理( 特别是原生x m l 数据库中的x m l 数据处理) 提供了新型的、高效的 处理技术和专业工具。 部分求值作为程序优化技术在理论上已经比较成熟，但是在具体的应用、特 别是当前工业界广泛使用的程序开发语言中却明显缺乏有力的支持，故a c m s i g p l a n 专业委员会的主要组成p e p m ( p a r t i a le v a l u a t i o na n dp r o g r a m m a n i p u l a t i o n ) 专题会议现在对其收录的文章的有如下主要建议：“早期部分求值 的工作通常都在l a m b d a 演算的基础上展开，可以视为核心语言，然而现在基础 的部分求值技术已经比较成熟，p e p m 接收的文章应该瞄准于当前编程环境中的 技术”。通过搜集和查询相关资料，在x m l 查询的性能的研究方面，国外个别 学者考虑到能否应用部分求值技术进行改善：有人按照部分求值原理，在x s l t 查询处理中将x m ls c h e m a 作为己知信息对查询计划实施部分计算，发展了 x m l 查询优化技术；有人提出在x q u e r y 语言中的f l w o r 表达式处理中使用部 分求值技术来进行优化。但是，据作者了解，目前国外尚未开展针对x q u e r y 语 言的部分求值技术的研究，也未发现任何部分求值系统能够支持x q u e r y 程序的 自动例化。将x q u e r y 与部分求值相结合，只要能够提取出x q u e r y 程序描述和 执行环境中的程序不变量，部分求值系统便可提前完成相关计算，生成与原始程 序等效的、执行效率更高的滞留程序，达到对原始程序优化的目的。并且，由于 x q u e r y 语言部分求值技术能够提供基于分段计算的、通用程序优化方法和软件 工具，因此，鉴于这种技术的通用性，课题对x m l 数据库技术、x q u e r y 查询 技术和部分求值技术的拓展都有着重要的科学研究和实际应用意义。 1 3 课题来源 本课题得到北京市自然科学基金：面向g m l 数据集成的通用查询语言及实 现方法的研究( 项目编号：4 0 5 2 0 0 6 ) 和( ( x q u e r y 语言动态编译技术的研究 ( 项目编号：4 0 8 2 0 0 3 ) 的支持。 4 第1 幸绪论 1 4 本文的工作 本文主要研究x q u e r y 语言部分求值问题。提出了将部分求值技术应用于 x q u e r y 语言的方法，包括提出了以引用敏感分析这一手段去发现和标记重构失 效表达式，使得人们能够正确地判断出，针对哪些表达式的计算结果可以采用 x m l 文档重构的常量折叠方法来实现x q u e r y 语言的部分求值，从而保证基于 已知信息的、不涉及反向轴等特定运算的表达式计算都可以在部分求值阶段完 成；提出了一个两阶段的绑定时间分析，该分析不仅需要根据初始的静态指定和 程序中的不变量等其它静态信息来标记表达式的绑定时间状态，而且还需要参考 各个表达式的引用敏感分析状态来最终确定表达式的绑定时间状态；提出了针对 x q u e r y 语言的部分求值技术，拓展部分求值技术以及其应用领域。提供了目前 世界上第一个针对x q u e r y 查询程序的自动例化的部分求值工具：x q p e ；提出 了基于x q u e r y 部分求值的动态编译技术，并且已经将该技术成功的运用于x q j 接口的实现中，为x m l 数据处理提供了新型高效的方法和处理工具。 本文的内容组织如下： 第1 章绪论。主要介绍了课题研究内容的背景、来源，x q u e r y 部分求值 的研究目的和意义。 第2 章x q u e r y 语言与部分求值技术。对x q u e r y 语言和部分求值技术进行 基本的介绍，包括其基本概念，基本原理、相关定义、相关研究现状。通过分析 二者各自的研究现状后提出将x q u e r y 与部分求值结合作为研究课题对x m l 数 据库技术、x q u e r y 查询技术和部分求值技术的拓展都有着重要的科学