（计算机软件与理论专业论文）xquery编译后端实现技术的研究.pdf

摘要 摘要 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 ) 是由w 3 c 提出和维护的数据交换标准， 是一种平台无关的数据表示方法。自提出之日起，在很短的时间内，x m l 渗透 到了i t 相关的各个领域。随着x m l 越来越广泛地运用到数据存储和传输领域， 如何有效地实现对x m l 的查询成为互联网发展的重要课题。 x q u e r y ( x m lq u e r yl a n g u a g e ) 是一种功能强大的数据查询语言，适用于查 询各种类型的x m l 数据源，它能够从x m l 文档中选择并提取数据，进而把查 询结果重构为用户所需的新的x m l 文档。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 是一种强类型语 言，它还支持自定义函数、s c h e m a 导入等特性。 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 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 c ( x q u e r yc o m p i l e r ) 。 该系统在原有x q u e r y 解释执行系统上添加编译后端。本系统引入s e c d 抽象机 模型，将原系统中的查询计划，翻译为基于栈结构的s e c d 指令序列，进而编译 为j a v a 字节码文件，在j a v a 虚拟机上直接加载运行。本文给出了编译系统结构、 详细描述了s e c d 抽象机模型及其指令系统以及目标程序生成算法。 关键词x q u e r y ；编译；j a v a 字节码 a b s t r a c t a b s t r a c t 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 ) s u g g e s t e da n dm a i n t a i n e db yw 3 c a sd a t a e x c h a n g es t a n d a r di sap l a t f o r m i n d e p e n d e n tm e t h o df o rd a t ar e p r e s e n t a t i o n i na s h o r tt i m es i n c ei th a sb e e np u tf o r w a r d ，x m lo v e r s p r e a d st h em o s to fi tf i e l d s a s x m li sw i d e l ya p p l i e di nd a t as t o r a g ea n dd a t at r a n s f e r , i ti s p r o m o t e da sa n i m p o r t a n tt o p i cf o ri n t e r n e td e v e l o p m e n t t oe f f i c i e n t l yi m p l e m e n tq u e r i e sf o rx m l x q u e r y ( x m lq u e r yl a n g u a g e ) ，af u n c t i o n a ld a t aq u e r yl a n g u a g eb a s e do n x m l ，i sa p p l i c a b l et oe v e r yt y p eo fx m ld a t as o u r c e s x q u e r yi sa b l et os e l e c ta n d a b s t r a c td a t af r o mx m ld o c u m e n t ，a n dr e c o n s t r u c tt h er e s u l ta san e wx m l d o c u m e n ti nd e m a n d x q u e r ya b s o r b st h eq u i n t e s s e n c ef r o mm u l t i k i n d so fq u e r y l a n g u a g e s ，a n dt a k e s a d v a n t a g e so ft h e m x q u e r yi sw e l ld e s i g n e da n df l e x i b l ea n d w i l lh a v eg r e a ti n f l u e n c eo na p p l i c a t i o no fx m li nt h ef o r e s e e a b l ef u t u r e x q u e r yi s as t r o n g l y - t y p e dl a n g u a g e i ts u p p o r t su s e r - d e f i n e df u n c t i o n ，s c h e m ai m p o r t i n g ，e t c b e c a u s ex q u e r yi sf l e x i b l ea n ds u i t a b l ef o rm a n yd if f e r e n tt y p e so fx m ld a t a s o u r c e ，m a n yo r g a n i z a t i o n sa r ed e d i c a t e dt ot h ei m p l e m e n t a t i o no fx q u e r ya n dt r yt o f i n dc h a n c e st oo p t i m i z ei tt om a k et h ee x e c u t i o no fx q u e r ym o r ee f f i e n t i ti sa c o m m o nw a yt oa p p l yd a t a b a s et h e o r i e so nx q u e r yi m p l e m e n t a t i o n ，f o re x a m p l e ，t o o p t i m i z et h eq u e r yb ys o m ea l g e b r am e t h o d ss u c ha sq u e r yr e w r i t i n g p r e s e n t l y , x q u e r yi sm o s t l yi n t e r p r e t e d f i r s t ，t r a n s l a t et h ex q u e r yp r o g r a mi n t oaq u e r yp l a n t h e no p t i m i z et h eq u e r yp l a nb ya p p l ys o m ed a t a b a s et h e o r i e s a n da tl a s t ，e x e c u t e t h eo p t i m i z e dq u e r yp l a na n dg e tt h er e s u l t t h i sd i s s e r t a t i o nr e s e a r c h e st h ec o m p i l i n go fx q u e r y , f o rp r o m o t i n gt h e e f f i c i e n c yo fx q u e r ye x e c u t i o n am u t i p a r s et r a n s l a t i n gm e t h o di sa p p l i e do nt h e x q u e r yc o m p i l e rt oo p t i m i z eq u e r ya td i f f e r e n tl e v e l t h ed i s s e r t a t i o nd e s i g n sa n di m p l e m e n t sa nx q u e r yc o m p i l i n gs y s t e m ，x q c ( x q u e r yc o m p i l e r ) t h es y s t e m i st oa d dac o m p i l i n gb a c k e n dt oa nx q u e r y i n t e r p r e t i n gs y s t e m a ns e c da b s t r a c tm a c h i n em o d e lb a s e do ns t a c ki si n t r o d u c e d i nt h es y s t e m t h eq u e r yp l a ni nt h eo r i g i n a ls y s t e mi st r a n s l a t e di n t oa ns e c d i n s t r u c t i o nl i s t ，a n dt h e ni sc o m p i l e di n t oa ja v ab y t e c o d ef i l ew h i c hi sl o a d e da n dr a n b yj v m t h i sd i s s e r t a t i o ni n t r o d u c e st h es t r u c t u r eo ft h ec o m p i l e rs y s t e m ，t h es e c d a b s t r a c tm a c h i n em o d e la n dt h ei n s t r u c t i o n s ，a n dt h ea l g o r i t h mf o rg e n e r a t i n gt h e o b j e c tp r o g r a m k e y w o r d sx q u e r y , c o m p i l e ，j a v ab ”e c o d e i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：氍：邋 日期：鲨2 ：! 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：盔：选 导师签名：日期：切? 纠 第l 章绪论 1 1 课题简介 1 1 1 课题背景 第1 章绪论 x m l 是由w 3 c 提出和维护的数据交换标准【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 q u e r y 是基于x p a t h 2 表达式的、用于对x m l 文档进行查询的语言，其对 x m l 的作用类似于s q l 对关系型数据库的作用。x q u e r y 以其良好的设计和强 大的功能，为人们提供了一种更强大的数据查询语言，目前已成为w 3 c 的推荐 规耐3 6 1 并被包括i b md b 2 t 7 1 、o r a c l e t 钔、m i c r o s o f t t 9 1 在内的所有主要数据库引擎 支持。 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 解释执行系统工作流程【1o 】为：首先对x q u e r y 查询进行词法语法分析 生成x q u e r y 语法树；对x q u e r y 语法树应用查询分解、规范化、静态类型检查 等操作，生成x q u e r y 核心语法树：进而将核心语法树翻译为中间语言f x q l ( f u n c t i o n a lx m l q u e r yl a n g u a g e ) 描述的查询计划；最后由执行引擎执行查询 计划。 1 1 2 研究目的和意义 x q u e r y 语言目前已被众多研究组织实现，并从多个方面寻找优化机会，以 提高x q u e r y 的查询处理效率。常见的方法是借鉴数据库理论【1 1 1 来研究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 查询进行处理和执行，有助于在不同层次 上对查询进行优化。 f x q l 1 2 】是为解释和优化x q u e r y 而引入的中间语言，作为一种函数式语言， f x q l 语言无副作用，支持函数和递归函数的定义和调用，支持函数作为参数， 并且提供了丰富的原语函数来完成各类x m l 数据处理和程序逻辑控制的任务。 f x q l 在以简洁的方式表达查询意图方面比x q u e r y 更具优势，它在原始用户查 询和计算机处理之间建立起一个桥梁。因此本系统选用f x q l 表示x q u e r y 查询 计划，并实现该层次的相关优化。 由课题组前期设计并实现的g e o q u e r y l l 3 j 系统，对f x q l 进行了解释执行。 为了进一步提高执行效率，本文的研究课题是引入了基于栈结构的s e c d 抽象 机，对其进行优化并编译执行。使用s e c d 抽象机可以实现求值环境元素的常数 时间存取和尽早释放求值环境中无用元素所占的内存单元，由此来提高程序的执 行效率【1 4 】。在s e c d 求值环境中取消了变量常量名，而采用环境中的位置d 来 代替。实现了常数时间存取变量常量。利用s e c d 抽象机基于栈结构的特点， 可以进行诸如消除尾递归之类的优化，此类优化实现了尽早释放求值环境中无用 元素所占内存单元。 关于x q u e r y 查询的执行方式有解释执行和编译执行两种选择。虽然解释执 行效率较低，但编译执行对于程序中执行频度较低的部分，由于增加了编译时间， 其效率不如解释执行。因此，将来本课题组计划引入j a v a 字节码执行的 h o t s p o t 1 5 - 1 7 1 概念，对于由程序的功能模块进行频度分析，并对执行频率高的模 块编译为j a v a 字节码，以后对调用该程序时则直接执行相应的j a v a 字节码。本 文所介绍的x q u e r y 编译实现为h o t s p o t 编译实现提供了条件。 对于编译执行x q u e r y ，系统采取将s e c d 机指令编译为j a v a 字节码的方式。 其优势在于直接生成的j a v a 字节码可以操作j a v a 虚拟机部件进行操作，其执行 效率将有提高，同时由于代码以j a v a 字节码的形式表示，因此仍具备良好的跨 平台性。另一方面，对s e c d 抽象机指令序列进行翻译最终得到的编译结果体现 了各级优化效果；编译结果被j a v a 虚拟机加载运行求值，省去了词法语法分析 的开销，从而提高了执行效率。 对x q u e r y 编译实现研究的目的是提高x q u e r y 程序的执行效率，和提供更 多的查询优化机会。 第l 章绪论 1 2 国内外相关工作 1 2 1s e c d 抽象机 s e c d ( s t a c k ，e n v i r o n m e n t ，c o n t r o ll i s t ，d u m p ) 抽象机【t s 1 9 1 作 入表达式【2 0 川 的求值机制，由l a n d i np e t e r 在1 9 6 4 年提出，由麻省理工学院研制的c a d r t 2 2 l 实现了一个非常接近s e c d 抽象机的微处理器。经过长期验证，s e c d 机成为操 作语义的经典范例【2 3 2 5 1 ，并经常在程序设计语言的验证与实现中被引入。s e c d 抽象机为操作语义提供了一个简单而清晰的描述，广泛地应用于编译领域。 1 2 2j a v a 虚拟机和j a v a 字节码 j a v a 虚拟机是s u n 的j a v a 程序设计语言的基石，s u n 公司一直在开发更高级 的j d k 版本来支持更新、功能更强大的j a v a 语言特性，最近的版本是j d k ( j a v a s ed e v e l o p m e n tk i t ) 6 2 6 j 。j a v ah o t s p o t 虚拟机已成为j a v a 标准环境平台的一项 核心组成部分。j a v a 字节码是唯一能被j a v a 虚拟机识别的文件格式，t h ej a v a v i r t u a lm a c h i n es p e c i f i c a t i o n ) ) 一书详细地阐述了j a v a 虚拟机规范和j a v a 字节码 的文件格式1 2 7 j 。 许多项目跳过j a v a 语言直接生成字节码，添加j a v a 程序所没有的新特性【2 引， 实现面向方面的程序设计，进行复杂的静态分析，或提高运行时效率。因此存在 很多关于字节码生成库的研究工作【2 9 l 。 a p a c h ej a k a r t a 项目组开发的b c e l ( b y t ec o d ee n g i n e e r i n gl i b r a r y ) 如j 为用户 提供了便捷的分析、创建和操作j a v a 字节码文件的工具，b c e l 是目前j a v a 字 节码工作中最广泛应用的一种框架。由东京技术学院的数学和计算机科学系的 s h i g e r uc h i b a 所创建的j a v a s s i t 3 1 】是一个开源的分析编辑和创建字节码的类库， 它已加入了开放源代码j b o s s 应用服务器项目，通过使用j a v a s s i t 对字节码操作 作为b o s s 实现动态a o p ( a s p e c to r i e n t e dp r o g r a m m i n g ) 框架。o b j e c t w e ba s m t 3 2 j 是轻量级的j a v a 字节码处理框架。c g l i b ( c o d eg e n e r a t i o nl i b r a r y ) t ”，3 4 l 是一个强 大的，高性能，高质量的代码生成类库，用于在运行时扩展j a v a 类和实现j a v a 接口，h i b e r n a t e 用它来实现p o ( p e r s i s e n to b j e c t ) 字节码的动态生成。 使用字节码生成工具直接生成字节码的优势在于可以动态地修改字节码，或 调整字节码使其具有新的特性来实现j a v a 语言所不能达到的效果。 北京工业大学工学硕士学位论文 1 2 3x q u e r y 实现技术的研究现状 x q u e r y 灵活易用、能够对各种类型x m l 数据源进行操作，许多组织都致力 于x q u e r y 的实现。 a x y a n as o f t w a r e 开发的q i z x o p e n t ”】是一个开源的j a v a 实现的x m l 查询解 释器，完整地实现了x q u e r y 语言。它被设计为一个嵌入到j a v a 应用中的x m l 查询和数据库引擎，并提供q i z xa p i 作为类库。开发者可以在此基础上进行试 验或相关的x m l 数据库的开发。 g a l a x 3 6 , 3 7 1 是一个轻量级可移植的x q u e r y 的开源实现。它完整地实现了 x q u e r y l 0 支持x p a t h 2 0 包括文档序操作，正向、反向轴，支持名字空间和类型 操作。因其忠实于x q u e r y l 0 系列的所有规范，并以开放的体系结构进行实现， 因此g a l a x 又成为研究各种x q u e r y 优化实现技术的试验平台。 s a x o n t 3 8 】是由英国的m i c h a e lk a y 开发的x s l t 与x q u e r y 处理器，自从1 9 9 9 年以开源产品发布。从2 0 0 3 年的7 6 版开始s a x o n 增加了对x q u e r y 的支持。s a x o n 中的x q u e r y 支持本质上由一个x q u e r y 解析器组成，解析器与x s l t 处理器一 样生产相同的内部可解释的代码。由人民大学研制的o r i e n t x 3 9 , 4 0 】是一个n a t i v e x m l 数据库系统，它提出o r i e n t x a 4 l 】为x q u e r y 优化处理提供了一个有效的代 数系统。2 0 0 7 年提出的o r i e n t x3 0 t 4 2 】更新了原有体系结构，提供一系列编程接 口。 现在国内外已经展开了对于编译实现x q u e r y 语言的研究，q e x o 4 3 , 4 4 】就是 利用g n u t 4 5 ik a w a l 4 6 1 实现x q u e r y 编译执行的成功案例。它直接将经过语法分析 得到的x q u e r y 语法树进行转换得到j a v a 字节码。s a x o n 的最新版本s a x o n s a t 4 7 】 也支持将x q u e r y 代码直接编译为j a v a 代码。 1 3 课题来源 本研究得到北京市自然科学基金( 项目编号：4 0 8 2 0 0 3 ) 的资助，项目名称： x q u e r y 语言动态编译技术的研究。 1 4 课题研究工作 本课题通过在原系统解释执行x q u e r y 的基础上，在后端添加编译模块，得 到如图1 1 的系统编译实现的工作流程： 4 第1 章绪论 x q u e r y $ 晌文本x q u e r y i 吾法树x q u e r y 语法树 主一一一x q u e r y 核心语法树一一一一一 叵闺獭愀树叵 i 。tf x q l i 删- j s e c d 抽象机指令序列 豳 j a v a 字节码流 图i - i 编译实现的x q u e r y 查询处理流程 f i g u r e1 - 1x q u e r yp r o c e s s i n gf l o wf o rc o m p i l i n gs y s t e m 其中编译后端的任务为将f x q l 语法树经由s e c d 抽象机指令序列编译为 j a v a 字节码。 本文的研究工作包括以下内容： s e c d 机的设计 s e c d 机设计的主要内容是s e c d 指令集的设计，s e c d 机指令集包括基本 指令集和扩展指令集两部分。s e c d 机基本指令集，指经典s e c d 机语义规范的 s c e d 机基本操作，如从环境中取变量值( l o a d ) 、取常量值( l o a d c ) 、绑定变 量到环境q b ( b i n d ) 、函数定义( f u n c d e f ) 、调用( c a l l ) 与返回( r t n ) 等操作。 s e c d 机扩展指令集指的是，根据系统中f x q l 原语函数设计的s e c d 机原语指 令。 j a v a 虚拟机的加载和执行机制的分析和s e c d 执行环境的设计 了解j a v a 虚拟机的特点，了解字节码层次可以操作的虚拟机部件，充分利用 虚拟机资源，为s e c d 机设计高效的执行环境。利用j a v a 虚拟机为每个方法分 配的操作数栈模拟抽象机的栈部件；抽象机指令序列直接翻译为j a v a 字节码指 令序列：对于转储区的实现，充分利用虚拟机为j a v a 方法保存调用现场的机制； 使用一个二维数据模拟抽象机环境部件。 字节码目标程序的结构设计 结合j a v a 虚拟机和s e c d 抽象机的特点，为编译目标程序设计结构。将每条 s e c d 指令对应为一段j a v a 字节码指令序列，s e c d 的一个函数定义被翻译为一 个j a v a 方法，若干j a v a 方法组成的j a v a 类文件就是编译得到的目标代码。其中 北京工业大学工学硕士学位论文 原始s e c d 指令序列将在作为该j a v a 类提供给外界的入口方法。 s e c d 机指令到j a v a 字节码指令序列翻译算法的设计与实现 根据j a v a 虚拟机特点和设计的字节码目标程序结构，为每条s e c d 指令设计 翻译算法，即s e c d 指令与j a v a 字节码指令序列的对应关系。 编译后端实现的其他研究工作由本组其他同学完成。 1 5 本文结构 本文介绍了x q u e r y 编译后端的设计和实现。第l 章为绪论，介绍课题的背 景与研究意义。 第2 章介绍x q u e r y 编译系统的基本模型，首先对x q u e r y 编译处理流程进 行介绍，进而介绍多级翻译各层次和引入这些层次的意义。第3 章对s e c d 抽象 机进行详细介绍，包括s e c d 抽象机的概念，s e c d 抽象机指令集和一个翻译示 例。第4 章重点介绍s e c d 抽象机的字节码实现，包括目标文件结构设计，支撑 环境设计以及翻译算法。 第5 章对x q u e r y 编译后端的具体实现加以介绍，包括介绍各模块的内容和 功能。并对编译实现过程中可能产生的优化加以介绍。第6 章给出了系统测试方 案和测试数据分析。最后，总结本课题的贡献并对其不足加以分析提出改进意见。 6 第2 章x q u e r y 编译系统模型 第2 章x q u e r y 编译系统模型 2 1x q u e r y 简介 随着w e bs e r v i c e 技术的不断普及，x m l 正在逐渐成为标准的数据传输语言。 同时，这项技术的另外一些特点：树形结构、对数据顺序的记忆能力、灵活的数 据结构( 半结构化) ，使得人们越来越相信x m l 数据库就是未来数据库技术的 发展方向。查询语言是数据库技术的重要组成部分。而x q u e r y 就是未来x m l 数据库的查询语言，相当于现在的关系数据库的s q l 语言。 x q u e r y 是x m lq u e r y 的缩写，它是一种基于x m l 的功能强大的数据查询 语言，适用于查询各种类型的x m l 数据源，它能够从x m l 文档中选择并提取 出数据，进而把查询结果重构为用户所需的新的x m l 文档。因为s q 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 中的s q l ”。x q u e r y 是x p a t h 的一种扩展，但与x p a t h 不同的是，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 m l 的应用产 生巨大的影响。 x q u e r y 是一种强类型语言，它还支持自定义函数、s c h e m a 导入等特性。 x q u e r y 具有多种语言的优点，适用于各种类型的x m l 数据源的查询。x q u e r y 使用它的姊妹语言x p a t h 2 0 作为在x m l 文档中导航、选择和提取数据的子语言。 x q u e r y 还是一种模块化语言，一个x q u e r y 查询由两部分组成：序言和查询 体。其中序言部分包括：名称空间和s c h e m a 的声明，以及用户自定义函数的声 明：而查询体则是一个查询表达式。表达式是x q u e r y 的基石，表达式可由关键 字、符号以及操作数构造而来。一般来说一个表达式的操作数是另一个表达式。 x q u e r y 表达式可以任意的嵌套，查询的结果即作为查询体的表达式的值。同样 地，用户自定义函数的函数体也是一个表达式。 下面介绍几种常见的表达式类型。 路径表达式( p a t h e x p r ) 在x q u e r y 中，路径表达式使用了x p a t h 2 0 的语法。x p a t h 提供了关于路径 导航( p a t hn a v i g a t i o n ) 、节点定位( n o d el o c a t i o n ) 、谓词选择等方面的精确规范，并 被作为x q u e r y 的核心部分。路径表达式使用路径标记在x m l 文档中选择节点。 北京工业大学工学硕士学位论文 如果把x m l 看作一个节点树，那么路径表达式用于在这棵树中定位节点。路径 表达式分为两种：绝对路径表达式和相对路径表达式。而绝对路径表达式可被看 作从根开始的相对路径表达式【4 引。 p a t h e x p r ：= ( 7 r e i a t i v e p a t h e x p r ? ) l ( “”r e l a t i v e p a t h e x p r ) l r e l a t i v e p a t h e x p r r e l a t i v e p a t h e x p r ：= s t e p e x p r ( ( ”) i ( “”) s t e p e x p r ) 宰 其中：s t e p 表达式是x p a t h x q u e r y 中的基本操作。s t e p 用来选择x m l 节点 树中由根开始的可得的节点。而 和”表示相关的轴操作( c h i l d 或 s e l f o r d e s c e n d a n t ) 。 如：d o c ( “b i b x m l ) b i b b o o k 是一个路径表达式，谓词则是在节点定位的基 础上进行筛选的条件，如：d o c ( “b i b x m l ”) b i b b o o k y e a r ”2 0 0 0 ”】。 f l w o r 表达式( f l w o r e x p r ) f l w o r 表达式分别代表f o r - l e t w h e r e o r d e rb y r e t u r n 的首字母缩略词。 x p a t h x q u e r y 将f l w o r 表达式用于迭代，f o r l e t 子句可以用来将变量绑定到 中间结果上，并且通过谓词( p r e d i c a t e s ：x p a t h 语法) 筛选被绑定的变量。其中f o r 子句通过将节点绑定到变量，一边去循环遍历序列中的每一个点；l e t 子旬为一 个变量赋一个值或一个序列；r e t u r n 子句将变量内容组织为用户需要的格式返回； w h e r e 子句是一个具有布尔值的表达式，如果将由f o r l e t 子旬绑定的内容视为由 每个被绑定变量所含节点进行半连接的形式组织的若干元组，则对于每一元组都 经过w h e r e 子句的筛选，如果该元组使w h e r e 子句的布尔值为真则保留该元组。 否则舍弃该元组；o r d e rb y 子句则用于对筛选过的所有元组按指定的关键字排序。 x q u e r y l 0 中的f l w o r e x p r 是由以下序列组成的：先是一系列的f o r 子句和l e t 子句，接着是一个可选的w h e r e 子句，后面是一个可选的o r d e rb y 子句以及一个 r e t u m 子句。 下面这个例子体现了f l w o r 表达式的作用： f o rs bi nd o c ( “b i b x m l ”) b i b b o o k ， $ ti n $ b t i t l e ， $ ai n $ b a u t h o r w h e r es t = d a t ao nt h ew e b ” r e t u m $ t ) $ a 首先由f o r 子句将$ b 绑定到路径表达式d o e ( “b i b x m l ”) b i b b o o k ，作为一个 中间结果。此时$ b 代表”b i b x m l ”文档中b i b 节点下的所有b o o k 节点。紧接着 又将$ t 和$ a 分别绑定到了每本书的书名和作者节点上。经过绑定后的( $ b ，s t ， $ a ) 元组经过w h e r e 子句的筛选只留下了令s t - - - d a t ao nt h ew e b 那一组。接着 的r e t u r n 子句将由筛选得到的( $ b ，s t ，$ a ) 元组以“ s t ) s a 这一形式组织起来返回给用户。 第2 章x q u e r y 编译系统模型 元素构造器( e l e m e n t c o n s t r u c t o r ) 上一段中的r e t u r n 子句通过形如：“ s t $ a ”的表达式来组 织返回结果，这即是元素构造器。它的作用是将表达式的计算结果构造成用户需 要的x m l 格式返回。 x q u e r y 的重要特点为：f l w o r 表达式是查询的框架：x p a t h 用于在文档中 定位：元素构造表达式把查询结果重构为用户所需的x m l 文档结果。 值得注意的是，x q u e r y 还支持嵌套的子查询并且能够进行查询结果的重构 和连接。这也是选择在x q u e r y 层进行优化的原因，x q u e r y 的这一特性使其能 够在保持语义不变的前提下灵活地分解查询和重构结果。 另外元素构造器中还可以嵌套f l w o r 表达式，如果把上节的例子嵌套在一 个元素构造器中，就形成如下查询： f o rs bi nd o c ( “b i b x m l ”) b i b b o o k ， $ ti n $ b t i t l e ， $ ai n $ b a u t h o r w h e r es t = d a t ao nt h ew e b ” r e t u m s t ) $ a ) 谓词表达式( p r e d i c a t e s ) 谓词符合x p a t h 语法。谓词也是一个具有布尔值的表达式，与w h e r e 子句不 同的是，它在绑定变量时就对变量内容进行筛选。如：f o r $ ti ns b t i t l e = ”d a t ao n t h ew e b ”】，此时$ t 所代表的是令$ b t i t l e = ”d a t ao nt h ew e b 的所有$ b t i t l e 节点。 运算符( o p e r a t o r ) 和函数表达式( f u n c t i o n c a l l ) x q u e r y 还支持常用的算术运算( n u m e r i c o p ) ，节点运算( n o d e e x p r e s s i o n ) ，同 时也支持x q u e r y 内置的函数调用，以及自定义函数的调用。 一个函数调用( f u n c t i o n c a l l ) 由- - 个限定名( q n a m e ) ，和0 或多个置于括号内 的参数列表组成。每个参数都可以是一个表达式。如：d e e p e q u a l ( $ i ，s j ) 等。 事实上，运算符也可以看作是内置函数的一种，虽然格式不是函数名( 参数， 参数，) ，但通过解析可以发现，它们的表达式树也是由一个q n a m e 和若 干参数( 操作数) 组成。因此，对于运算符不再赘述。 比较表达式( c o m p a r i s o n ) x q u e r y 支持三种类型的比较表达式：值比较表达式、通用比较表达式和节 点比较表达式。值比较表达式进行单一值之间的比较；通用比较表达式是存在量 9 北京工业大学工学硕士学位论文 词比较，它能够比较任意长度的两个序列；节点比较表达式则是根据节点的标识 符或文档序进行节点之间的比较。该类表达式的值为布尔值。 这里有一些比较表达式的例子： 1 s t - - - ”d a t ao nt h ew e b ”值比较表达式，判断是否相等 2 p o s i t i o n o = 2 值比较表达式，判断左侧操作数是否小于等于右侧 3 $ b o o k l $ b o o k 2 节点比较表达式，判断左侧节点文档序是否优 于右侧 a n d o r 表达式( a n d e x p r o r e x p r ) a n d o r 表达式用来表示逻辑关系，它们的值也是布尔值，与比较表达式不同 的是，a n d o r 表达式的操作数也是布尔值的，通常是由这些比较表达式组成( 也 可能是任何其他具有布尔值的表达式，如函数表达式c o n t a i n s ( $ b ，a b c ”) ) 。 再举一些例子： 1 $ b o o kl 10 0 0a n d $ i o f f e r e d _ b y = $ u u s e r i d 第一个表达式表示三个条件之间的逻辑与，而第二个表达式表示两个条件之 间的逻辑与。以上这些可能和必然具有布尔值的表达式构成了f l w o r 表达式中 w h e r e 子句的主体，即筛选条件。 2 2 编译系统结构 x q u e r y 语言作为数据查询语言，在语言实现方面需要借鉴数据库语言实现 方法引入查询代数等查询优化技术，而鉴于x m l 数据的半结构化数据特征，需 要探讨专用的查询优化方法。同时x q u e r y 又是一种函数式语言，依靠函数调用 和表达式求值完成计算，实现中需要使用编译优化技术。 考虑到以上需求，作者研制的x q u e r y 编译系统采用了多级翻译结构使用多 种不同的中间语言表示层，提供了不同的程序优化机会，允许在各个层次上采用 不同的优化策略。并最终编译为j a v a 目标代码。 通常，x q u e r y 查询处理需要经过词法分析、语法分析和求值过程【4 9 1 。本系 统采用多级方式处理x q u e r y 程序，x q u e r y 查询处理流程如图2 1 所示： 1 0 第2 章x q u e r y 编译系统模型 i x q u e r y 查询 x q u e r y 抽象语法树 f x q l 抽象语法树 s e c d 指令序列 j a v a 字节码指令序列 图2 - 1x q u e r y 查询处理流程 f i g u r e2 - 1x q u e r yp r o c e s s i n gf l o w 词法语法分析 语法分析将输入的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 q u e r y 表达式对象组成。 x q u e r y 到中间语言f x q l 的翻译 将x q u e r y 抽象语法树转换为本系统使用的f x q l 语法树。f x q