（计算机软件与理论专业论文）基于自动机的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 l 流上高效地执行大量x p a t h 查询成为 当今研究的热点，特别在管道处理等应用中还希望在解析流的同时尽早地输出查询结果。 x s i e 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 ) 是一种立即计算谓词并即时输出 的x m l 流查询系统。旨在建立一套高效的、能支持复杂查询并立即计算的x m l 流查询引 擎。它利用前缀共享的方法由多个x p a t h 式构造一个n f a ( n o n d e t e r m i n i s t i cf i n i t e a u t o m a t a ) ，并对n f a 状态进行分类和添加索引，使得在运行时能快速确定谓词计算和数 据缓存等的时机。 我们首先定义了基本x s i e q 机。它是一个x m l 流查询框架，是被索引化的、基于栈 的自动机，在其上可以扩展应用多种x p a t h 查询算法。我们晟初提出即时输出( i m m e d i a t e o u t p u t ，简称l o u t ) 的查询算法，即一旦谓词状态发生变更，则立即处理候选结果缓冲区。这 种算法会频繁操作缓冲区，当查询的x p a t h 式数目接近5 0 0 0 或谓词数偏多时，算法效率显 著降低。为此，我们又提出- t e e 逐层提升缓冲( p r o m o t i n gb u f f e r ，简称p b u f ) 的查询算法，该 算法只延迟了部分查询结果的输出时间，却极大地降低了对缓冲区的操作频率，从而使查询 效率得到显著提升。 我们形式地定义了x s i e q 机，并进行了设计、实现和测试。实验结果表明，提出的方 法能够支持复杂的x p a t h 查询，在执行效率方面优于传统算法。 在x p a l h 查询引擎的基础上，我们选择一个x q u e r y 子集，设计、实现了以满足该子集的 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 查询处理器得到x p a t h 式结果，然后构造出x q u e r y 的结果。 全文共分八章。第1 章介绍研究背景和研究内容：第2 章介绍x m l 数据流查询的现状 和相关工作：第3 章介绍x s i e q 系统框架和基本的x s i e q 机：第4 章介绍x s i e q 的l o u t 查询策略：第5 章介绍x s i e q 的p b u f 查询策略：第6 章介绍了系统的实现的框架和主要类 结构，说明了在系统实现时的一些优化技术，然后给出了部分实验结果及性能分析：第7 章介绍了以满足某x q u e r y 子集的x q u e r y 脚本为查询条件的x m l 流查询系统的实现：第8 章总结论文的主要内容，讨论今后可以进一步开展的研究方向。 关键字：x m l 流、查询、x p a t h 、有限状态机、x q u e r y 中国科学技术大学硕士学位论文a b s t r a c t a b s t r a c t a sx m lb e c o m e sd e f a c t os t a n d a r do fd a t ae x c h a n g e ，x m lh a sb e e nu s e de x t e n s i v e l y m o r e a n dm o r ex m ld a t ae m e r g e da ss t r e a mh o wt of i l t e ra n dq u e r yt h e s ed a t af a s ta n de f f i c i e n t l y b e c o m e sc u r r e n th o t s p o t i ns o m ea p p l i c a t i o n se s p e c i a l l yp i p e l i n e s ，i ti sf u r t h e rr e q u i r e dt oo u t p u t t h er e s u l t sw h i l ep a r s i n gx m ls t r e a m x s i e 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 ：，ak i n do f x m ls t r e a mq u e r y s y s t e m ，c a ne v a l u a t ep r e d i c a t e si m m e d i a t e l ya n do u t p u ti nt i m e i ta i m st oe s t a b l i s hx m l s t r e a m i n gq u e r ye n g i n ew h i c hs u p p o r t se f f i c i e n t ，c o m p l e xq u e r ya n di m m e d i a t ee v a l u a t i o ni n x s l e q ，a l lx p a t he x p r e s s i o n sa r ec o n v e r t e di n t oas i n g l en f ab yp r e f i xs h a r i n g ，a n dt h en f a s t a t e sa r el a b e l e dw i t ht y p ea n di n d e x ，s ot h eo p p o r t u n i t yo f p r e d i c a t ee v a l u a t i o na n dd a t ac a c h e c a nb eq u i c k l yd e c i d e di nr u n t i m e i nt h i sp a p e r ，ab a s i cx s i e qm a c h i n ei sd e f i n e d ，w h i c hi saf r a m e w o r ko fx m ls t r e a m q u e r ya n dak i n do fi n d e x e da u t o m a t ab a s e do i ls t a c kv a r i o u sk i n d so fa l g o r i t h m so nx p a t h e v a l u a t i o nc a nb ea p p l i e dt oe x t e n dt h eb a s i cx s i e qf i r s t l y ，a na l g o r i t h mb a s e do ni m m e d i a t e o u t p u t ( 1 0 u tf o rs h o r t ) i sp u tf o r w a r d ，t h a ti s ，o n c ep r e d i c a t e ss t a t u si sc h a n g e d ，p r o c e s sb u f f e r so f c a n d i d a t er e s u l t i m m e d i c a t e l y t h i sa l g o r i t h mw i l lo p e r a t eb u f f e r sf r e q u e n t l y ，w h e nx p a t h n u m b e ri sm o r et h a n5 0 0 0 ，e f f i c i e n c yr e d u c e dn o t a b l e s o ；a na l g o r i t h mb a s e do np r o m o t i n g l a y e r e db u f f e r ( p b u ff o rs h o n ) i sp u tf o r w a r d t h i sa l g o r i t h mo n l yp o s t p o n eo u t p u tt i m eo fp a r t r e s u l t ，b u tr e d u c eb u f f e r s o p e r a t i o n ，t h e r e f o r ，q u e r ye f f i c i e n c yi si m p r o v e dn o t a b l e t h ex s i e qm a c h i n eb a s e do np b u fi sf o r m a l l yd e f i n e da n da l s oi m p l e m e n t e da n dt e s t e d e x p e r i m e n t a l r e s u l t ss h o wt h a tx s i e qb a s e do np b u fs u p p o r t st h e c o m p l e xx p a t ha n d o u t p e r f o r m st h ef o r m e rw o r ki ne f f i c i e n c y b a s e do nx p a t hq u e r ye n g i n e ，w ei m p l e m e n tq u e r ys y s t e mt ox q u e r ys u b s e t s y s t e m sa i m i st os e l e c tax q u e r ys u b s e ta n dt os u p p o r tt h i ss u b s e ti ns t r e a m i n gq u e r ye n g i n ew ep i c ku p x p a t hf r o mx q u e r ys c r i p t ，r e u s ex p a t hq u e r ye n g i n et oo b t a i nx p a t hr e s u l t ，t h e nc o n s t r u c t x q u e r y sr e s u l t t h i sd i s s e r t a t i o nc o n s i s t so f e i g h tc h a p t e r sc h a p t e r1b r i e f l yi n t r o d u c e st h eb a c k g r o u n da n d c o n t e n to fr e s e a r c hp r o j e c t c h a p t e r2i n t r o d u c e sr e l a t e dw o r k c h a p t e r3i n t r o d u c e sx s i e q s y s t e ma n ds y s t e m s f o u n d a t i o n ：b a s i cx s i e qm a c h i n e c h a p t e r4i n t r o d u c e si o u t q u e r y a l g o r i t h m c h a p t e r 5i n t r o d u c e sp b u fq u e r y a l g o r i t h m ，c h a p t e r6 i n t r o d u c e s s y s t e m s i m p l e m e n t i o na n df r a m e w o r k ，o p t i m i z a t i o nt os y s t e m ，e x p e r i m e n ta n dp e r f o r m a n c ea n a l y s e s c h a p t e r7i n t r o d u c e sx q u e r ys u b s e tq u e r ys y s t e m t h el a s tc h a p t e rc o n c l u d e st h ed i s s e r t a t i o na n d p o i n t so u tt h ef u t u r ew o r k k e y w o r d s ：x m ls t r e a m ，q u e r y ，x p a t h ，f s m ( f i n i t es t a t em a c h i n e ) ，x q u e r y 中国科学技术大学硕士学位论文 第1 章绪论 第1 章绪论 x m l 是标准的通用标记语言，它的半结构化特性、良好的可扩展性、自描述等特性， 使它成为数据交换事实上的标准。随着w e b 的发展，x m l 数据在w e b 上的传输不断增加， 这些数据首先是以流的形式存在，另外，一些数据本来就以流的形式产生( 如股票市场更新、 实时新闻反馈、网络监控数据等) 。对于这些数据，它们以流的形式在高速的产生、传递， 如何快速、高效地处理这些数据，对它们进行解析、过滤与查询成为当前研究的热点问题。 本章首先介绍x m l 流查询的应用背景，从中抽象出x m l 流查询系统的框架结构，然 后介绍相关的背景知识，最后给出本论文的主要研究内容。 1 1x m l 流查询的应用 随着x m l 流数据的大量出现，x m l 流查询广泛地应用到以下系统之中： 1 信息选择分发系统( s d l ) ，如x f i l t e r 1 】、y f i l t e r 2 】。s d i 系统根据用户提交的不 同需求选择相应的信息发送给不同的用户。s d i 系统的例子如股票系统、交通信息 系统、电子杂志订阅等。 2 数据集成系统，如t u k w i l a 3 。数据集成系统的目的是将分布于网络上的数据源进 行集成。在网络环境下，数据以流的形式传输。 3 管道处理，如c o c o o n 4 $ hx p i p e 5 这样的应用体系越来越多。在这些应用中，不 同的处理组件能被组合到一起完成各种复杂灵活的自定义任务。由于流具有内存占 用少、增量式处理等优点，不同组件之间采用x m l 流的方式进行通讯。 4 连续查询，如n i a g a r a - c q 6 】、x s t r e a m c a s t 7 】。连续查询( c o n t i n u o u sq u e r i e s ) 是声 明一次然后对连续产生的数据流进行选择分发的连续服务。例如，在网络交通管理 中，连续查询可以用于监视网络行为如网络异常，也可以用于网络的负载平衡和 性能调整。 对于以上的x m l 流查询应用，如果将x m l 流数据全部存储到磁盘或内存，然后进行 处理，那么存在以下缺点：l 、非常占用内存；2 、处理效率低下；3 、对于实时产生的或无 限制的连续数据流，不可能完全凄入；4 、对于海量x m l 数据，将无法完全读入内存，导 致处理失败。所以，需要使用流查询技术，在读入数据的同时，通过一遍扫描得到查询结果。 1 2x m l 流查询系统 中国科学技术大学硕士学位论文第1 章绪论 x m l 流查询具有不同的 应用场合，但在这些应用中， 流查询系统的体系结构是大 致相同的，它们具有相同的输 入与输出。图1 1 为x m l 流 x m l 流 过滤查询条件 图1l x m l 流过滤和查询系统 结果 过滤查询系统的顶层结构图。从图中可以看出，流过滤，查询引擎解析x m l 流，然后按过 滤查询条件进行筛选，输出匹配的x m l 数据。 过滤，查询条件可能是x p a t h 8 表达式( 以下简称x p m h 式) ，也可能是某种查询语言脚 本。目前使用最广泛的查询语言是x q u e r y 9 。 1 3 背景知识 1 3 1x m l 解析 x m l 的解析主要有d o m ( d o c u m e n lo b j e c tm o d e l ) 1l i e us a x ( s i m p l ea p if o rx m l ) 1 2 】 两种方式。前者将x m l 数据一次读入内存，为x m l 文档在内存中建立一棵完整的对象树， 然后利用一组a p i 对x m l 文档进行增、删、改和查看。s a x 方式使用事件驱动，依次读 入数据，在读入数据的过程中实现对数据的处理。 最初，x m l 数据同其他w e b 文档一样，数据规模并不大，根容易考虑到将x m l 数据 都读入内存中进行查询等处理。d o m 使用的就是这种方式。由于d o m 方式占用内存大， 因此只适用于较小文件的处理。s a x 以事件驱动的方式控制x m l 数据，它占用系统资源少， 但操作是一次性的，不能重复访问。考虑到x m l 流过滤，查询的效率，一般都采用s a x 解 析x m l 流。 1 3 2x p a t h 式 x m l 是一种半结构化语言，根据x m l 的树状层次结构，广泛地使用x p a t h 表达式寻 址x m l 文档的各个部分。一个x p m h 表达式由一系列的位置步( 1 0 c a t i o ns t e p s ) 2 9 成。每一个 位置步又是由一个轴、一个节点测试和可选的若干个谓词组成。轴指明节点之间的层次关系， x p a h 共定义了1 3 种轴，分为两大类：前向轴和反向轴。其中主要的4 种轴是：孩子轴、 子孙轴、父亲轴、祖先轴。节点测试一般就是名字测试，可以是元素名或者通配符”，通 配符可匹配任意元素名。谓词是对当前位置步节点的选择条件，可应用到元素的属性、元素 的内容或者包含对文档中其他元素的引用。 x p a t h 式中去除谓词后剩余的部分称为主x p a t h 式，它确定x m l 查询匹配的候选结果 节点。在管道处理、连续查询等应用中，需要在查询过程中即时地输出当前查到的部分结果。 实现即时输出的晟大障碍是x p a h 式中存在的谓词。 例1 1x p a t h 式p ：a b = 2 【e = 3 c d nx m l 片段： 一2 中国科学技术大学硕士学位论文第1 章绪论 2 3 包含两个位置步：a 胁= 2 】 e = 3 和，c 【d 】。位置步a b = 2 】 e = 3 】的轴是孩子轴， 一a 是节点测试，该位置步包含两个谓词 肋= 2 和 e = 3 。l a c 是尸l 的主x p a i h 式。 当s a x 解析获得x m l 片段中的元素节点c ( 匹配到x p a t h 式a c 的节点) 时尸，中谓 词 e = 3 尚未计算，所以不能确定c 元素是否最终能匹配p ，也就是说，谓词阻碍了查询结 果的即时输出。这是x m l 流查询中的一个难点。 1 3 3 x 0 u e r y x m l 数据与关系数据和面向对象数据不同，因此传统的查询语言不能直接用于x m l 。 在过去几年中，针对x m l 的半结构化数据模型，己设计提出了多种x m l 查询语言，包括 x q u e r y 、x m l q l 1 2 等。 x q u e r y 是在x m l - q l 等语言的基础上提出的，具有比x m l q l 更强的查询语义。经 过几年的草案修订，w 3 c 于2 0 0 5 年1 1 月发布了x q u e w 的系列候选建议( c a n d i d a t e r e c o m m e n d a t i o n ) 。x q u e r y 基于f o r - l e t - w h e r e r e t u r n ( f l o w r ，发音为f l o w e r ) 结构：f o r 子旬使用x p a t h 表达式选择输入节点，l e t 子句定义值集合的表达式，w h e r e 子句定义选择、连接条件，r e t u r n 子句构造f l o w r 表达式的结果。x q u e r y 表达式能内 嵌在r e t u r n 子句中，构造出层次式的结果。此外，x q u e r y 提供了对任意递归函数的支持。 x q u e r y 的计算以变量绑定开始：在从x m l 文档的根开始的子树遍历中，f o r 和l e t 子句中的x p a t h 表达式首先被计算。如果一个x p a t h 表达式有多个匹配，则f o r 子句将变 量迭代绑定到每一个匹配的节点，执行w h e r e 和r e t u r n 子旬的查询。 该脚本对b i b x m l 中的每个b o o k 元素，按照属性出版日, ! g ( p u b d a t e ) 值进行排序，如 果该b o o k 的价格( p r i c e 子元素) 大于2 5 ，则构造一个包含- t ：g ( t i t l e 子元素) 的r e s u l t 节点。从 该例子可以看出，x q u e r y 的基本成分是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 查洵的主要 部件之一。 3 。 中国科学技术大学硕士学位论文 第l 章绪论 1 4 本文的研究内容 管道处理等应用要求在解析x m l 流时尽早输出己获得的查询结果。为支持此类应用场 合的x m l 流查询，我们开展了x s i e 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 ) 系统的 研究，旨在建立一套高效的、能支持复杂查询并立即计算谓词的x m l 流查询引擎。 对不含谓词的x p a t h 查询，在收集到匹配的x m l 节点后立即输出结果。对含谓词的 x p m h 查询，由于在收集到候选结果时，相应的谓词可能未完全确定故需要缓存候选结果。 为了在解析x m l 数据流的同时能即时确定为此计算、候选结果收集等动作的时机，我们首 先建立一个基本x s i e q 机。基本x s i e q 机是通过对x p a l h 式的解析，将x p a t h 式表示为有 限状态机，并对状态机的状态进行标记和索引而构造的。 在基本x s i e q 机的基础上，我们先后提出了两种流查询算法。首先提出的是即时输出 ( i m m e d i a t eo u t p u t ，简称i o u o 的查询算法，即一旦谓词状态发生变更，则立即处理候选结果 缓冲区：或输出，或清除，或更新候选结果的谓词状态。这种算法会频繁操作缓冲区，使得 当同时查询的x p a t h 式数目接近5 0 0 0 或谓词数偏多时，算法效率显著降低。为此，我们又 提出一种逐层提升缓冲( p r o m o t i n gb u f f e r ，简称p b u d 的查询算法，该算法只延迟了部分查询 结果的输出时问，却极大地降低了对缓冲区的操作频率，从而使查询效率得到显著提升。 在x p a t h 查询引擎的基础上，我们接着实现了一个简单的x q u e r y 流查询系统，即x s i e q v 1 0 。x s i e qv 1 0 的系统目标是选择一个x q u e r y 子集，实现以满足该子集的x q u e r y 脚本 为查询条件的x m l 流查询系统。关于x q u e r y 查询系统的实现将在第7 章介绍。 1 5 论文的组织 本文的组织如下：第2 章介绍x m l 数据流查询的现状和相关工作：第3 章介绍x s i e q 系统框架和基本的x s i e q 机：第4 章介绍x s i e q 的i o u t 查询策略：第5 章介绍x s i e q 的 p b u f 查询策略：第6 章介绍了系统的实现的框架和主要类结构，说明了在系统实现时的一 些优化技术，然后给出了部分实验结果及性能分析：第7 章介绍了以满足某x q u e r y 子集的 x q u e r y 脚本为查询条件的x m l 流查询系统的实现；第8 章总结论文，讨论今后可虬进一 步开展的研究方向。 d 中国科学技术大学硕士学位论文 第2 章相关工作 第2 章相关工作 近年来，学术界和工业界提出了很多x m l 流查询处理方法，这些方法主要采用有限自 动机技术、索引技术，以及代数查询技术等。本章将总结这些查询技术，并说明现有的查询 方法对，a t h 表达式的支持力度，如多x p a t l l 式查询，对反向轴、谓词等的支持。 2 1 基于自动机的查询技术 查询引擎的一种主流做法是根据查询条件中的各个x p a t h 式构造自动机，自动机的输入 是待查询的x m l 流，输出是匹配的相关x m l 节点。 自动机包括有限状态机( f s m f i n i t es t a t em a c h i n e ) , 1 1 下推自动机( p d a ，p u s h d o w n a u t o m a t a ) 。没有反向轴且没有谓词的x p a t h 式是正则语言，故存在有能接受此语言的f s m 。 而p d a 比f s m 具有更强的语义处理能力支持更强的x p a t h 子集，实现对谓词的计算。 2 1 1 有限状态机 有限状态机包括一些状态和状态之间的转换，是表示和处理路径表达式的一种自然、有 效的方法。x p a t h 路径表达式的位置步被映射到状态，节点测试是状态之间的转换条件。在 使用基于事件的x m l 解析器( 如s a x 解析器) 进行解析b e , 事件触发f s m 的状态转换：x m l 文档的开始事件激活f s m 的开始状态；元素的开始事件触发f s m 的状态转换；对于一个当 前状态，若当前面临的输入元素匹配该状态的一个状态转换时，则该转换被触发；如果到达 接受状态，则当前x m l 节点是x p a h 式的候选结果：元素的结束事件使f s m 退回到上一 状态；x m l 文档的结束事件将终止f s m 的执行。 f s m 分为不确定的有限状态自动机( n f a ) 、确定的有限状态自动机( d f a ) ，在x m l 流 查询处理中分别以y f i l t e r 2 lx m l t k 【1 3 为代表。n f a 在某一个状态下，面临某一输入记 号可能存在有多个转换。在x p a t h 表达式中，子孙轴映射到任意层次的匹配，通配符” 映射到任意元素测试。由于子孙轴，和通配符”的存在，许多状态可以同时被激活，x p a h 表达式自然地表示为n f a 的形式。 在实际应用中，经常需要对同一x m l 文档按多个x p a t h 表达式进行查询，这种查询称 为多查询。y f i l t e r 通过共享前缀的形式为多个查询x p a t h 式构造一个单个的n f a ，且n f a 可以动态地更新( 如插入新的查询表达式、删除过时的查询表达式) 。这样极大地减少了查询 状态数，通过路径共享也极大地提升了过滤性能。 y f i l t e r 支持谓词( 包括嵌套谓词) 。y f i l t e r 将谓词中的x p a l h 式提取出来，与主x p a t h 式同样处理，加入到n f a 结构中，在文档查询时得到匹配所有x p a t h 式的x m l 节点。由 于y f i l t e r 在查询前已经对x m l 文档进行了预解析且对所有的x m l 节点进行了编号，所以， 5 中国科学技术大学硕士学位论立第2 章相关工作 在查询时对匹配的x m l 节点记录下从x m l 根节点到该节点的编号列表。文档查询完成后 将谓词中x p a c h 式匹配的x m l 节点编号列表与主x p m h 式匹配的x m l 节点编号列表进行 前缀匹配操作，判断主x p a t h 式的谓词是否满足，从而判断匹配的x m l 节点是否最终满足 x p a t h 式查询条件。 y f i l t e r 存在的缺点有： y f i l t e r 采用后处理计算谓词，不支持谓词的实时计算和查询结果的即时输出： 对x m l 文档进行预处理，将x m l 内容先读入内存并对x m l 节点进行标记，导 致：1 ) 增加了内存开销；2 ) 不能处理数据量大的x m l 文档：3 ) 不适合于对数据流 的连续查询。 d f a 在某状态下面i 临某一输入只存在一个转换，故比n f a 技术效率更高。然而，使用 标准的算法从n f a 构造d f a ，构造出来的d f a 也称为e a g e r d f a ，其状态数随x p a c h 式中 ，轴和”的数目呈指数级增长，并且许多d f a 状态可能根本不会到达。为降低d f a 的状 态数，在x m l t k 中先静态地由x p m h 式构造n f a ，然后在运行时惰性地建立d f a ，称为 l a z yd f a 。初始时l a z yd f a 只有一个初始状态。在查询过程中，当转换到的状态不在原有 状态集中时，就调用从n f a 到d f a 的子集构造法计算出一个新的状态。这样将得到一个较 e a g e rd f a 小得多的状态集。 x m l t k 支持的多个x p a t h 式必须具有前缀依赖关系，不能是任意的x p a t h 式：并且支 持的谓词必须是在当前x m l 节点处理时能通过立即计算得到的，对谓词支持力度弱。 由于x m l 文档的树形结构，s a x 解析器在解析时进行的是深度优先遍历，元素结束 事件引起状态的回退，所以必须使用栈保存曾经经过的状态。 2 1 2 下推自动机 f s m 不缓存文档元素内容，因此不能计算一般的x p a i h 查询。下推自动机( p d a ) 通过 引入栈和缓冲区而具有更强的文法匹配能力。 p d a 技术对位置步的状态构造与f s m 相似，但加入了谓词中x p a t h 式的处理。一种实 现是将谓词中的x p a t h 式嵌入到p d a 中。s p e x 1 4 为x p a t h 式中的每个位置步定义一个下 推变换器并互连为s p e x 网，对谓词中的x p a t h 式也同样构造变换器，然后将它们插入到 s p e x 网中谓词所在位置步的变换器与下一变换器之间，形成s p e x 网的分支和连接。可见 s p e x 为谓词处理提供了一般化的方法。 另一种实现是将谓词处理包含进位置步的处理逻辑中。x s q 1 5 i 每个位置步生成一个 基本的下推变换器( b p d t ，b a s i cp u s h d o w nt r a n s f o r m e r ) 。每个b p d t 有三个状态：开始状 态、表示位置步中谓词计算为真的t r u e 状态和表示谓词还未计算的n a 状态。所有的b p d t s 以二叉树形式联合为一个层次式下推变换器( h p d t ，h i e r a c h i c a lp u s h d o w nt r a n s f o r m e r 、。 b p d t 能根据它在h p d t 中的位置知道谓词是否已经计算和计算的结果。然而x s q 只支持 其定义的五类谓词它为每一类设计了一个处理模板。 6 中国科学技术大学硕士学位论文 第2 章相关工作 以上两者采取直接构造的方法，而x p u s h 1 6 采用状态集构造方法。它为每个x p a t h 式 构造a f a ( a l t e r n a t i n gf i n i t ea u t o m a t a ) 1 7 】谓词中的x p a t h 式和计算条件也被构造到a f a 中：然后自底向上采用状态的闭包构造方法将所有的a f a 翻译为单个x p u s h 机。 p d a 为对谓词进行实时计算，必须对x p a t h 式中谓词还没有计算出来的候选结果进行 缓存。s p e x 和x p u s h 设置一个全局缓冲区，而x s q 为每个b p d t 设置局部缓冲区。谓词 计算结果将及时地传递到缓冲区，对相关候选结果进行输出或清除处理。 在流处理的过程中，栈被用来跟踪需要保存的、随解析事件动态变化的内容。为处理， 轴，s p e x 和x s q 使用栈跟踪当前x m l 节点的深度；x p u s h 使用栈保存当前状态。此外， 与x s q 和x p u s h 不同，s p e x 的状态机没有实现谓词计算逻辑，所以s p e x 使用栈跟踪谓 词计算条件。 2 2 索引技术 x p a t h 式由一系列由轴分隔的元素名( 节点测试) 组成。在解析x m l 的过程中，通过建 立额外的索引结构有助于提高文档的处理速度，加速对路径表达式的处理。 x f i l t e r 1 使用一个元素名索引结构和一个f s m 快速地定位相关的状态。它支持多 x p a t h 式查询，并为每个元素名维持一个哈希表索引，通过路径节点在索引中位置的变化实 现f s m 的状态转换。 仅根据x p a t h 式中的元素名建立索引，索引模式比较低效，会导致许多对x p a t h 式不 必要的检查，过滤时间极大地增长。另一种可行的方法是将x p a t h 式划分成若干子串，对精 心选择的子串集进行索引，这样可以撮小化需要试探的索引数量和代价。x t r i e 18 1 以”轴 和”为分隔符，将公共x p a t h 式子串提取出来组织为一棵t r i e 树。x t r i e 的空间代价是由t r i e 树中子串的数量决定的而x f i l t e r 的空间代价是由索引中元素名的数量决定的。 f a c t o ri n d e x 【1 9 也采用索引技术查询x m l 文档，但不支持流查询，它提出了c h a i n q u e r y 和t r e eq u e r y 的概念，对谓词支持灵活。c h a i nq u e r y 对应没有谓词的x p a t h 式，t r e eq u e r y 对应含有谓词的x p a t h 式。 f a c t o ri n d e x 模仿f s m 的方式，为所有的x p a t h 式( 包括谓词中的x p a t h 式) 建立一棵 索引树，不对主x p a t h 式和谓词中的x p a t h 式进行区分。和n f a 的构造类似，f a c t o r i n d e x 利用各个x p a t h 式之间的相似性，提取公共前缀构造索引树，充分地实现了x p a t h 计算的共 享。索引树中的每个节点都包括两个链表，保存x p a t h 式的结果节点( 主x p a t h 式的匹配节 点) 和叶子节点( 谓词中x p a t h 式的匹配节点) 信息。 f a c t o ri n d e x 对索引树采用自底向上的次序实现查询。在查询中使用链表跟踪谓词的匹 配情况和主x p a t h 式的匹配情况，在白底向上的索引树遍历过程中，将谓词计算结果即时作 用于x p a t h 的匹配结果。 ，7 中国科学技术大学硕士学位论文第2 章相关工作 2 3 其他查询技术 2 3 1x s m x s m 2 0 将x q u e r y 查询翻译成高效的x m l 流机器( x s m s ) ：它先将查向分解为子串， 每个子串映射成一个x s m ，x s m 实现了x q u e r y 查询的基本操作：然后将各x s m s 组合成 x s m 网络，减少x s m 执行的动作和测试次数以及缓冲区数量：最后，优化的x s m 被编译 为c 程序。 x s m 使用具有缓冲区的状态转换器模型处理x m l 流。它引入多个中间缓冲区缓存子 串的结果。缓冲区分为输入和输出两类，分别具有读、写指针。在状态转换时，x s m s 通过 指针访问并查询缓冲区中的内容，执行一系列的操作。 2 3 2 代数语义查询 x m l 代数系统【2 1 【2 2 】_ 一般都是嵌套关系代数的扩展，具备嵌套关系代数的主要特征。 它们的基本操作是将查询模式体( 树结构) 与x m l 文档( 图结构) 进行条件匹配，产生满足模 式体结构的结果树。 x s t r e a m c a s t 7 采用c s 结构，实现了基于流的连续查询。它最新颖的技术在于将x m l 数据流分段为信息块然后进行传输。它在服务器端递归地将x m l 文档树分成许多片断 ( f r a g m e n t ) ，在每个分割点上插入一个洞( h o l e ) 并分配i d i 在客户端对分块的x m l 流数据 使用白定义的查向代数，以管道的方式进行实时查询。 x s t r e a m c a s t 的x q u e r y 查询代数在x m l 查询代数基础上增加了操作x m l 流片断的特 性。它将x q u e r y 查询翻译成l i s tc o m p r e h e n s i o n s ( l c s ) ，这类似于x m l 代数的基本操作：然 后从l c s 得到代数形式。 2 4 对x p a t h 式的支持力度 x p a t h 式是查询的核心，对x p a t h 式的支持力度决定了查询的灵活性和查询能力的强弱。 在x p a t h 式位置步的三个组成部分中，对轴和谓词的支持是处理的重点。对比已有的x m l 流奄询引擎，本节从多个x p a t h 式、轴和谓词这三个方面比较它们的支持力度。 2 4 i 多查询支持 多查询是指对同一数据流实旋多种查询。x m l 流查询引擎必须并发地处理同一数据流 上的多查询。另外，如何共享公共的查询部分是提高处理效率的重要途径。 f s m 技术使用前缀共享的方法实现多查啕 2 3 】，而索引技术使用子串匹配或元素名匹 配的方法具有更大的灵活性。 r 。 中国科学技术大学硕士学位论文 第2 章相关工作 以上工作只共享查询的公共部分，文献 2 4 给出了共享任意操作的解决方案。它将所有 查询作为图引入，每个查询以子图的形式包含所有的原子查询。由于最大公共连接子图问题 是n p 一难解和n p 完全的，文献 2 4 1 使用几个启发式的算法检测不同查询中的公共查询，然 后在查询中菸享它们。 2 4 2 对x p a t h 反向轴的支持 计算x p m h 反向轴需缓存已经解析过的x m l 数据，阻碍了x p a t h 式的有效计算。所以， 在流处理器中支持反向轴的可行方法是在流处理前重写包含反向轴的x p m h 式，用等价的前 向轴代替反向轴。 文献 2 5 1 基于x p a t h 轴对称理论建立不包含反向轴的x p a t h 式的等价形式。该文提出两 条规则集：r u l e s e t l 引入基于标识的连接，产生的路径中包含的连接数与输入路径中包含的 反向轴个数相同，结果路径表达式复杂；r u | e s e t 2 产生的路径表达式不包含连接，但时间复 杂度与输入的位置步呈指数级关系，而使用r u l e s e t l 只具有线性的复杂度。 x a o s 2 6 提出了重写x p a t h 的另一种途径。它将x p a h 式构造为一棵x t r e e ，然后移 除x t r e e 中所有节点的祖先轴和父亲轴，并构造从根节点到该节点的子孙轴，得到一个等价 的有向无环图x d a g 。 2 4 3 对谓词的支持 谓词对x p a t h 计算的影响表现在：处理匹配最终位置步的数据项时，谓词可能还没有 被计算，无法确定数据是否就在结果中。所以必须缓冲数据，并标记缓冲区中哪些数据项被 计算结果影响。 使用f s m 技术的处理器，不支持谓词的实时处理或者只支持严格结构匹配的谓词。扩 展的p d a 具有栈和缓冲机制，实现了对谓词的实时处理。 查询中也可能存在大量的公共谓词。n i a g a r a c q 6 、c q o p 2 7 1 对共享公共谓词的查询 进行分组，对每个数据包首先计算分组中的公共谓词。但它们需要x m l 数据包的d o m 表 刁i 。 x p u s h 的重点是消除谓词中的公共子表达式。在构造出的a f a 中包含谓词条件表达式， 利用自底向上的方法对谓词中的公共条件表达式构造在同一个p d a 状态中实现谓词计算的 共享。 2 5 本章小结 当前x m l 流查询处理中还存在许多待解决的问题：如谓词的实时计算：对复杂x p m h 式的支持；对x p a t h 查询的优化：如何即时输出匹配的部分结果；如何降低x m l 流查询处 理器的时空复杂度等。 - 9 - 中国科学技术大学硕士学位论文 第2 章相关工作 对比各种x m l 流处理技术，p d a 能支持较强的查询语义，实现谓词的实时计算且时 空复杂度较低，显示了其优越性。如何构造状态数少的p d a ，实现有效的缓存和谓词计算， 提供对多查询的有力支持，是设计流处理器首要考虑的因素。所以，在x s i e q 流查询系统 中，我们采用了p d a 技术，通过在有限状态机上添加索引信息，实现了对复杂x p a t h 式和 谓词的支持，实现了谓词的实时计算，并能够在查询时即时输出匹配的部分结果。 中国科学技术大学硕士学位论文 第3 章x s i e q 系统与基本x s i e q 机 第3 章