（计算机应用技术专业论文）面向发布订阅的自动化订阅分解模型与匹配算法研究.pdf

浙江大学硕士学位论义摘要 摘要 移动计算、网格计算、云计算、普适计算等新型嘲络计算模式的兴起，带来 了分布式应用系统应用场景的巨大变革。传统的分布式系统中各个节点以请求 应答的方式进行信息交换及通信的同步通信模型，很难适应新一代分布式计算环 境大规模、松耦合、可扩展的需求。发布订阅系统由于能够将信息生产者和信息 消费者在时间、空间上完全解耦，很好地满足大规模信息发布系统松散通信的需 要，逐渐成为了构建大规模分布式系统的基础平台。 现有发布订阅系统不能很好地处理订阅的语义异构，原子订阅也不能得到最 符合订阅者需求的匹配事件甚至不能进行相应的匹配。论文针对上述问题，结合 国家8 6 3 计划与国家自然科学基金课题，研究支持语义等价自动化订阅分解的发 布订阅系统的数据模型与匹配算法，并实现了验证所提模型的原型系统 j t a n g p s d 。 论文首先提出了一种支持语义等价自动化订阅分解的数据模型。利用本体建 立概念模型，表达系统中涉及的所有概念和概念之间的关系，分别支持类、属性 的等价、继承关系。用r d f 事件图表示事件，用r d f 订阅图模式表示订阅，利 用r d f 能够在应用程序间交换信息并月保证4 i 丢失原有语义的特点，解决语义异 构的问题；并设计了一种订阅语言p s s l 。然后，定义组件语义，利用本体库中 定义的分解模型信息，给出了支持语义等价的自动化订阅分解算法，将可分解原 子订阅分解为语义等价的复合订阅，进一步提高了系统的订阅表达能力和可用 性。 在此基础上，论文提出了一种基于语义的高效的匹配算法。以订阅条件三元 组的主体为核心，将系统中所有订阅涉及到的语义信息存储在r d f 节点索引结构 中，并将不同订阅的相同订阅条件组织在一起；在匹配过程中，遍历事件图的节 点，通过r d f 节点索引结构，找到和其在语义上、语法上和图结构上均匹配的各 个订阅节点，更新各个订阅的匹配状态，然后进行该事件图节点所在弧的终止节 浙江大学硕i 学位论文摘要 点的下一轮匹配，最终获得和事件匹配的一组订阅。 最后，论文给出了原型系统j t a n g p s d 的设计和实现方案。 关键词：发布订阅，复合订阅，订阅语言，匹配算法，分布式计算，语义w e b a b s t r a c t t h ee m e r g e n c eo fn e wn e t w o r kc o m p u t i n gm o d e l ，s u c ha sm o b i l ec o m p u t i n g ，g r i d c o m p u t i n g ，c l o u dc o m p u t i n ga n dp e r v a s i v ec o m p u t i n g ，h a sl e dt og r e a tc h a n g e si nt h e s c e n a r i o so fd i s t r i b u t e da p p l i c a t i o ns y s t e m s i nt h et r a d i t i o n a ld i s t r i b u t e d s y s t e m s ， e a c hn o d e e x c h a n g e s i n f o r m a t i o na n dc o m m u n i c a t e sw i t ho t h e rn o d e s u s i n g r e q u e s t r e s p o n s em e t h o d t h i ss y n c h r o n o u sc o m m u n i c a t i o nm o d e li sd i f f i c u l tt oa d a p t t oan e wg e n e r a t i o no fd i s t r i b u t e dc o m p u t i n ge n v i r o n m e n tt h a ti sc h a r a c t e r i z e db yt h e l a r g es c a l e ，l o o s e l yd e c o u p l e da n ds c a l a b i l i t y t h ep u b l i s h s u b s c r i b es y s t e m sh a v e a b i l i t i e st om a k ei n f o r m a t i o n p r o d u c e r sa n d i n f o r m a t i o nc o n s u m e r s c o m p l e t e l v d e c o u p l e di nt i m ea n ds p a c et h a tm e e t st h en e e d so ft h el a r g e s c a l ei n f o r m a t i o n d i s t r i b u t e ds y s t e m s ，s oi th a sg r a d u a l l yb e c o m et h ei n f r a s t r u c t u r e p l a t f o r mf o rt h e l a r g e - s c a l ed i s t r i b u t e ds y s t e m s h o w e v e r , t h ee x i s t i n gp u b l i s h s u b s c r i b es y s t e m sd on o th a v ea b i l i t i e st os u p p o r t s e m a n t i c sh e t e r o g e n e o u s i ns o m ea p p l i c a t i o n s ，a na t o m i cs u b s c r i p t i o nc a n n o tg e tt h e e v e n t st h a tt h es u b s c r i b e r sa r em o s ti n t e r e s t e di no re v e nc a n n o tg e tt h em a t c hr e s u l t t oa d d r e s st h e s ei s s u e s ，s u p p o r t e db yn a t i o n a l8 6 3p r o g r a ma n dn a t i o n a ln a t u r a l s c i e n c ef o u n d a t i o n ，w er e s e a r c ho nt h ed a t am o d e lo fp u b l i s h s u b s c r i b es y s t e m s ， t r y i n gt oi m p l e m e n ta u t o m a t e ds u b s c r i p t i o nd e c o m p o s i t i o ns u p p o r t i n gs e m a n t i c e q u i v a l e n c ea n dm a t c h i n ga l g o r i t h ma n dt h e ni m p l e m e n tap r o t o t y p es y s t e m j t a n g p s dv e r i f i e dt h ep r o p o s e dm o d e l f i s t ，w ep r o p o s ead a t am o d e lt h a tc a n i m p l e m e n ta u t o m a t e ds u b s c r i p t i o n d e c o m p o s i t i o ns u p p o r t i n gs e m a n t i c e q u i v a l e n c e o n t o l o g y i si n t r o d u c e di n t o p u b l i s h s u b s c r i b es y s t e mt ob u i l dc o n c e p t u a lm o d e l ，e x p r e s s i n ga l lo f t h e c o n c e p t sa n d r e l a t i o n s h i p sb e t w e e nt h e m r d fc a nb eu s e dt oe x c h a n g ei n f o r m a t i o nb e t w e e n a p p l i c a t i o n sa n dg u a r a n t e en o tt oc h a n g et h es e m a n t i c i no r d e rt oa d d r e s st h ei s s u eo f s e m a n t i ch e t e r o g e n e o u s ，w eu s er d fg r a p h st or e p r e s e n te v e n t sa n dr d fg r a p h p a t t e r n st or e p r e s e n ts u b s c r i p t i o n s ，a n dd e s i g nas u b s c r i p t i o nl a n g u a g ep s s l t h e n ，w e d e f i n ec o m p o n e n ts e m a n t i c s o nt h i sb a s i s ，a na u t o m a t e ds u b s c r i p t i o nd e c o m p o s i t i o n a l g o r i t h ms u p p o r t i n gs e m a n t i ce q u i v a l e n c ei sd e s i g n e da c c o r d i n gt od e c o m p o s i t i o n i i i 浙江大学堡兰垡笙奎 一型堡竺生 _ _ _ - _ _ _ _ _ - - _ _ _ _ - _ _ _ - _ - _ _ _ - - - _ _ _ - - i _ 一一 m o d e l t h ed e c o m p o s i t i o na l g o r i t h md e c o m p o s e dt h ea u t o m a t e ds u b s c r i p t i o n i n t o c o m p o s i t es u b s c r i p t i o n s ，t h u si n c r e a s i n gt h es y s t e m se x p r e s sa b i l i t ya n du s a b i l i t y a ne f f i c i e n ts e m a n t i c - b a s e dm a t c h i n ga l g o r i t h mi sp r o p o s e db a s e do nt h ed a t a m o d e l w es a v ea l lo ft h es y s t e m ss e m a n t i c si n f o r m a t i o ni n t ot h er d f n o d ei n d e x s t r u c t u r eb a s e do nt h es u b j e c t st y p e so ft h es u b s c r i p t i o n s t r i p l e s t h es a m e s u b s c r i p t i o nc o n d i t i o n sb e t w e e nd i f f e r e n ts u b s c r i p t i o n sa r e s a v e do n l yo n c e t h e m a t c h i n gp r o c e s si s t ot r a v e r s et h ee v e n tg r a p hn o d e ；f i n dt h es u b s c r i p t i o n s n o d e s w h i c hm a t c hw i t ht h ee v e n tn o d ei nt h es e m a n t i c ，t h es y n t a xa n dg r a p hs t r u c t u r e ； u p d a t et h em a t c h i n gs t a t u so fe a c hs u b s c r i p t i o n a n dt h e np r o c e e dm a t c h i n go nt h e t e n n i n a t i o nn o d eo fe v e n ta r c a tl a s t ，t h ea l g o r i t h mr e t u r n st h es e to fm a t c h i n g s u b s c r i p t i o n s f i n a l l y , w ed e s i g na n di m p l e m e n tap r o t o t y p es y s t e mj t a n g p s d k e y w o r d s ：p u b li s h s u b s c r i b e ，c o m p o s i t i o ns u b s c r i p t i o n ，s u b s c r i p t i o nl a n g u a g e ， m a t c h i n ga l g o r i t h m ，d i s t r i b u t e dc o m p u t i n g ，s e m a n t i cw e b 浙江大学顺- ：学位论义图闩录 图目录 图1 1 发布订阅范型4 图2 1r d f 事件图例子14 图2 2r d f 订阅图模式例子16 图2 3 复合订阅的索引结构d s a 2 6 图2 4 可分辑原子订阅实例2 8 图2 5 多媒体家用电脑的分解模型2 9 图3 1r d f 节点索引结构和一个订阅s 3 6 图3 2 事件图g 3 8 图3 3 匹配算法a 勺u , j 间消耗4 4 图3 4 订阅维护的空间消耗4 4 图4 1j t a n g p s d 系统的体系结构陶4 7 图4 2 客户端模块类图：5 0 图4 3 核心模块类图51 图4 4 下跌盒融股订阅5 3 图4 5 股票事件。5 4 图4 6 匹配的股票事件5 5 图4 7 事件服务代理列表5 5 图4 8 事件服务代理的订阅列表5 6 浙江大学硕j ：学位论文第1 章绪论 第1 章绪论 1 1 研究背景 随着网络技术的飞速发展和普及，分布式系统的应用范同和规模发生了很大 的变化，分布式计算已经成为构建大规模信息发布系统的主流技术。传统的分布 式系统使用同步通信模型，系统中的各个节点以请求应答的方式进行信息的交换 及通信。这种模型在节点较少、业务需求相对简单的系统中具有很好的效果。但 是近年来i n t e r n e t 迅速普及，特别是移动计算、网格计算、云计算、普适计算等 新型网络计算模式的兴起，带来了分布式应用系统应用场景的巨大变革，具体表 现在： 参与者的数量异常庞大并处于大规模且分散的地理环境中； 用户希望能够动态地、智能地加入或退出系统： 信息的海量产生与用户对于信息精确投递的需求之间的矛盾。 参与者希望以一种松耦合的方式进行信息通讯、资源共享。 为了适应i n t e r n e t 计算环境大规模、松耦合、可扩展等需求给分布式技术带 来的挑战，过去的多年里，人们提出了多种技术，包括各种类型的巾间件应用技 术、网格技术、移动主体技术、p 2 p 技术、w e bs e r v i c e 技术。中间件技术为上层 分布式应用提供了透明的网络通信实现，适用于构建分布式信息系统及对现有系 统的集成；网格技术提供了天然的分布式计算支持，适合大规模并行计算应用， 能够有效地利用网络中可用的计算资源，在科学研究领域应用广泛；移动主体技 术有效提升了分布式计算的安全性和容错能力，在移动计算领域发挥着重要作 用；p 2 p 技术为分布式计算提供了网络通信方面的底层支持，基于对等节点的p 2 p 网络具有自适应、容错性i 岳等对于分布式应用来说很重要的特性：w e bs e r v i c e 技术的主要目的在于使计算机能够理解互联网的信息，从而为使用者提供最精确 的信息及最有用的功能。但是这些技术都没能很好的解决大规模应用中系统内节 点问通信解耦的问题，系统叫j 的参与者无法同时在时问、空间及同步上解耦，从 浙江大学硕i 学位沦文第l 章绪论 而大大限制了系统的并发处理能力并导致系统对网络拓扑的变化无法充分自适 应。而发布订阅技术由于具有异步、多点通信、松散耦合的特点，能够很好地满 足当前大规模信息发布系统松散通信的需要，逐渐成为了构建大规模分布式系统 的基础平台。基于发布订阅模型的系统，一般由信息生产者、信息消费者和一个 用于交互的中间件“事件服务”组成。消息生产者将消息发布到中间件，信息消费 者可以向中间件订阅他们感兴趣的消息，“事件服务”异步的将消息生产者发布的 消息发送到所有对该事件感兴趣的消息消费者。目前，已经有很多应用使用发布 订阅范型，比如股票报价、r s s 系统等。 1 2 研究意义 目前，发布订阅范型已经得到学术界和工业界的极大关注，开发出了许多支 持该范型的系统，并在电予商务、银行、证券等各个领域得到应用。同内外高校 和研究所开发的原型系统包括：s i e n a 、g r y p h o n z 、e l v i n 3 1 、h e r m e s 4 、x f i l t e r 5 1 和x t i r e 6 等：t 业界的产品包括：t i b c o 公司的t i b r e n d e z v o u s t 、j a v am e s s a g e s e r v i c e 8 1 、b a y e u x 9 j 、s c r i b e l l o 、i b m 公司的m q s e r i e s 1 l 】等。 但是，现有很多发布订阅系统都只能进行语法层次上的匹配，而忽略了事件 之间的语义关系。在新一代分布式计算环境中，众多的参与者往往来自各个不同 的地区和组织，他们发布的消息在语义上可能存在异构。比如在一个使用摹于内 容描述事件的在线购物系统中，有一个参与者p u b 发布消息e ： c o m m o d i t y = ”p c ” & p r i c e = “￥3 5 0 0 ” ，而如果另一参与者s u b 表示对满足条件 s ： c o m m o d i t y = ”c o m p u t e r ” & p r i c e 匿名性：发布者和订阅者不需要知道对方引用等信息。订阅者不知道获 得的事件是由哪个发布者发布的，发布者也不知道事件最终发送给哪些 订阅者。 扩展性：系统不需要做任何改变就可以支持新的参与者加入到系统中， 进而使系统可以无缝地扩展到适应i n t e m e t 应用需求的大规模性。 1 4 关键技术及国内外研究现状 数据模型、匹配算法和路由算法是发布订阅系统的三大关键技术。数据模型 用来获取事件的信息，表达订阅条件和订阅模式，决定了发布订阅系统的表达能 力；同时，数据模型也会影响匹配算法和路由算法，进而影响系统的效率。在发 布订阅系统中，大量事件以一个快速的速率到达，且订阅数目非常庞大，如何能 够及时、可靠地为每个事件找到所有匹配的订阅是非常重要的，匹配算法直接影 响到匹配事件的转发延迟和发布订阅系统的效率。路由算法解决了如何将事件沿 着系统中的事件代理高效、可靠地转发到匹配的订阅者，它影响着发布订阅系统 的效率和可靠性。本文主要研究数据模型和匹配算法，在本节中将介绍这两方面 的国内外研究现状。 1 4 1 数据模型 数据模型主要包括事件模型和订阅模型。事件模犁定义事件的数据格式；订 4 叵兰竺 爹遗 刁 器 固匪 浙江大学硕十学伊论文 第l 审绪论 阅模型定义订阅条件的表示方式。目前，研究人员已经提出了多种数据模型，包 括基于主题、基于内容和基于类型【1 2 】等。 基于主题的发布订阅系统 系统将事件划分成一个个主题( t o p i c ) ，用关键字( k e y w o r d s ) 表示；每个事 件属于某个主题，订阅者可以表达对特定的主题感兴趣。基于特定主体的事件到 达时，事件服务代理将其分发给所有订阅该主题的订阅者。 该模型是最早出现的模型，早期的发布订阅系统均基于该模型，包括 t i b r v 、b a y e u x 、s c r i b e 及i b mm q s e r i e s 的早期版本等。该模型的最人问题 是不能理解事件的内部结构，表达能力非常有限。 基于内容的发布订阅系统 与基于丰题的模型中，事件根据预先定义的外部主题米划分不同；基于内容 的模型可以让订阅者基于事件本身的内容来表达他们的兴趣，从而使得发布订阅 系统的表达能力更强，具有更细的粒度。其中，基于m a p 的和基于x m l 的模型 是基于内容的发布订阅系统中两种比较流行的模型。 基于m a p 的模型用属性名值对表示事件，订阅者通过使用特定的订阅语言 描述过滤( f i l t e r s ) 条件来订阅感兴趣的事件。过滤条件使用基本的运算符( = ， = ， ， - - - - - 等) 表示对属性名值对的约束，如”p r i c e 基于语义的发布订阅系统 在新一代分布式计算环境下，参与者的数目庞大，分散在各个地域，并且发 布订阅系统的参与者之间进行匿名通信，因此，系统中来自不同参与者的事件和 订阅之间往往在语义上是异构的，原有的数据模型都不能解决语义异构问题。 随着语义w e b 技术的发展，基于语义的发布问阅被提出并成为新的研究热 点。目前，研究人员已经开发了一些原型系统，包括：s - t o p s s t l 5 1 、d r e a m t l 6 】、 g t o p s s 17 】和o p s 0 s 】等。 s t o p s s 是通过在原有的基于内容的发布订阅系统基础上提出同义词、概念 层次和映射函数来扩展系统，使其具有语义匹配的能力。同义词转换阶段是将事 件和订阅中语义相同f 日名字不同的属性名转换为统一的“根”属性。同义词转换虽 然较为简单，但是它只考虑了属性层，而且没有考虑属性值的语义关系。概念层 一次将术语组织成层次结构，包含专门( s p e c i a l i z e d ) 概念的事件可以和包含广义 ( g e n e ：r a l i z e d ) 概念的订阅匹配，反之不能。映射函数可以指定不能用同义词和 概念层次表示的关系，它通过多对多函数把一个或多个属性名值对和语义相关的 另一个或多个属性名值对关联在一起。 d r e a m 是一个用于分布式异构应用的基于事件的中问件平台，其中c r e a m 是基于发布订阅系统模型的事件分发服务模块。与s t o p s s 相似，c r e a m 原有 的数据模型也是基于内容的。为了提供对语义异构事件的支持，c r e a m 定义了 6 浙江大学顾= f 二学位论文第l 章绪论 自己的数据模型m i x ，提供元数据和转换函数将属性名和值转化成本体中的概 念。 支持复合事件的发布订阅系统 近年来，支持复合事件的订阅与匹配也逐渐成为发布订阅的研究热点。它是 指多个事件匹配一个订阅。用户订阅的不再是单个事件，而是事件的集合。这些 事件相互间具有一定的关系，如时间先后顺序或者囚果关系。只有一系列符合订 阅条件的事件被发布，且相互满足规定的关系，才将复合事件分发给匹配的订阅 者。支持复合事件的系统有两个优点：首先，订阅者接收到相对较少的匹配事件， 进而减少网络阻塞问题。这是因为很多原子事件不满足相互之间的关系，如时间 先后顺序，在到达订阅者之前就被过滤掉。其次，由于在网络中而不是在网络边 缘检测复合事件，所以可以提高系统的整体性能。 c o u r t e n a g e 1 9 】提出了一种基于类型九演算的复合事件语言。该复合事件语言 用函数表达式来表示订阅，并用事件作为其参数。利用函数提供的参数比需要的 参数少，进而等待剩余参数来产生函数结果的特性，来保存复合事件的状态。但 是，久演算的表达能力是有限的，并且不能指定事件的顺序及时问约束。 p a d r e s 2 0 】是适用于工作流管理和业务流程执行的发布订阅系统，它支持 与、或、顺序等关系的复合订阅，特别地支持依赖关系和基于条件的重复关系的 表达，并将复合订阅映射到j e s s 的规则上，由j e s s 的推理引擎实现复合订阅的 匹配。 1 4 2 匹配算法 正如c a r z a n i g a l 2 1 】等人提出的事件服务中事件的规模性和表达能力是一对互 相矛盾的目标，随着数据模型表达能力的不断提高，如何提高匹配算法性能的挑 战也越来越多。在本节中，我们将介绍匹配算法的研究现状。 基于主题的发布订阅系统，不需要特别的匹配算法，只需要在事件到达时， 由事件服务代理将事件分发给所有订阅该主题的订阅者即可。在基于内容的发布 订阅系统中，研究人员提出了基于计数和基于树的匹配算法。随着语义概念被引 7 浙江大学硕f j 学位论文第1 享绪论 入发布订阅系统中，逐渐开始基于图的匹配算法的研究。 基于计数的匹配算法 基于计数的算法通过为每个订阅维护一个计数器，记录已经被当前事件匹配 的订阅条件数。当一个事件到达时，对事件的每个属性，依次匹配所有订阅的订 阅条件，如果事件的属性值满足订阅的条件，则将订阅的计数器增加一。当迭代 完事件的所有属性后，那些计数器的值等于订阅条件数的订阅就是和事件匹配的 订阅。可以对不同订阅的相同订阅条件只匹配一次，以提高匹配的效率。 l b r e a s l a u l 2 2 】等人和t y a n 【2 3 】等人均提出了基于计数的匹配算法。 基于树的匹配算法 基于树的算法将订阅组织成一颗有根节点的匹配树，树的非叶子节点代表属 性，叶子节点代表汀阅。当有事件到达时，从根节点开始根据属性值选择合适的 路径直到叶子节点，这些叶子节点就是匹配的订阅。 a g u i e r a 2 4 】等提出的基于匹配树的算法是在学术界使用最广泛的算法之一。在 该算法所创建的匹配树中，每个节点代表一个关于某个属性的测试，该节点的各 条弧表示测试的结果。匹配树的下一层是上层测试的细化。匹配树的叶子节点表 示各个订阅。事件到达时，从根节点开始在各层节点上依次测试，并沿着表示测 试结果的弧( 可能有一条或者多条弧) 进行下一层属性检测，直到叶子节点为止。 这些叶子节点就是和事件匹配的订阅。该算法的时间复杂度与订阅数成线性关 系，空间复杂度与订阅成次线性关系。另外，该算法对订阅插入或者删除的维护 代价也较小。 基于图的匹配算法 在基于图的匹配算法中，用事件图g 。和订阅图模式g 。分别表示事件和订阅。 当有事件到达时，匹配算法计算事件图g 。或其子图足否和g 。同构。 目前，研究人员已经提出了一些基于图的匹配算法。在o p s 中，通过构建扩 展元语句e m s 数组建立订阅索引。当有事件到达时，遍历事件图g 的每条弧， 以e m s 为索引，找到匹配的订阅弧，并用g 。的节点标签替代6 s 中对应节点的变 8 浙江大学硕 ：学位论文第1 章绪论 量，g 。中只有在上一层的弧匹配成功后，才能进行下一层弧匹配，最终形成一颗 “与或”匹配树，通过计算匹配树各节点的b o o l e a n 值，最终得到订阅是否匹配成 功的结果。在该算法中，对于每一个订阅都要构建一颗匹配树，这会有不小的时 间开销；而且随着概念模型的扩展，e m s 数组将会非常庞大，如何维护e m s 数 组也是一个很大的问题。 g t o p s s 以订阅图中的每条弧的两个节点组成的节点对建立索引。当有事件 到达时，对事件图g 。中的弧遍历，找到标签匹配的订阅；然后对这些订阅进行类 型检查和约束检查，找剑最终的匹配结果。该匹配算法对于可能匹配的每个订阅 都要进行约束检查，也就是说对于不同订阅的相同订阅条件，要进行多次约束检 查，这并没有利用订阅的覆盖性，即对相同订阅条件只进行一次约束检查，进而 影响系统的性能；类型检查也类似，对于每个相同的订阅条件都要对其主体、属 性和客体的类型进行多次检查。 1 5 论文背景及研究内容 论文涉及的背景是课题组承担的国家自然科学基金项目“自组织语义发布订 阅模型及路由算法”和国家8 6 3 计划资助项e 1 “软件产品线工程配置模型与问题求 解技术研究”。“自组织语义发布订阅模型及路南算法”项目针对目前发布订阅系 统在订阅和事件表达能力、匹配算法和路由算法等方面对语义异构的支持不够的 问题，分析跨领域边界的发布订阅体系，将本体概念引入发布订阅系统，建立 语义表达能力较强且具有较高语义匹配效率的发布订阅模型；将全局订阅匹配图 分解成局部订阅匹配图，分布到网络中的各个节点上，以提高复杂的语义匹配的 效率，适应大规模分布式计算的要求。 在上述课题背景下，我们对课题中现有发布订阅系统数据模型表达能力不 足、事件匹配算法效率不高等问题进行了研究并给出解决方案，最后给出了原型 系统j t a n g p s d 的设计和实现方案。本文重点介绍j t a n g p s d 支持语义等价自动 化订阅分解的数据模型、事件匹配算法和j t a n g p s 原型系统的实现。 本文共有五章，其中第二章至第四章是本文的主要内容。论文的组织结构如 9 浙江大学顾士学何论文 第l 章绪论 f ： 第一章绪论，介绍论文的研究背景、研究意义；介绍发布订阅系统概述 和关键技术的国内外研究现状；介绍论文背景及论文的研究内容。 宅一第二章支持语义等价自动化订阅分解的数据模型，给出了j t a n g p s - d 的 概念模型、事件模型、订阅模型及订阅语言；在此基础上，定义组件语 义，并描述分解模型的形式化表示和o w l 表示，并给出分解算法和分 解实例。 第三章基于语义的匹配算法，首先给出匹配算法的设计目标，在此基础 上，介绍匹配算法的基本思想；给出r d f 节点索引结构和订阅插入、删 除算法；然后给出基于语义的事件匹配算法，并分析了算法的时间复杂 度和空问复杂度，通过一组实验数据，分析算法的性能；最后给出了复 合订阅的匹配算法。 第四章j t a n g p s d 原型系统实现，介绍j t a n g p s d 的体系结构、各个模 块的功能描述、各主要模块的类图；最后给出一个应用实例，介绍 j t a n g p s d 在股票报价应用中的使用。第五章总结弓展望，总结了本文 所作的工作，并提出以后还需要继续完成的工作。 1 6 本章小结 本章首先介绍了发布问阅系统的研究背景；通过分析目前研究存在的不足之 处，阐述了论文进行支持语义等价自动化订阅分解的数据模型和事件匹配算法研 究的意义；介绍了发布订阅范型的基本概念和基本结构；分析了发布订阅系统 的关键技术及同内外研究现状；最后简要介绍了论文背景、论文的研究内容和论 文组织结构。 1 0 浙江大学硕士学位论文 第2 章支持语义等价自动化订阅分解的数据横型 第2 章支持语义等价自动化订阅分解的数据模型 数据模型作为发布订阅系统的关键技术，用来获取事件的信息表达订阅条 件和订阅模式，决定着发布订阅系统的表达能力。在新一代分布式计算环境下， 参与者的数目庞大，分散在各个地域，他们发布的事件和注册的订阅均可能存在 语义异构。目前发布订阅系统的表达能力已经比较强大，但是仍不能很好地解决 语义异构的问题。在本章中，我们将引进语义w e b 中的本体概念来建立数据模型， 使得事件和订阅具有表达语义的能力，提高事件匹配的精度。由于我们只利用了 本体中类、属性的等价、继承关系，不能解决原子订阅由一组事件匹配的问题， 我们进而定义了组件语义，并提出了支持语义等价的自动化订阅分解算法，将可 分解原子订阅分解为语义等价的复合订阅。 2 1j t a n g p s d 概念模型 概念模型描述了系统中所有事件和订阅涉及的各个概念及概念之间的关系。 在语义w e b 领域中，使用本体对一个特定领域中重要概念进行共享的形式化描述 p 5 。本体使用基丁逻辑的语言进行描述，可以精确、详细的表达概念、实体、特 性及它们之间的相互关系，而且被设计为用于那些从不同的组织查找信息的应 用。目前比较有影响力的本体描述语言是o w l l 2 6 1 。可以看到，本体适合基于语 义的发布订阅系统中对数据模型能够支持语义异构的要求。所以，在j t a n g p s d 中我们引入本体来定义概念模型，并使用o w l 语言进行描述。 奉体中定义了类、属性、类的实例以及它们之间的关系。在j t a n g p s d 概念 模型中，我们引入了类的等价、继承关系及属性的等价、继承关系。本体还支持 其它一些类的复杂关系，包括类的交运算、补运算等，目前，在我们的概念模型 中还不能支持这些关系。 定义1 系统中的概念模型可以用表示五元组d = c ，p ，c r ，豫，c s 表示。其 中： 浙江大学硕士学位论文第2 章支持语义等价自动化订阅分解的数掘模型 c 表示系统中所涉及到的所有类的集合。任何实例必须属于c 中的类； 一个实例可以属于多个类。 尸表示系统中所有属性的集合。 c r 表示系统中类之间所有关系的集合，包括等价、继承。其中，一个类 可以继承自多个父类，但不能出现循环继承。 朋表示系统中属性之间所有关系的集合，包括等价、继承。和类之间的 继承关系类似，属性也支持多继承，但不能出现循环继承。 c s 表示对类、属性的所有约束的集合。 本体可以由组织或者个人制定。目i j i ，一些知名组织和团体已经在网络上发 布了各个不同领域的本体。我们可以从网络上获取这些由计算机专业人士和领域 专家共同制定的本体。在进行事件和订阅匹配时，我们可以利用本体利于推理的 特性，进行语义匹配。 2 2j t a n g p s d 事件模型 由于我们采用本体作为概念模型，而本体是基于r d f 2 7 】的；r d f 可以在应 用程序间交换信息并且保证不丢失原有的语义，因此，我们可以使用r d f 语言描 述事件。r d f 用三元组( s u b j e c t ，p r o p e r t y ，o b j e c t ) 陈述资源。其中，主体( s u b j e c t ) 表示被陈述资源的u r i 引用，p r o p e r t y 表示属性u r i 引用，客体( o b j e c t ) 表示 主体在该属性下的值，可以是u r i 引用，也可以是文本值。在r d f 规范中，已 经定义了文本值的类型。r d f 可以用机器可处理的r d f x m l 语言进行描述，并 可以表示为一个有向图，其中每一个三元组可以用r d f 图中的一对节点对和节点 对间的弧表示。 j t a n g p s d 采用r d f 图表示事件模型。当有事件发布到系统时，将其转化为 统一的r d f 格式，最终，事件服务代理将r d f 格式的事件发送给所有匹配的订 阅者；这在一定程度上解决了结构异构的问题。为了匹配的方便，我们对r d f 事件图进行了一定的约束。约束如下： 事件图中的节点除了文本节点外，必须至少要有一个类型。如果没有类 1 2 浙江大学硕二i ：学位论文第2 章支持语义等价自动化订阅分解的数据模型 型，则设为缺省值o w l ：t h i n g 。对于文本节点，可以采用r d f 规范中预 先定义的数据类型。 事件图中的每个节点不能有相同的标签， 事件图中的每个节点对之间至多只能只有一条相同标签的弧。 每个事件图都有一个根节点r v 。 上述约束虽然使得r d f 事件图的表达能力受到一定限制，但是这已经满足 j t a n g p s d 对数据模型表达能力的要求，并且有利于匹配效率的提高。r d f 事件 图可以用七元组g 。进行表示。 定义2 一个r d f 事件图可以用七元组g ，= y ，e ，互，t ，p ，占，c s 表示。其中： v 表示事件图中所有节点的集合。节点包括资源节点、文本节点和匿名 节点。 互表示事件图中所有弧的集合。 工表示事件图中所有节点标签的集合。 三。表示事件图中所有弧标签的集合。 p 表示从节点到节点标签的所有映射两数的集合，即矿山l 。 占表示从弧到弧标签的所有映射函数的集合，即e _ 厶， 劣表示事件图的所有约束的集合。 图2 1 是一个r d f 事件图的例子，描述了一个在线购物网站发布了个电脑 事件，该电脑是全新的，品牌为联想，价格为5 0 0 0 元，外观颜色为红色。 1 3 浙江大学硕i ：学位论文第2 审支持语义等价自动化订阅分解的数掘模型 j 一 r d f ：t y p 。 一一一 图2 1r d f 事件图例子 2 3j t a n g p s d 订阅模型 我们用r d f 图表示事件模型，因此，可以用r d f 图模式表示订阅模型。r d f 图模式规定了事件图的形状，并规定了节点的约束条件，来表达订阅者感兴趣的 事件。当有订阅发布到系统时，将其转化为统一的r d f 格式进行转发和匹配。为 了匹配的方便，我们对r d f 订阅图进行了一定的约束。约束如下： r d f 订阅图模式中的节点除了文本节点外，必须至少要有一个类型。如 果没有类型，则设为缺省值o w l ：t h i n g 。对于文本节点，可以采用r d f 规范中预先定于的数据类型。 r d f 订阅图模式中的每个节点不能有相同的标签。 r d f 订阅图模式中的每个节点对之间至多只能只有一条相同标签的弧。 r d f 订阅图模式不能存在匿名节点。 r d f 订阅图模式都有一个根节点r v 。 定义3 一个r d f 订| 列图模式可以用八元组g = 矿，e ，乙，乞，p ，s ，f s ，c s 表 示。其中： y 表示r d f 订阅图模式中所有节点的集合。节点包括资源节点、文本节 点和变量节点，在订阅图模式中不存在匿名节点。 1 4 浙江大学硕i j 学位论文 第2 奇支持语义等价自动化订阅分解的数据模型 表示r d f 订阅图模式中所有弧的集合。 厶表示r d f 订阅图模式中所有节点标签的集合。 厶表示r d f 订阅图模式中所有弧标签的集合。 p 表示从节点到节点标签的所有映射函数的集合，即y 山厶。 s 表示从弧到弧标签的所有映射函数的集合，即 三。 f s 表示所有文本节点的过滤函数集合( f i l t e r f u ns e t ) 。对于每个文本节 点，可以设置一个过滤函数，约束该文本节点的值。对于没有过滤函数 的文本节点，则可以设置一个返回值始终为t r u e 的过滤函数。 c s 表示r d f 订阅图所有约束的集合。 j t a n g p s d 要解决语义匹配的问题。因此，我们在订阅幽模式中引入元语句 ( m e t a s t a t e m e n t ) ，在匹配过程中，通过索引元语句，提高匹配效率。如果对于 一个- - 元n ( s ，p ，d ) ，主体s 的类型为s ，客体0 的类型为0 ，则该三元组的元语 句为( s ，p ，0 ) 。 在订阅图模式中，我们用群i 表示变量节点。”j 9 ”表示该节点是变量节点，i ( 0 ) 表示变量名。每个顶点用表达式( i d ，f i l t e r f u n ( i d ) ) 表示。f i t t e r f u n ( i d ) 表示节点的过 滤函数。没有约束的节点可以匹配任何值，而有约束的节点只能匹配那些满足约 束条件的值。 图2 2 是一个r d f 订阅图模式的例子，描述的订阅条件为：一台外观颜色为 红色、价格小于5 0 0 0 人民币、品牌为联想的新电脑。 1 5 浙江大学硕l 学位论文 第2 章支持语义等价自动化订阅分解的数掇模型 一 r d f ：t y p e 一一l 一、 c u r r e n c y 图2 2r d f 订阅图模式例了 在订阅图模式的基础上，我们定义j t a n g p s - d 的订阅语言p s s l ( p u b l i s h s u b s c r i b e