（计算机应用技术专业论文）无线内容下载平台中事件流处理应用研究.pdf

中文摘要 随着无线内容下载技术的出现和成熟，在下载平台中逐渐出现了许多对大量 事件进行实时处理的应用需求。事件流处理需要应对庞大的数据集和高度的流动 性，由此产生了许多新的基础性研究问题。本文在对无线内容下载平台中对事件 流处理需求进行分析的基础上，提出了一种全新的事件流处理模型，并对其中的 关键算法和实现进行了研究。 本文将基于数据流的处理模型和基于时态逻辑的处理模型进行了结合，在对 事件、事件流和事件模式进行形式化定义基础上，定义了事件流处理语言，其语 义继承了持续查询语言的优点，既可以利用现有关系语言的形式化基础和实现技 术，处理语句又非常简单易用。其中两种处理模型的结合主要是针对事件流的模 型匹配需求，本文给出种正则语言来表达所要进行匹配的事件模式。并通过给 出构造与该语言等价的有穷自动机的算法，采用有穷自动机的方法对事件流处理 中的模式匹配问题进行求解。并且将目前的研究工作中只能按照给定的输入元素 进行既定的模式匹配扩展到了能够支持自定义事件模式。 本文另外一个创新点在于对使用增量数据模型进行事件流处理优化的做了 深入研究。在事件流处理中的性能优化方面，目前国内外的研究工作中还没有关 于增量数据模型的讨论，所以本文研究中没有办法进行比较和分析，主要是探索 性的研究工作。工作包括使用增量数据模型对事件流处理进行建模，利用递归划 分和求解最优评估树的方法来实现优化事件流处理、降低成本，并且对算法进行 了复杂度分析。由于在多输入事件流多处理语句的事件流处理问题的求解复杂度 是n p 难的，本文给出了在多输入事件流多处理语句的事件流处理中的贪婪算法。 在应用创新方面，本文给出了事件流处理引擎的原型实现，包括事件流处理 的整体架构、内部各组件之间的关系、事件流处理引擎的事件内部表示、处理模 型及执行计划等。并在研究已有s q l x 儿标准的基础上，将瑚l 这种半结构化的 事件表达方式扩展到事件流处理语言。在描述无线内容下载平台系统组成的基础 上，详细的阐述了平台中的事件流处理实现。实验通过对大量事件流的成功处理， 验证了第一点创新流处理模型的有效性；而实验中的平均响应时间、分位数响应 时间和吞吐量充分说明了增量数据模型这种优化算法的高效性、鲁棒性和适应 性。综述，本文的研究工作具有很好的社会推广价值。 关键词：无线内容下载、事件流处理、模式匹配、增量数据模型 a b s t r a c t w 1 mt l l em a t u m t i o no fg e n e d cw i r e l e s s c o n t e n td e l i v e r y 廿l e r ei sa nu r g e n t f e q u l r e m e n to fr e a l t i m ep r o c e s s i n go fe v e n t sg e n e r a t e di nt l l ed e i i v e 珂p l a t f o 咖 3 1 。耽e v e n ts 仃e 锄p f o c e s s i n gh a st oh a n d l eh u g eb u l k so fe v e n t s0 c c u d n g f r e q u e n t l v l nr e a lt l m ea 1 1 di ti ss of a ri m p o s s i b l et op u ta l le v e n td a t ai n t ot h el i m i 砌m e m o 以 t 【l e r et l l e na n s em 柚yf u n d a m e n t a lr e s e a r c hp r o b l e m s h lt l l i s d i s s e n a t i o n m e rt l l e r e q u l r e m e n t sa r ec a r e f u l l ya l l a l y z e d ，ab r a n d n e we v e n tp r o c e s s i n gm o d e li sp r o p o s e d ， a n dt b eo p n m l z a t j o na n d p a t t e mm a t c h i n ga l g o r i t h mi n 血i sm o d e la r em e ns t u d i e d t h et e m p o r a i l o g i cb a s e d 触m e w o r ka n dm ed a t as 廿e 锄p r o c e s s i n gm o d e la r e c o m b i n e di n t h i sd i s s e r t a t i o nf o re v e n ts 骶a mp r o c e s s i n g o nt h eb a s i so ff 0 珊a l a e f l 劬o no te v e n t ，e v e n ts 仃e 锄a 1 1 dp a t t e mm a t c h i n gf o re v e n ts 仃e 锄，t 1 1 e e v e n t s 嗽l i i lp 眦e s s l n gl a n g u a g ei sd 嘶v e df r 啪c o n t i n u o u sq u 唧p r o c e s s i n g a n d ，m e l a i l g u a g e1 sv e 叮e a s yt 0u s e ，n l ep a t t i m lm a t c h i n gi se x p 佗s s e db ya 酉v e nr e g u l a r e x p r e s s l o nl a n g u a g e s i n c er e g u l a re x p r e s s i o n sh a v et i l es 锄脸c o m p u t i n ga b i l i t ya s f l n l t e 。s t a t e 锄t o m a t o n ，t l l ep a t t e mm a t c h i n gc a i lb ed o n ew i md f a a r i dh e n c em e a u t o m a t o nc o n s t m c t i o na l g o r i t l l mi ss t u d i e d 1 0r e d u c et l l ec o s t0 fa c c e s s i n ge v e n t sa i l df i l lr e a l t i m er e q u i r e 】m e n t si ne v e n t p “) c e s s l n g ，粕l n c r e m e n t a la p p r o a c hi s a d o p t e dt 0o p t i m i z et l l ee v e n ts 仃e 锄 p r o c e s 8 l n g i h es i n g l eq u e r yp r o c e s s i n ge v a l u a t i o n a l g o r i t h mo fm u l t i p l ei n p u t s 廿e 锄si sg i v e ni nm i sd i s s e r t a t i o n ，w i mt 1 1 ec o s ta n a l y z e d s i n c et l l em u l t i p l e q u e r y o p t l 肌z a t l o np r o b l e m sa r en p - h a r d ，g r e e d ya l g o r i t h mi su s e di n 呻e s s i n gm u l t i p l e q u e r i e so v e rm u l t i p l ei n p u ts t r e a m s a p m t o t y p el s 埘p l e m e n t e dt op r o v e 吐l ea b o v em o d e l sa n da l g o r i t l l m si n l er e a l w o d d ，a j l dax m ls u p p o r te x t e n s i o ni s d e v e l o p e dt op r o c e s sx m le v e ms 仃e a m s b o t ho fw h i c ha r e e f f e c t i v e l ya p p i i e di nt l l ew i r e l e s sc o n t e n td e l i v e r ) rp l a t f o m f m a l l y ，as u r m n a 巧i sm a d eo nt l l ee v e n ts 仃e a mp r o c e s s i n g n l ed i s s e n a t i o n p o i n t so u tm a tm ee v e n ts t r e a mp r o c e s s i n gw i l lh a v eaw i d ea p p l i c a t i o np e r s p e c t i v e ， w l t bt | l ea p p l l c a t i o ns c e n a r i oc l a s s 蛹e d f u n h e rr e s e a r c hp r o b l e m s a r ea l s os t u d i e d k e yw o i m s ： w i r e l e s sc o n t e n t m a t c l l i n g ，h l c r e m e n t a ld a t am o d e l d e l i v e e v e n ts 吮锄p r o c e s s i n g ，p a t t e m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤室蠢堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：逐庐 签字隰 工呷年3 月3 日 学位论文版权使用授权书 本学位论文作者完全了解墨壅盘堂有关保留、使用学位论文的规定。 特授权苤鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：盏毋 签字日期：上叼年3 月j 日 导师签名： 签字日期： 一 咫饮 q 辱弓其) 日 天津大学博士学位论文第一章绪论 第一章绪论 本章描述了无线内容下载平台的概况以及其对事件流处理的迫切需求，并且 指出事件流处理的特点与挑战。在对国内外研究学者对事件的定义、表示模型、 事件流处理模型、模式匹配和优化算法的相关研究工作进行回顾和总结的基础 上，阐述了本论文的主要研究方向和贡献，给出了文章组织结构。 1 1 研究背景与挑战 1 1 1 无线内容下载平台 随着底层通信技术的进步和网络架构的成熟，基本电信业务的各种需求已经 得到满足，各种增值业务在产业结构中所占据的比重越来越大。在第三代及其之 后的移动通信系统的发展中，业务已经占据了越来越重要的位置，如在第三代合 作伙伴计划的规范制定中，业务的需求是被放在导向地位的，直接指导网络架构 的设计；而由无线通讯协议论坛发展而成的开放移动联盟更是一个跨底层网络的 业务标准化组织。 移动增值服务是在通信技术、计算机技术、互联网技术不断发展融合的基础 上，在人们对以信息为基础的各种应用需求快速增长的激励下，在社会信息化水 平日益提高的前提下，迅速发展的一种全新的服务方式。由于移动通信自身所具 有的可移动性、无时空限制性、专属性、安全性和时尚性的特点，再加上基于这 些特点之上的短消息、游戏、支付、定位、办公等丰富多彩的应用服务，为广大 用户带来更方便、更灵活的通信服务，为企业带来了无限商机。从协议结构上说， 作为从属于应用层业务的移动增值服务，在其所必需的数据承载能力要求被满 足的前提下，是完全可以实现基于不同无线网络。 无线内容下载平台能使无线用户在网络上找到其感兴趣的内容并且发起下 载请求，并且实现为完成该下载过程所需要的基础功能，如内容管理、用户管理 和计费等功能。内容下载服务在移动世界并不陌生，它始于短信方式的铃声和运 营商图标下载，从而使得用户的手机个性化。作为一种非常流行的服务，被广泛 地应用于世界各地。早期的许多内容提供商仅仅提供铃声、图标、提示和贺卡等 天津大学博十学位论文第一章绪论 无线内容服务。随着j a v a 应用技术在手机平台广泛应用，出现了一种新的基于 用户订制或交易模式的收费模式。用户能够下载互动和动态应用软件到手机上来 增强自己手机的功能 1 。通用无线内容下载技术是一种可以用于下载普通内容 的方法，这些普通内容可以是无法容纳在单条短消息的非j a v a 的媒体对象，其 可支持下载的应用和媒体对象包括互动游戏、新闻提示、多媒体视频、管理工具、 虚拟宠物以及和弦铃声等 2 。 随着通用无线内容下载技术的出现和成熟，它也适用于把下载功能与浏览结 合起来，所以在在下载平台中逐渐出现了许多需要对大量事件做出实时处理的应 用需求，例如设备管理事件、用户管理事件、访问控制事件、计费事件、内容提 交事件、内容发现事件、目录浏览事件等【3 】。 1 1 2 事件流处理的挑战 1 事件处理的挑战 传统的无线内容下载平台采用基于远程过程调用方式的请求、响应处理模 型。在此处理模型中，服务请求者指明要调用的服务，并发送请求；服务提供者 接收请求并进行处理，随后返回响应信息。这种请求、响应的处理模型不能提供 主动的事件通告功能，也不是能实现松耦合的通信，在处理例如下面这几类问题 时会存在困难。 1 ) 当下载平台需要获取某无线终端未来的位置以开展某项收费业务时，下 载平台就必须具有对实时事件流进行处理的能力，并能根据无线终端位置和速度 事件流计算出相应的位置值。 2 ) 为保持无线内容下载业务的传染性，要求下载平台根据无线终端用户最 新的内容下载事件或内容传播事件，判断该终端用户是否喜欢下载平台推广的内 容。 3 ) 为了确保终端用户能够使用下载到的无线内容，下载平台需要对含有该 用户最近下载的媒体类型、大小，以及名称、厂商等信息的事件流进行处理，来 智能分析判断终端是否支持指定媒体类型的内容，以及内存容量是否足够等。 在分析这个需求的时候，数据仓库也是一种可能的解决方案。但数据仓库通 常会沿着某些变量轴聚合信息并转化数据间的关系，有时候必须先聚合数据才能 作分析。数据仓库应用在使用中有许多缺点，它不仅非常昂贵，而且e t l ( e x t r a c t ， t r a i l s f o 衄a l l dl o a d ，提取、转换、装载) 软件的工作方式意味着要付出可伸缩 性和反应能力的代价。首先，e l 给生产数据库增加了明显的负担。如果业务有 空窗期可以做e t l ，那是最好的；如果没有，管理可伸缩性就是很大的挑战。第 二，数据仓库里的数据新鲜度一般滞后二十四小时或更长，随着业务增长，滞后 天津大学博士学位论文第一章绪论 时间会越来越长，这样就无法满足实时性的要求了。 这些对事件流的实时查询处理是用户请求事件流处理系统对事件流进行一 些操作，然后返回用户需要得到的结果或者触发相应行为。按照查询处理的运行 方式，事件流中的查询处理通常是持续查询，就是只需发送一次查询请求，但一 直不断运行的查询，它是对事件流的持续计算。持续查询的查询结果是基于时间 的，它反映了到目前为止已到达的事件流的情况，查询结果本身以事件流的形式 输出。例如，在无线内容下载平台中，用户可能要求“所有在下载甲内容后五分 钟内又下载了乙内容的下载记录这样的查询处理。 2 模式匹配的挑战 许多早期的事件系统只提供原子事件的检测机制，没有提供检测事件模式的 功能，因而不能表示由原子事件复合而成的事件模式。这给系统带来很多不足， 特别是在大型应用中，事件接收方会被大量的原子事件淹没。 例如在无线内容下载平台中存在这样的场景需求，用户甲希望在他的订购的 内容费用上涨而订购用户数下降时得到通知，这样他只能分别订阅内容费用上涨 和该内容订购用户数下跌这两个事件，并自行编程实现对这种时序事件模式的检 测；另外，若另一个用户乙有跟用户甲一样的需求，则他只能跟用户甲一样分别 订阅。这样有如下的几种缺点： 1 ) 对原子事件的分别订阅并不直接对应到事件的逻辑关系，如上例中，用 户甲实际上并不对市场指数下跌这单个原子事件感兴趣，但为检测整个事件模 式，他不得不订阅它，这无疑浪费了用户的带宽，并造成事件的订阅数过多给平 台带来很大的负担，使平台的性能下降； 2 ) 在平台中实现的事件模式匹配方法不支持软件复用，但现实情况下，事件 的复合模式又经常会被用到，例如与、或、时序等。 因此在无线内容处理平台的事件流处理中需要引入事件模式概念，这样既符 合直观思维逻辑的需要又可以减轻事件流处理负担，实现这些可复用模式会极大 地减低应用程序的开发难度，极大地扩展平台的事件流处理能力和灵活性。 3 处理优化的挑战 事件流处理可以监测事件流并当特定事件发生时触发某些行动可看作 是把数据库反过来，语句是固定的，而事件流进进出出。相对于已经得到广泛深 入研究的静态数据处理，事件流处理往往需要应对数据集庞大，具有高度的流动 性的问题，由此产生了许多新的基础性研究课题。 1 ) 相对传统数据库的查询处理方式，事件流处理往往需要大量预先定义的 处理语句被注册到平台中，等待事件的到来。一旦事件到来，将触发处理语句的 执行。 天津大学博士学位论文第一章绪论 2 ) 该领域的应用面对的都是在线的、持续的高速事件流，系统处理的对象 形态完全不同于传统的静态数据处理，由于受到存储空间的限制，这些事件数据 往往不可能完全保存到存储器中，但又需要不问断无延迟地处理这些事件流，以 获得实时处理结果。 3 ) 传统数据处理中操作算子仅在需要时从它的查询计划树中的子操作算子 中请求数据，所以许多关系操作算子都是阻塞方式的，即在所有的输入被处理完 之前不能输出结果。例如在返回下一个元组之前，嵌套的循环连接会扫描内关系 的全部元组，使当前外元组能够和每一个元组比较。事件流处理由输入流推入事 件数据，且事件源中的事件元素可以且仅可以被读取一次，而绝大部分的持续查 询是有状态的，需要一定的存储空间来确保执行的准确性，所以存储非常容易耗 尽或者说处理成本非常高。 1 2 国内外相关研究工作 本节先回顾一下国内外学者在事件的定义、表示模型及事件流处理方面所做 的研究工作。 1 2 1 事件的定义及表示模型 事件源自认知学科，虽然很多学者都给出过事件的定义，但到目前为止暂时 还没有统一的定义。语言学家给出的事件及其语义结构定义通常包括目的、时间 和外在条件。c h u n g 将事件定义为是由谓词、事件框架和事件界三个部分组成的 术语 4 ，其中事件框架指谓词发生的时间段，事件界指谓词发生的情况或者条 件。p u s t e j o v s k y 从语义理解的角度围绕动词及其属性给出了事件的定义 5 。在 信息检索和信息提取领域，a 1 l a n 和y a n g 等认为事件是细化了的用于检索的主题 6 7 ，m a r s h 和g r i s h i n a n 等人分别将事件信息与事件相关的特定组织、人或实 体关联起来，采用事件以提取预先指定的事件信息 8 9 。 事件的表示也有很多的不同的研究模型。从认知科学的角度，可以把事件表 示作为分类知识的基础。结合基于脚本的知识表示方法，提出了一种基于脚本的 通用事件表示方法。事件以面构成，包括行为人、行动和其他道具构成。根据事 件的不同，这些面可以有相应的值。同时，认为事件是具有结构的，也是有时间 因果顺序的，所以事件可以有层次关系和因果关系两种组织方式，整体事件可以 由若干个行为片段组成。事件知识表达了事件及其关系的信息。n e l s o n 在1 9 8 6 年研究认知发展时，提出的事件表示模型认为事件是包含了对象和关系的整体， 包括为取得某些结果，而有目的行动的人与物体相互之间的作用 1 0 。他认为事 天津大学博士学位论文第章绪论 件是动态的、复杂的、随着时间发生的。 f i l a t o v a 等提出的元事件是由动词和动词连接的行为的主要组成部分构成， 这些行为的主要连接成分是指参与者、地点和时间三类命名实体，可以表示成三 元组 命名实体，动词，命名实体) 。事件多元组模型提出，事件包括动词v 和动 词连接的高频名词或者命名实体，n 表示高频名词和命名实体，则事件可以表示 为多元组 ， ，咒，z 。l 。相对于三元组，多元组更能体现事件的整体 情况，避免丢失事件中的重要信息 1 1 。 国内的一些语言研究者也从语言学的角度，提出了事件域认知模型并探讨了 该模型的解释能力，指出事件主要包括行为和事体两大核心要素。事件以动词为 核心，只要有动作就要涉及到动作的发出者或接受者，事件域中的动作和个体之 间就建立起了一定规律的匹配关系。因此语言就可形成各种基本句法构造，进而 可以解释语句的构成、语汇的关系等 1 2 。 1 2 2 事件流处理模型 在事件流处理方面的研究工作主要有两种思路，一种是基于时态逻辑的处理 方案，使用算法来检测事件；另一种是通过扩展数据流模型，即通过扩展原有的 流查询语言，增加流上的事件操作算子以支持事件流处理。 1 基于时态逻辑的处理模型 在事件流处理方面，语言学学者在考虑动词的同时考虑动词的结构信息，在 此基础上发展了语言学上的事件理论。p u s t e j o v s k y 通过谓词分解和动词具体化的 方式理解语句提取事件【5 】。 f i l a t o v a 等将文本看作事件的集合，打破传统意义上将文本看作概念的集合 的常规。通过自然语言处理和统计学的方法，从文本中提取元事件。但该方法在 两个方面有待进一步完善：一方面，将事件固定地定义为三元组，在事件提取过 程中，特别是对复杂的语句处理后，将丢失掉语句中大量的信息；另一方面，完 全根据统计数据来确定事件，处理过程中没有考虑将语义的信息包含进去，事件 提取的准确性和有效性都不高 1 l 】。 事件多元组提取方法也是将文本看作事件的集合，通过自然语言处理技术， 将文本断句分词标注后，提取出命名实体和高频名词，再采用句法分析的方法， 找出核心动词作为该事件多元组的核心行为词，构成一个事件多元组，相对于三 元组而言，它更为灵活，同时也保留了更多的信息，但显然在处理过程中，需要 多进行一道句法分析的工序。 此外，h u n t e r 给出了从结构数据中提取事件，他还给出了一种从时序数据中 提取事件的技术 1 3 】。y a n g 在寻找一种新的问题回答技术时，提出了将信息检索 天津大学| 孛士学位论文第一章绪论 和机器学习技术应用于事件探测和追溯中，该技术可以从按年代顺序组织的新闻 报道文件流中自动探测出新的事件，也可追溯用户感兴趣的发生在特定时期的事 件【7 】。 国内的研究人员，如清华大学的吴平博、陈群秀等，湖南大学的梁晗等采用 基于框架法的事件信息提取技术，从事件语料中提炼出事件的框架知识，用该预 先定义的框架对灾难性事件的不同侧面进行表示，定义侧面词，形成事件框架， 利用该框架抽取规则及侧面词的匹配方法，抽取文本的事件信息，在事件抽取时， 绕过了深层句法分析的难题，降低了系统的实现难度 1 4 】 1 5 】。 中国科学院计算技术研究所的姜吉发等也给出的一种事件信息抽取模式的 获取方法，该方法主要通过定义事件模式、事件触发模式和事件抽取模式三种模 式来实现。事件模式描述待抽取事件类型的各个角色及其相应语义约束；事件触 发模式描述了某个待抽取事件类型的各个角色及其相应的可能的触发词，通过某 个角色的触发词，找出该角色的候选描述语句；事件抽取模式用来指导从自由文 本中进行实际的事件抽取。由这三个模式定义的事件框架，用来通过关键词定位 事件的候选描述语句。 2 基于数据流的处理模型 本节中，首先对过去几年中和当前正在进行的数据流管理相关的项目作一个 概述，然后对其中的数据流模型的查询语言建议方案做一下小结。 数据流技术是当前国际数据库领域的一个研究热点，【1 6 】 1 7 】 1 8 】着重介绍了 如何构建数据流管理系统d s m s 。 1 9 】【2 0 】介绍了流数据模型下查询和挖掘的一 些算法。而目前已存在的流数据分析和管理的项目以及相关研究有： 斯坦福大学的s l r i 砸a m 项目拓展了s q l 语言在数据流上的处理功能， 开发连续查询和关系的查询语言。通过特殊的窗口操作项将流数据转换 为关系处理，并将结果转为数据流 2 l 】 2 2 】 2 3 】【2 4 】 2 5 】。 伯克利大学的t e l e g r a p h c q 是一个连续查询处理系统，其重点在于共享 查询估算和自适应查询处理 2 6 】【2 7 】【2 8 】。 布朗大学的a u r o r a 是一个应用于监控的面向工作流的系统。它允许用户 通过安排操作项和操作项间的工作流) 来创建查询计划。a u r o m 和 m e d u s a 介绍了两种大规模分布式的流处理系统 2 9 】【3 0 】 3 l 】。 威斯康星州立大学的n i a g a r a c q 是一个为监控动态w 曲目录而设计的 执行多个连续查询系统。它将流数据划分为组，相似查询的组数据共享 一个执行计划【3 2 】。 在上文提到的这些数据流管理项目中，已经有很多数据流模型的查询语言建 议方案【2 5 】【2 8 】 3 3 】【3 4 】【3 5 】 3 6 】【3 7 】【3 8 】。由于篇幅和研究关注点限制，本节只对 天津大学博士学位论文第一章绪论 这些流查询方案进行简单回顾，不进行非常精确和量化的评估和比较。 其中的很多文章都提到调度策略 3 9 】，但是很重要的一点是调度策略是与评 估模型垂直的。例如，【3 9 】讨论的一个批处理调度方式，即当一批输入元组到达 后进行查询调度，但这只是一种不影响元组驱动模型的优化策略。类似的，时间 驱动模型的调度器可以在每个元组到达时调度计算，利用元组到达之间的空隙分 步地生成结果，然后在下一个时钟滴答发出。 元组驱动模型和时间驱动模型在流处理系统出现之前都有其历史先驱模型。 元组驱动模型基于视图维护【4 0 】，输入事件流的任何更改都必须反映在一个依赖 视图来确保视图的准确性。这样，视图维护是相应于从输入事件流插入、删除或 者变更元组的事件而发生的。视图维护的实现可以是迟缓方式的，但这是一种优 化，并不会改变被认为是正确视图的语义。类似的，数据库集成约束和触发器也 是基于元组的执行模式。另一方面，时间驱动模型是从早期的持续查询处理而来 【3 3 】，这些系统的参数之一是决定生成增量查询结果频率的时间间隔。 1 2 3 事件流的模式匹配 许多早期的事件系统只提供原子事件的检测机制，没有提供事件模式匹配的 功能，因而不能表示由原子事件复合而成的事件模式。这给系统带来很多不足， 特别是在大型应用中，事件接收方会被大量的原子事件淹没。引入事件模式概念 既符合直观思维逻辑又可以减轻事件系统的事件流处理负载，可以极大地扩展系 统的事件流处理能力和灵活性【4 l 】。 本节从事件模式匹配中对事件模式的定义和匹配机制入手，分别剖析四种经 典的事件模式匹配方法，即基于树、基于图、基于p e t r i 网和基于自动机的匹配 方法。 1 基于树的事件模式匹配 基于树的匹配方式的基本思想是由事件模式构造出相应的匹配树。在匹配树 中，叶节点表示原子事件，其他节点表示事件的复合。下面以g e m 4 2 】为例介 绍基于树的匹配方法。 1 ) 事件模式定义 事件模式表达式是对原子事件或其他事件模式表达式应用事件操作复合而 成。基本操作及语义如下，其中e ，e 2 ，e 3 ，e 表示原子事件或子事件模式。 e l & e 2 表示e l 和e 2 都发生且与它们发生的顺序无关。 e + t i m e - p e r i o d 表示e 在t i m e p e r i o d 后发生。 e l ；e 2 ! e 3 表示e 2 在e l 后发生，且中间没有发生e 3 。 ( e lie 2 ) 表示e l 发生或e 2 发生。 天津大学博士学位论文 第一章绪论 ( e l ；e 2 ) 表示e l 发生在e 2 前。 基于树的匹配方式中假定存在一个良好同步的全局时钟。原子事件是在一个 确定的时间点瞬时发生的；事件模式则有一个发生间隔，第一个使得事件模式开 始发生的原子事件的时间是间隔始端，最后使得事件模式完全发生的原子事件发 生的时间是间隔终端。而事件的发生和匹配之间存在一定的延迟，这样可能导致 匹配到的事件失序。为避免发生错误的匹配，采取在匹配阶段来处理这种延迟， 下面简单介绍这种处理延迟的方法。 这里引入匹配窗口和计划时间事件的概念。匹配窗口表示事件存储在事件历 史中的时间。超过这个时间，此事件的记录则会被抛弃，匹配窗口的大小可由系 统默认或程序员来指定。计划时间事件表示对于每个特定的事件最大能容忍的延 迟，即在这个事件的匹配时间加上匹配窗口的时候发生。每个新到的事件都会根 据它们的时间戳被放在事件历史的正确位置，在计划时间事件发生的时间前，若 没有使得事件不符合要求的事件发生就匹配到了事件发生。 2 ) 匹配机制 采用基于树的机制来匹配事件模式，关键的步骤是为事件表达式创建一棵事 件求值树，使得其结构匹配事件表达式以及处理延迟。 叶子节点表示守卫原子事件表达式，内部节点表示守卫事件模式表达式。每 个节点都有三个主要属性：类型、守卫和历史。类型定义节点的类型；守卫为布 尔表达式，指向一棵可求布尔值的表达式树，当所关联的事件被匹配到时进行计 算，只有当满足它时，此事件才会被记录在事件历史记录中；历史表示该节点所 对应的事件记录，叶子节点的事件记录为此原子事件实例序列，内部节点的事件 记录则为此事件模式实例序列。每个实例都是由其直接子节点所代表的事件复合 而成，即依赖于其直接子节点，为节省空间它只保存其直接子节点事件记录的指 针。由事件求值树中每个节点的历史形成一个分层历史，这样避免了一些不必要 的排序；另外，这个历史只维持匹配窗口内的事件记录，过旧的事件记录则会被 抛弃，这样避免事件被永久存储。 匹配是递归进行的，首先对每一个事件模式表达式创建相应的事件求值树； 然后每当事件模式中的原子事件被匹配到时，就会通知相应的叶子节点它们的发 生；接着计算其守卫表达式，如果满足则叶子节点就在它的历史中更新相应的事 件记录，并且通知它的父节点新记录的产生，父节点根据其语义使用此子节点的 新记录和其他子节点的历史记录以及它的守卫表达式去产生尽可能多的新事件 记录，接着它又通知它的父节点。这个过程一直持续到此事件模式被匹配到或者 不能产生新的记录。 天津大学博士学位论文第一章绪论 2 基于图的事件模式匹配 基于图的匹配方式类似于基于树的方式，事件发生自节点由底向上流向它们 的父节点。叶子节点则表示原子事件，非叶子节点表示事件操作。下面以s n o o p 【4 3 】 为例介绍基于图的匹配方法。 1 ) 事件模式定义 事件模式是由原子事件以及事件操作构造而成，事件操作及其语义如下，其 中e 1 ，e 2 ，e | 1 表示原子事件或子事件模式。 d 尺( v )( 巨v 如) 0 ) = 互( f ) u 最o ) a d ( ) ( 巨a 已) ( f ) = ( j ) ( ( ( 巨( f ) n 乞o ) ) u ( 易0 ) n 巨( f 2 ) ) ) n f ) 距q ( ；) ( 巨；巨) ( f ) = a ) ( 巨( ) n 易( f ) n ( f ) ) ，d 丁( 1 )1 ( 岛) 【巨；毛】( f ) = ( 巨( f 1 ) n 鸣( 乞) n 易( f ) ) 删df l 乞f 除了这四个常规操作外还有任意操作、非周期操作以及周期事件操作。 基于图的匹配方式中假定每个事件存在一个全序关系，且事件的发生和匹配 之间不存在延迟。原子事件是在一个确定的时间点瞬时发生的，事件模式发生时 间则是最后一个使得事件模式发生的原子事件的发生时间。 2 ) 匹配机制 基于图的匹配方式引入事件历史的概念。给出一个全局的事件历史，就可以 计算任意由上述事件操作构造的事件模式历史，即所有可能使得事件模式发生的 原子事件组成的集合。因为这个集合有大量的事件实例组合，而并不是所有的都 对应用程序有用，所以引入上下文参数的概念，根据上下文参数而得到相应需要 的事件实例组合。 基于图的匹配方式的匹配思想是对于每个事件模式构造相应的事件图，叶子 节点为原子事件，非叶子节点为操作节点，分别存储其每个子节点，并且同一个 事件的不同实例也被作为不同的实体存储起来。若匹配到原子事件发生就把它的 参数存储到相应的叶节点，然后标记此事件，接着把它的参数传给其父节点即操 作节点，然后操作节点根据自身操作语义以及所给出的上下文参数执行相应的算 法得到相应的事件序列，再把此事件序列传给它的父节点，依此下去直至根节点 匹配到此事件模式。当此事件模式被匹配到后，根据上面所讲的上下文参数语义 删除此匹配序列中的时间，最后从子节点的参数列表中删除已传播的实体。 3 基p e t r i 网的事件模式匹配 基于p e t r i 网的匹配方式的基本思想是由事件模式构造出相应的p e m 网，输 入位置表示原子事件，输出位置表示事件模式【4 4 】。下面以s a m o s 【4 5 】为例介 绍基于p e t r i 网的匹配方法。 天津大学博士学位论文 第一章绪论 1 ) 事件模式定义 事件模式的定义是通过以下六种事件构造操作，其中e l ，e 2 ，e 表示原子事 件或子事件模式： ( e l ，e 2 ) 表示e l 发生并且e 2 也发生。 ( e lie 2 ) 表示e l 发生或e 2 发生。 ( e l ；e 2 ) 表示e l 发生并且在e l 发生后发生e 2 。 ( 水e 烈i ) 表示在时间间隔i 中e 的第一次发生。 ( t m e s ( n ，e ) 玳d 表示在每时间间隔i 中e 的第n 次发生。 ( n o t e 玳i ) 表示在时间间隔i 中e 没有发生。 基于p e t r i 网的匹配方式中每个事件实例的先后顺序是可以唯一确定的，即 事件集是一个全序关系。把事件看作一个时间点，原子事件的时间点由其本身定 义来确定，事件模式的时间点则根据构造操作的语义来定义。 2 ) 匹配机制 基于p e t r i 网的匹配方式中，用一个元组( n ，m o ) 来表示p e t r i 网，其中n 表 示p e t r i 网的静态结构，m o 是p e t r i 网的初始标记。n 是一个五元组( p ，t ，a ， p s ，p e ) 。其中p 是库所的有穷集合，除辅助库所表示事件之间的依赖性外，其 他每个库所对应一个事件模式，当相应的事件发生时则该库所被标记。t 是迁移 的有穷集合。ac ( p tut p ) ，是弧的有穷集合，表示库所和迁移之间的联系。 对每一个迁移t 定义它的输入库所术t = pi ( p ，t ) a l ，输出库所t ：l ：= pi ( t ，p ) a ) 。p scp 是表示输入库所的有穷集合。p ecp 是表示输出库所的有穷集合。 在一个具体状态下，p e t r i 网给库所分配非负数量的记号，每一个库所的记 号数是由映射m 来定义的，m ：p _ nu 0 l 。m 0 是p e t r i 网的初始标记，定 义了辅助库所的标记数目。每当p e 砸网的一个输入库所被标记了，就要检查相 应的迁移是否能发生。一个迁移能发生当且仅当对于p 木t 有m ( p ) 1 ，即这个 迁移对应的所有输入库所都做了标记。一旦迁移发生了就转为给输出库所作标 记，输入库所的标记也要改变，相应的变化由公式( 1 1 ) 给出。 m i 尸 f 盯( p ) + 1v p ，宰 = f 盯( 夕) 一1v 夕术， 【m ( p ) 其他 其匹配思想是对每一个新的事件模型创建相应的p e t r i 网，输入库所表示原 子事件，输出库所表示事件模式。原子事件的发生就会导致相应的输入库所被标 记了，而当一个迁移对应的所有的输入库所被标记了，则此迁移对应的输出库所 天津大学博士学位论文第一章绪论 就被标记了，依此下去，直到找到一个表示此事件模型且没有向外的迁移的库所， 则匹配成功。 4 基于自动机的事件模式匹配 不带参数的事件模式表达式类似于正则表达式，这样就可以直接利用有穷自 动机来实现事件表达式。剑桥大学研究组在传统的自动机基础上加入时间模型和 参数化机制。在此介绍他们研究的框架 4 6 】中的事件模式匹配方法。 1 ) 事件模式定义 事件模式的组成元素可以是原子事件也可以是简单的事件模式。该方法使用 一个基础描述语言来描述事件模式，下面介绍该语言的一些操作以及语义。 e 或【屯垦翻，即不发生事件e 。 c 1 c 2 ，表示事件c 2 在事件c 1 之后，但只是表示事件c l 比事件c 2 先开 始，并不要求c 2 在事件c 1 结束之前发生。 c 1 ；c 2 表示事件c 2 在事件c 1 之后，且事件c 2 开始时事件c l 已结束， 也就是说它们的时间间隔不会交叠。 c l 卑表示匹配任意次数c 1 的发生。显然，若c l 匹配失败则c l 木也失败。 c 1 ic 2 是指如果c 1 或c 2 匹配则c l i c 2 匹配。 ( c 1 ，c 2 ) t 1 = 给定时间表示匹配事件联合发生在或不在给定的时间间隔 里。 c 1 l i c 2 表示匹配并发事件c 1 ，c 2 ，c 1 和c 2 都要成功匹配，并且这两个事 件的时间间隔必须严格交叠，也就是说存在一个时间点，在这个时间点 c l 和c 2 都已开始而且未结束。 在一个大规模分布式系统中，由于没有集中的管理以及存在时钟漂移等问 题，很难确定两个事件谁先发生。为了反映时间测量内在的不准确性，使用事件 时间戳模型，它基于全局时间服务和网络时间协议n t p 来确定事件的时间戳， 并提出相应的事件复合及事件消费算法。这样无论原子事件还是事件模式都会被 指派一个间隔时间戳，并用偏序关系“ o ，序列s 的第k 个频率因子f k 定义为e = 罗7 群。频率因子获取的是序列s 的值分布的统计。例如f 0 可以表 示元素序列中不同值的个数，f 1 可以表示元素序列的长度，f 2 可以表示自连接的 大小。用概要技术估算数据项不同值的数量f 0 的方法使用线性哈希函数仅需要 o ( 1 0 9 d ) 内存和o ( 1 0 9 “l o g n ) 的空间，并应用于许多数据库文献如连接大小估 算，估算变量的l 。范式和处理多个流的复杂聚合。f 2 的计算与计算关系的自连 接相似，进一步扩展估算两个不同关系连接大小的方法到估算多方向连接以应答 复杂聚合，同时还提供了优化分割数据域并对每个分割独立估算的技术以便最小 化整个内存需求。i i l d y k 提供了一个统一框架以计算l p 范式( p ( 0 ，2 ) ) ， 充分 利用了p s t a b l e 分布的特性，扩展了概要方法，可估算出数据集的p 阶矩大小， 其中o p 2 。【5 3 】【5 4 】 5 5 】 5 6 】 4 ) 直方图技术 直方图是一种常用的数据摘要结构，直方图能简洁地表示数据集上的值分布 5 7 】 5 8 】 5 9 】。在数据库技术中已经大量使用直方图技术进行查询结果集大小估 计、近似聚合查询以及其它数据挖掘任务。在很多种的直方图中最常用的直方图 v - 最优直方图、等宽直方图和偏端直方图 6 0 】【6 1 】 6 2 】。 v - 最优直方图是用一个分段常值函数近似数据集上的值分布，并使得近似的 方差最小。等宽直方图是将数据集的值域划分为等宽的间隔，然后统计数据集中 落在每个间隔的数据元素个数。等宽直方图实际上给出了数据集按照间隔划分的 分位数。一个数据集的分位数给出了数据集按值分布的全序关系，【6 3 】给出了一 种计算流分位数的近似算法。偏端直方图只保留那些出现频率超过一定阈值的元 素计数，对于其余元素用均匀分布近似。而流中的一类查询，冰山查询【6 4 】关心 的正是高频元素。 5 ) 小波技术 小波技术类似于傅里叶变换，小波变换可将输入的模拟量，变换成一系列的 小波参数，根据内存大小提取顶端的n 个高能量参数，近似还原原始信号。小波 种类很多，最常见且最简单的是h a a r 小波。【6 5 】 6 6 】提出了一种基于哈尔小波技 术，在数据流上生成直方图的算法。该算法将整个数据集转换为一系列的小波参 数，然后有选择地保留有限个高能量参数，从而近似模拟原始数据集。对于时序 数据而言，只需要保存最多l o g n 个计数器，就能够获得任一时刻的小波参数， 即如果流中元素已经排好序，则仅需o ( b + l o g n ) 的存储空间，就能够获得b 个最大的小波参数。 天津大学博士学位论文第一章绪论 2 流约束优化算法 在事件流处理中，面临的主要挑战之一是需要大量存储必要的运行时状态。 所以需要采用非阻塞的操作方式来对事件流处理进行优化。目前的研究工作关注 比较多的非阻塞的优化方式是使用流约束，模式级约束包括在多条流之间的同 步、聚类和排序；数据级上的约束可以以控制包的形式插入到流中，控制包指定 的全部条件是对未来流内容的断言。【6 7 】提出一种处理结构，它在数据流