（计算机软件与理论专业论文）基于延迟求值的xquery语言实现技术.pdf

摘要 摘要 x m l 事实上已经成为万维网上的数据的通用格式标准，无论是消息、网页、 本地文件还是数据库，都把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 查询的函数式语言。 延迟求值是函数式语言的一种重要优化手段。在数学表述方面，延迟求值对 应着入演算的规范规约，有着深刻的数学背景。在程序设计方面，延迟求值语义 下的程序更具有声明性。对于典型的函数式语言，一些优化方式，例如不变计算 的提升( h o i s ti n v a r i a n tc o m p u t a t i o no u to ff u n c t i o n ) 和死代码的移除 ( d e a d - c o d er e m o v a l ) ，不经仔细分析，在脱离延迟求值语义的情况下是无法采 用的，因为这样会改变程序执行的终止性。 对于x q u e r y 语言的处理器，延迟求值是一种可用的并且是主要的优化技术。 通过延迟求值，可以消除不必要的计算，可以构造和访问数据量很大的有限、无 限的序列。对于x m l 数据流的处理，使用延迟求值方式可以显著地减小x m l 中间 数据的存储空间开销，提高系统的执行效率。 为了采用延迟求值优化技术提高x q u e r y 语言的执行效率，本文介绍了 x q u e r y 语言的延迟求值器一) ( m lq u e r yl a z ye v a l u a t o r ( x q l e ) 。系统采用形式简 洁的函数式语言一f u n c t i o n a lx m lq u e r yl a n g u a g e ( f x q l ) 作为中间语言。在数 据模型上，x q l e 使用可以容纳闭包和x m l 结点的广义表，支持广义表结点的延 迟计算。对于x m l 数据的获取，采用延迟模式消除了与计算结果无关的数据的获 取开销。在相当多的程序平均执行速度的对比上，采用延迟求值模式的求值器优 于采用积极求值模式的求值器。 关键词函数式语言；) ( m l ；x q u e r y ：延迟求值；广义表 a h s t r a c t 一i li | | 舅| 一 a b s t r a c t x m list h ed ef a c t od a t af o r m a ts t a n d a r df o rt h ew o r l dw id ew e b m a n y d i f f e r e n tk i n d so fd a t a ，i n c l u d i n gm e s s a g e s ，w e bp a g e s ，l o c a lf il e sa n d d a t a b a s e s ，u s ex m la st h ef o r m a tf o rd a t as t o r a g ea n de x c h a n g e t o w a r d s l a r g ea m o u n t so fx m lr e s o u r c e so nt h ew e b ，t h ei s s u e so fi n t e l li g e n t l y q u e r y i n ga n do r g a n i z i n gt h ex m ls e g m e n t so fu s e ri n t e r e s ta r ee x t r e m e l y i m p o r t a n t x q u e r yi sd e s i g n e dt o t ob es u c haf u n c t i o n a lp r o g r a m m i n g l a n g u a g ei nw h i c hx m lq u e r i e sa r ec o n c i s ea n de a s il yu n d e r s t o o d l a z ye v a l u a t i o ni sa ni m p o r t a n to p t i m i z a t i o nt e c h n i q u eo f t e nu s e di n f u n c t i o n a lp r o g r a m m i n gl a n g u a g e l a z ye v a l u a t i o nc o r r e s p o n d st on o r m a l o r d e rr e d u c t i o ni nm a t h e m a t i c s t h ep r o g r a mu n d e rl a z ys e m a n t i c si sm o r e d e c l a r a t i v et h a nt h ee a g e ro n e o nt h eo t h e rh a n d ，t h ee a g e rc o m p il e r s o ff u n c t i o n a ll a n g u a g e sc a n n o td os o m ek i n d so fo p t i m i z a t i o n s ( e g h o i s t i n v a r i a n tc o m p u t a t i o no u to ff u n c t i o n ，d e a d c o d er e m o v a l ) w i t h o u tc a r e f u l a n a l y s i s t h er e a s o ni st h a tw em i g h tc h a n g et h et e r m i n a t i o np r o p e r t yo f ap r o g r a ma f t e rd o i n gt h eo p t i m i z a t i o n f o ra nx q u e r yp r o c e s s o r ，l a z ye v a l u a t i o ni so n eo ft h ec h i e f o p t i m i z a t i o nt e c h n i q u e sa v a i l a b l e i n f i n i t es e q u e n c ec a nb eb u i i ta n d v i s i t e du n d e rl a z ym o d e a n o t h e rb e n e f i tb r o u g h tb y l a z ye v a l u a t i o ni s t h ed e c r e a s eo fs t o r a g ea n dc a l c u l a t i o no v e r h e a df o ri n t e r m e d i a t ed a t a i n ) ( m ld a t as t r e a mp r o c e s s i n g i no r d e rt oa c c e l e r a t et h ee x e c u t i o no fx q u e r y ，t h i sp a p e ri n t r o d u c e s a ne v a l u a t o rn a m e da sx m lq u e r yl a z ye v a l u a t o r ( x q l e ) ，w h i c hu s e sl a z y e v a l u a t i o no p t i m i z a t i o nt e c h n i q u e t h ei n t e r m e d i a t el a n g u a g ei s f u n c t i o n a lx m lq u e r yl a n g u a g e ( f x q l ) t h a ti saf u n c t i o n a ll a n g u a g ew i t h c o n c i s ef o r m f o rd a t am o d e l ，x q l eu s e sg e n e r a l i z e d1 i s tw i t ht h ea b i l i t y t oh o l dc l o s u r ea n dx m ln o d et os u p p o r tl a z yc a l c u l a t i o no fli s tn o d e u n d e rl a z ym o d e ，t h eo v e r h e a do fa c q u i r i n gt h ed a t at h a th a sn o r e l a t i o n s h i pt ot h ef i n a lr e s u l to fc a l c u l a t i o nc a nb ee l i m i n a t e d f i n a l l y ， w eu s eal o to fe x a m p l ep r o g r a m st os h o wt h el a z ye v a l u a t o rh a sb e t t e r p e r f o r m a n c ec o m p a r e dw it he a g e re v a l u a t o ri nt h ea v e r a g ee x e c u t i o ns p e e d k e y w o r d sf u n c t i o n a ll a n g u a g e ；x m l ；x q u e r y ；l a z ye v a l u a t i o n ；g e n e r a l i z e d 1 i s t i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：z 奎壁i 兰日期：兰塑：兰：! 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：签遂导师签名：签名：公遂 导师签名： 第1 章绪论 i iii_i曩 1 1 课题背景 第1 章绪论 2 0 0 7 年1 月，w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ) 正式批准通过了x m l q u e r y ( 简称为x q u e r y ) 语言规范乜t 引，这标志着一种无论对工业界还是学术界都有巨 大意义的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 q u e r y 是一种能够简洁和清晰地表达x m l 查询的函数式 语言。在x q u e r y 语言规范发布之前，有两个重要的规范一x m ls c h e m a 规范h r 洲 和x p a t h 规范影响了它。通过x m ls c h e m a 可以描述x l d l 文档的结构和文档内 部的各种合法结点类型，而x p a t h 则提供了对x m l 文档进行导航的能力。x q u e r y 语言把x p a t h 集成进语言特性中，把x p a t h 作为一个子集，并且补充了可编程 的特性。通过这三者的结合，用户可以使用一种类型系统完善的一阶函数式查询 语言对x m l 数据进行查询和组织。从s u n 公司设计x q u e r y 的j a v a 编程接l 的 j s r 2 2 5 ：x q j 哺1 工作组的进展来看，x q u e r y 语言对于x m l 的查询作用类似于s o l 语言对数据库的查询作用。 本文针对x q u e r y 语言，介绍了采用延迟求值旧1 0 1 优化技术的求值器一x m l q u e r yl a z ye v a l u a t o r ( 简称为x q l e ) 。 1 2 研究意义 一般来说，延迟求值是函数式语言的一种求值方式，相对于积极求值n 。延 迟求值的基本思想是：只有真正需要值的时候才去求值。传统的积极求值方式执 行的语言，对于函数调用的参数和变量初始化的定义体要立即进行求值，但是之 后的程序可能并不使用这些变量，在特定情况下会产生较大的时间和空间浪费。 除此之外，对于积极求值的执行引擎来说，如果不经仔细的分析，不变计算的提 升、无用代码消除这些优化方法不能使用。原因在于这些方法的引入可能把能够 正常执行结束的程序变为不能执行结束的，或者把不能执行结束的程序变为能够 执行结束的。如果这个引擎采用的是延迟求值的求值方式，这些优化方法就可以 直接采用n 副。对于x q u e r y 语言的处理器来讲，对于那些求值结果从不被程序的 其他部分使用的表达式不进行求值处理，是可用的优化技术n 文14 。此外，通过采 用延迟求值技术，可以使执行引擎具有构造无限序列的能力n5 1 ，通过基于p u l l 北京工q p - 入学工掌硕士学待论文 方式的接口进行适当粒度的数据的获取引。在x m l 数据流处理方面，采用延迟求 值语义的流水线方式，消除积极求值语义下流水线模块的中间结果的构造，就可 以处理无限序列的x m l 数据流的情况。应用这种方式，可以显著地减小内存开销， 加快执行速度，从而提高系统执行效率n 力。 本研究的基础是课题组开发的g e o q u e r y 系统n & 1 9 , 2 0 , 2 1 。该系统是一个地理信 息数据集成系统，采用m e d i a t o r - w r a p p e r 的方式集成异构地理信息数据，采用 基于x m l 标准的g m l 格式3 1 作为通用的数据表示，采用支持网络多数据源和空间 数据处理的扩展x q u e r y 语言作为空间信息集成的通用数据查询语言，从而形成 完整的空间信息集成模型，使其支持空间信息和非空间信息的无缝连接、分布式 数据查询和数据集成，支持基于多空间数据源的分布式应用系统的数据建模和软 件开发。 g e o q u e r y 系统把对x q u e r y 语言翻译为一种语义清晰的函数式中间语言 叶u n c t i o n a lx m lq u e r yl a n g u a g e ( 简称为f x q l ) ，该语言在语法上类似于p e t e r l a n d i n 的i s w l m 函数式语言模型口刳。f x q l 的基本功能通过原语函数来完成。 本论文的研究目标是针对f x q l 语言的实现问题，通过采用延迟求值优化技 术，提高g e o q u e r y 系统对x q u e r y 语言的执行效率。 1 3 相关研究 英国s a x o n i c a 公司的s a x o n 比巩2 1 ，实现了x m lq u e r y1 0 和x s l t2 0 语言 规范乜5 26 1 。s a x o n 有两个主要版本，商用版本和开源版本。其中商用版本支持x m l s c h e m a 导入。由于x q u e r y 和x s l t 的核心语义和可完成的功能比较相似，作为 x s l t 的设计人和w 3 cx q u e r y 工作组的主要成员，s a x o n 的独立开发人m i c h a e l h k a y 把s a x o n 系统实现中的x q u e r y 和x s l t 表示统一起来。该系统实现了大 量的常用查询重写优化手段，比如常量折叠、公共子表达式消除和循环不变量的 提升。作为执行方面的优化，该系统实现了延迟求值，针对的是x p a t h 表达式层 面的延迟求值，并且主要考虑的是在特定情况下，进行一些谓词合并和序列共享 的优化。在该系统的实现中，没有设置中间语言一层，因此不能做彻底的延迟求 值，只能对比较典型的情况进行处理。s a x o n 系统对x q u e r y 执行结果数据的获 取方式采用管道、迭代器的方式，但不具有构造无限序列的能力。 美国c o g n e t i cs y s t e m s 公司的x q u a n t u m ) ( f ld a t a b a s es e r v e r 是一个n a t i v e x m l 数据库瞳7 - 2 引。它支持x q u e r y 的一个子集，x q u e r y 全文规范的一个子集和x s l t 。 x q u a n t u m 通过一个基于开销的算法进行查询优化，也即通过关于数据的统计数 据来优化查找过程。查询处理器依赖“递归x m l 索引 ( 一个与模式无关的索引 方法) ，支持查询的延迟求值和查询的流式处理。x q u a n t u m 是被设计用来满足大 第1 章绪论 规模x m l 数据存储的x m l 数据库，通过引入延迟求值和流式处理可以减小大规模 查询结果集所带来的内存开销。 e x i s t 晗剀是一个g n ul g p l 许可保护下的开源软件，它实现一个基于j a v a 的 n a t i v ex m l 数据库，并且拥有一个x q u e r y 接口。它使用延迟求值来处理x q u e r y f l w o r 表达式的r e t u r n 语句。也就是，直到数据库接收到串行化一个片断的请 求时，才去构造实际的真实片断。对于大多数应用来说，只把结果集的一小部分 展示给用户。为了避免内存耗尽，限制产生结果的数量为实际需要展示的数量。 俄罗斯科学院系统编程所的m o d i s 小组开发了两个x q u e r y 相关的系统， s e d n a 口町和b i z q u e r y 口。s e d n a 是一个n a t i v ex m l 数据库系统，提供了内容管理、 基于事件的s o a 等x m l 应用，并且是一个提供全部数据库核心服务( 查询、更新、 事务、恢复、安全) 的全特性数据库系统，它通过x q u e r y 语言来提供灵活的x m l 处理。b i z q u e r y 是一个虚拟数据集成系统，可以把不同数据源的语义相关的数 据进行垂直集成。这些数据源可以是基于x m l 的，关系型的。通过给定的描述数 据源关系和依赖的映射规则，在运行时该系统完成数据集成。全局数据数据模式 可以通过u m l 和x m ld t d 来建模。x q u e r y 是其内部实现的处理x m l 文档的语言。 这两个系统内部的x q u e r y 执行考虑到了积极求值语义和延迟求值语义的切换。 因为经过分析，虽然延迟求值语义适合于函数式语言和流式数据中不需要的数据 的物化，但过度依赖延迟求值语义会造成程序性能的下降。因此在他们的实现中， 执行会根据当前情况选择是使用积极求值模式还是延迟求值模式。如果函数调用 的参数非常容易计算，直接求参数即可。反之亦然，如果在积极求值模式下的物 理操作需要大规模的输入序列，这时应该切换到延迟求值模式口引。 1 4 课题来源 本课题来源于北京市自然科学基金项目( 4 0 5 2 0 0 6 ) ：面向空间数据集成的统 一数据查询语言的研究。本课题组总的目标是设计和实现一个基于g m l ) ( m l 和扩 展x q u e r y 空间数据集成系统。该系统屏蔽了地理信息的分布性和异构性，提供 高效的空间信息查询服务。 1 5 研究内容 本文的研究内容在于基于延迟求值的x q u e r y 语言实现。 ( 1 ) 扩展w 3 c 定义的x q u e r y 数据模型x d m ( x q u e r yd a t am o d e l ) 3 4 p 设 计并实现x q u e r y 延迟求值器x q l e 的数据模型： ( 2 ) 对于g e o q u e r y 系统的x q u e r y 执行引擎，设计并实现其中间语言f x q l 的延迟求值策略； 北京工业人学丁：学硕士学僚沦文 ( 3 ) 设计并实现x q u e r y 引擎的各种原语函数的延迟求值策略； ( 4 ) 测试延迟求值器实现的正确性和有效性，设计测试用例，对比用例优 化前与优化后的执行时间。 1 6 本文结构 本文第2 章一x q u e r y 语言和中间语言f x q l ，介绍了延迟求值器x q l e 所针对 的语言对象；第3 章一f x q l 求值策略，是本文的重点，展示了引入延迟求值的 f x q l 求值策略，进而细化为求值规则，指导求值器的实现；第4 章广义表数 据模型，介绍了延迟求值器x q l e 所使用的数据模型，该数据模型扩展了w 3 c 的 x d m 数据模型，能够满足延迟求值的需要；第5 章一x q u e r y 语言的实现，介绍了 集成延迟求值器的x q u e r y 查询处理引擎的结构和实现；第6 章优化效果分析， 通过实例进行测试，比较采用延迟求值优化前和优化后的系统执行效率，分析说 明优化效果。 第2 章x q u e r y 语言和中语青f x q l i i iiii 一一i 量一 第2 章x q u e r y 语言和中间语言f x q l x m l 是一种多用途的标记语言，能够表示结构化和半结构化的文档、关系数 据库、对象仓库等不同的数据源中的信息内容。如果一种查询语言能够灵活地利 用x m l 的结构，那么这种语言就可以表达跨多种数据源的查询，这些数据源或者 是存储为x m l 格式，或者通过中间件以x m l 格式展示。x q u e r y 语言就是被设计 为具有x m l 数据源查询能力的查询语言。 x q u e r y 语言适于作为数据集成系统的通用查询语言，并且可以自动翻译为 等价的具有简洁形式的函数式中间语言f x q l 。 2 1x m l 与x 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 m 文档类型声明) 和x m l s c h e m a 就可以定义数据集的结构信息。 x m l 作为一种文档标记语言，已被广泛接受和使用，各大软件生产商特别是 数据库生产商纷纷把支持x m l 作为一个重要的发展方向。 由于x m l 能够根据具体应用灵活地表现异构数据源中的各种信息，包括应用 程序之间的数据交换、结构化和半结构化的文档以及数据库中数据的输出。所以， 越来越多的信息开始采用x m l 进行存储、交换和表现，因而有效且高效地存取 x m l 信息，提供跨越不同数据源的基于x m l 信息的查询检索能力变得日益重要。 开发人员迫切需要一种灵活易用、针对各种类型x m l 数据源的查询语言。 同时，随着存储在) 【m l 文档中的信息量飞速增长，x m l 日益成为i n t e r n e t 上数据交换的标准，人们需要一种能够方便交换x m l 数据的手段。由于x m l 具有 自描述性且与平台无关，所以交换x m l 数据的途径也应该是与平台无关的。要实 现这一点，必须要有一种能够从x m l 文档中准确获得所需信息的查询语言。作为 x m l 标准的主要制定机构，w 3 c 成立了x m l 查询工作组，其任务是创建一种灵活 的查询语言来实现从x m l 文档中获取数据，具体目标是：为x m l 文档建立一个数 据模型、基于该数据模型的一组查询运算符以及建立在这些查询运算符操作之上 的查询语言。 虽然x s l t 和x p a t h 可以在一定程度上满足上述需求，但是其书写的复杂程 度和功能的不完善使其远远不能达到人们的要求。人们需要的是一种类似于s q l 北京工q p 入学工学硕士学能沦文 语言的、简单且易于编写的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 模糊了数据库、文档和消息之间的界线，但是， 要充分发挥x m l 的所有潜能，还必须要有一种强大而优雅的查询语言，x p a t h 还 远不够，x q u e r y 正在试图成为所需的语言。 2 2x o u e r y 语言 随着w e bs e r v i c e s 技术的不断普及，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 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 o 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 将查询表示成表达式，它支持多种表达式，因此，它的查询可以有 多种不同的形式。各种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 2 1x o 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 6 第2 章x q u e r y 语青平巾问语言f x q l 表达式序列则由多个表达式组成： 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 2 2x o u e r y 表达式 一个x q u e r y 查询包含一个或多个查询表达式。下而简要介绍几类x q u e r y 表 达式。 2 2 2 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 2 2 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 一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 子句中，如果其有效布尔值为假，那么该元组就被废弃。 例如，下面的查询： f o r $ b o o ki nd o c ( 。li b r a r y x m l ) b o o k ， l e ts t i t l e ：= s b o o k t i t l e w h e r es b o o k p u b l i s h e r = a d d i s o n w e s l e y r e t u r n s t i t l e ) 含义为：“对于文档中的每本b o o k ，将它绑定至u $ b o o k 变量上，同时将b o o k 北京工、i k 人学工学硕士学 节论文 的t i t l e 子元素绑定至l j $ t i t l e 变量上，如果书籍的出版商是a d d i s o n w e s l e y ， 则返同包含s t i t l e 元素的b o o k i n f o 元素。” 该查询展示了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 的 这些特性使其非常适合承担异构数据集成系统中查询分解和结果重构的任务。 2 2 2 3 条件表达式 x q u e r y 语言中也含有高级语言中代表程序控制逻辑的表达式。比较明显的 是i f 表达式。在查询语句中，可以使用i f t h e n e l s e 这样的选择结构， 比如下例： f o r $ ii nd o c ( b i b x m l ”) b i b v e n d o r b o o k r e t u r n i f ( $ i p r i c e 7 0 ) t h e n $ i t i t l e ，$ i p r i c e ) e l s e ( $ i t i t l e ，$ i p r i c e ) 2 2 3x o u e r y 语言的特点 作为查询语言，x q u e r y 有很多的特性和传统查询语言类似。首先，如前文 所述，x q u e r y 通过f l w o r 表达式支持很多查询语言中常见的操作，如选择、排 序、分组等，使得x q u e r y 的使用者可以方便地表示查询意图。第二，x q u e r y 的 数据模型严格限制在x m l 能表现的值域之内。x q u e r y 的数据模型包括结点和原 子值的序列，但是不包含集合( s e t ) 、包( b a g ) 、嵌套的序列等类型，但是在本 系统中扩展了数据模型，使x q u e r y 能够支持广义表( 即嵌套的序列) 。最后， x q u e r y 是声明式语言，它的语义允许同一个查询存在不同的查询策略，这使得 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 支持用户自定义函 数，函数之间可以嵌套调用，也可以递归调用。 8 第2 章x q u e r y 语膏和中问语言f x q l 2 3 中间语言f x o l 鉴于x q u e r y 是一种函数式语言，为了便于后续的优化处理，引入基于入演 算的采用延迟语义的中间语言f x q l 。x q u e r y 程序被翻译为形式简洁的f x q l 程序 之后，易于延迟求值技术的应用。 x q u e r y 是一种同时具有查询语言和编程语言特性的语言，它能够对各种结 构复杂的x m l 文档进行数据的检索、处理和转换，具有强大的表达能力和高度的 灵活性。f x q l 语言作为x q u e r y 查询在系统内部的抽象表示，精确地描述用户的 查询意图和执行动作。 2 3 1f x q l 语言的特点 f x q l 语言的特点主要表现在以下几个方面： 是一种函数式语言，无副作用； 用于描述查询计划； 支持函数和递归函数的定义和调用； 支持函数作为参数； 是一种x m l 查询语言，提供了丰富的原语函数，来完成各类数据处理和 程序逻辑控制的任务。 f x q l 是一种函数式语言，以函数调用为基本结构。一个函数语言程序就是 一个由函数嵌套调用构成的表达式。由于函数式语言具有良好的数学理论基础， 它在问题的描述及解决方面，就更加面向问题本身，而与计算机的实现细节无关。 在命令式语言中，命令会改变以前的命令所给予的变量名与值的关系，在程 序运行时，会导致一个变量名在不同时刻与不同的值相联系，这就是副作用 ( s i d e e f f e c t ) 。函数式语言则是无副作用的( s i d e - e f f e c tf r e e ) ，变量名或者 做为函数的参数并在函数调用时被赋予实际的参数值，或者通过变量绑定语句绑 定在一个固定的值上，变量一旦与实际值相联系就无法改变了。 f x q l 支持函数及递归函数的声明。递归函数使得f x q l 能够处理具有递归结 构的x m l 文档同时保持x m l 文档原有的树形结构。 在许多计算机语言中，子程序都可以作为参数传递给其他的子程序。f x q l 语言也具有这样的特性。在f x q l 中，使用了函数作为参数的原语有f o r e a c h 、 f o r e a c h a t 、f i l t e r 、f i l t e r a t 、q u a n t i f y s o m e 和q u a n t i f y e v e r y 。这些原语将 函数作为参数，在执行时才调用这些函数进行真正的运算。函数作为参数使得 f x q l 语言具备了更强的表达力和灵活性。 f x q l 语言为数据查询的实现提供了丰富的原语函数，用来完成各类数据处 理和程序逻辑控制的任务。例如，由于f x q l 不允许变量赋值，因此f x q l 无法像 9 北京工业人掌丁学硕士掌俺论文 命令式语言那样通过变量赋值来控制循环的终止和变量的迭代，只能用递归的方 式完成循环。为了能够比较简洁地处理循环结构，f x q l 提供了f o r e a c h 原语来 完成循环控制。此外，f x q l 设计中提供了) 【m l 结点构造、路径导航和数值计算 等各类函数。 2 3 2f x q l 的核心抽象语法 f x q l 语言是执行引擎执行动作的抽象，由计算机负责处理，它的形式应该 尽可能的简单，语义应尽量的明确。f x q l 的核心抽象语法如下： ( 1 ) e i d ( 2 ) e c ( 3 ) e 专i fet h e nee l s ee ( 4 ) e i d ( e 木) ( 5 ) e ew h e r eb 术 ( 6 ) b i d = e ( 7 ) b 专i d ( i d 木) = e 变量引用表达式 产生式l 表示变量引用，用于引用变量的值，对于f x q l 这个函数式语言， 变量也可以是函数名，这时变量的值就是函数闭包。 常数表达式 产生式2 表示常数。常数的数据类型主要来自x m ls c h e m a ，包括基本数据 类型，如x s ：s t r i n g 、x s ：i n t e g e r 等，也包括用户自定义类型，除此之外，还包 括s i n g l e q n a m e 类型，用来表示结点的名称。 条件表达式 产生式3 表示条件表达式，由判断条件、t h e n 子句和e l s e 子句组成。条件 表达式用i f t h e n e l s e 结构控制程序的运行逻辑。 函数调用表达式 产生式4 表示函数调用，其中i d 为函数名，括号中的多个表达式为调用该 函数时传递的若干参数。函数调用有两种类型，一种是系统内置函数的调用，作 者在本文中称为原语函数，另一种是自定义函数的调用，该类函数在查询中定义。 带局部求值环境的表达式 产生式5 表示带局部求值环境的表达式，由w h e r e 前面的主体表达式和w h e r e 1 0 第2 覃x o u e r v 语言和巾阃语青f x q l 一i i i | 量罾罾皇皇| | 罾量| 量量一 后面的若干条绑定子句组成，这些绑定子句作为执行主体表达式的环境。 变量绑定 产生式6 表示变量绑定，含义是把表达式求值的结果赋给变量。f x q l 将通 过变量引用表达式来访问变量绑定的值。f x q l 的变量绑定子句防止了表达式的 重复求值，不允许对同一个变量重复赋值，这一点和命令式语言的变量赋值语句 有显著的不同。 函数绑定 产生式7 表示函数绑定，含义是把函数体以及函数的若干参数( 括号中的多 个变量) 绑定到函数名f 上。引擎执行w h e r e 表达式的绑定子句时，通过扩展执 行环境来完成这些绑定动作。f x q l 可以通过函数调用表达式直接调用绑定的函 数，也可以将通过引用函数名把绑定好的函数作为其他函数的参数。 2 3x o u e r y 语言实现的问题 对于x q u e r y 语言的实现，考虑到无用实参的存在，通过减少、避免无用实 参的计算，即可提高查询的执行效率。 对于大数据量的x m l 查询，消耗的内存较大，通过消除中间结果的构造，就 能减少查询的内存占用。 考虑到对远端x m l 数据流进行查询处理的需求，由于无法一次性把数据序列 构造出来，因此需要一种实现机制来支持无限长序列的表示和处理。 引入延迟求值优化技术可以较好地解决以上几方面的查询处理需求。 2 4 本章小结 本章介绍了作为x m l 查询语言的x o u e r y 语言，为了应用延迟求值技术对 x o u e r y 的执行做优化，x q u e r y 程序被等价地翻译为函数式语言f x q l 的程序。f x q l 语言作为中问语言，具备较强的表达能力和简洁的形式。 第3 章f x q l 求位策略 iiii i i i o 一 第3 章f x q l 求值策略 为了应用延迟求值优化技术，需要对中间语言f x q l 进行分析，制定相应的 延迟求值策略，作为x q u e r y 语言延迟求值实现的依据。 3 1 延迟求值技术 从广义上来讲，延迟求值是一种计算思想，只有真正需要值的时候才去进行 计算。对于计算机程序的编译，延迟求值主要用于函数式语言的编译实现，比如 h a s k e l l 副和m i r a n d a 1 语言等。这是因为，首先，纯的函数式语言是无副作用 的，这是延迟求值的基础，在延迟求值和积极求值下程序的某些部分的执行次数 可能不同，如果是含有副作用的程序设计语言，这会得出程序编写人员难以预知 的结果；其次，函数是高阶函数式语言的第一类值，函数式语言的数学基础是入 演算口7 1 ，规范规约的计算顺序隐含着非严格的求值顺序，也就是延迟求值。而与 它对应着的是积极求值，也称为严格求值，主要用于传值