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
第4期 冯锡炜等：发布/订阅系统语义Wb匹配算法 .545. 定义1设语义Web事件数据模型（事件图） e,el(e,e;∈Ep),当e≠ej→Fpe(e)≠ GE,语义Web订阅数据模型（订阅图模式）GS,设 FE(e),反之也成立，即FPp(e)≠FpE(e,)→e:≠ (F,pF,u5)∈TE,(u,p,y)∈Ts,其中TE为GE ej. 中三元组集合，Ts为GS中三元组集合，2和vF FsE:Es一UR,是RDF图模式中弧的标识 分别代表TE中三元组的第i个主体节点和第j个 函数.Es表示为RDF图模式弧（有向边）的集 客体节点，和v分别代表Ts中三元组的第i个 合.e,e(e,ej∈Es,当ei卡ej→FsE(e)卡 主体节点和第个客体节点，p和分别是上述 FsE(e),反之也成立，即FsE(e)≠FsE(e)→e≠ 两个三元组的第i个属性 ej. GE匹配GS,当且仅当满足下列条件 filter v是节点v的过滤函数，可以为空，则 条件1对任意的(，p,v)∈Ts,都有对应 filter vs()=true. 的(F,pF,v5)∈TE; 对于语义Wb订阅数据模型GS中任意一条 条件2 constraint(type(Fpv(uF),≤type(Fsv 弧，在事件数据模型GE中都有一条弧与之对应， (v5)))A(constraint(Fpv(vf),=,Fsv(vs))vFsv(vs)E 它们的节点类型约束相匹配，属性标识约束相匹配， VA); 且用GE中顶点标识替换GS中对应顶点的变量标 条件3 constraint(FpE(p),≤，FsE(p): 识，使得GS中顶点过滤函数约束结果为真，则GE 条件4 constraint(type(Fpv(u),≤type(Fsv 匹配GS. (vs)))A(constraint(Fpv(vf),=,Fsv(vs))VFsv(vs)E 2语义匹配数据结构与算法 VA)Afilteres(Fpv(vf)). 其中，constraint()是对节点约束，允许其为 在比较已有的算法5-9)]基础上，本文设计如下 空.一个约束constraint为(？x,op,v)的谓词（断 数据结构和实现算法. 言)，其中？x表示变量，v表示变量值，op表示 2.1语义匹配数据结构 操作运算符.运算符op包括六种关系运算符，即 定义五种存储语义Web订阅数据模型的数据 =,>,≥，subNumSet;/订阅序号集合 引用，文本节点.C是所有类的集合，包括XML enum filterType;/六种关系运算符 Schema数据类型集合， Object elem Value;/变量类型对象 FPv:VP→(UR U LV UBV),是RDF图 } 中节点的标识函数.Vp表示为RDF图节点的集 (2)VTL:变量类型表.用于存储在订阅数据模 合，UR表示URI引用集合，V表示文本节点集 型中由rdf:type指引的URIRef参照本体类型.其 合，BV表示空白节点集合.节点可以是URI引 数据结构如下： 用，文本节点或空白节点.，vl(,∈Vp),当 Class Vtl{ 卡U→Fpv()≠Fpv(u),反之也成立，即 HashSetsubNumSet;/订阅序号集合 Fpv(v)≠Fpv(y)→卡v URIRef uRIRef;:/URIRef变量类型 Fsv:s→(URULUVA),是RDF图模式中节 点的标识函数.UR表示URI引用集合，L表示普 (3)HTVI:变量索引哈希邻接表.在其中，有两 通文本和类型文本节点集合，VA表示所有变量集 类边表，即VFL List表和VTL List表，由HTVI共 合，即以“？"开头的标识集合.，vl(i,v∈Vs), 同管理，建立索引，便于实际操作.由于VFL List 当卡v→Fsv()≠Fsv(U),反之也成立，即表与VTL List表结构不同，对任意一个语义Web Fsv()≠Fsv(y5)→≠Uj. 订阅模型中变量，当且仅当属于上述两个Lst表之 FPE:EP→UR,是RDF图中弧的标识 一，通过VFL List表和VTL List表的标记数据项 函数.EP表示为RDF图弧（有向边）的集合.区别.当多个订阅条件合并于同一个订阅图模式后
第 期 冯锡炜等 发布 订阅系统语义 、, 七 匹配算法 定义 设语义 事件数据模型 事件图 , 语义 订 阅数据模型 订阅图模式 , 设 仕只可,了 任几, 谭,可,呼 。马, 其中几为 中三元组集合, 为 中三元组集合, 厂和 。夕 分别代表 几 中三元组的第 艺个主体节点和第 了个 客体节点,峪和呼分别代表 中三元组的第乞个 主体节点和第 个客体节点, 舒和可 分别是上述 两个三元组的第 乞个属性 匹配 , 当且仅 当满足下列条件 条件 对任意的 峪,,矛,呼 。 , 都有对应 的 厂, 尹, 贾任几 条件 外 户 , 毛 凡 ,,尹 八 。户, , 弃 尹 条件 外 舒, 毛, 拿 条件 ` ` 丹 啧 ,毛` 呼 八 ` `外 啧 ,一, 呼 凡 贾任 八 娜外 啧 其中, 是对节点约束 , 允许其为 空一 个约束 为 , , 。 的谓词 断 言 , 其 中 表示变量 , 表示变量值 , 表 示 操作运算符 运算 符 包括六种关系运算符, 即 , , , , , 并 它分为两类运算 对文 本类型节点, 过滤是布尔运算 对 类型 , 过 滤是 一 关系运算 、 , 是 图模式 中顶点的类型 函数, 用于指定每个资源变量节点的类型 其 中 表示为 图模式节点的集合 节点可 以是 引用 , 文本节点 是所有类的集合 , 包括 数据类型集合 、 日 , 是 图 中节点的标识 函数 外 表示为 图节点的集 合 , 表示 引用集合 , 表示文本节点集 合 , 表示空 白节点集合 节 点可 以是 引 用 , 文本节点或空 白节 点 、,巧 , , 。 任饰 , 当 , 务 井 二, 兴 , 反之也成立 , 即 , 异 , 井 ” 兴 , · , 是 图模式 中节 点的标识函数 表示 引用集合 , 表示普 通文本和类型文本节点集合 , 表示所有变量集 合, 即以 `卿 开头 的标识集合 `, 、,巧 任 , 当 、并巧 、 兴 , 反之也成立 , 即 凡 , 务 井 饭并 , 外 尸 , 是 图中弧 的标识 函数 尸 表示为 图弧 有向边 的集合 丫 、, 。 、, , 任 , 当 并 , 井 、 兴 凡 , 反之也成立 , 即 外 。` 并 , 乡 护 已 · , 是 图模式 中弧的标识 函数 表示为 图模式弧 有 向边 的集 合 , , , 任 , 当 兴 。, 井 , 务 , 反之也成立, 即 务 , 井 笋 , · 呼是节点呼的过滤函数, 可以为空, 则 。贾 一` · 对于语义 、碗 订阅数据模型 中任意一条 弧, 在事件数据模型 中都有一条弧与之对应 , 它们的节点类型约束相匹配, 属性标识约束相匹配, 且用 中顶点标识替换 中对应顶点的变量标 识, 使得 中顶点过滤 函数约束结果为真, 则 匹配 语义 匹配数据结构与算法 在比较 已有的算法 一” 基础上 , 本文设计如下 数据结构和实现算法 语义匹配数据结构 定义五种存储语义 从飞 订阅数据模 型的数据 结构 变量约束表 用于存储变量约束的条 件, 包括约束 的操作运算符 , 约束的类型对象 值 , 操作运算符为六种关系运算符 其数据结构如下 订阅序号集合 六种关系运算符 变量类型对象 变量类型表 用于存储在订阅数据模 型中由 指引的 参照本体类型 其 数据结构如下 订阅序 号集合 取 取 变量类型 卜变量索引哈希邻接表 在其中, 有两 类边表 , 即 表和 表 , 由 共 同管理, 建立索引 , 便于实际操作 由于 表与 表结构不 同, 对任意一个语义 从飞 订阅模型中变量 , 当且仅当属于上述两个 表之 一 , 通过 表和 表的标记数据项 区别 当多个订阅条件合并于同一个订阅图模式后
.546 北京科技大学学报 第35卷 各订阅条件可能存在变量名冲突，HTVI以变量名 于订阅条件自身三元组数量的订阅条件，作为匹配 +订阅序号作为索引哈希表的联合主键其数据结 成功的订阅条件 构如下： //Intelligent Semantic Matching Algorithm aashSet()PSHatch (GE,GS) Class Htvi{ RDrModel vAList;:/VFL列表 保存配指中不动的行阅件号列： ListvtlList;/VTL列表 nt B (4)PDT:谓词表.用于存储每个订阅条件三元 !查询合并订阅敷籍结构s中订阅安哈希邻锁表： 2 if (htaizlem !-null) 组中，主语和宾语变量通过订阅序号标识所属订阅 21 pdtLiat《一hta1E1em,getPdtLiat):/将到词列表pdtLiat 2 for ench prediente item pdt(pdtSubject,pdtobject)in pdtLiat 条件，对主语和宾语变量再通过HTVI查询到变量 if (checkTypeVar (eventsubject,pdtSubject) 2 类型或变量约束.其数据结构如下： Class Pdtf String subNum;/订阅序号 /若元话句级匹配成功。将R /订阅条件序号，数据值城计数加1 lt5 abacrbe中对应的 String subject VarName;/主体变量名称 hBhu1t号 htReauitsuba ()) String object VarName;/客体变量名称 1 e1se/首次终取已匹配订阅序号 ()) 微索益 (pdt.(),Inte 7 htResultSubacribe.remove(pdt.getsubNum()): (⑤)HTSI:订阅索引哈希邻接表.此表是语义 /在htResultSu山acribe保存的是可能匹配成功的订阅条件序号列表 Web订阅数据模型的起始点.各订阅条件约束谓词 subacribe No.item subacribelo in htReaultSubacribe.keyset ( htReaultSubacribe.get (aubacribeNo): 集是个有限集合，在两个订阅条件中可能有相同的 /即为匹配成功的阅条件 属性标识严，在HTSI中属于一个数据元素，通 把远配成功的司案件，放结果集au15uset中 过订阅序号HashSet标记约束谓词对应已有的ss. 把相同的属性标识“一的订阅条件链接在同一个边 图1支持语义的智能匹配算法 表PDT中，根据订阅序号加以标识.其数据结构如 Fig.1 Matching algorithm of ISMA 下： 2.3算法复杂性分析 Class Htsl{ URIRef uRIRefPro;/属性URIRef 设有S个订阅，共Sp个订阅谓词属性，分属于 HashSetsubNumSet;/订阅序号集合 Ps个类别、Sr个变量约束和Sr个变量类型，Sr ListpdtList;/PDT列表 分属Fs个类别，SR分属Rs个类别.设R=∑R· 设有e个发布事件，共Ep个断言，分属于PE个 22支持语义的智能匹配算法(ISMA) 类别.从时间复杂度和空间复杂度两方面进行匹配 算法（包括发布事件）的复杂性分析 发布事件需要与所有的订阅条件比较，查找匹 2.3.1时间复杂度分析 配的订阅条件集{S},是对语义Web订阅数据模型 的匹配，算法如图1所示. 匹配算法时间复杂度分析：设第E,发布事件 为了适应分布式、大规模和动态变化的需求10， 共有EP个断言，第，断言对应订阅索引哈希邻 匹配算法分两个阶段.第一阶段是对RDF/XML格 接表HTSI中的谓词列表长度为PDTLen,单个发 式存储的发布事件通过本体库规范其术语，检查其 布事件与订阅条件匹配的时间复杂度为 逻辑关系是否符合本体库要求，通过规则进行同义 词推理，完成语义标识；第二阶段是对三元组形式 (1) 表示的事件与语义Wb订阅数据模型，根据属性 进行结构比较，将可能满足的订阅条件一次性选出 因为∑PDTLen2=Sp,所以 来，再根据已匹配的三元组数量与订阅条件自身三 元组数量比较，将匹配选择的订阅条件中，大于等 TEMSi≤O(SP), (2)
5 4 6 · 北 京 科 技 大 学 学 报 第 卷 各订阅条件可能存在变量名冲突 , 以变量名 订 阅序号作为索引哈希表 的联合主键 其数据结 构如下 变量名称 订阅序号 肠 枚举类型, 选一 、 列表 列表 谓词表 用于存储每个订阅条件三元 组中, 主语和宾语变量通过订阅序号标识所属订阅 条件 对主语和宾语变量再通过 查询到变量 类型或变量约束 其数据结构如下 订阅序号 主体变量名称 。 客体变量名称 订阅索引哈希邻接表 此表 是语义 订阅数据模型的起始点 各订阅条件约束谓词 集是个有 限集合, 在两个订阅条件中可能有相同的 属性标识 叼斗乙, 在 中属于一个数据元素 , 通 过订 阅序号 标记约束谓词对应 已有的 把相 同的属性标识 叼〕产的订阅条件链接在 同一个边 表 中, 根据订阅序号加以标识 其数据结构如 下 印 属性 订阅序号集合 列表 支持语义 的智能匹配算法 发布事件需要与所有的订阅条件 比较 , 查找匹 配的订阅条件集 , 是对语义 订阅数据模型 的匹配 , 算法如图 所示 为了适应分布式 、大规模和动态变化的需求 , 匹配算法分两个阶段 第一阶段是对 格 式存储 的发布 事件通过本体库规范其术语, 检查其 逻辑关系是否符合本体库要求, 通过规则进行 同义 词推理 , 完成语义标识 第二阶段是对三元组形式 表示的事件与语义 从飞 订阅数据模型 , 根据属性 进行结构比较 , 将可能满足的订阅条件一次性选 出 来 , 再根据 已匹配的三元组数量与订阅条件 自身三 元组数量比较 , 将 匹配选择 的订阅条件 中, 大于等 于订阅条件 自身三元组数量的订阅条件 , 作为匹配 成功的订 阅条件 口即 息, 口 匕 七功 口 王卯 七 血 , 劫 七` 七 土 》 《 口 困匕 卜 艺, 》 加口刀纽川巨 互 `一 民 山山 比 , 记 口口, 扣口 。`比 已 `花 口刀比川 一 。 目 旧 二 洲 陇 硬 叹口山川 , 工生 七记 月之 。七 。勺 吧 目 巴 带 , 七 仁孟这 仁 一 别 目匕口 巴 仁工生 】言 七 七, 。七」上吧 二 万 , 七 七 咤 七 切 , 忆 叨 》 砚》 , 保 存可 能匹配成 功 的订阅条件 序号 列表 , 其健 值为 订 圈序 号 , , 橄 据值 为匹配 成功 的谓词表达 式个 橄 , 及 臼匕 心 七 ” 口 七 《 七 红月 》 砚 刀保 存匹陀 过理 中不成 功的订 阅条件 序号列 襄 七 口七 七吧, 巴口 日 艺 吧 口 口七 乙主口 民 户以沈 立, ` 目 已 , 二 七, 。七, 州茸吧 。 七 , 即 比 七」 , 吧, 曰月犯 , 七 忆, 吧” 加 加 巴不 理 抓 犯 匕 , 王 解 比 七一土兀立 《 。 , 口书记 刀 查钧合 并订 匆橄拐 结撰招, 中订 阅宜引哈 希邻挂 表 伪 月生厄 夕二 《一 址 , 妞加 价 以 》 ,' 得 到讨 词列 表冈 以 纪。 。助 州, 以 比 七, 亡 , 口 七工立 立亡 。七 亡宜了萝 吧, 抽 《 , 心 , “ 。七 `上 亡, 知上 砚 , 七 , 七 》 , 根拓主 语 。曲 与 七 女 盈类 组是 否 匹配和 宾语 , , 吧, 七 , 与训幽 喊 变 盈的 束是 否匹配 标准 , 断言 与订阅条件 谓词表 姑式 是否 匹配到 , 实 现 发布事件 日 匕口 , 获取以 砚洲食湘口 知 及 , 七 力 口 《】川 定 , 称 为元 语 句级 匹配 , 二 七翻仙 峨 》 已匹 配订 阅序 号为洲 ` , 比刘 卜 。的月 性徽 级 洲 食湘 口 七 口 ,' 若元语句 级 匹吮成 功, 将 七。 呱 七, 曲 二 派 中对 应 的 , 订阅条件 序 号, 孩拐 值坡 计橄加 口 , 七 上吧 。 吧 口, 吐目 一口吧比 七口口 》 》 七七 口七 。七 泛 一 七 砚 。 , 首 次获取江 己匹配订 日序 七七口吧 血 」上吧 七七月 七翻 《 , 劝 七于 口 叱曰 砚》 , 切 砚 公 , , 若元语句 级 匹充不 成功 , 将七四 公 。 曲 山吧中川 , 此 订阅序 号 , 间时在汤 舰 加 切曲 邮 曲 玲希纽 合仑 井 `订 阅序 号且 七七及 , 己 」上吧 。 吧 口, 。口吧 上日幼 《 》 》 七 口 口山妇 七石 七 。 《 。口 ` 七翻 砚》 》 刀在汤口 吐 。 七 派 保 存的 是可 曲匹配 成功 的订 阅条件 序 号列衰 亡。 `七 七 力吧 。 。 二 既 月义沮 。 刀 加七皿 日 」上吧 丫阮 《 》 冶 七 皿 , 上比 , 硬 立 月 亡《 劝 , 舀 口 月 , 立兀立, 《 。 上吧 匕 刀 硕口七 幻洲组。 》 , 每个橄拐元贵值峨大于 、 娜于订阅条件“ 的谓词衰达式橄最的订阅条件 即为 匹配成功 的订 阅条件 忿吧 宝, 创民犯 。 `, 七 幻跳口 , 把 匹配成劝 的订 阅条件 , 放人 结某 典民 皿 吧 中 吧二 , 创民沁 图 支持语义的智能匹配算法 入 算法复杂性分析 设有 个订阅, 共 异 个订阅谓词属性, 分属于 个类别 、 个变量约束和 几个变量类型 , 尸 分属 个类别, 。分属 、 个类别, 设 又 、 设有 。个发布事件 , 共 尸个断言 , 分属于 几 个 类别 从时间复杂度和空间复杂度两方面进行匹配 算法 包括发布事件 的复杂性 分析 时间复杂度分析 匹配算法时间复杂度分析 设第 , 发布事件 共有 尸、个断言, 第 升, 断言对应订阅索引哈希邻 接表 中的谓词列表长度为 , 单个发 布事件与订阅条件匹配的时间复杂度为 么 、 `七`一口头” 了少 因为 艺 了 尸, 所以 几 、 蕊 尸
第4期 冯锡炜等：发布/订阅系统语义Web匹配算法 ·547. 不失一般性，设EP:个断言对应X·Sp个PDT 因为Sp=Sp+Sr-S,其中SF+Sr为语义Veb 谓词元素，其中0≤X≤1，则TES=O(ASP): 订阅数据模型节点总个数，S为订阅条件数量：所 设Er,= EP,入=max{(A,0≤入≤1，则整个匹 以 配算法的最大时间复杂度为 SSDS =O(2(SF+SR)-S+Ps +Fs+Rs),(7) T=O(A:Sp·e). (3) 又由于Sp≥Ps,SF≥Fs,Sr≥Rs,所以最大空间 其中，入表示单个发布事件断言数与订阅条件总订 复杂度为 阅谓词数比值的最大值，从概率上考虑，入《1，甚 至入·e《1.在匹配算法的实现过程中，采用元语 SX≤O(4(Sr+S)-2S), (8) 句级匹配不成功标记方法，当订阅S某次元语句匹 配不成功，在本次发布事件以后的匹配判断中，不 即最大内存消耗与总节点个数成正比. 需要再对订阅S进行元语句级匹配判定，所以 一般情况下，订阅条件谓词种类Ps是有限的， 设P=∑Ps.变量类型种类Rs是有限的，在一个 T=O(Sp). (4) 大规模的分布式系统内，Ps《SPRs<SR,考虑到 即匹配算法的最大时间复杂度与订阅条件谓词数量 订阅条件维护的效率，语义Web订阅数据模型数据 成线性关系 结构中，把变量约束完全相同才共享同一空间，但 发布事件时间复杂度分析：发布事件RDF图 变量约束完全相同的情况随机性很大.设 Fs =AF SF 是由Jena工具直接转换为RDF/XML格式，获得 其中入F≤1，称入F为变量约束反向重复率，其值 发布事件每个断言表达式，遍历其过程也是匹配算 越小，表示重复率越高：当入F=1时，没有重复的 法的过程，所以发布事件时间复杂度为常量级，即 变量约束.所以 Tp=O(1). (5) SsDS =O((2+AF)SF+2SR+P+R-S), 2.3.2空间复杂度分析 因为P和R都为固定值，则 内存空间消耗包括VFL变量约束表、VTL变 量类型表、HTVI变量索引哈希邻接表、PDT谓词 SSDS =O(SF+SR-S). (9) 表和HTSI订阅索引哈希邻接表，五类表的数据存 储结构总和.因为每部分的数据元素所占空间大小 即空间复杂度与语义Web订阅数据模型总节点个 固定，与数据元素数量成正比，合并订阅图模式空 数呈线性关系 间复杂度为： 3测试与分析 SSDS=O(Ps+Sp+SF+SR+Fs+Rs), (6) 语义匹配模拟实验参数项如表1所示， 表1语义匹配模拟实验参数列表 Table 1 Simulation parameter list of semantic match 项目参数名称 项目值 说明 备注 15个本体类：每个本体有5个属性，共75个属性 (O.P.S) (15.5,3) 平均每个本体有3个同义词，共计45个同义词. 本体类间和属性间无继承关系 (SN,SE.SURN) (10,9,5) 订阅条件结构：10个节点9条弧，5个URIRef SUBC 10000 订阅条件数量 可调 Tps 15% 订阅条件请词属性重复率 可调 URC 15 订阅条件变量类型种类，等于本体类数量 AF 0.9 订阅条件变量约束反向重复率，其值越小，表示重复率越高 可调 SYNONYMS 3 URIRef同义词 可调 (PN,PE,PURN) (20,19,8) 事件图结构：20个节点19条弧，8个URIRef PUBC 5000 发布事件数量 可调 rpe 3% 发布事件新言属性重复率 可调 rm 2% 订阅匹配成功率 可调
第 期 冯锡炜等 发布 订阅系统语义 、 匕 匹配算法 不失一般性 , 设 尸, 个断言对应 入, ·尸个 谓词元素 , 其中 毛入 蕊 , 则 几 林, ·司 。 、 曰 二` 人一 设 尸, 兰 , 入 凡 , 。 毛入簇 , 则整个匹 配算法的贰 时间复杂度为 因为 尸 一 , 其中 为语义 订阅数据模型节 点总个数 , 为订阅条件数量 所 以 二 几 一 , 殆黯 一 ·尸·。 其 中, 入表示单个发布事件断言数与订阅条件总订 阅谓词数 比值的最大值, 从概率上考虑 , 入《 , 甚 至 入·。《 在匹配算法的实现过程中, 采用元语 句级匹配不成功标记方法, 当订阅 某次元语句匹 配不成功 , 在本次发布事件以后的匹配判断中, 不 需要再对订阅 进行元语句级匹配判定, 所 以 又由于 , , , 所 以最大空间 复杂度为 盆甜 毛 一 , 殆拭 尸 · 即匹配算法的最大时间复杂度与订阅条件谓词数量 成线性关系 发布事件时间复杂度分析 发布事件 图 是 由 , 工具直接转换为 格式, 获得 发布事件每个断言表达式, 遍历其过程也是匹配算 法的过程 , 所 以发布事件时间复杂度 为常量级 , 即 即最大 内存消耗与总节 点个数成正 比 一般情况下 , 订阅条件谓词种类 是有限的, 设 尸 又 变量类型种类 、 是有限的, 在一个 大规模的分布式系统内, 《 尸 《 。, 考虑到 订阅条件维护的效率, 语义 七 订阅数据模 型数据 结构中, 把变量约束完全相 同才共享 同一空间, 但 变、 量 约二宋, 兄、 全, 相 问 的二倩, 况` 随一习`性, 很, 大 坟、。 下兰 入, 其中 入 毛 , 称 入 为变量约束反向重复率 , 其值 越小, 表示重复率越高 当 入 时, 没有重复的 变量约束 所 以 入 一 , 注 空间复杂度分析 内存空间消耗包括 变量约束表 、 变 量类型表 、 变量索引哈希邻接表 、 谓词 表和 订阅索引哈希邻接表 , 五类表的数据存 储结构总和 因为每部分的数据元素所 占空 间大小 固定 , 与数据元素数量成正 比, 合并订阅图模式空 间复杂度为 因为 尸和 都为 固定值 , 则 二 二一 即空间复杂度与语义 认飞 订阅数据模型总节点个 数呈线性关系 凡 尸 尸 二 , 测试 与分析 语义匹配模拟 实验参数项如表 所示 表 语义匹配模拟实验参数列表 项 目参数 名称 项 目值 说明 备 注 , 尸, , , 〔 入 , , 飞〕 , , , , 个本体类 每个本体有 个属性 , 共 个属性 平均每个本体有 个同义词, 共计 个同义词 本体类 间和属性间无继承关系 订阅条件结构 个节点 条弧, 个 订阅条件数量 订阅条件谓词属性重复率 订阅条件变量类型种类 , 等于本体类数量 订阅条件变量约束反向重复率 其值越小, 表示重复率越高 同义词 事件 图结构 。个节点 条弧, 个 发 布事件 数 量 发布事件断言属性重复率 订阅匹配成功率 可 调 可 调 可 调 可 调 可 调 可 调 可调
北京科技大学学报 第35卷 ·548 实验采用Java语言作为工具语言，应用 图2(b)显示调整PUBC发布事件数量参数，统 Jena(V2.6.2)作为本体操作和逻辑判定的第三方辅 计匹配算法花费时间情况，平均匹配时间1610ms. 助开发包.本体库采用LUBM中提供的样本山，进 测试表明，PUBC对订阅匹配时间有一定影响，但 行适当的裁剪，增加同义词，推理规则只限本体同 比SUBC参数影响要小些.分析可知，匹配成功主 义词因素 要取决于匹配订阅谓词情况，一般发布事件与订阅 实验环境：Java JDK1.6.010,Windows2?003 谓词匹配都是不成功的 Server SP2,Dell PowerEdge 1900 ECM01 Server,2G 图2(c)显示调整rm订阅匹配成功率参数，统 内存，Xeon2.0 GHz CPU,数据随机生成器Test Dic- 计匹配算法花费时间情况，平均匹配时间1481.6 tionary. ms.测试表明，rm对订阅匹配时间影响较明显.若 3.1订阅匹配花费时间和订阅合并占用内存测试 要成功匹配一个订阅条件，发布事件需要成功匹配 发布事件的过程就是订阅匹配的过程，以下测 每个订阅谓词，每次需要分别实现结构级HTSI和 试的匹配时间值，包括发布事件 语义级HTVI匹配订阅谓词，后者需要的时间更长 图2给出了测试匹配算法在不同参数条件下花 些 费时间及内存的情况.图2(a)显示调整SUBC订阅 图2(d)显示调整SUBC订阅条件数量参数，订 条件数量参数，统计匹配算法花费时间情况，平均 阅合并占用内存情况，平均每个订阅条件占用内存 匹配时间1413s.测试表明，SUBC对订阅匹配时 7077字节.匹配算法使用Java语言开发实现，这个 间有一定影响.订阅条件数量的逐步增加，需要判 数据跟操作系统环境没关系.根据表1中的参数设 定的订阅谓词量在增加，匹配时间也在增加，但匹 定，每个订阅条件结构为10个节点，9条弧，5个 配时间增加的幅度逐渐减少， URIRef,估算每个订阅条件的内存 1700 2000r 1650(a) (b) 1900- 1600 1550 1800 1500 1700 1450 1600 1400 1350 1500 1300 1400 1250 1300 1200 1150 1200 1100 100050001000020000300004000050000 1100 250050007500100001250015(0017500 条件数 条件数 2750 350 (c) (d) 2500 315 2250 280 2000 245 1750 210 1500 175 140 1250 105 1000 70 750 35 500 oL 上◆ 0.50%1.00%1.50%2.00%2.50%3.00%3.50% 500100020005000100002000030000-4000050000 重复率 条件数 图2不同参数条件匹配订阅花费的平均时间和内存.(a)SUBC对匹配时间的影响：(b)PUBC对匹配时间的影响；(c)rm对匹配 时间的影响：(d)SUBC对占用内存的影响 Fig.2 Average time and memory size of matching subscribe under different arguments:(a)effect of parameter SUBC on matching time;(b)effect of parameter PUBC on matching time;(c)effect of parameter rm on matching time;(d)effect of parameter SUBC on requiring memory
5 4 8 北 京 科 技 大 学 学 报 第 卷 实验 采用 语言 作为工 具语言 , 应用 作为本体操作和逻辑判定 的第三方辅 助开发包 本体库采用 中提供的样本 `, 进 行适当的裁剪, 增加同义词, 推理规则只限本体同 义词因素 实验环境 一 , , , 内存, , 数据随机生成器 · 订阅匹配花费时间和订阅合并 占用内存测试 发布事件 的过程就是订阅匹配的过程 , 以下测 试的匹配时间值 , 包括发布事件 图 给 出了测试匹配算法在不同参数条件下花 费时间及内存的情况 图 显示调整 订阅 条件数量参数 , 统计匹配算法花费时间情况, 平均 匹配时间 测试表明, 对订阅匹配时 间有 一定影响 订阅条件数量 的逐步增加 , 需要判 定的订阅谓词量在增加, 匹配时间也在增加 , 但匹 配 时间增加的幅度逐渐减少 图 显示调整 发布事件数量参数 , 统 计匹配算法花费时间情况 , 平均匹配时间 测试表明, 对订阅匹配时间有一定影响 , 但 比 参数影响要小些 分析可知, 匹配成功主 要取决于匹配订阅谓词情况 , 一般发布事件与订阅 谓词匹配都是不成功的 图 显示调整 订阅匹配成功率参数 , 统 计匹配算法花 费时间情况 , 平均匹配时间 测试表 明, 对订阅匹配时间影响较 明显 若 要成功匹配一个订阅条件 , 发布事件需要成功匹配 每个订阅谓词, 每次需要分别实现结构级 和 语义级 匹配订阅谓词, 后者需要的时间更长 此 图 显示调整 订阅条件数量参数, 订 阅合并占用 内存情况, 平均每个订 阅条件 占用内存 字节 匹配算法使用 语言开发实现 , 这个 数据跟操作系统环境没关系 根据表 中的参数设 定 , 每个订阅条件结构为 个节点 , 条弧 , 个 , 估算每个订阅条件的内存 日斗苗匡赶匕如日 亥除亘岔碳目的已 条件数 ' 不丁— 奔 卜 泛 宜 “ 寸 , 馨 `了。。 悬 书 阵 ` ` 。 了 」 ` 一一一声 重复率 “ 准前万赫下俪不赫而南而就而该丽 条件数 “ 陈不一一一 — 一一万六 ”对 厂 ' , 卜 岑 一 子 卜 歹 一 芝 ` `, 尹 一 ` 一 叮 声 一 ” 二, 二二二一了` ` 一声 一 〔 】 〔 〕 图 不同参数条件匹配订阅花费的平均时间和内存 对匹配时间的影响 时间的影响 对 占用 内存的影响 条件数 对匹配时间的影响 。 对匹配 , 、 , 丫 价 丈
第4期 冯锡炜等：发布/订阅系统语义Web匹配算法 549 3.2与其他算法比较 S(s)=9×S(HTSC)+9×S(PDT)+10× 将匹配算法与Broker算法8！、G-ToPSS算法2 S(HTVI)+5×S(VFL)+5×S(VTL. (10) 进行比较，在系统的匹配时间和占用内存方面进行 HashSet集合和哈希表存储结构，是一次性按 测试，各类参数设定取表1中默认参数.测试结果 块分配空间，通过装填因子阈值扩充空间 如图3所示 8000,(b) ISMA iBroker G-ToPSS 10000 6 7000 9000 ■ISMA.iBroker■G-ToPSS 600 8000 7000 5000 6000 4000 5000 4000 3000 3000 2000 2000 1000 1000 100050001000020000300004000050000 25005000750010000125001500017500 条件数 条件数 600r(c) ISMA■iBroker■G-ToPSS 500 9400 100 5001000200050001000020000300004000050000 条件数 图3执行三种算法结果比较.(a)参数SUBC下三种算法匹配时间比较；(b)参数PUBC下三种算法匹配时间比较；(c)参数 SUBC下三种算法订阅条件存储空间的比较 Fig.3 Comparison of three different algorithms:(a)matching time comparison by parameter SUBC;(b)matching time compar- ison by parameter PUBC;(c)subscription condition storage space comparison by parameter SUBC 从图3(a)和(b)可知，在同等条件下，匹配算 存储空间的目的.引入标签序列(a special sequence 法的订阅匹配时间基本都优于另两个算法，随着系 of labels)标识带变量的订阅条件，便于在第一级 统规模扩大，算法的优越性更明显。分析可知，匹 HashTable中存储，但增加了格外的存储空间. 配成功的比率不大，即大部分匹配订阅都是不成功 4结论 的.匹配算法采用元语句级匹配不成功标记方法， 当订阅S某次元语句匹配不成功，在本次发布事件 通过引入本体、语义Web技术，采用谓词结构 以后的匹配判断中，不需要再对订阅S进行元语句 级HTSI匹配和语义级HTVI匹配，实现了发布事 级匹配判定，匹配不成功的大部分订阅条件只判定 件与订阅条件两级匹配.对订阅条件存储结构以及 少部分谓词条件.G-ToPSS算法采用对所有订阅元 支持语义的智能匹配算法进行了详细表述，并从算 语句级匹配后再判定是否订阅匹配成功. 法时间和空间两方面对其复杂度进行了定量和定性 图3(c)是对三种算法订阅条件存储空间的比 分析.最后，设计了实验条件，与其他算法进行了三 较.iBroker算法把用户的订阅条件规范化以符 方面比较.实验表明，本文设计的匹配算法效率较 合SPARQL文件形式(user profiles),采用两级 高，具有良好的应用前景.下阶段工作重点是实现 HashTable存储订阅条件，对不同用户相同的原子 订阅条件维护算法，同时考虑进一步优化算法，完 订阅条件，也分别存储.其第二级HashTable元素 成一致性对外接口和语义路由等方面设计 由四个数据项(ID,Next ToMatch,Value,Var)组成， 但大部分情况下都是局部为空.这使得Broker算 参考文献 法的空间存储效率不高.G-ToPSS对不带变量的相 同的原子订阅条件只存储一次，从而达到节约订阅 [1)Deng S G,Yin J W,Li Y,et al.Method of semantic web
第 期 冯锡炜等 发布 订阅系统语义 、 七 匹配算法 集合和哈希表存储结构, 是一次性按 块分配空间 , 通过装填 因子闽值扩充空间 与其他算法 比较 将匹配算法与 算法 、 一 算法 进行比较, 在系统的匹配 时间和 占用 内存方面进行 测试, 各类参数设定取表 中默认参数 测试结果 如 图 所示 , 之 宜 言 赶 因 宜盆碳目的日 条件数 条件数 卜匀﹃︸曰日八钊曰︺ 诊长国昌 条件数 图 执行三种算法结果比较 参数 下三种算法匹配时间比较 参数 下三种算法匹配时间比较 参数 下三种算法订阅条件存储空间的比较 从图 和 可知 , 在 同等条件下 , 匹配算 法 的订阅匹配时间基本都优于另两个算法 , 随着系 统规模扩大 , 算法 的优越性更 明显 分析可知 , 匹 配成功的比率不大, 即大部分匹配订阅都是不成功 的 匹配算法采用元语句级匹配不成功标记方法 , 当订阅 某次元语句匹配不成功, 在本次发布事件 以后的匹配判断中, 不需要再对订阅 进行元语句 级匹配判定 , 匹配不成功的大部分订阅条件只判定 少部分谓词条件 一 算法采用对所有订阅元 语句级匹配后再判定是否订阅匹配成功 图 是对三种算法订阅条件存储空间的比 较 算法把用户的订阅条件规范化 以符 合 文件形式 , 采用两级 存储订阅条件 , 对不同用户相 同的原子 订阅条件 , 也分别存储 其第二级 元素 由四个数据项 , , , 组成, 但大部分情况下都是局部为空 这使得 算 法的空间存储效率不高 一 对不带变量的相 同的原子订阅条件只存储一次, 从而达到节约订阅 存储空间的 目的 引入标签序列 标识带变量的订 阅条件 , 便于在第一级 中存储 , 但增加了格外的存储空间 结论 通过引入本体 、语义 技术, 采用谓词结构 级 匹配和语义级 匹配 , 实现 了发布事 件与订 阅条件两级匹配 对订 阅条件存储结构以及 支持语义的智能匹配算法进行 了详细表述 , 并从算 法时间和空间两方面对其复杂度进行了定量和定性 分析 最后, 设计 了实验条件 , 与其他算法进行了三 方面 比较 实验表 明, 本文设计的匹配算法效率较 高, 具有 良好的应用前景 下阶段工作重点是实现 订阅条件维护算法 , 同时考虑进一步优化算法, 完 成一致性对外接 口和语义路 由等方面设计 参 考 文 献 , , ,
.550 北京科技大学学报 第35卷 service discovery based on bipartite graph matching.Chin 工程与科学，2008,30(1)：99) J Comput,,2008,31(4):1364 [7]Hu XX.Publish/subscribe system for large scale dis- (邓水光，尹建伟，李莹，等.基于二分图匹配的语义Web tributed computing.J Zhejiang Univ Eng Sci,2008 服务发现方法.计算机学报，2008,31(4)：1364) 42(10):736 [2]Petrovic M,Liu H F,Jacobsen H A.G-ToPSS:fast.filter- (胡昔样.面向大规模分布式计算的发布/订阅系统.浙江大 ing of graph-based metadata /Proceedings of the 14th 学学报：工学版，2008,42(10)：736) International Conference on World Wide Web.Chiba, [8]Park M J,Chung C W.iBroker:an intelligent Broker for 2005:539 ontology based publish/subscribe systems//Proceedings [3]Muthusamy V,Liu H F,Jacobsen H A.Predictive of the 25th International Conference on Data Engineer publish/subscribe matching//Proceedings of the 4th ing.Shanghai,2009:1255 ACM International Conference on Distributed Event- [9)Gao Q S,Li L,Liu H L.Key word filter method based on Based Systems.Cambridge,2010:14 pruning on the tree representations of semantic elements [4 Chen C,Jacobsen H A,Vitenberg R.Divide and con- J Univ Sci Technol Beijing,2006,28(12):1191 quer algorithms for publish/subscribe overlay design / (高庆狮，李莉，刘宏岚。基于语义单元表示树剪枝的关键 Proceedings of the 30th International Conference on Dis- 字过滤方法.北京科技大学学报，2006,28(12)：1191) tributed Computing Systems.Genova,2010:622 [10]Chandramouli B,Phillips J M,Yang J.Value-based notifi- (5]Cheung A K Y,Jacobsen H A.Load balancing content- cation conditions in large-scale publish/subscribe systems based publish/subscribe systems.ACM Trans Comput //Proceedings of the 33rd VLDB Conference.Vienna Systs,2010,28(4):9 2007:878 6 Chen Q,Zhang Y,Zhang M.A semantics supported pub-[11 Guo Y B,Pan Z X,Heflin J.LUBM:A benchmark lish/subscribe system.Comput Eng Sci,2008,30(1):99 for OWL knowledge base systems.Web Semant,2005, (陈勤，张颖，张旻.一种支持语义的发布/订阅系统.计算机 3(2/3):158
· 北 京 科 技 大 学 学 报 第 卷 乞几 刀刃。, , 邓水光, 尹建伟, 李莹, 等 基于二分图匹配的语义 服务发现方法 计算机学报, , 」 , , 鱿 一 一 、 。成二夕 云 亡二 亡乞 们 爬 。 不夕 叭 已石 , 」 , , `叼 云 几夕 艺二 乞 们 阳” 乞 ” , 夕占 爪 占 , , , 卯 叮 尸,℃ 亡 乞。几 爬 几 葱 、 刀。 叼 如 忿 , , 二 乍 呷 。艺 勺 , , , , · 呷 、 倪夕 乞, , 陈勤, 张颖, 张星一 种支持语义的发布 订阅系统 计算机 工程与科学, , 【 匀玄几夕 几 几夕 , , 胡昔祥 面 向大规模分布式计算的发布 订 阅系统 浙江大 学学报 工学版, , , 罗 尸。 , 。夕 玩 二 乞 , 二。 、 二 乞 , , , 。、 、 咖 , 。 砂`二夕, , 高庆狮, 李莉, 刘宏岚 基于语义单元表示树剪枝的关键 字过滤方法 北京科技大学学报, , 一 , , 一 刀 叼 亡 记 二 , , , 。乙 ,
