第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% 订阅匹配成功率 可调第 期 冯锡炜等 发布 订阅系统语义 、 匕 匹配算法 不失一般性 , 设 尸, 个断言对应 入, ·尸个 谓词元素 , 其中 毛入 蕊 , 则 几 林, ·司 。 、 曰 二` 人一 设 尸, 兰 , 入 凡 , 。 毛入簇 , 则整个匹 配算法的贰 时间复杂度为 因为 尸 一 , 其中 为语义 订阅数据模型节 点总个数 , 为订阅条件数量 所 以 二 几 一 , 殆黯 一 ·尸·。 其 中, 入表示单个发布事件断言数与订阅条件总订 阅谓词数 比值的最大值, 从概率上考虑 , 入《 , 甚 至 入·。《 在匹配算法的实现过程中, 采用元语 句级匹配不成功标记方法, 当订阅 某次元语句匹 配不成功 , 在本次发布事件以后的匹配判断中, 不 需要再对订阅 进行元语句级匹配判定, 所 以 又由于 , , , 所 以最大空间 复杂度为 盆甜 毛 一 , 殆拭 尸 · 即匹配算法的最大时间复杂度与订阅条件谓词数量 成线性关系 发布事件时间复杂度分析 发布事件 图 是 由 , 工具直接转换为 格式, 获得 发布事件每个断言表达式, 遍历其过程也是匹配算 法的过程 , 所 以发布事件时间复杂度 为常量级 , 即 即最大 内存消耗与总节 点个数成正 比 一般情况下 , 订阅条件谓词种类 是有限的, 设 尸 又 变量类型种类 、 是有限的, 在一个 大规模的分布式系统内, 《 尸 《 。, 考虑到 订阅条件维护的效率, 语义 七 订阅数据模 型数据 结构中, 把变量约束完全相 同才共享 同一空间, 但 变、 量 约二宋, 兄、 全, 相 问 的二倩, 况` 随一习`性, 很, 大 坟、。 下兰 入, 其中 入 毛 , 称 入 为变量约束反向重复率 , 其值 越小, 表示重复率越高 当 入 时, 没有重复的 变量约束 所 以 入 一 , 注 空间复杂度分析 内存空间消耗包括 变量约束表 、 变 量类型表 、 变量索引哈希邻接表 、 谓词 表和 订阅索引哈希邻接表 , 五类表的数据存 储结构总和 因为每部分的数据元素所 占空 间大小 固定 , 与数据元素数量成正 比, 合并订阅图模式空 间复杂度为 因为 尸和 都为 固定值 , 则 二 二一 即空间复杂度与语义 认飞 订阅数据模型总节点个 数呈线性关系 凡 尸 尸 二 , 测试 与分析 语义匹配模拟 实验参数项如表 所示 表 语义匹配模拟实验参数列表 项 目参数 名称 项 目值 说明 备 注 , 尸, , , 〔 入 , , 飞〕 , , , , 个本体类 每个本体有 个属性 , 共 个属性 平均每个本体有 个同义词, 共计 个同义词 本体类 间和属性间无继承关系 订阅条件结构 个节点 条弧, 个 订阅条件数量 订阅条件谓词属性重复率 订阅条件变量类型种类 , 等于本体类数量 订阅条件变量约束反向重复率 其值越小, 表示重复率越高 同义词 事件 图结构 。个节点 条弧, 个 发 布事件 数 量 发布事件断言属性重复率 订阅匹配成功率 可 调 可 调 可 调 可 调 可 调 可 调 可调