（计算机软件与理论专业论文）基于谓词的xml数据流查询处理研究.pdf

哈尔滨t 程大学硕士学何论文 摘要 随着x m l 数据在互联网络上应用的不断增长，越来越多的信息以 x m l 的格式通过网络进行发布和交换。在这些应用中，x m l 数据以流的 形式不断地快速到达，而针对x m l 数据流上的查询是对大量的x p a t h 表达式的查询。因此，如何在x m l 数据流上对大量的x p a t h 表达式进 行查询处理是一个重要问题。 本文围绕x m l 数据流的查询处理问题展开研究工作，就如何在x m l 数据流上有效地处理大量路径表达式进行了研究，针对简单路径表达 式和复杂路径表达式的查询处理技术，提出了一种新的基于谓词的方 法来对简单路径表达式进行过滤，该方法可以有效地支持对简单路径 表达式中的通配符“：i c ”号和后代轴“”的处理；通过实验验证了该 方法优于已有的基于自动机的处理方法；同时设计了多阶段哈希表谓 词索引来对该方法进行优化，以提高过滤处理的性能：通过对包含有 分支结构的复杂路径表达式的分解，提出了采用路径流的方法基于简 单路径匹配对复杂路径表达式进行查询处理的方法：在对x m l 数据流 应用需求进行深入分析的基础上，设计了一个x m l 数据流查询处理模 型，并对每个模块的主要功能进行了详细的介绍。 关键词：x m l 数据流；x p a t h 表达式；查询处理；谓词索引 a bs t r a c t w i t ht h ex m ld a t ao nt h ei n t e r n e ti n c r e a s i n gr a p i d l y ，i t i sw i d e l y a p p l i e di nt h ee m e r g i n ga p p l i c a t i o ns y s t e m s i nt h e s ea p p l i c a t i o n s ，p l e n t y o fx p a t he x p r e s s i o n sa r ep r o c e s s e da g a i n s tx m l d o c u m e n t st h a ta r r i v e r a p i d l y i ns t r e a mf o r m c o n s e q u e n t l y ，t h em a j o rr e s e a r c hc h a l l e n g eo f q u e r yp r o c e s s i n go nx m l s t r e a mi st oe f f i c i e n t l yh a n d l eal a r g en u m b e r o fx p a t he x p r e s s i o n s i n t h i st h e s i s i ti sf o c u s e do nt h a tr e l a t e d t oq u e r yp r o c e s s i n go n x m ls t r e a ma n de f f i c i e n t l yh a n d l eal a r g en u m b e ro fx p a t he x p r e s s i o n s o nx m ls t r e a m sw i t hf o c u s i n g o nt h ep r o c e s s i n go fs i m p l e x p a t h e x p r e s s i o n sa n d b r a n c h e dx p a t he x p r e s s i o n s i sr e s e a r c h e d a n o v e l p r e d i c a t e - b a s e dm e t h o di sp r o p o s e df o rt h ep r o c e s s i n g o fs i m p l ex p a t h e x d r e s s i o n s t h em e t h o ds u p p o r t st h ee f f i c i e n tp r o c e s s i n g o fw i l d c a r d c h a r a c t e ra n dd e s c e n d a n t a x i so fs i m p l ep a t he x p r e s s i o n s ih e p e r f o r m a n c eo ft h em e t h o da r e 。e v a l u a t e da c c o r d i n g t oe x p e r i m e n t sa n d s h o wt h a to u rp r e d i c a t e b a s e dm e t h o d t a k e sl e s st i m et h a ne x i s t i n g a u t o m a t o n b a s e dm e t h o d t oi m p r o v et h ef i l t e r i n gp e r f o r m a n c e ，an e w d a t as t r u c t u r ei si n t r o d u c e d ，p r e d i c a t e i n d e xi m p l e m e n t e dt h r o u g n m u r i p l es t a g e so fh a s h t a b l e s n e x t ，a l lb r a n c h e dx p a t he x p r e s s l o n s a r e d e c o m p o s e di n t os i m p l ex p a t he x p r e s s i o n sa n dt h e b r a n c h e dq u e r l e sa r e e v a l u a t e db a s e do nt h eo u t p u to fs i m p l ex p a t he x p r e s s i o n sf i l t e r i n g o n t h eb a s i so ft h e s e ，t h ed e s i g no fam o d e lf o rx m l s t r e a mq u e r yp r o c e s s m g i sp r e s e n t e da n dp r o v i d ead e t a i l e dd e s c r i p t i o no fm a j o rf u n c t i o no f1 t s c o m p o n e n t s k e y w o r d s ：x m ls t r e a m ；x p a t he x p r e s s i o n ；q u e r yp r o c e s s i n g ；p r e d i c a t e i n d e x 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中己 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：埠 日期：咖秽留年专月i2 ，日 哈尔滨t 程大学硕士学位论文 1 1 研究背景 第1 章绪论 在进入信息化时代的今天，人们每天会面对大量的各种形式的信息，对 信息的处理变得与人们的生活密切相关。互联网技术的发展为人们提供了丰 富的信息来源，同时也对信息处理技术提出了更高的要求。在数据库研究领 域，研究人员不再仅仅面对传统意义上的结构化数据，对各种形式的非结构 化、半结构化数据的处理逐渐成为研究的热点。经过多年的发展和应用，可 扩展标识语言x m l 己经被广泛地应用于半结构化的数据描述中。作为一个精简 的s g m l 子集，x m l 具有自我语义描述，便于创建和传输，易于对数据进行封装 等诸多特性。因此，x m l 已经成为互联网上信息表示和信息交换的事实标准。 面对互联网上海量的信息，个性化的定制服务逐渐成为人们获取信息的 一个重要手段。越来越多的信息提供者开始在互联网上以x m l 格式发布信息。 n i t f ( n e w si n d u s t r yt e x tf o r m a t ) 是被世界各地的新闻机构广泛使用的，用 于发布新闻信息的格式标准；r s s ( r e a l l ys i m p l es y n d i c a t i o n ) 是另外一种 基于x m l 的信息发布方式，它允许信息的发布者以x m l 格式来发布信息，用户 可以根据信息发布者的u r l 或使用关键字来订阅感兴趣的信息内容。目前国内 的很多新闻网站都已经开始提供基于r s s 的新闻定制服务。 对于个性化的信息定制服务来讲，其核心技术是如何对大量的用x m l 格式 表示的数据进行有效的处理。用户通过图形化界面或其它方式将他们的订阅 请求发送给服务器，这些订阅请求被当作对x m l 数据的查询保存在服务器上。 当系统中产生或从其它信息发布者处获得新的x m l 数据时，需要判断每一条新 的x m l 数据与哪些用户查询相匹配。这种查询匹配处理的难点在于： 1 对于信息定制服务来说，其用户的数量往往是巨大的，因此用户所提 交查询的数量也是巨大的。显然，以传统的方式对每条查询进行匹配处理， 是不能够满足系统服务性能的要求。如何同时对大量的用户查询进行处理是 所面临的一个挑战。 哈尔滨工程大学硕士学位论文 2 在信息定制服务系统中，往往每时每刻都会有新的x m l 数据产生，这 些新的数据就像数据流一样源源不断地到达，系统必须快速及时地对到达的 数据进行处理和分发。传统的将数据保存后建立索引，然后进行查询的处理 方式，很难对快速的数据流进行及时的处理。 此外，) ( m l 还被很多其它类型的应用系统采用为数据表示的格式。例如， 在w e b 服务以及应用集成领域，不同系统之间相互传递的消息都开始采用x m l 格式表示。大量的以x m l 格式表示的消息在网络被发送和接收，对于应用系统 或消息路由服务来说，这些消息形成了一个源源不断的数据流嗍。对x m l 数据 流处理技术的研究不但被学术界所关注，越来越多的企业也开始关注相关技 术和产品的研发，例女i m i c r o s o f t 和b e as y s t e m s 公司都已经开始致力于开发 下一代基于x m l 的消息处理中间件。目前，在现有的相关软件产品中，还仅针 对于已知格式的数据流进行处理，对于大量的不同格式或格式未知的数据流 进行处理是一个有待于进一步研究的领域。 1 2 研究的现实意义 主动服务姆是近几年来提出的建立在w e b 服务技术规范之上的新的服务模 型。它能够根据用户的个性化要求和特点，对服务进行定制和帮助，从而改 变服务无法根据用户需要而动态变化、主动适应用户要求的状况。 目前广泛应用的订购和发布系统就是主动服务中的一个典型应用。而其 中关键技术之一就是海量x m l 数据的查询问题。在订购阶段，用户利用x p a t h 表达式描述其需求，保存到系统中。在发布阶段，当数据以网络速度流入时， 系统根据描述，判断数据流是否满足某个用户的需求。如果满足，则触发应 用程序采取某种动作，如向用户返回相关的文档等。如何在x m l 数据流上高效 地执行查询处理成为主动服务实现中要解决的关键问题之一。 1 3 国内外研究现状 x m l 过滤和x m l 查询处理已经被广泛地研究，大多数工作都集中在存 储、检索和通过关系数据管理方法来处理x m l 数据。目前，x m l 数据流的查 询处理研究已经取得了一定的成果，如x f i l t e r 、x t i r e 、y f i i t e r 、 2 哈尔滨工程大学硕士学位论文 i n d e x f i l t e r 和x a o s 等。文献 4 中的x f i l t e r 将有限状态机模型( f s m ) 引 入x m l 流的过滤处理中，通过建立x p a t h 的确定状态机，实现简单x p a t h 表 达式的处理。x t r i e 嘀提出了只包含父子关系的子路径表达式索引机制，并使 用索引提取多个查询的公共子路径，实现包含谓词逻辑x p a t h 表达式处理的 y f i l t e r 系统是对x f i l t e r 的扩展，y f i l t e r 将多个x p a t h 表达式合并成为一 个单独的非确定有限状态机，实现多个x p a t h 表达式的高效查询处理。文献 6 提出了x a o s 算法，该算法能够在x m l 数据流中有效地处理x p a t h 表达式 的前向和后向运( f o r w a r d b a c k w a r da x e s ) 。文献 7 给出了使用索引的 i n d e x f i l t e r 过滤算法，并比较了基于i n d e x - f i l t e r 和基于y f i l t e r 的多查 询处理技术。 在这里主要讨论与本文研究工作最相关的技术，是对x m l x p a t h 过滤的 方法。这些方法可以分为两类。一类是基于自动机的方法，另一类是基于索 引的方法。基于自动机的方法是基于系统处理的x p a t h 表达式构造一个自动 机，自动机状态的转换由被处理的x m l 文档路径触发。x f i l t e r 是转换成有 限自动机，这种方法不能处理重叠部分，特别是表达式之间的前缀重叠， y f i l m r 通过在系统中对所有x p a t h 表达式构造一个非确定有限自动机来对 x f i l t e r 进行扩展。它能处理表达式中的共同前缀，n f a 的每个终态与一个表 达式列表相关，x m l 文档一次解析一个标签触发n 】认中的状态转换，到达 终态表明被处理的x m l 文档被匹配。传统的n f a 和y f i l t e r 的数据结构之间 的不同是当第一个终态到达时，y f i l t e r 的n f a 不停，直到访问完所有可能要 接收的状态，这样算法能确定n f a 中的所有匹配。y f i l t e r 的文章证实了它的 性能优于) ( t i l e 。另一种基于自动机的方法x p u s h ，为系统中的x p a t h 表达 式懒散地构造成一个单一的决策下推自动机，对于在线选择信息处理。这种 方法的缺点是从被构造的自动机中增加或删除查询比较困难。 基于索引的方法是在x m l 文档或x p a t h 表达式上利用提前计算的模式， x t n e 提出了一种基于t r i e 的索引结构，把x p a t h 表达式分解成只含 p a r e m c h i l d ( ) 符号，因此，在查询中这些共同的子串能被共享。除了这种 共享，y f i l t e r 已经证实在固定的负载下比它有更好看性能。 哈尔滨 ：程大学硕十学何论文 1 4 本文的主要工作 本文在大量前人研究的基础上，系统研究了x m l 数据流查询处理及优化的 关键技术，如基于自动机的查询技术，基于索引的查询技术等。本文所做的 主要有工作有： 1 深入研究3 x m l 的特性以及现有的x m l 数据流查询处理的相关技术。 2 从不具有分支路径和元素内容约束的简单路径表达式的处理入手，研 究了针对简单路径表达式的x m l 数据流的查询处理技术。 3 提出了一种新的基于谓词的方法对简单路径表达式进行过滤处理，并 通过谓词索引的方法来优化该方法。 4 在对简单路径表达式进行过滤处理的基础上，提出基于简单路径匹配 的复杂路径表达式查询处理的技术。 5 在简单路径表达式和复杂路径表达式研究的基础上，提出一个x m l 数 据流查询处理模型，并详细介绍了各模块的主要功能。 1 5 本文的组织结构 第1 章介绍了研究的背景、意义，国内外相关技术研究的情况及本文所做 的工作和本文的组织结构。 第2 章介绍了x m l 语言及对x m l 数据的建模和相关解析技术，然后对路径表 达式和x m l 查询语言进行了介绍；针对本文所研究的x m l 数据流查询处理，还 对当i j i j x m l 数据流查询处理技术进行了综述，并介绍了两个x m l 数据流处理原 型系统。 。第3 章主要介绍了针对简单路径表达式查询对x m l 数据流进行过滤处理的 技术，并提出了基于谓词的x p a t h 表达式过滤处理的方法，以及利用谓词索引 对该方法进行改进。最后通过实验对该方法进行了性能分析。 第4 章详细地介绍了在x m l 数据流上对复杂路径表达式进行查询处理的方 法。首先讨论了对路径表达式中所包含的节点内容约束的处理，之后介绍如 何对复杂路径表达式进行分解，在此基础上提出基于简单路径匹配的复杂路 径表达式连续查询处理的技术。 第5 章对x m l 数据流模型的应用需求进行了分析，提出了一个x m l 数据流查 4 哈尔滨丁程大学硕十学位论文 询处理模型。 第6 章对全文进行了总结，指出本文的研究成果及后续工作。 哈尔滨t 程大学硕士学位论文 第2 章x m l 与x m l 数据流 2 1x m l 语言 可扩展标记语言( e x t e n s i b l em a r k u pl a n g u a g e ) ，简称x m l 语言呻钒旧1 ， 是由w 3 c 组织提出的一种简单灵活的文本数据格式。x m l 语言是从s g m l 语 言派生出来的，是s g m l 语言的一个子集。定义x m l 语言的目的在于弥补h t m l 语言在对数据语义和结构上表达能力的不足。目前，x m l 越来越广泛地被应 用于各个领域，己经成为互联网上数据表示和数据交换事实上的标准。 2 1 1x m l 文档基本结构 一个x m l 文档通过标记( t a g ) 来表示一组数据对象，其中每个数据对象被 称为一个元素( e l e m e n t ) 。x m l 文档中的每个元素通过一个开始标记和一个结 束标记指定了该元素所包含数据的范围，标记名描述了该元素所包含数据的 语义。元素与元素之间存在着层次关系，即一个元素可以被包含在另一个元 素的范围之内。一个元素的内容可以是嵌套的子元素，也可以是属性或字符 串值。每个x m l 文档都有一个唯一的根元素，包含了该文档的所有内容。下面 给出了一个良构的x m l 文档的例子。 x q u e r yg u i d e 1 0 s c o t tb o a g 3 5 0 0 p r i c e 元素大于3 5 0 0 的b o o k 元素 选取b o o k s t o r e 节点下的所有包含 b o o k s t o r e b o o k p r i c e 3 5 0 0 t i t l ep r i c e 元素大于3 5 0 0 的6 d0 _ 后节点下 的t y t l e 元素 在x p a t h 标准中，谓词操作的实质是对查询的中间结果进行过滤，包含谓 词的x p a t h 表达式不再是线性的，由于谓词操作在每次对当前节点集进行过滤 时都要执行，因此如何处理x p a t h 表达式中的谓词是影响查询时间空间复杂度 的一个关键因素。x p a t h 中谓词通常有三种形式；元素位置、属性比较和分支 选择，而分支选择中每个分支由前两种形式组成。 2 2 2 本文所处理的路径表达式 本文研究工作所支持的路径表达式语法如图2 2 所示： 图2 2 本文所处理的路径表达式语法 哈尔滨 ：稃人学硕十学位论文 简单路径表达式是在本文所提出的文档过滤技术中用来表示用户查询时 的x p a t h 表达式，它属于x p 。州的范围，即不允许在路径表达式中出现谓词 分支。本文中所用到的简单路径表达式的语法如图2 3 所示： 图2 3 简单路径表达式语法 一条简单路径表达式由一个或多个定位步( s t e p ) 组成，定位步之间通 过“”或“”进行分隔，表示两个定位步之间是父子或祖先一后代关系； 简单路径表达式中的每个定位步可以使用一个节点名或是节点通配符，在其 中不包含任何谓词；最后一个定位步后可以添加对其节点内容的约束，其约 束内容只能对数值和字符型数据进行比较。一条简单路径表达式中所包含定 位步的个数被记成是这条简单路径表达式的长度。如果在表达式最后有对文 本内容的约束，不算作一个定位步，而算成是最后一个定位步的内容。 2 3x m l 查询处理技术 随着) 【m l 作为数据表示和交换的标准被广泛地应用，在过去的几年中，在 x m l 数据管理方面已经有大量的研究工作和成果被发表，不少研究机构和企业 纷纷推出对x m l 数据进行管理或处理的工具及原型系统。对x m l 数据的查询处 理是相关研究工作中很重要的一部分，本节对目前数据查询处理技术的发展 现状做一简单综述。 现实中被处理的数据可以分成两种形式，一种是被存储在一起的x m l 文档 库，如用来表示和保存研究文献信息的d b l p 数据库；另一种是通过网络接收 到的x m l 数据流，如通过网络以x m l 格式发布的新闻信息；两种形式的x m l 数据 在应用场景和处理技术上都存在着很大的不同。 哈尔滨i 摧人学硕十学位论文 231 x m l 文档数据库查询 本文中x m l 文档数据库”“是指大量的被存储在起的数据。这样的x m l 数 据可以被存储在关系数据库系统中，也可以被存储在专用的x m l 数据库系统 中，同时也可以以文件形式存储。这罩，主要介绍后两种x m l 数据库上的查嘲。 对x l 文档库进行查询的应用模型如图24 所示。 1 查询请求 2 查询结果 | 磊_ l x m l 文档f ：，： 查询处理器 幽24x m l 文档数据库布嘟应h 模型 在这个应用模型中大量的文档被集中存储和管理用户可以向查询服务 器提交查询请求，查询服务器在收到用户的查询请求后在x m l 文档库上进行查 嘲处理，将得到的结果返回给用户。用户的查询请求一般是某利? x m l 查询语言 的语句，其最基本的形式都是路径表达式：返回的查询结果可以是文档库中 能够匹配用户查询的文档，也可以是文档中f 好匹配用户查询的h 段。这样 的应用具有两个特点： 1 整个应用系统的运行主要是查询骀动的，即只有当用户提交查询时， 查询服务器才进行查询处理。通常，用户提交查询的数量不会很大，因此与 关系数据库系统中类似，查询服务器一次仅处理一个用户查询，为这个查询 生成查询计划，通过在文档库上执行这个查询计划来获得结果。 2 由于保存在文档库中的x m l 数据量很大，在刘用户查询进行计算的过 程中，为了提高性能必须对x m l 数据进行索引。这一点与关系数据库系统中情 形类似，系统要在数据集上维护索引结构，在文档库中的x m l 数据发生变化时， 对索引结构进行更新。 哈尔滨工程大学硕士学位论文 在专用的x m l 文档库中进行查询时，通常将x f l l 文档建模成一棵文档树或 者图的形式，在这一研究领域中已有了大量的研究工作。例如，g a l a x 是一个 基于d o m u 7 1 模型的x q u e r y 查询引擎；文献 1 8 ，1 9 3 中提出了一种基于随机访问 的在x m l 文档上进行x p a t h 查询处理的内存算法。同时，大量的针对树或图的 索引技术啪。2 妇被提出，用于支持对x m l 文档的查询处理及查询优化。其中结构 索引技术是以有向图的形式对x m l 文档的结构建立索引，通过在结构索引上进 行查询处理，从而减小了搜索空间，提高了查询处理的效率。在这些索引结 构中，可以支持路径查询，t i n d e x 和砼2 1 可以支持带有谓词约束的特定查询， 但这些索引结构并不支持包含有后代轴的查询。除了上述的结构索引外，还 有一些特殊的索引结构可以用于支持对x m l 文档的查询处理。 除了在x m l 文档库上进行查询处理的研究外，还有一些研究工作致力于对 查询处理进行优化。例如，文献 2 3 提出了在存在物化视图的情况下，通过对 输入的x m l 查询进行改写来提高查询性能的方法。 2 3 2x m l 数据流查询 目前，在互联网上越来越多的信息被以x m l 格式发布和传输。对于这些 信息的使用者来说，x m l 格式的数据是以数据流的形式实时到达的，将这些数 据完全保存下来再进行处理，往往在性能上不能够满足应用的需求。因此， 必须对这样的x m l 数据采用与) ( m l 数据库不同的模式进行处理。 对x m l 数据流进行查询处理的应用模型如图2 5 所示。在这个应用模型 中，首先会有大量的用户，每个用户会根据自己的兴趣提交对x m l 数据的查 询请求到一个x m l 路由分发服务器。通常用户的查询请求是以路径表达式的 形式表示，并且每个用户都可能提交大量的查询请求，例如，在网络环境下， x m l 数据从产生者到使用者往往会经过多次路由和分发，一个路由分发服务器 可以被看成是其邻居服务器的一个特殊用户。此时，这个路由分发服务器提 交到邻居服务器上的是其所有用户的查询请求，因此数量会很大；路由分发 服务器必须能够对这些用户查询进行有效管理。x m l 数据是以数据流的形式不 断到达的，路由分发服务器对于每一个接收到的x m l 文档必须能够快速判断 这个文档能够满足哪些用户查询，并以此将整个文档或文档中满足用户查询 哈尔滨工程大学硕士学位论文 请求的片断发送给被匹配查询相对应的用户。在这个应用模型中，与x m l 数 据库查询应用不同，对于x m l 数据的处理具有以下两个特征： ( 1 ) 对x m l 数据的处理是由到达的x m l 文档驱动的。也就是说，只有当有 新的x m l 文档到达时，系统才会启动查询处理。由于数据到达的速率可能会 很快，将其完全读到内存中建立一个对应的文档树后进行查询，或者为其创 建索引来支持查询在性能上都很难满足应用的需求。因此，只能够采用推模 型技术将其扫描一遍，存扫描的过程中完成查询处理。目前的处理技术都是 采用s a x 解析器g , j - , l j 达的x m l 数据进行解析，产生一个事件流，通过对事件 的响应来进行查询处理。 ( 2 ) 路由分发服务器上用户所提交查询的数量是巨大的，当到达一个x k l l 文档时，依次对每个查询进行计算显然是不可行的。因此必须对用户提交的 查询进行处理，用一个精心设计的数据结构将所有的用户查询管理起来，当 x m l 数据流到达时，通过在这个数据结构上的处理，快速找出被匹配的查询。 x m l 文档流 冒 。旦苹 a a 垒 j j 匹 配 的 文 档 路由分发服务器 图25x j a l 数据流查询应用模型 这里所介绍的x m l 数据流查询处理问题与连续查询问题“4 2 5 2 “，以及发布 订阅问题很相似。在连续查询应用中，用户的查询是相对固定的，当数据发 生更新时，用户可以获得与查询相关的更新的数据。发布订阅应用是以复杂 的谓词约束为基础，在信息发布者和订阅者之间实现多对多的数据包路由。 枷l 数据流查询处理可以被看成是针对x m i 。数据的连续查询，也可以被看作是 - - 二 e e 基于x m l 格式的信息发御与订阅处理。这是一个近些年来倍受关注的研 究方向，大量的技术和方法被提出用于解决数据流上的查询处理问题。 哈尔滨工程大学硕士学位论文 已有的技术在) ( m l 数据流上进行查询处理时，往往仅支持路径表达式的 部分特征，或对所支持的特征进行_ 定的限制。x f i i t e r 乜7 1 和y f i l t e r 汹删使 用基于自动机的技术，对包含有后代轴和通配符的路径表达式查询进行处理。 x s m 是一个基于t r a n s d u c e r 技术的x o u e r y 处理器，可以对不包含后代轴的 x q u e r y 查询进行处理。文献 3 0 对x m l 数据流上x p a t h 查询处理所需的缓存 空间进行了分析，但仅针对不包含通配符的x p a t h 查询。x s q 口”使用带有缓存 区的p d t ( p u s h - d o w nt r a n s d u c e r ) 结构对x p a t h 查询进行处理，可以支持对后 代轴和谓词约束的处理，但限定每个查询节点只能够包含一个谓词约束。 s p e x 怕羽使用一个t r a n s d u c e r 的网络对数据流进行处理，并且支持与x s q 类似 的x p a t h 查询。 除了上述的数据流查询处理技术外，还有一些研究工作对查询处理l 搀其 它方面进行了研究。r a m d r o p 研究了如何利用数据的模式信息来对x m l 数据流 上x q u e r y 查询处理进行优化引。提出了对x q u e r y 查询进行改写的技术，用 于在x m l 数据流上对大量的x p a t h 表达式查询进行支持。在数据流上做了相 当多的工作，并对如何支持大量查询请求的连续处理进行了研究。y f i l t e r 通过非确定有限自动机在大量x p a t h 查询之间共享前缀处理；x t r i e 1 使用 t r i e 结构对x p a t h 查询中的公共子表达式进行索引：x p u s h 5 1 使用确定有限自 动机对包含谓词约束的x p a t h 查询进行了处理。 2 4x m l 数据流原型系统 对于j ( m l 数据流的查询处理问题，近些年来国际会议v l d b 和a c ms i g m o d 等都将数据流作为一个热点问题来讨论。大多数的研究者都是通过实验来对 自己的研究成果进行验证，为了能够公正客观地对比各种技术和方法的优缺 点，有不少的研究者会将实验用的源代码共享出来，供其它研究者参的考。 这里，将介绍两个已经公开发布的原型系统。 2 4 1 华盛顿大学的x m l t k 系统 x m l t k 涵1 是华盛顿大学计算机科学与工程系开发的一套面向x m l 数据流的 工具集，其中包含了对文档进行排序、压缩、以及查询处理等多个工具。在 1 7 哈尔滨工程大学硕士学位论文 数据流处理方面，有两个重要的贡献：一是实现了一个基于确定有限自动机 的数据流处理器：另一个是设计和实现了针对数据流的索引结构s i x ( s t r e a m i n d e x ) 。s i x 索引要求先对x m l 数据进行索引，然后将索引与数据一起进行发 送，这样x m l 数据流处理器才能够利用索引对接受到的x m l 数据进行处理。 这里，主要介绍x m l t k 的数据流查询处理技术。 x m l t t ( 在数据流上进行查询处理的基本思路是：首先将个复杂的