（计算机软件与理论专业论文）基于secd抽象机的xquery编译实现技术的研究.pdf

摘要 曼曼皇曼皇曼詈曼曼量曼曼曼曼量曼鼍曼曼曼量曼曼曼曼曼皇曼量曼量曼曼曼曼量量皇_ 曼 mmmm 蔓曼曼曼璺曼曼皇曼曼曼皇曼曼曼量皇曼曼曼皇曼曼曼皇 摘要 随着x m l 逐渐成为互联网应用的数据交换格式，越来越多的应用使用x m l 作为数据存储格式，对于x m l 的查询语言需求正在日益增加。x q u e r y 语言的 推出使得x m l 查询语言有了一种统一的标准。x q u e r y 语言具有良好的查询能 力、数据组织能力和算法描述能力，其应用领域正在不断地扩展。x q u e 珂语言 实现与应用技术的研究逐渐成为了一个重要的研究方向。 随着应用的增多，x q u e 巧语言已经逐渐成为了一种主流的计算机语言。对 于应用程序来说，x q u e r y 程序执行效率的高低是十分重要的，x m l 半结构化数 据特点的限制使得x q u e 巧语言实现技术的研究一直受人关注。和解释实现技术 相比，采用编译实现的方法可以为代码优化创造更多机会，生成的代码拥有更高 执行效率。同时，编译技术的研究也将为动态编译的实现提供了前提条件。 本文对x q u e d ，的编译实现进行了研究，给出了基于s e c d 抽象机的x q u e d ， 编译实现方案，实现了x 叫e r y 程序到j a v a 字节码程序的编译。该实现使用s e c d 抽象机作为编译后端的语义基础，保证了中间语言f x q l 翻译到s e c d 抽象机 指令的语义不会丢失。x q u e r y 语言的编译实现方案的主要特色在于采用了分层 的体系结构，采用了f x q l 中间语言和s e c d 抽象机指令系统等中间表示，为 编译优化提供了多种机会，允许在不同的层次上引入了不同性质的优化策略。其 中，f x q l 语言主要用于表示查询计划，基于查询代数的查询重写可以通过f x q l 语言的程序变换来实现，这种优化技术主要借鉴了数据库查询优化技术；而 s e c d 抽象机指令易于表示程序控制流程和函数调用过程的实现，所以可以引入 消除尾递归、函数内联等一般程序设计语言的代码优化技术。 本文已经实现了一个基于s e c d 机的x q u e r y 编译系统x q c 系统。在该 系统中，x q u e d ，程序先后被翻译成f x q l 中间语言程序、s e c d 机指令序列， 并经过消除尾递归和函数内联等优化处理，最终被翻译为j a v a 字节码形式的目 标程序。在本系统提供的运行支撑环境下，这种目标程序能够正确地运行在j a v a 虚拟机上。 本文针对字节码目标程序进行了功能测试和性能测试。实验结果说明：使用 基于s e c d 抽象机的x q u e r y 编译实现方案，可以将x q u e r ) r 程序编译为等价的 j a v a 字节码程序。在j a v a 虚拟机上加载运行编译产生的字节码程序比解释执行 效率更高。同时，在s e c d 指令序列中引入的尾递归消除优化策略，可以有效地 消除部分函数调用的开销，节省栈空间，提高执行效率。 关键词x o u e r y ；编译实现；s e c d 抽象机：尾递归消除 a b s t r a c t a b s t r a c t x m lh a sb e e nt h ef a c t u a ls t a n d a r do fd a t ae x c h a n g i n ga n dd e s c r i b i n go nt h e i n t e r n e t ，a sar e s u l t ，m o r ea n dm o r ea p p l i c a t i o n ss t o r ea n dd e s c r i b ed a t aw i t hx m l ， w h i c hl e a d st ot h er a p i d l yi n c r e a s i n gr e q u i r e m e n to fx m lq u e r yl a n g u a g e a s x q u e r yi sp u b l i s h e d ，i tb e c o m e st h eu n i v e r s a ls t a n d a r do fx m lq u e r yl a n g u a g e x q u e r yh a sg o o dp o w e ro fq u e r y i n g ，d a t ao r g a n i z i n ga n da l g o r i t h md e s c r i b i n g ，w h i c h m a k e si t sd o m a i ne x p a n d i n g i ti sg r a d u a l l yb e c o m i n gac h i e fr e s e a r c hf i e l do ft h e x q u e r yi m p l e m e n t a t i o na n da p p l i c a t i o nt e c h n o l o g y x q u e r yb e c o m e sam a i n s t r e a mo fc o m p u t e rl a n g u a g es i n c ei t sa d o p t e db ym o r e a n dm o r ea p p l i c a t i o n s a st h ee x e c u t i o ns p e e do fx q u e r yi sv i t a lf o rt h ea p p l i c a t i o n s ， t h ei m p l e m e n t a t i o nt e c h n o l o g yo fx q u e r yb e c o m e sah o ti s s u ee s p e c i a l l yw h e n x m u ss e m i s t r u c t u r eb e c o m e st h en e g a t i v ep a r tf o rt h ep e r f o r m a n c e c o m p a r e dw i t h t h ei n t e r p r e t a t i o n ，c o m p i l a t i o np r o v i d e sm o r eo p p o r t u n i t i e sf o ro p t i m i z a t i o n ，a n dt h e c o m p i l e dc o d ei sm o r ee f f i c i e n tf o re x e c u t i o n ，a l s o ，c o m p i l i n gt e c h n o l o g yr e s e a r c hi s t h eb a s eo fi m p l e m e n t a t i o no fd y n a m i cc o m p i l i n g 1 1 1 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 u d yo fx q u e r yc o m p i l a t i o n ，a n dt h ec o m p i l e s o l u t i o nb a s e do nt h es e c da b s t r a c tm a c h i n e ，w h i c hc o m p i l e sx q u e r yp r o g r a mi n t o j a v ab y t ec o d ep r o g r a m t h es e c dm o d e li st h eb a s eo fs e m a n t i c si nt h es o l u t i o n w h i c hg u a r a n t e e st h en o n l o s so fs e m a n t i c sw h e nc o m p i l i n gf x q li n t e r m e d i a t e l a n g u a g ep r o g r a mi n t os e c di n s t r u c t i o nl i s t t h ek e yp o i n to fx q u e r yc o m p i l a t i o n s o l u t i o ni st h em u l t i p h a s e da r c h i t e c t u r eu s i n gs e v e r a li n t e r m e d i a t ep r e s e n t a t i o n ss u c h a sf x q la n ds e c di n s t r u c t i o nl i s t ，w h i c hp r o v i d e so p t i m i z i n go p p o r t u n i t i e si n d i f f e r e n tp h a s e sf o rd i f f e r e n to p t i m i z a t i o ns t r a t e g i e s o no n eh a n d ，f x q li nt h e s o l u t i o ni sm a i n l yu s e df o rq u e r yp l a no r g a n i z i n ga n ds o m eq u e r ya l g e b r ab a s e d r e w r i t i n go p t i m i z a t i o n sb o r r o w e df r o md a t a b a s ec o m m u n i t yc a l lb ep e r f o r m e db y p r o g r a mt r a n s f o r m a t i o n ；o nt h eo t h e rh a n d ，s e c da b s t r a c tm a c h i n ei n s t r u c t i o nl i s t c a nd e s c r i b et h ec o n t r o lf l o wo fap r o g r a ma n dt h ei m p l e m e n t a t i o no ft h ef u n c t i o n i n v o c a t i o n ，w h i c hm a k e st h et a i lr e c u r s i v ee l i m i n a t i o na n di n l i n i n go p t i m i z a t i o n s t r a t e g yb o r r o w e df r o mt h eg e n e r a lp r o g r a m m i n gl a n g u a g eo p t i m i z a t i o nt e c h n o l o g y c a l lb cp e r f o r m e ds t r a i g h t f o r w a r d l y w ei m p l e m e n t e d 缸x q u e r yc o m p i l es y s t e mb a s e do nt h es e c da b s t r a c t m a c h i n e ，c a l l e dx q c i nt h es y s t e m ，x q u e r yi st r a n s l a t e di n t oi n t e r m e d i a t ef x q l p r o g r a ma n ds e c di n s t r u c t i o n l i s ts e q u e n t i a l l y , o p t i m i z e dw i t ht a i lr e c u r s i v e i i i 北京土业大学工学硕士学位论文 e l i m i n z t i o na n di n l i n i n gs t r a t e g y , a n dt h e nt r a n s l a t e di n t oj a v ab y t ec o d e t h eo b j e c t c o d e w i t ht h eh e l po fs u p p o r tl i b r a r y , t h eo b j e c tc o d ec a nb ee x e c u t e di nt h ej v m c o r r e c t l y t h r o u g ht h ef u n c t i o na n dp e r f o r m a n c et e s to ft h eo b j e c tb y t ec o d ep r o g r a m ，i t s s h o w nt h a tt h ec o m p i l es o l u t i o nb a s e do ns e c da b s t r a c tm a c h i n ec o u l dp e r f o r ma c o r r e c tc o m p i l a t i o nf r o mx q u e r ys o u r c ec o d ei n t ot h ee q u i v a l e n tj a v ab y t ec o d e p r o g r a m t h ep e r f o r m a n c eo fl o a d i n ga n de x e c u t i n gt h eg e n e r a t e dj a v ab y t ec o d e o v e r w h e l m st h a to fi n t e r p r e t a t i o n , a n dt h et a i lr e c u r s i v ee l i m i n a t i o no p t i m i z a t i o n s t r a t e g yp e r f o r m e do ns e c di n s t r u c t i o nl i s ta l s os a v e st h es p a c eo fo p e r a t o rs t a c ka n d i m p r o v e st h ep e r f o r m a n c eb yg e t t i n gr i do fs o m ef u n c t i o ni n v o c a t i o n s k e y w o r d sx q u e r y ；c o m p i l ei m p l e m e n t a t i o n ：s e c d ；t a i lr e c u r s i v ee l i m i n a t i o n i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：彳乏l 吼雄 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：妞导师签名： 日期：丝乳、z ， 第1 章绪论 1 。1 课题背景 第1 章绪论 x m l o - 3 ( e x t e n s i b l em a r k u pl a n g u a g e ) 经逐步成为i n t e m e t 环境中数据交换 和表示的标准，越来越多的应用开始使用x m l 作为数据存储或表示。x m l 是 一种具有可扩展性的语言，允许使用者创建和使用他们自己的标记来定义领域相 关的特殊标记语言，作为相关领域信息共享与数据交换的基础。x m l 还具有相 当的灵活性，它提供了一种半结构化的数据表示方式，可以很灵活地扩充数据的 结构。所以，w e b 用户所追求的许多先进功能在x m l 环境下更容易实现。x m l 文档通常包含一个文档类型声明，具有自描述性，不仅易于阅读，也方便计算机 处理。x m l 表示数据的方式真正做到了独立子应用系统，并且数据能够重用。 因此，x m l 文档被看作是文档的数据库化和数据的文档化。 随着越来越多的应用中使用x m l 作为数据表示形式，针对大量x m l 数据， 如何有效地进行组织、提取所需要的信息成为了一个研究的重点。 1 9 9 9 年，w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ) 发布了x p a t h t 4 j 】1 0 的推荐标 准，它被用于在x m l 文档中定位和查找信息。通过x p a t h 的路径表达式可以选 取x m l 文档中的节点或者节点集，同时，x p a t h 还提供了一些函数增强对x m l 数据的查询处理功能。x p a t h 能满足简单的对x m l 处理的需求，但对于表达更 复杂的计算逻辑、数据格式转换和递归查询，x p a t h 语言功能就略显不足。 2 0 0 7 年，w 3 c 发布了x m l 查询语言标准：x q u e r y _ 【鲫】语言( 煳lq u e r y l a n g u a g e ) 。x q u e r y l 0 以x p a t h 2 0 为基础，使用序列来表示值，主要语言结构 有路径表达式、f l o w r 表达式、构造表达式、条件选择表达式等f i 驯列。它支持 条件选择、结果转换，还支持自定义函数与类型描述。x q u e r y 适用于查询各种 类型的x m l 数据源，它能够从x m l 文档中选择并提取出文档片段，进而把查 询结果重构为用户所需的新的x m l 文档结构。设计初始时期，w 3 c 着眼于 x q u e r y 的查询功能，从数据库及s q l 语言汲取经验，将x q u e r y 设计为一种强 大的x m l 查询语言，使得x q u e r y 具有查询语言的各种特性。同时，x q u e r y 又 是一种图灵完全的函数式语言【l3 1 ，即除了进行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 j 1 4 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 的实现展开了研究，给 出了编译实现方案。 1 2 研究意义 对x q u e r y 编译实现进行研究，目的是提高x q u e r y 程序的执行效率；同时， 给x q u e r y 程序提供更多的优化机会。 x q u e r y 被w 3 c 发布为推荐标准，标志着对于x m l 查询有了一种统一标准 的描述方式，使用这种描述方式可以使x m l 的查询更加规范。许多公司以及组 织都陆续研发自己的x q u e r y 执行引擎，推出不同的x q u e r y 实现，如o r a c l e 的 x m ld b t l 6 17 1 、i b m 的d b 2p u r e x m l t l 8 - 1 9 2 0 2 1 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 m l 半结构化数 据的特点阻碍了查询效率的提高，因此x q u e r y 语言实现技术的研究一直受人关 注。 由于x m l 主要应用于数据的存储与表示，x q u e r y 主要被看作是一种查询语 言，用于对x m l 数据进行查询和组织，许多现有研究【2 2 】将x m l 与关系数据库 做比较，将x q u e r y 与s q l 进行比较，并借鉴关系数据库领域的理论来研究 x q u e r y 的实现技术。关系数据库领域有一些成功的经验、成熟的理论可以提供 参考，如关系模型与关系代数，基于代数的优化手段，查询重写等，使用这些技 术可以高效地实现s q 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 数据进行查询。 在另一个方面，和众多的解释实现相比，编译实现f 2 3 2 4 2 5 】的方式往往有更高 的执行效率。研究x q u e r y 的编译实现重点是研究如何将x q u e r y 源程序编译为 等价的低级语言程序，如字节码，以及如何根据语言的特点在编译中引入优化的 机会。研究编译实现技术可以提高目标程序执行效率，通过编译生成的代码，是 低层次的，更面向机器，这种代码在执行的时候可省去解释执行所带来的前端编 译的开销，编译出的代码常常拥有更高执行效率。除此之外，引入编译的另一好 处就是为优化创造机会，由于解释执行大多是翻译到一种中间表示形式后进行解 释，所以可以使用的优化手段只涉及到这种中间表示的层次，所提供的优化机会 较少，而在编译实现中，引入了多个中间层次，因此可以使用一些解释执行所不 2 第1 章绪论 能使用的优化策略，如尾递归的消除等，可以在不同的角度对不同的层次引入优 化策略，增加了优化的机会。 除此之外，编译系统也可以嵌入到解释系统中，执行时对高频使用的代码段 进行编译实现，采用类似于h o t s p o t 2 6 刀瑚】的策略，实现动态编译，获得更高的 执行效率。因此，静态编译技术的研究是实现动态编译系统的基础。 1 3 相关研究与研究现状 1 3 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 时从 不同的技术角度考虑，采用不同的优化策略，最终优化的效果也不一。 ( 1 ) 纯解释执行方式 q i z x o p e n t 2 9 】是a x y a n a 从2 0 0 3 年开始提供的一个开源的x q u e r y 引擎，基本 实现了x q u e r y 规范中规定的语言特性，测试通过了大部分w 3 c 对于x q u e r y 的测试用例。q i z x o p e n 是q i z x 系统的前身，二者在访问x m l 的方式上有所不 同，q i z x 系统重点放在了x m l 数据的持久性存储上面，而q i z x o p e n 更注重于 x q u e r y 的语言功能实现。q i z x o p e n 对于x q u e r y 查询内部采用纯解释执行的方 式，将x q u e r y 翻译为一种抽象表达式树，逐一解释执行。这种引擎提供了简单 的x q u e r y 规范实现，具有较高的参考价值，尽管这种实现方式简单易懂，但是 提供的优化手段比较少。 作者所在实验室开发的g e o q u e r y t 3 0 引3 2 】系统也是一种采用纯解释执行方式 的x q u e r y 引擎，支持多数据源的异构数据集成和g m l 空间数据集成。 ( 2 ) 查询代数和t w i g 查询优化技术 在x q u e r y 弓l 擎的实现中引入了查询代数技术。如g a l a x 3 3 3 4 3 5 】，起初的目的 是作为x q u e r y 的参考实现，后来随着工作的的进展，g a l a x 逐渐地提升系统性能， 在其实现中引入了编译阶段，但其所谓的“编译 是引入查询代数，h vj a g a d i s h 等人为g a l a x j j l ：l 入了舭专用的查询代数_ t a x 【3 6 1 ，包括带标签的有序树模型 以及专用的查询算子，g a l a x 将x q u e r y 编译为查询计划，最后再由引擎解释执行 查询计划，返回结果。 像g a l a x 等x q u e r ) r 引擎设计借鉴了数据库查询优化的思路，在x q u e r y 实现 中引入了查询代数。由于数据库中针对查询代数的实现与优化技术已经比较成 熟，在x q u e r y 实现中可以使用类似的查询优化手段，因此，此类引擎在执行查 询时有较好的性能。 3 北京工业大学工学硕士学位论文 除了x q u e 哆查询代数的研究，t w i g 模式查询技术的研究也是一个重要的研 究方向。此类算法大多将x m l 查询请求转换为一种自定义的查询模式，如基于 树的模式( t w i g 模式) ，采用模式匹配的方式将符合模式的x m l 数据实例求出， 尽量减少中间结果数量以及对x m l 文档树的扫描次数。该类算法主要的代表有： t w i g s t a c k 3 7 1 、t w i g l i s t t 3 钔、t w i 9 2 s t a c k 3 9 1 ，这类算法的特点表现为用于实现模式 匹配的结构连接算法的高效实现。 ( 3 ) 编译实现方式 q e x o 4 0 4 1 是g n u t 4 2 】实现的x q u e r y 执行引擎，它部分实现了x q u e r y 语言。 q e x o 使用了编译实现的方式，将一个x q u c r y 源程序编译为可执行的j a v a 字节 码，并加载到j a v a 虚拟机中执行。q e x o 在底层使用了k a w a t 4 3 4 4 框架。k a w a 是 一个j a v a 实现的通用的编译框架，用于将高级语言或动态语言编译为j a v a 字节 码程序，在语言实现中只需要将一种高级语言转换为k a w a 指定的中间形式，k a w a 就可以方便地将其翻译为j a v a 字节码程序。q e x o 系统对输入的x q u e r y 程序做 语法分析，并将其转换为k a w a 规定的中间表达式树，然后交由k a w a 对树遍历 进行翻译，生成可执行的j a v a 字节码形式的目标程序。 q e x o 等引擎从程序设计语言实现的角度出发，将x q u e r y 作为一种编程语言， 对其进行多级转换，最终得到可执行代码。这些引擎在编译过程中可以使用一些 通用的语言实现与优化方法，使得编译后的代码能够更高效的执行；同时，由于 q e x o 系统侧重于从一种编程语言的角度实现x q u e r y ，x m l 数据相关的操作并 不是研究重点，与x m l 相关的优化策略应用较少，也失去了一些优化机会。 这些引擎在对x q u e r y 的实现中采用了不同的思想，从各种角度对x q u c r y 这种语言进行考察，为本论文的研究工作提供了很好的参考。 1 3 2s e c d 抽象机研究现状 2 0 世纪6 0 年代，l a n d i np e t e r 提出t s e c d 抽象机【4 5 4 e 4 7 】的概念。s e c d 抽象机 作为是一种经典的操作语义，可以用于入表达式的求值，经常在程序设计语言的 验证与实现中被引入。s e c d 抽象机为操作语义1 4 & 4 殳5 0 】提供了一个简单而清晰的 描述，广泛地应用于编译领域。s e c d 抽象机的实现方式是多种多样的，同时许 多实现对s e c d 机进行必要扩充以符合各种需求。k e ns l o n n e g e r 使用p r o l o g 逻辑 程序设计语言实现了s e c d 抽象机【5 1 ；j o h nd r a m s d e l l 提出了基于尾递归实 现的s e c d 抽象机【5 2 】等。 以上关于s e c d 抽象机研究成果为x q u e r y 实现的抽象机实现模型提供了借 鉴，并为x q u e r y 语言的编译过程提供了理论基础。 4 第l 章绪论 1 4 课题来源 本研究得到北京市自然科学基金( 项目编号：4 0 8 2 0 0 3 ) 的支持，项目名称： x q u e r y 语言动态编译技术的研究。 1 5 本文的研究工作 本文得主要研究工作基于s e c d 抽象机的x q u e r y 编译实现技术，在原有的 x q u e r y 解释系统g e o q u e r y 的基础上研究x q u e r y 的编译实现方案。 g e o q u e r y 系统是课题组前期研制的x q u e r y 实现系统。该系统采用解释执行 方式；输入的x q u e r y 程序被翻译为抽象语法树，然后被转换为中间语言f x q l 的代码序列，最后由一个解释程序完成f x q l 代码的解释执行。 在x q u e r y 编译系统的实现中，采用了g e o q u e r y 系统前端提供的语法分析、 中间代码生成等模块，开发了编译后端系统，实现了从f x q l 语言到s e c d 抽 象机指令序列的翻译和从s e c d 抽象机指令序列到j a v a 字节码目标代码的翻译。 本文的研究工作如下： 1 分析了f x q l 的语言特点与s e c d 抽象机的运行机理，设计了用于实现 f x q l 的s e c d 抽象机及其指令系统。 2 分析了f x q l 语言的结构，设计并实现了f x q l 程序到s e c d 抽象机指 令序列的翻译算法。 3 设计并实现了高性能的目标程序运行支撑环境，并开发了测试用的s e c d 抽象机指令解释执行引擎。 4 研究s e c d 抽象机指令的优化策略，设计并实现了尾递归消除1 5 3 ，5 4 彤1 等代 码优化策略。 j a v a 字节码目标程序结构的设计、以及目标代码生成程序的设计与实现由本 组其他同学负责完成。 1 6 本文结构 本文的内容组织如下： 第1 章绪论。主要介绍课题的背景、来源，研究基于s e c d 抽象机的x o u e r y 编译实现目的和意义，以及本文的主要工作内容。 第2 章基于s e c d 抽象机的x q u e r y 编译系统的解决方案。首先介绍了x m l 查询语言x q u e 口，接下来介绍课题组原有的x q u e r y 的解释实现基础 g e o q u e r y ，这些内容都是x q u e r y 编译实现的工作基础。然后，详细介绍了x q u e r y 5 北京工业大学工学硕士学位论文 的编译实现方案，包括编译器的体系结构，以及各模块的介绍，重点阐述引入各 模块的原因。最后给出一个案例介绍x q u 睨y 编译实现方案的工作流程。 第3 章s e c d 抽象机与指令系统的设计。本章首先介绍了f x q l 语言的构 成，以及如何根据f x q l 的语言特点设计s e c d 抽象机及指令，并给出了基本 指令的操作语义，同时介绍了如何设计s e c d 抽象机指令来实现f x q l 原语函 数。 第4 章s e c d 抽象机指令的生成。主要介绍了s e c d 抽象机指令序列的生 成技术，主要包括如何将f x q l 程序翻译为s e c d 抽象机指令序列，系统对f x q l 基本语法元素和f x q l 原语采用了不同的翻译方式，以及如何优化指令序列，为 了消除一些函数调用的开销，系统引入了尾递归消除的优化手段。 第5 章x q u e w 编译后端的实现。对基于s e c d 抽象机的x q u e r y 编译实现 的后端实现进行介绍，为了检验翻译规则以及运行机制，系统实现了一个s e c d 抽象机指令的解释执行原型，在此原型中对抽象机的各抽象部件进行了模拟实 现。对于s e c d 抽象机的实现重点介绍了环境的实现设计，阐述了环境的实现方 案分层栈式，同时对其他部件的实现进行了介绍。本章还涉及了翻译算法的 实现，介绍了翻译中用到的辅助数据结构。 第6 章系统测试。对基于s e c d 抽象机的x q u e r y 编译实现进行了测试， 介绍y n 试方案并以图表的方式给出了测试结果，并对结果进行分析，给出测试 结论。 最后在结论部分对本文的工作进行了整体总结，并分析了进一步研究的方 向。 6 第2 章基于抽象机的x q u e r y 编译系统 l m 一一 mi i i m 。mm 曼曼曼 第2 章基于抽象机的x q u e r y 编译系统 随着x q u e r y 语言的标准化以及广泛应用，其执行效率成为了主要关注点之 一。纵观各种计算机语言的实现，如c + + 、j a v a 等，编译技术在提升语言执行效 率的过程中起了重要的作用，编译期间可以进行代码优化，编译得到的目标程序 ( 二进制代码) 可以较高效地在目标机上运行，从而提高运行速度。本章首先介 绍x q u e r y 语言，在此基础上介绍已有的解释实现基础，主要介绍了基于s e c d 抽象机的x q u e r y 编译解决方案，并给出一个实例展示编译实现方案。 2 1x q u e r y 语言 2 1 ix m l 查询语言 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 工作组于1 9 9 8 年2 月正式推出了x m l1 0 版本。x m l 具有一些被公认 的优点：纯文本表示，具有平台无关性；信息的内容与信息的表示是分开的，能 够满足各种不同的应用需求等。x m l 还有一个很大的优点就是具有自描述性， 因为通过x m l 文件的d t d ( d o c u m e n tt y p ed e c l a r a t i o n 文档类型声明) 和 x m ls c h e m a 就可以定义数据集的结构信息。 由于x m l 能够根据具体应用灵活地表现异构数据源中的各种信息，包括应 用程序之间的数据交换、结构化和半结构化的文档以及数据库中数据的输出。所 以，越来越多的信息开始采用x m l 进行存储、交换和表现，因而如何有效且高 效地存取x m l 信息，提供跨越不同数据源的基于x m l 信息的查询检索能力变 得日益重要。开发人员迫切需要一种灵活易用、针对各种类型x m l 数据源的查 询语言。 虽然x s l t 和x p a t h 可以在一定程度上满足上述需求，但是其书写的复杂程度 和功能的不完善使其远远不能达到人们的要求。人们需要的是一种类似于s q l 语 言的、简单且易于编写的x m l 数据查询语言。作为x m l 标准的主要制定机构， w 3 c ( w o r l dw i d ew e bc o n s o r t i a m ) 成立了x m l 查询工作组，其任务是创建一 种灵活的查询语言来实现从x m l 文档中获取数据，具体目标是：为x m l 文档建 立一个数据模型、基于该数据模型的一组查询运算符以及建立在这些查询运算符 操作之上的查询语言。 鉴于此，w 3 c 的x m l 查询工作组制定出了x m l 查询语言规范x q u e r y 语言。x q u e r y 是一种从x m l 格式的文档中获取数据项的查询语言。x m l 模糊 7 北京工业大学工学硕士学位论文 了数据库、文档和消息之间的界线， 须要有一种强大而优雅的查询语言， 需的语言。 2 1 2x q u e r y 简介 但是，要充分发挥x m l 的所有潜能，还必 x p a t h 还远不够，x q u e r y 正在试图成为所 随着w c 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 q 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 贝j j 是对建 立在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 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 也是一种强结构化的语言， 表达式中的操作数、操作符、函数都必须遵循已经定义好的模式。 2 1 3x q u e r y 语言的构成 一个x q u e r y 查询由查询序言和查询体组成。查询序言是一系列的声明和定 义，建立了查询处理的环境，主要包括命名空间声明、s c h e m a 导入、定义用户 自定义函数等。 查询体由定义查询的表达式序列构成： q u e r y b o d y ：= e x p r 表达式序列则由多个表达式组成： e x p r ：= e x p r s i n g l e ( ，”e x p r s i n g l e ) 第2 章基于抽象机的x q u e r y 编译系统 2 1 4 x q u e r y 表达式 一个x q u e r y 查询包含一个或多个查询表达式。下面简要介绍几类x q u e r y 表达式。 ( 1 ) 路径表达式 在x q u e r y 中，路径表达式的语法就是x p a t h2 0 的语法。它们使用路径标记 从x m l 文档中选择感兴趣的节点。x p a t h 把x m l 文档看作是节点树。一个p a t h 表达式描述了浏览这个节点树从而找到感兴趣的节点的方式。其语法和u n i x 中 文件系统的路径表示方法类似。 ( 2 ) f l w o r 表达式和元素构造表达式 x q u e r y 中最强大的特性是f l w o 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 的首字母缩略词。f l w o r 表达式包 含模式匹配、过滤选择和结果构造这三种操作。 f l w o r 语句是x q u e r y 所具有的最接近于s q l 的语句。使用f l w o r 语 句，可以用比x p a t h 语句更自然的方法来创建特定的查询。它支持循环并且可 以把变量绑定到中间结果。对两个或多个文档进行连接和重构数据时这种表达式 非常有用。每个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 子句。 f o r 子句通过将节点绑定到变量，以便继续去循环遍历序列中的每一个节点：l e t 子句为一个变量赋一个值或一个序列；r e t u r n 子句定义每个元组要返回的内容； 对于w h e r e 子句，如果其有效布尔值为真，那么该元组就被保留，并且它的变量 绑定用在r e t u r n 子旬中，如果其有效布尔值为假，那么该元组就被废弃。 例如，表2 1 的查询中包含了f l w o r 表达式与元素构造表达式的组合： 表2 1 ) ( q u e r y 程序例( f l o w r 表达式和元素构造表达式) t a b l e2 - 1x q u e r yp r o g r a me x a m p l e ( f l o w re x p r e s s i o na n dc o n s t r u