D0I:10.13374/j.issn1001-053x.2013.04.018 北京科技大学学报 Vol.35 No.4 第35卷第4期 2013年4月 Journal of University of Science and Technology Beijing Apr,2013 发布/订阅系统语义Web匹配算法 冯锡炜)四，汪俭华)，冯瑶，林培光2) 1)辽宁石油化工大学计算机与通信工程学院，抚顺1130012)山东财政学院计算机学院.济南250014 区通信作者，E-mail:feng,xw@163.com 摘要将语义Wb技术引入发布/订阅系统中，结合领域本体，提出一种智能匹配算法.以双索引哈希邻接表，结合 谓词表、变量约束表和变量类型表作为订阅条件DP图模式的数据结构，采用元语句级匹配计数方法，使原子订阅条 件仅匹配一次，原子订阅条件间“与关系”的顺序匹配.定量和定性分析了算法的时间和空间复杂度.实验结果比较表 明，所设计的智能匹配算法具有较高的订阅匹配效率，适合于大规模发布/订阅系统 关键词算法：语义Wb:Web服务：发布/订阅系统：哈希函数：本体论 分类号TP393.09 Semantic Web-based matching algorithm for publish/subscribe systems FENG Xi-wei),WANG Jian-hua),FENG Yao),LIN Pei-guang2) 1)School of Computer and Communication Engineering,Liaoning Shihua University,Fushun 113001.China 2)School of Computer Information Engineering,Shandong University of Finance,Jinan 250014,China Corresponding author,E-mail:feng.xw@163.com ABSTRACT The semantic Web technology was introduced into publish/subscribe systems and an intelligent seman- tic matching algorithm(ISMA)was proposed by domain ontology.With double-index hash tables,predicate.variable filter and type tables as the data structure of resource description framework(RDF)graph patterns which stores subscrip- tion conditions,the algorithm adopts meta-statement match counting method to efficiently process atomic subscription factor match only once,and the subscription conditions are an "and"serial sequence matching relationship.The time and space complexities of the algorithm were derived and analyzed by quantitative and qualitative methods.Experi- mental results demonstrate that the algorithm is efficient and scalable,and it is suitable for large-scale publish/subscribe systerns. KEY WORDS algorithms;semantic Web:Web service;publish/subscribe systems;hash functions;ontology 发布/订阅系统模型中，发布事件与订阅条件1数据模型 匹配的传统方法有基于关键字匹配、主题匹配、内 发布/订阅系统的语义Web数据模型，包括语 容匹配等，虽然事件模型和订阅模型实现简单， 义Web事件模型、订阅模型和概念模型.事件模型 但匹配效率不高.引入语义Wb的发布/订阅系统， 定义事件的描述方式，事件利用RDF(resource de- 通过语义层上进行匹配，可以提高匹配的准确性、 scription framework)图来表示：订阅模型规定订阅 灵活性和丰富表达能力，但对大量的发布事件和 的表达方式及过滤条件，用RDF图模式来表示；概 订阅条件，其匹配算法需要设计高效合理的数据模 念模型描述某一领域中的概念及其之间的关系，用 型.发布/订阅系统的数据模型决定了系统的表达 OWL(Web ontology language)语言来表示，概念信 能力2-4 息被系统无歧义的理解和处理 收稿日期：2011-12-24 基金项目：国家自然科学基金资助项目(60172044)：辽宁省教育厅科学研究资助项目(L2011055):辽宁省教育科学“十二五”规划 立项资助课题(JG11DB163,JG12DB27):辽宁石油化工大学科学基金资助项目(2011XJJ-018)第 卷 第 期 年 月 北 京 科 技 大 学 学 报 发布 订阅系统语义 、 亡 匹配算法 冯锡炜 网, 汪俭华 , 冯 瑶 , 林培光 辽宁石油化工大学计算机与通信工程学院, 抚顺 山东财政学院计算机学院, 济南 困 通信作者 , 摘 要 将语义 技术引入发布 订阅系统中, 结合领域本体, 提 出一种智能匹配算法 以双索引哈希邻接表, 结合 谓词表 、 变量约束表和变量类型表作为订阅条件 图模式的数据结构, 采用元语句级匹配计数方法 , 使原子订阅条 件仅匹配一次, 原子订阅条件间 “与关系 ” 的顺序匹配 定量和定性分析了算法的时间和空间复杂度 实验结果比较表 明, 所设计的智能匹配算法具有较高的订阅匹配效率, 适合于大规模发布 订阅系统 关键词 算法 语义 服务 发布 订阅系统 哈希函数 本体论 分类号 下匕一 尸百浑 乞一 回 , 恻 万` 五 一人。 , 尸召万 ` 儿 , 石脚 尸 乞一夕。 夕 , 、 , , , 困 , 一 沉 回 ￡ 七 , 一 , , , “ ,, , 一 亡 认飞 、 发布 订阅系统模型中, 发布事件与订阅条件 数据模型 匹配的传统方法有基于关键字匹配 ·主题匹配 、 内 发布 订阅系统的语义 数据模型, 包括语 容匹配 等 , 虽然事件模型和订阅模型实现简单 , 义 事件模型 、订阅模型和概念模型 事件模型 但匹配效率不高 引入语义 的发布 订阅系统 , 定义事件 的描述方式, 事件利用 通过语义层上进行 匹配 , 可 以提高匹配的准确性 · 、 。 图来表示 订阅模型规定订阅 灵活性和 丰富表 达能力 , 但对大量 的发布事件和 的表达方式及过滤条件, 用 图模式来表示 概 订阅条件 , 其匹配算法需要设计高效合理 的数据模 念模型描述某一领域中的概念及其之 间的关系, 用 型 发布 订阅系统 的数据模型决定 了系统 的表达 。 语言来表示, 概念信 能力 一钊 息被系统无歧义的理解和处理 收稿 日期 一 一 基金项目 国家自然科学基金资助项 目 辽宁省教育厅科学研究资助项 目 辽宁省教育科学 “十二五 ”规划 立项资助课题 , 辽宁石油化工大学科学基金资助项 目 一一 DOI :10.13374/j .issn1001 -053x.2013.04.018