（计算机软件与理论专业论文）xml流的复杂查询处理及其优化技术.pdf

x m i ，流的复杂矗询处理及j 优化技术 摘要 x m l 已经成为i n t e r n e t 上数据交换的标准。x m l 不仅可以作为个完整的 文件传输，而且还有可以以一种串行数据流的方式传输。近年来，针对x m l 数 据流的处理在研究领域引起了广泛的兴趣。x m l 流处理的挑战是如何能有效地 处理巨量的针对x m l 数据流的查询集。这种查询通常是基于路径表达式的，如 x p a t h 、x q u e r y 。 随着应用需求的增长，查询表达式也变得越来越复杂。我们发现，对于具有 嵌套a n d o r 谓词的复杂t w i gp a t t e r n 查询，目前还没有有效的处理方法。为此， 我们开发了一个称为l e o x s q 的x m l 流处理系统。在l e o x s q 中，我们提出一 种新的方法解决上述查询问题。围绕l e o x s q ，我们还开发了节点缓存管理组件 和基于d t d 的查询优化组件。本文的主要贡献概括如下： 1 ) 提出一种新的方法处理具有嵌套a n d o r 谓词的复杂t w i gp a t t e r n 查询。 在该方法中，将a n d o r 谓词作为单独的抽象语法树来处理，利用基于运j j ：时 栈的算法，结合自顶向下与自底向上的过程，有效处理针对x m l 流的复杂t w i g p a t t e r n 查询。 2 ) 将所有t w i gp a t t e m 组合成单个可共享前缀的查询树，从而可以节省查询 处理的空问与时间，并以输入的x m l 流顺序单遍处理所有的查询。通过对查询 树中逻辑表达式进行公共子表达式的共享处理与短路计算，进一步提高了查询处 性能。 3 ) 提出了一种针对单个查询的基于语义链的缓存管理算法，并将其扩展并 应用到前缀共享的多查询环境下。该算法能够以尽可能小的缓存空问处理递归嵌 套文档与一对多关系文档。基于一种基于运行时栈的x m l 部分编码技术，来判 断缓存节点间语义关系。这种方法只对进入运行时栈的节点编码，大大缩小了编 码的范围。 4 ) 分析影响x m l 流数据处理性能的关键因素。利用正则树文法和树自动机 作为理论指导，阐述了使用d t d 进行查询优化的方法。基于该方法，实现了查 询优化组件。该组件在系统运行前进行预处理，不影响系统运行时的性能。 关键字：x m l 流，复杂查询，t w i gp a t t e r n ，d t d ，缓存 x m l 流的复杂查询处理及其优化技术 a b s t r a c t 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 ) h a sb e c o m et h ee x c h a n g es t a n d a r df o r d a t ao nt h ei n t e r a c t i nm a n ya r e a s ，x m ld a t aa r en o to n l yt r a n s f e r r e da sa c o m p l e t ed o c u m e n t ，b u ta l s oa sc o n t i n u o u sd a t as t r e a m s t h ep r o b l e mo f p r o c e s s i n gs t r e a m i n gx m ld a t ai sg a i n i n gw i d e s p r e a da t t e n t i o nf r o m t h e r e s e a r c hc o m m u n i t y t h ek e yc h a l l e n g eo ft h i sp r o b l e mi sh o wt op r o c e s st h e h u g es e to fq u e r i e so v e rx m l s t r e a m se f f i c i e n t l y q u e r ye x p r e s s i o n sh a v eb e c o m em o r ea n dm o r ec o m p l e xt om e e tt h e i n c r e a s i n ga p p l i c a t i o nr e q u i r e m e n t s n o wt h e r ei sn oa ne f f e c t i v em e t h o dt o p r o c e s st h ec o m p l e xx p a t he x p r e s s i o nw i t hn e s t e da n d o rp r e d i c a t e s i nt h i s p a p e r , w ed e v e l o p e das t r e a mp r o c e s s i n gs y s t e mc a l l e dl e o x s q ，a i m i n ga t s o l v i n gt h i sv e r yp r o b l e m n o t e w o r t h y , b u f f e r i n gm a n a g e m e n ti sc o n s i d e r e da s a n o t h e rk e yp r o n e mi nl e o x s q t h ec o n t r i b u t i o n so ft h i sp a p e ri n c l u d et h e f o l l o w i n g ： 1 ) w ep r e s e n tan o v e la p p r o a c hf o rp r o c e s s i n gc o m p l e xt w i gp a t t e r nw i t h o r p r e d i c a t e s a n da n d p r e d i c a t e so v e rx m ld o c u m e n t ss t r e a m i nt h e a p p r o a c h ，a n d 0 rp r e d i c a t e so fan o d ea r er e p r e s e n t e da sas e p a r a t ea b s t r a c t s y n t a xt r e ea s s o c i a t e dw i m t h en o d e 2 ) f o rt h ei m p r o v e m e n to ft h ep r o c e s s i n gp e r f o r m a n c eo ft w i gp a t t e r n s ，a l l t h et w i gp a t t e m sa x ec o m b i n e di n t oa s i n g l ep r e f i xq u e r yt r e et h a tr e p r e s e n t ss u c h q u e r i e sb ys h a r i n gt h e i rc o m m o np r e f i x e s w ep r o v i d et w oo p t i m i z a t i o nm e t h o d s t oa c c e l e r a t et h ee v a l u a t i o no fl o g i ce x p r e s s i o n si naq u e r yt r e e 3 ) w ep r e s e n tab u f f e r i n gm a n a g e m e n ts t r a t e g yb a s e do n as e m a n t i cl i n kf o r as i n g l eq u e r y , a n dt h e ne x t e n di tt ot h ec i r c u m s t a n c ef o rm u l t i p l eq u e r i e s w e d e v e l o pap a r t e n c o d i n gt e c h n o l o g yf o ras i n g l ex m ld o c u m e n tb a s e do n r u n t i m es t a c ku s e di nt h i ss t r a t e g y 4 ) b a s e do nt h ep r i o rw o r k s ，t h eo p t i m i z a t i o no f t w i gp a t t e r n su n d e rd t db y u s i n gs t r u c t u r a la n dc o n s t r a i n ti n f o r m a t i o no fd t di sa l s oa d d r e s s e d ，w h i c hi s s t a t i c ，n a m e l y , i ti sp r o c e s s e db e f o r et h er u n t i m eo f s t r e a mp r o c e s s i n g k e y w o r d s ：x m ls t r e a m ，c o m p l e xq u e r y , t w i gp a t t e m ，d t d ，b u f f e r 2 x m l 流的复杂查询处理及其优化技术 1 1 研究背景 1 1 1x m l 流处理概述 第一章引言 随着近年来互联网领域的高速发展，x m l b p s + 9 8 】已经成为w 曲上数据交 换的标准格式。同时，x m l 的使用方式也在不断的演化与扩展。在很多领域， x m l 数据不仅作为一个完整的文件进行传输，而且还能够以持续的串行数据流 的方式进行传输。因此，处理x m l 流数据的理论与技术已经成为流数据研究领 域的一个研究热点。 应该讲，促使x m l 流处理领域迅速发展的根本因素来自于应用领域的迫切 需求。这些领域包括：新闻订阅、传感器网络、位置搜寻、网络监控、金融分析 以及在线拍卖等，其主要特征是需要及时地对大量用户进行选择性的信息分发。 举例来说，在典型的新闻订阅应用中，用户向服务供应商注册自己感兴趣的新闻 类型，然后供应商能够及时准确地将这样的新闻信息分发给订阅用户。 x m l 流处理系统的核心功能是使用x m l 查询语言对x m l 流数据进行查洵。 x m l 查询语言主要包括x p a t h c d 9 9 与x q u e r y b c f + 0 2 】。典型地，x m l 流数 据沿着某个网络端口按顺序在线到达。用户通过使用某种概要语言( p r o f i l e l a n g u a g e ) 向系统表达自己的兴趣，系统将这种概要语言转换成能接受的查询形 式( 如x p m h ) 并永久存储。系统实时侦听网络上的x m l 流数据，并将用户感 兴趣的数据部分及时分发到相应的用户那里。 x m l 流数据处理系统通常部署在i n t e r n e t 上，用户会迅速增加到十万、百万 级的数量。由于一个用户可以提交若干查询，查询的数量更是十分巨大。x m l 流数据处理研究的一个关键挑战是如何同时有效处理大量来自用户的查询并及 时将结果返回给用户。 1 1 2 研究现状与研究动机 针对x m l 流处理系统，目前所采用的主要方法是基于自动机的方法 【a f o o d a f + 0 3 g s 0 3 g m o + 0 3 o k b + l m p + 0 2 ，其它的有基于索引的方法 【b g k + 0 3 、基于b l o o m f i l t e r 的方法 g q y + 0 5 】、f i s t 方法 k r m + 0 5 。 x m l 流的复杂查询处理及其优化技术 y f i l t e r d a f + 0 3 是基于自动机方法的典型代表，具有较强的查询处理能力，浚 方法目前只支持具有a n d 谓词的分支查询。但它采用的是后置处理的方法，会 产生大量中间结果，不能单遍处理所有查询，处理大文档时性能明显下降。 i n d e x f i l t e r b g k + 0 3 采用基于索引的技术处理x m l 流数据。i n d e x - f i l t e r 利用 x m l 文档流的文档标记动态地建立x m l 文档的索引，从而避免处理一部分 x m l 文档。跟y f i l t e r 相比，i n d e x f i l t e r 更适合处理查询数量较小x m l 文档相 对较大的情况。在i n d e x f i l t e r 的方法中，建立索引要花费一定的时间代价。此 外，它不能单遍处理x m l 文档，缓存文档要花费的一定空间代价。i n d e x f i l t e r 没有考虑对a n d 或o r 谓词的处理问题。f i s t k r m + 0 5 是将一组t w i gp a t t e r n 转换为p r u f e r 序列，并对一组t w i gp a t t e r n 与x m l 流数据进行整体性( h o l i s t i c ) 匹配。f i s t 避免了将t w i gp a a e m 转换为自动机，同时避免了嵌套谓词的后置处 理。但f i s t 没有考虑如何处理o r 谓词。基于b l o o mf i l t e r 的x m l 包过滤器利 用b l o o mf i l t e r ，将x p a t h 表达式看作字符串，将x p a t h 与x m l 文档之间的匹 配转换为字符串之间的匹配，从而提高查询性能。它只可用来处理不含谓词的简 单查询，并且有。一定失误率。 对x m l 流处理缓存方面的研究显得比较欠缺。文献 p c 0 5 忡提出的x s q 是一种针对x m l 流的x p a t h 处理引擎。x s q 使用了缓存区暂存可能结果，其缓 存操作是由有限状态机驱动的。x s q 为每个匹配建立一个缓存项，不管其内容 是否是某元素的同一份拷贝。因此，缓存的利用率比较低。另外，x s q 只处理 单个查询。文献 b f j 0 5 文章给出了一个针对任何前向( f o r w a r d ) x p a t h 查询的 流处理算法，声称其缓存空间几乎能够达到理论上的最小边界。不过，这个算法 只能处理非递归嵌套文档。文献 k s s + 0 9 提出了一个x q u e r y 的扩展语言f l u x ， 能够支持事件驱动查询处理与对缓存空间有意识的处理。它的主要思想是利用 d t d 中的顺序约束指导事件处理器以达到缓存需求的最小化。 在部分应用中，x m l 文档具有d t d 。对于这类文档，可以有效利用d t d 的 信息来优化x p a t h 表达式，从而优化x m l 数据流的处理。参考文献 c o o l n 用树 自动机( 表示d t d ) 和一般的自动机( 表示路径) 的乘积去除x p a t h 表达式中 的+ ，参考文献 c o o 】利用d t d 的语义信息给出相关优化规则，并利用这些优化 规则简化x p a t h 表达式。这些研究成果同样可以应用在流处理的研究领域中：参 考文献 c o o q 用树自动机的乘积去除* a n 部分( 在d t d 包含环的部分，不能 去除) ，参考文献 s r m 0 5 在利用x m ls c h e m a 的语义信息定义相关优化规则用 于x m l 流处理。我们结合参考文献 g y t + 0 5 c 0 0 1 的基础上，实现了基于d t d x m l 流的复杂查询处理及其优化技术 优化x p a t h 的组件。 1 2 本文工作 我们使用j a v a l 5 开发了一个称为l e o x s q 的x m l 流处理系统，其核心是一 个强调对复杂查询处理的流过滤引擎。在此基础上，为了返回给用户更好的结果， 我们为引擎开发了缓存管理组件，并使用了提出的缓存管理算法。为了进一步挖 掘系统对具有d t d 的x m l 文档流的处理性能，我们还开发了基于d t d 的查询 优化组件作为l e o x s q 的预处理器。 本文的工作是围绕l e o x s q 完成的，主要内容如下： 对于含嵌套a n d o r 谓词的复杂t w i gp a t t e r n ，我们抽出其中的逻辑表达式 并将其表示成一棵单独的抽象语法树。这样，利用基于运行时栈的算法，结 合白顶向下与自底向上的过程，很容易对其进行真值演算以达到查询匹配的 目的。不难看出，这样的抽象语法树容易处理含任意嵌套的a n d o r 谓词的 t w i gp a t t e r n 。 将所有t w i g p a t t e m 组合成单个可共享前缀的查询树，从而可以节省查询处理 的空间与时间。通过运行时栈驱动，可以单遍地处理所有的t w i g p a t t e r n 。在 共享前缀的查询树中，我们对具有公共子表达式的逻辑表达式进行进一步共 享。这不仅能减少逻辑表达式的空间复杂度，还可以加速对它们的计算。 提出了一种基于语义链的缓存管理算法处理单个查询匹配，并将其扩展并应 用到前缀共享的多查询环境下。该方法能够以尽可能低的缓存需求处理递归 嵌套文档与一对多关系文档。我们开发了一种基于运行时栈的x m l 部分编 码技术，用于缓存节点间语义关系的判断。这种方法只对进入运行时栈的节 点编码，缩小了编码的范围。 分析了影响x m l 流数据处理性能的关键因素，并利用正则树文法和树自动 机作为理论指导，阐述了使用d t d 进行查询优化的方法。基于该方法，实 现了查询优化组件。该组件在系统运行前进行预处理，不影响系统运行时的 性能。 x m l 流的复杂查嘲处理及其优化技术 1 3 本文结构 本文分为六章。第一章引言，介绍x m l 流处理的研究现状、研究动机和本 文的研究工作与组织结构。第二章介绍x m l 基础知识。第三章提出一种处理具 有a n d o r 谓词的复杂t w i gp a t t e m 查询的新方法。这种方法可以处理带任意嵌 套的a n d o r 分支的复杂查询，而无需后置处理。第四章提出了一种针对单个 查询的基于语义链的缓存管理算法，并将其扩展并应用到前缀共享的多查询环境 下。该算法使用了我们开发的一种基于运行时栈的x m l 部分编码技术。第五章 首先分析了影响x m l 流处理性能的关键因素，然后阐述了利用d t d 进行查询 优化的方法，最后给出了d t d 优化组件的实现方法。第六章总结了全文工作， 并展望了进一步的工作。 x m l 流的复杂查询处理及其优化技术 2 1x m l 简介 第二章x m l 基础知识 x m l b p s + 9 8 是可扩展标记语言( 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 的源头可以追溯到2 0 世纪6 0 年代由i b m 研究人员开发的一种自参考语言g m l ( g e n e r a l i z e dm a r k u pl a n g u a g e ) ，其目的 是为了解决文档在操作系统之间的互换性问题。经过不断努力，g m l 发展成了 s g m l ( s t a n d a r df o rg e n e r a l i z e dm a r k u pl a n g u a g e l 即通用标记语言标准，并在 1 9 8 6 年被国际标准化组织( i s o ) 采纳，收录在i s 0 8 8 9 7 中。 s g m l 不仅是一种标记语言，同时也是一种元语言。利用它可以定义各种各 样的标记语言。s g m l 定义了一种语法，允许开发者根据需要制定自己的元素。 要使用它描述一个特定的文档，需要利用d t d ( d o c u m e n tt y p ed e f i n i t i o n ，文档 类型定义) 定义一个合适的文档结构，并依据d t d 在处理文档之前进行合法性的 检查。 x m l 可以看作是s g m l 的一个子集，在x m l 中保留了s g m l 的强大功能， 降低了s g m l 的复杂程度，使x m l 具有强大伸缩性与灵活性。x m l 是一种元 标记语言，允许用户在x m l 文档中根据需要定义特定的标记与属性，使信息内 容有结构地进行描述，从而使x m l 文件的结构可以复杂到任意程度。x m l 文 档本身是纯文本格式的，良好的数据存储格式使得x m l 文档更加便于网络中传 输。在各种应用中，x m l 都具有特定的优势。 一个x m l 文档主要是由很多元素组成的。一个元素可以看作是一个类型， 这种类型通常是由d t d 定义的。元素可能具有一组属性。每个属性都有一个属 性名和属性值。在文档中，每个x m l 元素是由一个开始标记 和一个对 应的结束标记叫元素名 界定的。一个元素通常并不是独立存在的，而是会与其 它的元素构成嵌套关系。事实上，一个x m l 文档实际上是一棵只有一个根元素 的有序的标记树。图2 1 是一个x m l 文档实例。 x m l 流的复杂查询处理及其优化技术 b o o ky e a r = “1 9 9 8 ” x m l 技术内幕 n a t a u y a p i t t s $ 2 5 2 2d t d 简介 图2 - 1 一个x m l 文档的示例 一个d t d ( d o c u m e n tt y p ed e f i n i t i o n ) 为x m l 文档定义了一套基本规则，该 规则构筑了x m l 文档的基本结构。在一个d t d 声明中，包含了文档中使用的 所有元素、元素属性、实体以及它们之间的相互关系。下面是图2 - 1 中x m l 文 档的d t d 内容。 用于定一个元素b o o k 的 类型，它有三个子元素分别是t i t l e 、a u t h o r 和p r i c e 。元素a u t h o r 旁边的“表 示一个b o o k 元素可以有多个a u t h o r 子元素。 用于定义b o o k 元素的属性列表。在这里，b o o k 只有一个属性y e a r ， 它类型是c d a t a ，并且是必需的。元素p r i c e 定义中的# p c d a t a 表示该元素没 有子元素，只能有# p c d a t a 类型( 不包括标记的字符文本) 的内容。 图2 - 2 一个d t d 的示例 x m l 流的复杂查询处理及其优化技术 2 3x p a t h 简介 x p a t h c d 9 9 1 是一种x m l 路径语言，用于定位x m l 文档中的任何内容。一 个x p a t h 表达式是由一组通过“”分隔的定位步( l o c a t i o ns t e p ) 组成的。一个 定位步可以表示成a x i s ：n o d e t e s t p r e d i c a t e s l i 的形式。a x i s 称为轴，它指定了定 位的方向。例如，孩子轴( c h i l d ：，简写为“”) 用于定位子节点，后代轴 ( d e s c e n d a n t ：，简写为) 用于定位后代节点。n o d e t e s t 称为节点测试，用 于选择x m l 文档中满足特定模式的节点。其中最重要的是名称测试，即用于匹 配与n o d e t e s t 相同名字的节点。p r e d i c a t e s 是谓词部分，用于进一步限制节点测 试的选择范围。本文中，我们只关注一类重要的谓诃即分支路径。 2 4x q u e r y 简介 x q u e r y 【b c f + 0 2 是被w 3 c 设计用来作为x m l 的标准查询语占的。x q u e r y 是一种比x p a t h 更强大的查询语言，尽管它们在语法的描述和数据模型的表示上 是统一的。x q u e r y 除了使用与x p a t h 相同的路径表达式进行定位外，关键还是 支持f l w r ( f o r , l e t ，w h e r e ，r e t u r n ) 表达式。f o r 子句用于对表达式中要出现的 变量指定明确的范围。l e t 子句用于对f o r 语句指定的所有变量进行赋值。w h e r e 子句用于对上述变量制定限制条件。r e t u r n 子句指定要返回的结果及其形式。 r e t u r n 语句中还可以再嵌套f l w r 语句。本文中，我们将利用x q u e r y 可以指定 返回结果形式的能力，更有效地进行x m l 流的缓存管理。 x m l 流的复杂查嘲处理及儿优化技术 3 1 引言 第三章x m l 流的复杂查询 流数据处理系统与传统数据库管理系统不同。传统数据库管理系统的主要特 点是：数据持久存储，在某一时刻执行查询并通过稳定查询计划给出精确的回答； 而流数据处理系统强调：数据在线到达、查询持久存储。在流数据处理系统中， 不可能控制数据到达的顺序，将所有到达的数据存储在本地进行管理和查询也是 不现实的。流数据处理技术引起研究界广泛兴趣，具有极其广阔的应用前景，可 以应用在传感器网络，位置搜寻，网络监控，金融分析，在线拍卖等诸多领域。 由于x m l 已经成为w e b 上数据交换的标准，用于各种应用和信息源之间的数据 交换，处理x m l 流数据的理论和技术目前是流数据研究领域中的一个研究热点 a f 0 0 d a f + 0 3 g s 0 3 g m o + 0 3 b g k + 0 3 g q y + 0 5 k r m + 0 5 o k b + 0 3 l m p 0 2 g y t + 0 5 】。 x m l t w i g 查询本质上是具有针对x m l 文档结构和内容的选择谓词的查询。 将组t w i gp a t t e m 与随时到达的x m l 文档进行匹配是x m l 流数据处理的核心 操作。我们发现，对于具有嵌套a n d o r 谓词的t w i gp a t t e r n 的处理，目前还没 有有效的处理方法。然而，实际应用中的一个查询，通常同时包含逻辑o r 和逻 辑a n d 谓词。例如， q = d b l p p a p e r t i t l e ；x m ls t r e a m o r ( y e a r22 0 0 6a n de o n f = v l d b ) l a u t h o r 它要求选择p a p e r 的a u t h o r ，其发表过t i t l e 为x m ls t r e a m 的文章或者在2 0 0 6 年的v l d b 上发表过文章。这种查询称为具有a n d o r 谓词的复杂t w i gp a t t e r n 。 针对x m l 流处理系统，目前所采用的主要方法是基于自动机的方法 a f 0 0 d a f + 0 3 】 g s 0 3 g m o + 0 3 】 o k b + 0 3 l m p 0 2 g y t + 0 5 】，其它的有基丁 索引的方法 b g k + 0 3 j ，基于b l o o m f i l t e r 的方法 g q y + 0 5 ，f i s t 方法 k r m + 0 5 i 等。基于自动机方法的一个瓶颈是随着查询的复杂性和数量的增加，状态数目会 指数级增长。y f i l t e r d a f + 0 3 是基于自动机方法的典型代表，具有较强的查询 处理能力，该方法目前只实现了具有a n d 谓词的查询( 它称为嵌套的x p a m ) 。 我们认为，从理论上讲，它也能够用同样的方法处理具有o r 谓词的查询。但它 采用的是后置处理的方法，会产生大量中间结果，不能单遍处理所有查询，尤其 是a n d o r 谓词数量和嵌套层次增加时，处理性能明显下降。对此，我们提出 基于查询树的处理方法，将所有具有a n d o r 谓词的t w i gp a t t e m 合成为一颗查 x m l 流的复杂查询处理发其优化技术 询树，并将a n d o r 谓词单独表示为逻辑抽象语法树。采用自顶向下和自底向 上结合的方式，单遍同时处理所有t w i gp a t t e r n 。 在我们研究y f i l t e r d a f + 0 3 ，发现一个有趣的现象：针对其中的演示例 子所给出8 个查询( q l = a b ；q 2 = a cq 3 = a b 、c ；q 4 = a b c ；q 5 = a 4 c ：q 6 2 a c ； q 7 = a * * c ：q 8 = a b c ) ，我们假设存在已知的d t d ： 那么，根据d t d 的信息，我们可知：不会有任何符合d t d 的文档与查询 q 2 和q 7 匹配；q 4 、q 5 、q 6 和q 8 ( 根据d t d 将“ 和去除) 是与q 3 等价的查询。其结果，根据d t d ，可将这8 个查询简化为：q 1 = a b ；q 4 ，q 4 ， q 5 ，q 6 ，q 8 = a b c ；q 2 和q 7 的返回结果为空。 利用已知的d t d ，可以有效简化x p a t h ，从而改善x m l 流处理系统的处理性 能d t d 有两类信息可用于优化x p a t h 表达式：结构信息和语义信息。利用结构 信息，可以去除x p a t h 中的4 和部分 g y t + 0 5 c o o ；利用d t d 的语义信息，可 以有效简化x p a t h 表达式 s r m + 0 5 p w 0 1 1 。基于已有的研究工作，本文概要讨 论了相关优化技术，包括逻辑表达式的短路计算和公共子表达式的共享。这两种 优化只适用于我们提出的方法。 3 2 相关研究工作 由于流数据处理系统所具有的广泛应用前景，以及x m l 已经成为w e b 上数 据交换的标准，x m l 流数据处理的研究引起了广泛研究。很多研究采用基于自动 机的方法处理x m l 流数据 a f 0 0 d a f + 0 3 g s 0 3 g m o + 0 3 o k b + l m p + 0 2 。 x f i l t e r a f 0 0 1 首次利用基于有限状态自动机( f s m ) 的方法过虑x m l 文档。 x f i l t e r 对每一个路径查询使用一个单独的f s m ，并在文档处理的过程中，同时 运行所有的f s m 。y f i l t e r d a f + 0 3 在x f i l t e r 的基础上进行了改进：将所有的 x p a t h 查询合并成一个单独的非确定有限自动机( n f a ) ，并共享所有查询的公 共前缀。y f i l t e r 将t w i g p a t t e r n 视作嵌套路径表达式，并使用查询分解进行处理。 在他们的方法中，当一个查询包含嵌套路径时，就被分为主路径和一组扩展路径， 每一个扩展路径都用一个相对独立的n f a 进行处理。对它的处理分为两步：路 径匹配和路径匹配结果的后置处理( 执行连接操作) 。针对嵌套路径，y f i l t e r 主 要考虑的是具有a n d 谓词的查询，并且，这种后置处理的方式可能会产生大量 x m l 流的复杂查询处理及其优化技术 中间结果，从而影响系统性能。影响y f i l t e r 性能的另外的问题是：1 ) 随着查询 的复杂性增加以及查询数目的增多，状态数会指数级增长：2 ) 由于采用n f a ， 对一些状态需要支持多个转移。g r e e n 等人将n f a 转换为确定有限自动机 ( d f a ) ，并使用懒惰d f a 控制状态爆炸带来的运行时负载，以提高处理性能。 d a n 等 o k b + 0 3 使用状态机处理x p a t h 表达式，将一个x p a t h 表达式转换为多 个下推自动机构成的网络。这种方法难以处理大量x p a t h 查询。x p u s h g s 0 3 将 所有的x p a t h 表达式构造为单个定制的确定下推自动机( x p u s h 机) 。该方法首 先将每一个x p a t h 转换为等价的交替有限自动机( a l t e r n a t i n g f i n i t e a u t o m a t o n ， a f a ) 。a f a 是个非确定有限自动机，其中，每一个状态标记为a n d ，o r ， 或者n o t ；然后，在此基础上构造自底向上的x p u s h 机。x p u s h 主要强调原子 谓词( 基于值的谓词) ，同其它基于自动机的方法样，随着x p a t h 的增加，状态 数目会指数级增长。为此，它也采用懒惰构造的方法在运行时构造x p u s h 机。 然而，这种情况下当首次发现并计算该状态时，运行代价很高。参考文献 g y t + 0 5 1 基于树自动机，采用自项向下和自底向上的方式处理x p a t h 表达式。 其它处理x m l 流的方法主要有基于索引的方法 b g k + 0 3 1 ，基于b l o o mf i l t e r 的方法 g q y + 0 5 】以及f i s t 方法 k r m + 0 5 】。i n d e x f i l t e r b g k + 0 3 采用基于索引 的技术处理x m l 流数据。i n d e x f i l t e r 利用x m l 文档流的文档标记动态地建立 x m l 文档的索引，从而避免处理一部分x m l 文档。与y f i l t e r 的相比，他们通 过实验表明，当查询数量相对较小x m l 文档相对较大时，i n d e x f i l t e r 更有效( 在 不考虑建立索引所花费的代价的前提下) ；当查询数量相对较大x m l 文档相对 较小时，y - f i l t e r 更有效。在i n d e x f i l t e r 的方法中，建立索引要花费一定的时间 代价。另外，不能单遍处理x m l 文档，因此，缓存文档要花费的定空间代价。 i n d e x f i l t e r 没有考虑对a n d 或o r 谓词的处理问题。f i s t k 1 l m + 0 5 针对t w i g p a t t e r n 提出一种有别于y f i l t e r 的方法，将一组t w i g p a t t e m 转换为p r u f e r 序列， 并对一组t w i gp a t t e r n 与x m l 流数据进行整体性( h o l i s t i c ) 匹配。对于t w i gp a t t e r n ， f i s t 方法优于y f i l t e r ，表现在两点：1 ) 避免将t w i gp a t t e m 转换为自动机；2 ) 避免后罱处理嵌套谓词。但f i s t 处理查询的能力不足，考虑的是具有a n d 谓 词的t w i gp a t t e m ，而没有考虑如何处理o r 谓词。基于b l o o mf i l t e r 的x m l 包 过滤器 g q y + 0 5 是一种近似查询方法，利用b l o o mf i l t e r ，将x p a t h 表达式作为 字符串，将x p m h 与x m l 文档之间的匹配转换为字符串之间的匹配，从而提高 查询性能。它只是用来处理简单的x p a t h 表达式( 不包括谓词，只包括“” “，称为x p “, 叶) ，并且有定失误率。 x m l 流的复杂查嘲处理及其优化技术 上面提到的许多研究工作根据自己方法提出了一些特定优化技术，不能适用 于别的方法，在此不再赘述。我们将通用x m l 流数据处理优化技术分为两类： 基于部分文档结构的优化【g m o + 0 3 g h s 0 2 】和基于d t d 的优化 g y t + 0 5 s r m 0 5 。 参考文献 g h s 0 2 用基于预先计算的视图来加速x m l 流数据的处理。该方 法的关键之处是把对视图的回答进行编码，作为x m l 文档流的头。这样，当 x m l 文档流达到时，流处理引擎通过解读视图，就可以了解相关文档结构的信 息，从而优化文档的解析和查询匹配。参考文献 g m o + 0 3 根据同样的思想，但 使用不同的技术。他们使用轻量级的二进制数据结构预先编码x m l 文档的部分 结构信息，称为流索引( s t r e a mi n d e x ，s i x ) ，并把其加入x m l 文档流。这样， 流处理引擎就可以根据流索引提前决定略去对哪些元素的解析。这种方法的一个 缺点是：流处理引擎必须了解数据源端的流索引信息。 3 3l e o x s q 流处理系统 l e o x s q 是一个不同于传统数据库系统的流数据处理系统：持久性存储并索 引大量来自用户的查询，x m l 文档随时到达，驱动查询与文档间的匹配图3 - 1 是l e o x s q 的体系结构示意图。l e o x s q 具有同时有效处理百万级数量的x p a t h 表达式的能力，包括4 个基本组件：x p a t h 优化组件，x p a t h 解析器，s a x 解析 器和x m l 流处理引擎。l e o x s q 的输入源有三个：持续到达的x m l 文档流， 持久存储的大量x p m h 表达式，用于优化的x m l 文档的d t d ( 可选) 。 x p a l hq u e r i e s 图3 - 1 l e o x s q 的系统结构 u s e r s x p m h 解析器解析x p a t h 表达式，并将解析结果发送给流处理引擎。它接受 来自x p a t h 解析器的输入并把x p a t h 表达式转换为内部的查询树表示。s a x 解 析器解析输入的x m l 文档，输出“o p e n ”、“c l o s e ”等事件。“o p e n ，表示 x m l 流的复杂盘询处理及其优化技术 遇到一个元素的开始标记，“c l o s e ”表示遇到一个元素的结束标记。x m l 流 处理引擎是系统的核一t l , 组件，将所有的x p a t h 表达式都在内部合成一个共享前缀 的查询树。当文档流到达时，它接受并处理来自s a x 解析器的事件，根据x m l 的文档顺序，将其与x p a t h 进行匹配，并将匹配的结果分发给相应用户。l e o x s q 目前能够处理通常的x p a t h 表达式( 包括“ 、“一、“ ”) ，尤其是能够有 效处理具有嵌套a n d o r 的复杂t w i gp a t t e m 查询。 l e o x s q 的处理引擎具有节点缓存管理能力。处理过程中，它将可能作为结 果的数据缓存起来，等到这些数据构成完整的元组时，将其立即分发给用户。当 缓存内容不可能再被使用时，引擎立即清除它们以节省空阳资源。 l e o x s q 的交付平台是i n t e r n e t ，系统的用户会很快增长到百万级的数量。为 了进一步提高效率，我们实现一个基于d t d 的x p a t h 优化器，对用户查询( 表 示为x p a t h 表达式) 进行优化，以减少x m l 文档解析的代价和查询匹配的代价， 从而改善系统性能。 3 4 复杂查询的相关定义 3 4 1 基本概念 为了便于后面的叙述，我们先给出下面对于查询的定义。这里的查询均指 x p a t h 表达式。这早的谓词只考虑路径表达式，不考虑基于值的谓词。 定义3 1 简单查询：不含任何谓词的路径表达式所构成的查询。 定义3 2 分支查询：至少包含一个路径谓词的路径表达式所构成的查询。这 种查询相应的查询树中包含有分支，因此也称为t w i gp a t t e r n ( 树模式) 查询。 定义3 3 确定查询：不含任何”与“”的路径表达式所构成的查询。 定义3 4 非确定查询：至少包含一个“ 或“”的路径表达式所构成的查 询，即确定查询之外的查询。 定义3 5 复杂查询：统称分支查询或者非确定查询为复杂查询。 3 4 2 问题定义 本章主要讨论问题针对复杂t w i g p a t t e m 的x m l 流处理问题，问题定义如下 给定一个包含复杂t w i g p a t t e r n 的查询集合q ，以及一个x m l 文档d ，找出q 、q 满足对每一个q q 、，都匹配文档d 。 x m l 流的复杂查询处理及其优化技术 3 5 具有a n d o r 谓词的t w i gp a t t e r n 的表示 直观地，可将t w i gp a t t e m 表示为一颗查询树( 我们称为通常的查询树) ，在 树中插入相应的a n d 节点和o r 节点，以表示相应的谓词 s a x 。例如，对于 x p a t h 表达式q = d b l p p a p e r t i t l e = x m ls t r e a m o r ( y e a