（计算机应用技术专业论文）带order+by子句的xquery在xml流上的查询研究.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 e b 的发展， 越来越多的x m l 数据以流的形式存在，如何在x m 蹴上高效地执行查询成为当今研究的热 点。x m l 查询的语言主要有x p a t h 和x q u e r y ，a i i l 语言定义了如何在x m l 文档中精确定位 和匹配x m l 的元素结点，但表达语义简单，面对用户日益提高的查询需求，x p a t h 显得力不 从心。而x o 刚生能良好，功能强大，能够更好地满足用户对各种x m l 黉t 据的查询需求。 对x q u e r y i 吾言的研究是适应当前x m l 查询技术发展的要求，而利用x q u e r y 来实现x m l 查询 是真正意义上有效使用x m l 数据的途径 一次典型的x q u e r y 查询过程可分为x p a t h 查询处理、查询后处理两个阶段。 x s i e q ( x m ls t r e n nq u e r yw 袖i m m e d i a t ee v a l u a t i o n ) 是笔者所在实验室研发的基于x m l 流 的查询x p a t h 引擎，能支持多个x p a t h 式的同时查询，记为x s m q - x p 。根据x q u e r y 查询 过程，在充分利用x s m q - x a , 已有工作的基础上，笔者及组内其他成员通过分析x q u e r y 查 询与x p a t h 查询的区别与联系，设计并实现了x q u e r y 查询原型系统x s i v - x ) - x q 。 本文的研究集中在x s l e q - x q 系统的查询后处理阶段，主要的工作和成果有： l 、追踪x q u e r y 标准的发展，对x q u e r y 语言进行深入的分析与研究，从而找到了在现 有的x p a t h 查询引擎x s m q - x p 的基础上扩展支持x q u e r y 查询的途径。 2 、参与定义了扩展的x s m q 机e - x s l e q ( e x t o n d e dx m l s t r e a mq u e r yw i t hi m m e d i a t e e v a l u a t i o n ) ，以及查询后处理所输出的中间结果( 即原子表集合) 的格式。 3 、提出并设计，实现了两种原子表排序连接算法，基于这个算法可以完成由中间结果 到结果文档的构造实现。 4 、参与实现了x s m q - x q 原型系统，它用j a v a 编写，该系统支持嵌套、o r d e rb y 子句 的多关键字捧序等x q u e r y 查询的复杂特性。对原型系统的查询性能和所做的系统优化进行 了大量的实验，实验结果表明查询后处理性能优于q i z x ，x s i e q - x q 系统能有效地处理x m l 数据流。 5 、设计了查询引擎的客户端复用方法，来支持客户端的信息选择分发 关键字：x q u e r y 、查询后处理，二次查询、选择分发 中置科学技术大学硕士学位论文 a b s t r a c t a sx m lb e , o o m 铭d ef a c t os t a n d a r do f d a t ae x c h a n g e , x m lh a sb e e nw i d e l yu s e d m o r ea n d m o r ex m ld a t ae m e r g e da ss t r e a m h o wt oq u e r yt h e s ed a t aa n dg e tu s e f u lr e s u l te f f i c i e n t l y b e c o m e sc u r r e n th c t s p o t t h e r ea r et w om a i nx l v i lq u e r yl a n g u a g e s ：x p a t ha n dx q u e r y x p a t hi s ad e c l a r a t i v el a n g u a g ef o ra d d r e s s i n ga n dp a t t e r nm a t c h i n g , b u ti ti st o os i m p l et oe x p r e s s c o m p l i c a t e ds e m a n t i c so fq u e r y i n g t h a n k st ow e l l - d e s i g n e df r a m e w o r ka n dp o w e r f u lf u n c t i o n s ， x q u e r ym a ym e e tt h en e e do fr e t r i e v a lo nx m l d a t as o u e x t h ea p p e a r a n c eo fx q u e r ya r o u s e d m u c hi n t e r e s to f m a n yr e s e a r c h e r sc a n c e l n e d , s os t u d i e so ni th a sb d ? a ) m eo n eo f h e a t e di s s u e s at y p i cp r o c e s so fx q u e r yq u e r yi sd i v i d e di n t ot w os t a g e s ：x p a t hq u e r ya n dq u e r y p o s t - p r o c e s s i n g x s w _ q ( x m ls t r e a mq u e r yw i t hi m m e d i a t ee v a l u a t i o n ) s y s t e m ，a nx p a t hq u e r y e n g i n e , i sd e v e l o p e db yo u rx m ls t r e a mp r o c e s s i n gr e s e a r c h t e a ma n da l s o c a l l e d x s i e q - x p b a s e do nx s m q - x p w ei m p l e m e n tq u e r ys y s t e mt ox q u e r y 1 1 1 em a i nw o r ka n d a c h i e v e m e n t so f t h i sp a p e ri n c l u d e ： 1 ) t r a c kt h ed e v e l o p m e n to fx q u e r y ，r e s e a r c ho ni tt h o r o u g h l y t h ea u t h o ra n a l y z e da n d d i s c u s s e dt h em a i ni s s u e so nx q u e r y 。s u c ha 3x q u e r ye x p r e s s i o n s ，t h er e a l i z a t i o no f c o m p l i c a t e df u n c t i o n so fx q u e r y ，q u e r y i n go p t i m i z a t i o n , a n ds oo ni no r d e rt of i n dh e w a yt oi m p l e m e n t a t i o no f x q u e r ye n g i n e t h eo r i g i n a lx s i e qi se x t e n d e da n dt h er e s u l t f o r m a to f x p a t hq u e r yi sd e f l n d e d 3 ) s f a j aa n dj a s i ta l g o r i t h m a t q u e r yp o s t - p r o c e s s i n gs t a g e a r ep r o p o s e da n d i m p l e m e n t e d 4 ) d e s i g na n di m p l e m e n ta l lx m lq u e r ye n g i n eb a s e d0 1 1x q u e r y ( c a l l e dx s i e q - x q ) x s i e q - x qi saj a v ai m p l e m e n t a t i o nw h i c hs u p p o r t st h ec o m p l i c a t e dx q u e r yq u e r i e s i n c l u d i n gn e s t e dq u e r i e sa n do r d e rb yc l a u s e sw i t hm u l t i p l ek e y s e x t e n s i v ee x p e r i m e n t s a r eg i v e dt os h o wt h a to fx s i e q - x qo u t p e r f o r m st h ef o r m e rw o r ki np o s t - p r o e e s s i n g p e r f o r m a n c e i si m p r o v e dc o n s i d e m b l e l yc o m p a r e dt oq i z x 5 ) s e c o n d a r yq u e r yi ss u p p o r t e db ym u s i n gt h ex s i e q x qa tc l i e n t t h et e s tr e s u l t ss h o w t h a tt h i sm e t h o di se f f e c t i v et od e c r e a s et h ec o m m u n i c a t i o n sb e t w e e ns e r v e ra n dc l e n t a n d c a na f f o nc o m p l e t ef u n c t i o n si nq u e r y k e y w o r d e ：x q u e r y ，q u e r yp o s t - p r o c e s s i n g , s e c o n d a r yq u e r y , s e l e c t i v ed i s s e m i n a t i o n i i 中国科学技术大学学位论文相关声明 本入声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特t l l j i l 以标注和致谢的地方外，论文中 不包含任何他人己经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅或借阅，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名关声谚 作者签名：裂竺型 沙一年 月6 日 中国科学技术大学硕士学位论文 第1 章绪论 1 1 研究意义 第1 章绪论 x m l 是t h ee x t e m i b l em a r k u pl a n g i l 丑g c ( 可扩展标识语言) 的简写，它的半结构化特性、 良好的可扩展性、自描述等特性使其成为数据交换事实上的标准。随着w e b 的发展，x m l 数据在w e b 上的传输不断增加，这些数据首先是以流的形式存在，另外，一些数据本来就 以流形式产生( 如股票市场更新、实时新闻反馈、网络监控数据等) 。随着x m l 流数据的 大量出现，x m l 流查询广泛地应用到以下系统之中：数据集成系统，如t u k w i l a t 3 ；管道处 理，如c o c o o n t 4 和x p i p e l 5 1 这样的应用体系越来越多，在这些应用中。不同的处理组件能被 组合到一起完成各种复杂灵活的自定义任务 连续查询，如n i a g a r a - c q t 6 j 、x s t r e a m c 笛p ”， 连续查询( c o n t i n u o u sq u e r i e s ) 是声明一次然后对连续产生的数据流进行选择分发的连续服 务；信息选择分发系统( s d i ) ，如x f i i t e l i ”、y f i | l e r 【2 1 ，信息的选择性分发s 系统根据 用户提交的不同需求选择相应的信息发送给不同的用户。由于s d i 应用要求系统能够对互 联网上的海量x m l 文档进行基于内容的实时过滤分发，因此如何进行高效的处理、匹配以 及分发便成为一个重要问题。 对于以上的x m l 流查询应用，如果将x m l 流数据全部存储到磁盘或内存，然后进行 处理，那么存在以下缺点：1 、非常占用内存：2 、处理效率低下；3 、对于实时产生的或无 限制的连续数据流，不可能完全读入；4 ，对于海量x m l 数据，将无法完全读入内存，导 致处理失败。所以，需要使用漉查询技术，在读入数据的同对，通过一遍扫描得到查询结果。 与传统应用环境相比，数据流环境有很多特点；数据流环境中的查询是连续的：查询处理所 使用的内存远远小于数据流本身；查询处理过程中数据仅仅能够被扫描一遍。对于这些数据， 它们以流的形式在高速的产生、，传递，如何快速、高效地处理这些数据，对它们进行解析、 过滤与查询成为当前研究的热点问题 x m l 流查询具有不同的应用场合，但在这些应用中，流查询系统的体系结构是大致相 同的，它们具有相同的输入与输出图l ，l 为x m l 流过滤查询系统的顶层结构图。从图中 可以看出，流过滤，查询日i 擎解析咀，漉，然后按过滤，查询条件进行筛选。输出匹配的x m l 数据。 x m l 流 过滤查询条件 果 图1 1x m l 流过滤和查询系统 x m l 流查询引擎负责接收x m l 流并按设定的查询条件筛选，然后输出匹配的结果。 查询条件可能是一组x p a t h i s ( x m lp a t hl a n g u a g e ) ：t - 襄达式，也可能是x q 矿1 ( x m l q u e r y ) 、x m l q l 2 0 l 等查询语言编写的查询脚本x p a t h 语言定义了如何在x m l 文档中精 确定位和匹配x m l 的元素结点，但表达语义简单，面对用户曰益提高的查询需求，x p a t h 显得力不从心，而x q u e r y 性能良好，功能强大，能够更好地满足用户对各种x m l 数据的 查询需求。x q u e r y 的基本成分是x p a t h 路径表达式，因此它包含按x p a t h 查询的能力。 中国科学技术大学硕士学位论文第l 章绪论 近年来，国外提出许多在x m l 流上按x p a t h 查询计算的算法，它们普遍使用s a x u q ( s i m p l ea p if o rx m l ) 事件驱动方式在一遍扫描x m l 文档的同时完成查询计算，主流的技术 有自动机技术和索引技术。 同时x q u e r y 支持类似s q l 语言的复杂查询语义，如嵌套和o r d e rb y 排序等特性。由 于流查询是连续的，当x q u e r y 中有o r d e r b 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 m l 数据的途径。 1 2x o u e r y 语言 人们提出并使用过的x m l 查询语言有x s l 、x q l i ”、x m l q l l 2 0 1 、q u i l t l 2 1 肄。x q u e i y 具有上述很多语言的优点，如x q u e r y 吸收t x q l 语言的路径表达式，x m l - q l 语言的变量 绑定机制，o q l 中的函数概念等。2 0 0 3 年w 3 c 出台7 x q u e r y l 0 语言的第一个草案之后， x q o e r y 逐步成为最流行的查询语言之一。目前已是w 3 c 的正式建议。 x q u e r y i 吾言的核心是x p a l h 和f l w o r 表达式。 x p a t h 是x q u e r y 语言的一个重要并且独立的组成部分，用于访问x m l 文档的莱一部分， x q o e r y 查询中模式匹配的工作是由路径表达式x p a t h 实现的。一个x p a l h 表达式由一系列的 位置步( 1 0 c a t i o ns t e p s ) 组成每一个位置步又是由一个轴、一个节点测试和可选的若干个谓 词组成。轴指明节点之间的层次关系，x p a t h 共定义了1 3 种轴，分为两大类：前向轴和反向 轴。其中主要的4 种轴是：孩子轴、子孙轴、父亲轴、祖先轴。节点测试一般就是名字测试， 可以是一个元素名或者通配符，通配符可匹配任意元素名。谓词是对当前位置步节点的 选择条件，可应用到元索的属性、元素的内容或者包含对文档中其他元素的引用。 定义1 1 对一个x p a t h 式p ，p 的主x l a t h 式是指去除p 中所有谓词后剩余的部分。 主x p a t h 式匹配的x m l 结点称为候选结果 x p a t h 式中去除谓词后剩余的部分称为主x p a t h 式，它确定x m l 查询匹配的候选结果 节点。在管道处理、连续查询等应用中，需要在查询过程中即时地输出当前查到的部分结果。 实现即时输出的最大障碍是x p a t h 式中存在的谓词 倒1 1x p a t h 式 ：鲥b = 2 f e = 3 j c d 和x m l 片段： q 】2 1 9 9 1 o r d e rb y $ b t i t l e r c u l r l l s b y e a r ) $ b t i f l e 上例x q u e r y 查询要求列出f h a d d i s o n - w e s l e y 于1 9 9 1 年后出版的所有书籍的t i t l e s 和y e a r s ， 并按t i t l e 排序。从该例子可以看出，x q u e r y 的基本成分是x p a t h 表达式，执行x q u e r y 查询首 先需要解析、处理这些路径表达式，根据它们定位x m l 节点 1 3 本文的研究内容 本实验室开发的x m l 流查询引擎x s i e q 2 2 1 ( x m ls t r e a mq u e r yw i t hi m m e d i a t e e v a l u a t i o n ) ，其主体是一个基于x p a t h 的x m l 流查询引擎，实现了对x m l 流的多个x p a t h 式的同时查询，记为x s i e q - x p 。x s m q x p 系统支持的x p a t h 特性包括：子孙轴，尸、孩子 轴伊、自身轴“属性轴“ ；通配符“ 、“ ”、文本t e x t o 等。由于x q u e r y 脚本中 的x p a t h 式不同于单独的x p a t h 式查询。x p a t h 式之问存在着复杂的依赖关系t 如 何对这些x q u e r y 中的多个x p a t h 式进行组织、查询，并将结果按要求进行连接最 后形成用户要求的结果文档，亦即开发具有复杂功能的x q u e r y 查询引擎是x s i e q 的研究重点 根据x q u e r y 查询过程。在充分利用x s m q - x p 已有工作的基础上，再通过分析x q u e r y 查询与x p a t h 查询的区别与联系，笔者与组内其他成员设计并实现了x q u e r y 查询原型系统 x s i e q - x q 。一次典型的x q u e r y 查询过程可分为x p a t h 查询、查询后处理两个阶段x p a t h 查询阶段负责提取x q u e r y 中的x p a t h 式作为条件，查询x m l 文档；查询后处理阶段负责 将x p a t h 查询得到的中间结果按要求进行过滤、捧序和连接。并将最终结果输出。本文的研 究集中在x s i e q - x q 系统查询后处理的设计与实现技术上。主要的工作和成果有： 通过对x q u e r y 语言进行深入的分析与研究，找到了在现有的x p a t h 查询引擎x s l e q x p 的基础上扩展支持x q u e r y 查询的途径。主要研究内容有： 1 、追踪x q u e r y 标准的发展，对x q u e r y 语言进行深入的分析与研究，从而找到了在现 有的x p a t h 查询引擎x s i e q - x p 的基础上扩展支持x q u e r y 查询的途径。 2 、定义了扩展的x s i e q 机e - x s i e q 。引入相关数据结构如变量依赖树、原子表等。 用变量依赖树来维护依赖变量之间上下文关系，在得到x p a t h 查询的结果后，根据变量之间 的依赖关系连接有上下文关系的变量结果作为中间结果，并将这些结果组织在原子表中。 3 、分析并实现o r d e rb y 子句，在查询后处理阶段找到能有效对x p m h 查询得到的结果 进行连接排序的算法，并进行算法分析支持信息选择分发的应用并给出具体的设计方案。 3 中置科学技术大学硕士学位论文 第1 章绪论 4 、实现x $ 1 e q - x q 原型系统，并对原型系统的查询性能和所做的系统优化进行实验 1 4 后续章节的组织 第2 章介绍了在m ，数据流上进行x q u e r y 查询的相关工作，包括本实验室的已有工 作 第3 章主要从应用场景、支持力度、系统结构等方面介绍x s m q - x q 系统。并对x q u e r y 查询进行了初步分析。 第4 章介绍查询后处理的实现，包括变量表到原子表连接，原子表连接形成块表，其中 提出了两种原子表的排序连接算法。 第5 章介绍了利用查询引擎复用的方法支持信息选择分发以及在结果文档上进行二次 操作等应用。 第6 章介绍了x s l e q - x q 系统的实现与实验，并给出了部分实验结果及性能分析 第7 章总结全文，提出今后可以进一步开展的研究方向 4 中国科学技术大学硕士学位论文第2 章相关工作 第2 章相关工作 基于自动机的技术处理x p m h 查询是比较成燕的技术， ；王x q u e r y 为查询条件 的x m l 流查询研究尚处于发展阶段。一些基于x p a t h 的x m l 流查询引擎能支持 简单的x q u e r y 查询o 】i l l l 。此外，还有一些专门的以x q u e r y 为查询条件的x m l 流查 询工具如：r a i n d r o p 1 射、f l u x q u e r y t s l 、t u r b o x p a t h 5 j 等，这些工具主要采用自动机和代 数相结合的技术、查询重写技术等 2 1 自动机和代数相结合的技术 查询引擎的一种主流做法是根据查询条件中的各x e a ：t 5 式构造自动机，自动机的输入是 待查询的x m l 流，输出则可能是查到的相关x m l 节点。基于自动机的技术处理x p a d l 查 询是比较成熟的技术，但由于f l w o r 表达式和嵌套查询块等特性使得x q u c r y 比x p a t h 更 复杂。所以，近来的工程出现了自动机和代数相结合的技术来处理x q u , r y 流查询，这种技 术的优势在于在查询的每个阶段都采用了最恰当的技术。拥有很好的分层模型。有更多的优 化机会，使查询更加高效。n e x 一粥、r a i n d r o p 1 均采用此技术 n e x t 是一个x q u e r y 流查询系统，系统前端拥有一个n e x t 代数优化框架。框架的目 标是将查询条件最优化。优化框架选择了x q u e r y 语言的一个子集o p t x q u e r y ，在o p t x q i l e r y 上定义了一套重写规贝i 】和最小化算法。输入的o p t x q u e r y 经过r e w r i t i n g 、 f u n c t i o n a l - t o - l o g i c a l 和m i n i m i z a t i o n 三个步骤后构造自动机进行查询。 r a i n d r o p 系统由r a i n b o w l 2 s 继承而来，r a i n b o w 是一个数据库查询引擎。拥有一套完整 的代数操作定义，r a i n d r o p 在r a i n b o w 的操作基础上增加了流查询中特有的代数操作。 r a i n d r o p 还运用了数据库中的概念将系统分为语义层、逻辑层、物理层和执行层四层，代数 优化集中在逻辑层上。系统数据模型是一个标记序列，标记包括元素开始标签，结束标签和 p c d a t a ，在该模型上的操作有选择( s e l e c t i o n ) 、投影口m j e c t i o n ) 、连接( j o i n ) ，聚集 ( a 站m 凹t e ) 、t a g g e r ，导航( n a v i g a t e ) 、提取o ! x t r a c t ) ，建立在逻辑操作上的改写规则有 n a v i g a t i o np u s h i n 、r e d u n d a n ts j o i n 、r e d u n d a n te x t r a c t 、n a v i g a t i o np u s h d o w n 、s e l e c t i o n p u s h d o w n r a i n d m p 中进行的一系列代数优化措施虽然使得系统的时间性能得到提升，但是却让系 统占用更多空间，同时又不能及时地对缓存的数据进行转移，使得系统不利于大数据量的查 询。 2 2 查询重写技术 在现有的查询引擎中的经常性地过度依赖缓冲区引起的问题，已经成为重要研究课题 然而在流上的x p a l h 查询的有效的计算得到了广泛的研究。而在x q u e l y 流查询处理上的工 作却不多。x q u e r y 的特性，作为一个数据转换查询语言。与节点选择x p a t h 完全不恩，需 要新的技术来处理内存缓冲区，如查询重写技术。 查询重写技术是利用已知的信息如x q u e r y 脚本或是文档的d t d 等对查询进行变换， 以便适应于流查询的连续一趟的特性，减少内存的使用，从而提高查询效率。 f l u x q u e r y t ”1 定义了一种内部语言f l u x 。来支持事件驱动的查询处理和有意识地控制内 存缓冲区的使用。具体做法是利用给定文档的d t d 中的模式信息，如父子元素的映射关系， 兄弟元素之间的顺序等，来获得哪些节点需要缓存，哪些节点在解析到达后便可直接输出的 5 中国科学技术大学硕士学位论文第2 章相关工作 信息。以此来优化缓冲区的使用。在查询开始前x q u e r y 查询条件即通过重写规则转换成f l u x 语言，以后的查询均是对f l u x 的操作。f l u x 语言的优势在于使系统的缓冲区得到优化，优 化表现在更早的输出缓冲区、减少待缓冲的内容甚至不用缓冲区。 文献f 1 4 】针对流查询的x ( 沁r y 处理，提出了对x q u e r y 查询进彳亍变换优化的方法，依据 查询中的依赖关系用s d f g ( s t r e a md a t af l o wg r a p h ) 来建模，通过运用一系列的高层变换， 将x q u e r y 查询重写变形，以便于在数据集上正确有效地应用一趟算法，并根据s d f g ，提出 了在数据集上应用一越算法的判定条件基于g n l ( g e n e r a l i z e d n e s t e dl o o p s ) 提出底层转 换技术，如聚集重写和递归分析来优化查询。 2 3 其它技术 t u r b o x p a t h b q 提出一种不用将x q u e r y 查询转换成自动机的新的查询算法。它的主要组 成部分有表达式解析器、计算器、元组构造器。表达式解析器从输入的x q u e r y 脚本中提取 x p a t h 表达式，解析并连接成一个具有多个输出节点的解析树p t ( p a r a et r e e ) 。计算器使用 p t 来处理输入文档产生的s a x 事件流，检索得到的x m l 片断作为中间结果，存储在输出 缓冲区和谓词节点中，并根据这些s a x 事件来完成状态转换和缓冲区的刷新。当输出缓冲 区包含了足够的信息来输出结果元组时，触发元组构造。 q i 划1 是实现x q u e r y 规范的开源j a v a 软件，是x m l 数据库查询引擎x a l 龆p 冽的一 个子集，它利用 定义的一系列函数来完成查询。xquestq i z x 虽然支持x m l 流查询，但是 登须把x m l 文挡全部读入到内存刨建x m l 文档树，然后对树中的结点进行索引和查询。 对于较小规模的x m l 文档，q i 盛能获得良好的查询性能。 2 4 支持力度比较 由于不同的查询引擎所关注的焦点不同，所以对x p a t h 的支持力度和对x q u e r y 语句的 支持也不尽相同。 1 、对x p a t h 的支持 r a i n d r o p 和t u r b o x p a t h 查询处理的第一阶段都是对x p a t h 的查询，所以它们对x p a t h 的支持力度较完整。如：都支持孩子轴( ，) 、子孙轴( 疗) 、部分谓词、节点铡试允许是通 配( + ) 等。t u r b o x p a t h 还支持反向轴、函数和多文档查询。f l u x q u e r y 应用于缓存有限的情 况，所以系统致力于尽可能地减少查询缓存开销，对查询的支持力度较弱，它不支持x p a t h 式内的“”和v r 2 、对x q u e r y 语句缒支持 对x q u e r y 查询语句的f o r - w h e r e - r e t u r n 结构的支持，是查询引擎的基本功能，而x q u e r y 中的嵌套查询、聚集函数，排序功能是当前研究的难点。 虽然n e x t 优化框架为o p t x q u e r y 提供了一套通用的重写和最小化方案，但是它只支 持f o r 、w h e r a 和r e t u r n 子句没有考虑融和o r d e r 姆子旬。这对x q u e r y 查询来说是不完整 的。r a i n d r o p 和t u r b o x p a t h 对x q u e r y 的支持力度有限，不支持o r d e rb y 子旬。 f l u x q u e r y 对x q u e r y 语句的支持力度较弱。它不支持f l w o r 表达式中的l e t 、o r d e r b y 子句，并且x q u e r y 到f l u x 的重写需要d t d 的支持，使得查询应用的范围受到较大的限制， 不能作为一种通用的查询技术。目前只有文献【1 4 】通过查询重写支持嵌套和聚集，包括用户 定义的递归函数。 6 中国科学技术大学硕士学位论文 第2 章相关工作 q i z x p 7 1 支持带多关键字排序的o r d e rb y 子旬等复杂的功能。q i 丛虽实现了x q u m , y 的大 部分功能，但它是把x m l 文档读入内存再处理，它以空问的代价来获得稳定的性能，不适 合较大文件的查询和连续查询，也不支持模式的导入与验证。 2 5x s i e q x p 介绍 x m l 流查询引擎作为本实验室近期的研究重点，现己开发出x s m q - x # m ，x s m q - x p 主体是一个基于x p a t h 的x m l 流查询引擎，实现了对咀流的多个x p a f l a 式的 司对查询。 x s i e q - x p 系统的框架是一个基本的x s m q 机1 2 2 1 。 x s i e q - x p 系统将待查询的各个x p a t h 式中的主x p a t h 式和谓词中的x p a t h 式提取出 来，利用前缀共享的方法增量式地构造为一个n f a ；然后对n f a 中的以下特殊状态进行类 型标记并添加索引。 定义2 1 对于基本x s m q 机中的任意n f a 状态j ，如果它匹配某一主x p a t h 式，则称 为结果状态，并在该状态上保存所匹配的各主x p a t h 式的列表l r o ) 。如果状态j 匹配某一 出现在谓词中的x p a t h 式，则称为叶子状态并在该状态上保存它关联的各谓词列表l p ( s ) 如果状态s 是某x p a t b 式对应的主路径上具有的、分支到谓词中x p a t h 式的状态，则称为分 支状态，在分支状态保存从该状态分支出去的谓词列表l b ( s ) 在基本x s m q 机上可以实施不同的查询算法，如逐层提升缓冲( p r o m o t i n gb u f f e r , 简称 p b u l ) 的查询算法。p b u f 算法1 2 2 j 的特点体现在候选结果的缓冲机制上。对于一个x p a t h 式p 。 若它含有b , 1 个带谓词的位置步，自左至右依次标记为，豇k 1 ，则p 的缓冲区含有m 层。 第f ( 0 塑咖- 1 ) 层保存的候选结果满足s ，到趣中的所有谓词当x s m q 机运行回溯到扫 对应的分支状态时，将候选结果添加到缓冲区的第* 1 层；回溯到嘶陋g 锄1 ) 对应的分支 状态时进行缓冲区的层次提升；在到达第0 层缓冲区后得到确认 p b u f 查询方案的设计是基于这样的一个事实；对含谓词的x p a t h 式，当x s i e o 机运行 回溯到该x p a t h 式的最左分支状态时，一定能确认在此前收集到的该x p a l h 式的候选结果是 否匹配p b u f 算法具有较高的查询效率通过对大量的实验，结果表明基于p b u f 的x s m q 机优于y f i n e 一。 x s i e q - x p 不仅支持 + f i l t e r 所支持的所有x p a t h 式特性，而且支持更复杂的谓词表达 式，如逻辑和算术运算、函数等图2 1 给出了x s i e q - x p 支持的x p a t h 式的形式定义这 些x p a t h 式可以包含以下特性： 支持的轴包括子孙轴，、【l 】p ：2 e f h e 孩子轴，、自身轴。、属 2 】e ：- - e e i 聃l e 【q l i i + e l l t e 域) l i i 1 t a b e l 性轴国，； 【3 】q ：2 e i e o p c o n s t i q a n d q i q o r q i n o t ( q ) i f u n “q ) 挈噼翌苎有勰符m 7 翟# i 裂茹持的劬片段 、 ”、文本t e x t o , 、 。 支持三类谓词；索引谓诃、存在性谓词和普通谓词。另外也提供了对嵌套谓词的 支持。 有关x s l e q - x p 的更详细介绍请参见文献c z 2 】。 7 中国科学技术大学硕士学位论文 第2 章相关工作 2 6 本章小结 本章主要介绍了x p a t h 和x q u e r y 在x m l 流上的查询处理技术基于自动机的技术 处理x p a t h 查询是比较成熟的技术。以x q u e r y 为查询条件的x m l 流查询研究尚 处于发展阶段，主要采用自动机和代数相结合的技术、查询重写技术以及其它技术等， r a i n d r o p 采用自动机和代数相结合的技术来实现流查询，但是它没有考虑流查询的及时性， 查询结果不能即时输出，这种延时性使得响应时间和内存开销都比较大，不能实现流查询的 高效性。f l u x q u e r y 采用的是查询重写技术，是一个非常注重实时性的系统。而且系统会 尽可能早的输出缓存数据，但是系统只能支持非常简单的x q u e r y ，力度很弱。x s m q - x p 是本实验室开发的x p a t h 在x m l 流上的查询引擎，实现了对x m l 流的多个x p a t h 式的同 时查询本文的目标就是在x s m q - x p 已有工作的基础上实现复杂的x q u e r y 查询。 8 中国科学技术大学硕士学位论文第3 章x s l e q - x q 系统与查询分析 第3 章x s i e q x q 系统与查询分析 按x s m q - x q 系统的数据流程将整个查询分为三个阶段，查询预处理。x p a t h 查询处理， 查询后处理，对应于三个模块。下面按x s l e q - x q 查询系统的支持力度、系统流程、应用 场景等介绍x s i e q - x q ，然后进行x q u e r y 查询的初步分析 3 1x q u e r y 的支持力度 3 1 1 所支持的x q u e r y 特性 完整的x o m r y 语言功能非常强大，e b n f 见x q u e r y1 0a nx m lq u e r yl a n g u a g e 9 1 ， 并且x q u e r y 语言的很多特性不符合流查询的特点，因此，在选择x q u e r y 子集时，忽略了 一些次要研究点，这里主要考虑f l w o k 查询表达式及其相关特性。 支持特性； 多x q u e r y 的同时查询 嵌套查询：在f l w o r 表达式的各子句中，允许r e t u r e 、w h e r e ，f o r 子旬嵌套。 r e t u r n 、w h e r e 子旬可以递归嵌套多层；f o r 子旬只能嵌套一层；衄子句嵌套f l w o r 表达式的层数视绑定该f l w o r 表达式的变量的用途而定。 排序特性：支持多关键字排序，允许指定关键字类型为字符串或者数值类型。 变量依赖关系：在f l w o r 查询块中的变量无依赖关系限制，不仅同层的变量 可以存在依赖关系，内层变量也可依赖于外层变量，且依赖关系具有传递性。 连接依赖：在w h e r e 子旬的运算表达式中允许出现其外层f l w o r 表达式中的 变量。 元素构造器：支持直接元素构造器 不支持特性： 聚集函数 动态元素构造器 节点比较 3 1 2 支持力度的e b n f 表示 x s i e q 支持的f l w