目前, 工作流的应用已经从最初的领域——业务过程扩展到新的领域, 如电子商务、医疗、软件开发、科学分析、信息集成甚至烹饪等.对柔性工作流的需求不断增加, 促使研究者寻求新方法来支持领域专家创建、监控和修正工作流^[1].近年来, 研究者提出基于知识的业务过程管理, 将基于事例推理(case-based reasoning, 简称CBR)引入业务过程管理中, 提出了面向过程CBR(process-oriented CBR, 简称POCBR).POCBR使用工作流案例记录过去的工作流建模、执行活动的经验知识, 进行推理以支持领域专家创建、修正和重用工作流^[1].

工作流是业务过程的自动化实现, 基于知识的工作流管理需要以领域知识为背景.语义工作流^[1]作为一种基于知识的工作流, 提供了充足的语义、数据或资源信息, 为高效率的工作流重用提供了便利.工作流重用通过复用工作流库中的相似工作流或其片段来构建新工作流, 它的两个重要任务是检索相似工作流和修正检索工作流^[2].当检索到的最相似工作流不能满足查询中的特殊需求时, 可以对它进行修正.目前, 工作流修正基本上有两种方法:手工修正和自动修正.手工修正方法对工作流建模人员的经验要求较高, 而自动修正方法需要充分利用工作流库的知识.当前, 语义工作流重用是工作流重用研究的热点之一.目前, 对相似语义工作流检索的研究已经取得了较多成果, 但对语义工作流修正方法的研究还较少.本文关注语义工作流的自动修正方法.

目前, 用于CBR案例修正的变换修正法^[3]已被引入工作流修正中.Minor等人^{[4, 5]}提出了基于修正案例的语义工作流变换修正法.该方法基于预先建立的修正知识(即修正案例)实现, 但获取工作流的修正案例是一个难题.Müller等人^[6]提出了基于工作流泛化的语义工作流变换修正法, 在引入领域本体知识前提下, 通过泛化工作流的部分元素的语义描述得到已泛化工作流, 通过特化已泛化的工作流来完成语义工作流修正.该方法需要预先泛化语义工作流库, 计算量较大.Müller等人^[2]提出了一种无需预先建立的修正知识、基于工作流stream的语义工作流复合修正方法.该方法将语义工作流库中的每个工作流分解成有意义的片段——工作流stream, 作为可重用的组件, 组成工作流stream库.检索语义工作流中的工作流stream被来自工作流stream库、最符合变更请求且足够结构相似的stream替换, 最终得到修正语义工作流.Müller等人^[7]提出了基于工作流streamlet修正算子(包括插入、删除和交换算子)的语义工作流修正方法.工作流streamlet是由处理某个数据对象的任务节点及其数据对象组成的一个工作流片段.使用修正算子链可以将检索语义工作流转换成修正语义工作流.该方法需要预先学习工作流streamlet修正算子集合, 该过程的计算量较大.以上两种方法可以得到与工作流库中的语义工作流的质量相当的修正语义工作流, 但其适用前提是在工作流库中存在符合变更请求并且足够结构相似的stream或streamlet.如果不存在这样的stream或streamlet, 则不能完成语义工作流修正.

研究者通常使用过程模型的有向标签图的拓扑结构或任务节点的连接关系来刻画过程模型结构特征.相比于结构特征, 过程模型的动态执行行为刻画了其本质特性^[8].试图通过获取过程模型所有的执行轨迹来准确地描述该业务过程模型的执行行为是行不通的.研究者一般使用行为特征来近似刻画过程模型的执行行为.目前, 已经提出了多种刻画过程模型行为特征的方法, 如变迁紧邻关系集^[9]、依赖图^[10]、主变迁序列集^[11]、因果足迹^[12]和行为轮廓^[13]、有代表性的轨迹集^[14]、任务发生关系集^[15]等.与其他方法相比, 变迁紧邻关系(transition adjacency relations, 简称TAR)集具有形式简洁、计算效率高和准确性较高等优点; 并且相比整个工作流, 工作流片段的TAR集更易于获取.

针对基于工作流stream的语义工作流修正方法^[2]的不足, 本文引入任务紧邻关系(task adjacency relations, 简称TAR)集来刻画stream的行为特征; 提出了一种基于stream行为特征的语义工作流修正方法.结合领域数据知识构建工作流stream库的锚集合数据索引ASDataIndex, 提出了stream匹配规则和stream的行为相似性方法.在此基础上, 设计了从工作流stream库中检索查询stream的匹配stream的算法。对于检索语义工作流中的每个stream, 先使用ASDataIndex和stream匹配规则过滤工作流stream库得到候选匹配stream集; 然后, 基于变更请求和stream行为相似性对候选stream集进行验证, 得到需替换的stream和最符合变更请求并与它足够行为相似的匹配stream; 接着使用匹配stream替换需替换的stream以逐步修正检索语义工作流的缺陷; 最后得到修正语义工作流.与基于stream的修正方法^[2]相比, 本文的基于行为特征的修正方法提高了基于stream修正方法的适用性和健壮性, 提高了修正语义工作流的质量, 为语义工作流重用的效率提供了更可靠的保障.

1 基本概念

为传统工作流的任务结点增加语义描述和输入/输出数据对象, 为边增加语义描述, 使工作流同时包含控制流、数据流和语义约束, 可以得到语义工作流^[1].

1.1 语义工作流

定义 1(语义工作流^[1]).语义工作流可以形式化为语义标注有向图SW=(N, E, S, τ).其中, N=N_T∪N_C∪N_D, N_T是任务节点的集合, N_C是控制流节点的集合, N_D是数据节点集合.E⊆N×N是边的集合; S:N∪E→Σ将节点或边映射为语义描述; S是一个领域相关的语义元数据语言.t:N∪E→type将每个节点或边映射为来自集合Ω的一个类型.集合Ω={task node, data node, control-flow node, control-flow edge, dataflow edge}.并记SN=N_T∪N_C为顺序节点的集合, CE⊆SN×SN为控制流边的集合, DE⊆(N_D×SN)∪(N_D×SN)为数据流边的集合.

为了表述简便, 本文仅以面向控制流的(control-flow oriented)业务工作流为研究对象; 将其形式化表示为语义工作流, 研究业务工作流的修正方法.

例1:图 1是描述意大利面食Baked spaghetti烹饪过程的语义工作流SW₁^[16].

在图 1中, 带箭头的实线表示控制流边, 为了简洁, 省略了它们的语义描述Control-flow; 带箭头的虚线表示数据流边, Input为输入数据流边的语义描述, Output为输出数据流边的语义描述.在图 1中, 分别只标注了1处输入数据流边和输出数据流边的语义描述, 省略了其余数据流边的标注.

语义工作流的任务结点以语义描述指示的方式消耗了输入数据对象, 生成了输出数据对象.在引入领域本体表示领域知识的前提下, 任务节点和数据对象节点的语义描述分别为领域任务本体和数据本体中的语义概念.在本文的烹饪工作流实例中, 以任务本体表示烹饪领域的烹饪动作知识, 以数据本体表示食材知识.故在烹饪工作流的语义标注有向图中, 数据对象节点代表了其语义描述所指示的食材, 而任务节点则代表了对这些食材采用其语义描述所指示的烹饪动作.

控制流边集CE包含了顺序节点间的一个严格偏序关系.对于顺序节点s₁, s₂∈SN, 如果s₁在s₂之前执行, 则记s₁$\prec$s₂.如图 1中, 有t₁$\prec$c₁, t₂$\prec$t₃, t₃$\prec$c₂.对s∈SN, 记s∈[s₁, s₂]当且仅当s₁$\prec$s∧s$\prec$s₂^[2].

例2:图 2是烹饪领域的任务本体和数据本体的片段.

在图 2(a)中, Cook是Bake, Simmer的泛化概念(父概念), Bake, Simmer是Cook的特化概念(子概念), 记为Bake⊑Cook, Simmer⊑Cook.特别地, 称Mix, Combine, Add为Gather的一步特化概念, 记为Mix⊑^*Gather, Combine⊑^*Gather和Add⊑^*Gather; 相反地, 称Gather为Mix, Combine, Add的一步泛化概念.假设C₁和C₂是图 2所示本体的语义概念, 则C₁和C₂的相似性为

$ sim({C_1}, {C_2}) = \left\{ {\begin{array}{*{20}{l}} {1, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{ if }}{C_1}{ \subseteq ^ * }{C_2}}\\ {\frac{{2 \cdot depth(LCS({C_1}, {C_2}))}}{{depth({C_1}) + depth({C_2})}}, {\rm{ otherwise}}} \end{array}} \right. $

(1)

其中, LCS(C₁, C₂)为C₁, C₂的最具体公共父概念, depth(C)为语义概念C在本体中的深度.如图 2(b)中, Food的深度为1, Pasta的深度为4.

如果语义工作流的每个并发、选择或循环控制流块均具有一个明确的开节点和一个闭节点, 并且这些控制流块可以嵌套但不能交错, 则该语义工作流被称为块结构化^[17]的(block-structured)语义工作流.为了限定研究范围, 本文假定所研究的语义工作流是块结构化的.

1.2 语义工作流stream

定义 2(部分语义工作流^[2]).语义工作流SW=(N, E, S, t)的一个部分语义工作流是一个块结构化的语义工作流SW'=(N', E'∪CE₊', S, τ), 其中, $ N' = {N'_{\rm{T}}} \cup {N'_{\rm{C}}} \cup {N'_{\rm{D}}} \subseteq N, {N'_{\rm{D}}} \subseteq {N_{\rm{D}}} $是SW'的数据节点, E'⊆E∩(N'×N')是连接N'中两个节点的边集合, CE₊'是为了保持顺序节点的执行关系而加入的附加边, CE₊'={(n₁, n₂)∈SN'×SN'|n₁$\prec$n₂∧¬∃n∈SN:(n₁, n)∈CE'∨(n, n₂)∈CE'∨n∈[n₁, n₂]}, S, t同定义1.

通常, 控制流节点也是部分语义工作流的一个部分.如图 3所示的部分语义工作流PW中的双线箭头, 就是为了保持顺序节点的执行关系而加入的附加边.

定义 3(生产者任务节点^[2]).在语义工作流中, 生成某个数据对象但不消耗该数据对象的任务结点被称为生产者(creator)任务节点.生产者任务节点的集合可以形式化为CT={t∈N_T|∃d∈N_D:((t, d)∈DE∧(d, t)∉DE)}.

例3:语义工作流SW₁中的工作流stream, 如图 4所示.

图 4中的被标记⊙的任务节点x, y, z均为生产者任务节点.本质上, 生产者任务节点完成了整个工作流的部分目标:它消耗多个数据对象, 生成新的数据对象.对于t₁, t₂∈N_T, 如果t₁$\prec$t₂并且t₂消耗了t₁生成的一个数据节点d, 则称t₁, t₂是数据流连接的^[2], 记为t₁$\mathop \mapsto \limits^d$t₂.如果t₁, t₂传递数据流连接的, 则记t₁$\mathop \mapsto \limits^*$t₂.

定义 4(工作流stream^[2]).语义工作流SW的一个划分为$ {S^W} = \{ S_1^W, S_2^W, ..., S_i^W, S_{i + 1}^W, ..., S_n^W\} $, 其中, $ S_i^W $为一个部分语义工作流, i∈{1, 2, ..., n-1}.如果对于∀t∈N_T都被包含在一个且仅一个$ S_i^W $中, 使得∀t∈N_T均满足传递的数据流连接, 并且每个生产者任务节点∀t∈CT都是$ S_i^W $的终节点, 则该部分工作流$ S_i^W $被称为一个工作流stream.

由定义4中, 每个生产者任务节点都是一个工作流stream的终节点, 这只是充分条件.也存在终节点不是生产者任务节点的工作流stream.如图 4中, 标号①, ②, ③, ④的部分语义工作流均为工作流stream, 分别记为S₁, S₂, S₃, S₄, 其中, S₁是终节点不是生产者任务节点的工作流stream.在不影响准确性的前提下, 为了简便, 下文在一些描述中将工作流stream简称为stream.

在使用Müller等人^[2]的方法进行语义工作流修正前, 首先需要从语义工作流库中获取stream集合.对一个语义工作流, 得到它的stream集合的方法^[2]如下:对于∀y∈CT, 首先识别出一个满足数据传递依赖的任务节点集T_y={t∈N_T|t$\mathop \mapsto \limits^* $y∧t∉CT∧¬∃x∈CT:(t$\mathop \mapsto \limits^* $x)∧¬(y$\prec $x)}∪{y}.y, T_y及其所连接的控制流和数据流边组成了一个stream.然后连接剩余节点, 组成一个工作流steam.对语义工作流库中的每个语义工作流进行分解, 保存得到的stream, 组成了工作流stream库.

定义 5(锚集合^[2]).设St为语义工作流SW的stream, St的锚集合是在它的输入/输出数据对象集合中, 被SW中不同于St的stream的任务节点生产或消耗的数据对象节点集合AS.表示为AS=AS_in∪AS_out, 其中, AS_in={d∈D_S|(∃t∈N_T\T_S∧∃t_S∈T_S):t$\mathop \mapsto \limits^d$t_S}, AS_out={d∈D_S|(∃t∈T\T_S∧∃t_S∈T_S):(t_S$\mathop \mapsto \limits^d$t)}.其中, AS_in为输入数据流对应的锚集合, 简称输入锚集合; AS_out为输出数据流对应的锚集合, 简称输出锚集合.D_S, T_S分别为St的数据对象节点集合和任务节点集合.

图 3中的被标记“∞”的数据对象节点r, s, t均为锚集合中的数据对象, 其中, {r}为S₃的输出锚集合, {r, s}为S₄的输入锚集合, 其他情况类似.两个stream是匹配的或可替换的(substitutable), 仅当它们的锚集合是匹配的.但这个替换过程还必须考虑锚集合内数据对象的处理方式, 这也是要求匹配stream必须结构或行为相似的原因.

2 基于工作流stream行为特征的语义工作流修正算法

针对Müller等人^[2]的方法的不足, 本文提出了基于stream行为特征的语义工作流修正算法.算法由两阶段构成:检索符合变更请求且行为相似的匹配stream阶段和修正检索语义工作流阶段.思路如下:当检索到的最相似工作流不能满足查询中的特殊需求时, 用户可以针对特殊需求对它进行修正.这些特殊需求被转换成对检索工作流的变更请求(change request).不满足这些特殊需求即与变更要求不一致.设SW为检索到的最相似且不满足特殊需求的语义工作流, 为了对SW进行修正, 首先把SW分解成stream集合WS₀.然后, 对于WS₀中的每个stream St_q, 从工作流stream库中过滤出St_q的匹配stream集RS.接着, 基于变更请求和stream行为相似性确定St_q是否需要被替换; 如果需要, 则从RS中检索出最符合变更请求并与St_q足够行为相似的匹配stream St_m.最后, 使用每个St_m替换SW中的对应St_q以修正检索工作流的缺陷.其中, 检索最符合变更请求且与St_q足够行为相似的匹配stream是本文的修正算法的重点, 也是核心工作.

2.1 检索与变更请求一致且行为相似的匹配工作流stream

为了便于阐述匹配stream检索算法, 先介绍stream匹配的相关概念.本节中的查询stream即为待修正的检索语义工作流中的stream.

2.1.1 工作流stream匹配规则

在检索与查询stream匹配的stream时, 有时不能得到锚集合完全一致的stream.这会使检索语义工作流无法修正.这时可以考虑锚集合相近的stream.因而本文定义了泛化stream和stream匹配的概念.

定义 6(泛化工作流stream).工作流stream St₁=(N₁, E₁, S₁, τ)是工作流stream St₂=(N₂, E₂, S₂, τ)的泛化工作流stream, 当且仅当存在St₁, St₂间的图同构I:N₂→N₁, 使得对于∀n₂∈N₂, S₂(n₂)⊑^*S₁(I(n₂)); 同时, 称St₂是St₁的特化, 记作St₂⊑^*St₁.

工作流stream对应的有向图规模较小, 本文对Ullmann算法^[18]进行改造来检验stream间的图同构关系.参考第1.1节的本体中语义概念间的泛化/特化关系, 本文规定:如果St₂⊑^*St₁, 则在语义工作流修正中可以使用St₂替换St₁.例如, 假设在领域任务本体中有Sprinkle⊑^*Garnish, Bake⊑^*Cook; 在领域数据本体中有Parmesan⊑^* Cheese.如图 5为stream S₅, S₁为图 4中SW₁的stream, 则由定义6可得, S₁⊑^*S₅.

定义7(语义描述集合的泛化).设集合SD₁, SD₂为数据对象节点的语义描述的集合, 如果SD₁, SD₂间存在一一对应的映射f, 并且对∀a∈SD₁, ∃b=f(a)∈SD₂满足b⊑^*a, 则称SD₁是SD₂的一步泛化, SD₂是SD₁的一步特化, 记为SD₂⊑^*SD₁.

例如, 假设领域数据本体中有Beef⊑^*Meat, Onion⊑^*Vegetable, 若有数据对象语义描述的集合B₁={Beef, Onion}, B₂={Meat, Vegetable}, 则B₂是B₁的一步泛化, B₁⊑^*B₂.

基于定义7, 定义基于锚集合匹配的工作流stream匹配概念.

定义 8(工作流stream匹配).设查询工作流stream St_q的锚集合为AS₁, 某工作流stream St₂的锚集合为AS₂. A₁, A₂分别为St_q, St₂的输入锚集合对应的语义描述集合, B₁, B₂分别为St_q, St₂的输出锚集合对应的语义描述集合:

1) 精确匹配:如果A₁=A₂, 并且B₁=B₂, 即A₁与A₂, B₁与B₂完全等价, 则称St₂与St_q精确匹配;

2) 泛化匹配:如果St₂⊑^*St_q, 即St₂比St_q更具体, 则称St₂与St_q泛化匹配;

3) 嵌入匹配:如果A₂⊑^*A₁, 并且B₂⊑^*B₁, 即A₂比A₁, B₂比B₁更具体, 则称St₂与St_q嵌入匹配;

4) 完全匹配:如果A₁⊑^*A₂, 并且B₁⊑^*B₂, 即A₁比A₂, B₁比B₂更具体, 则称St₂与St_q完全匹配;

5) 潜在匹配:如果A₂⊑^*A₁∨A₁⊑^*A₂, B₂⊑^*B₁∨B₁⊑^*B₂均不成立, 但∃a₁∈A₁∧∃a₂∈A₂∧a₁⊑^*a₂或者∃b₁∈B₁∧∃b₂∈B₂∧b₁⊑^*b₂成立, 则称St₂与St_q潜在匹配;

6) 不匹配:如果A₁, A₂, B₁, B₂不满足以上5种情况, 则称St₂与St_q不匹配.

假如某查询stream的要求是输入锚集合包含语义描述为Meat的数据对象节点, 由于Pork⊑^*Meat, Beef⊑^* Meat, 故输入锚集合包含语义描述为Pork或Beef的数据对象节点的stream都应该准确地满足该要求.这是嵌入匹配类型.又如, 假设在领域任务本体中有Stir⊑^*Mix, 在领域数据本体中有Soft_water⊑^*Water, Cream_mushroom_soup⊑^*Mushroom_soup, Mushroom_soup⊑^*Soup.如图 6所示为stream S₆, S₃为图 4中SW₁的stream, 则由定义8可得S₆, S₃是嵌入匹配.又由于S₆⊑^*S₃, 同时S₆, S₃也是泛化匹配.

基于定义8, 本文规定工作流stream匹配规则如下:先选择精确匹配的stream, 然后选择泛化匹配的stream, 再选择嵌入匹配的stream, 最后选择完全匹配的stream.但由于完全匹配、潜在匹配和不匹配类型不能给出准确满足要求的stream, 故本文只研究精确匹配、泛化匹配和嵌入匹配这3种类型.

2.1.2 基于锚集合数据索引和匹配规则获取候选匹配工作流stream

建立索引是提高检索效率的有效方法, 本节构建stream库的锚集合数据索引ASDataIndex.使用ASDataIndex并结合stream匹配规则, 可以从stream库中检索到与查询stream匹配的候选匹配stream集合.该过程被称为过滤^[19]匹配stream.

定义 9(锚集合数据索引).工作流stream库的锚集合数据索引ASDataIndex是一个倒排表.它的每个节点为形如(data, data.list_in, data.list_out)的项, 建立了从data到工作流stream集合的映射.其中, data为锚集合的数据对象, data.list_in为输入锚集合中包含data的工作流stream集合.data.list_out为输出锚集合中包含data的工作流stream集合.

索引ASDataIndex的结构如图 7所示.

对于较大规模的语义工作流库, 为了提高检索效率, 可以不存储(data, data.list_in, data.list_out), 而是将(data.hashcode, data.list_in.pointer, data.list_out.pointer)存储到B+树中^[20].其中, data.hashcode是data的哈希值, 用作B+树的键值; data.list_in.pointer, data.list_out.pointer分别指向data.list_in, data.list_out的位置.

索引ASDataIndex的建立过程如算法1所示.

算法1.锚集合数据索引ASDataIndex构造算法.

输入:工作流stream库STB.

输出:锚集合数据索引asDataIndex.

construct(STB)

1.  asDataIndex=Ø

2.  if STB==Ø then

3.    return asDataIndex;

4.  end if

5.  for each St∈STB do

6.    AS_in=computeAS_in(St), AS_out=computeAS_out(St);

7.    for each ad∈AS_in do

8.      if asDataIndex does not contain ad then  /^*如果asDataIndex不含ad, 则加入ad^*/

9.        asDataIndex.add(ad);

10.      end if

11.      ad.list_in.add(St);

12.    end for

13.    for each ad∈AS_out do

14.      if asDataIndex does not contain ad then

15.        asDataIndex.add(ad);

16.      end if

17.      ad.list_out.add(St);

18.  end for

19. end for

20. return asDataIndex.

在算法1中，第4行的函数computeAS_in(St), computeAS_out(St)分别用于获取stream St的输入锚和输出锚集合.易得, 只要索引ASDataIndex包含数据对象ad, 则ad.list_in和ad.list_out其中之一必不为空.算法1把stream库中stream的锚集合中的每个数据对象ad都加入到索引ASDataIndex中, 这一过程的时间复杂度为O(nm).由于可能存在重复的数据对象, 故空间复杂度的上限为O(nm), 其中, n=|STB|, m为stream库中的stream的最大数据对象数量.

针对某个查询stream, 为了获得与之匹配的stream, 设计结合索引ASDataIndex和stream匹配规则的算法对stream库进行过滤.过滤算法的流程如图 8所示.

针对查询stream St_q, 对于stream库中的每一个stream St, 首先, 借助锚集合数据索引过滤算法依次检查St与St_q是否满足精确匹配、泛化匹配或嵌入匹配条件.如果满足当前的匹配条件, 则保存St并停止针对St的检查; 否则, 检查St与St_q之间是否满足下一种匹配条件.若3种匹配条件均不满足, 则丢弃St, 继续检查下一个stream.算法伪代码如算法2所示.

算法2.结合锚集合数据索引和stream匹配规则的匹配stream过滤算法.

输入:stream库STB, 查询stream St_q, 索引asDataIndex, 数据本体DataOnto.

输出:与St_q满足精确、泛化或嵌入匹配的stream集合RS.

computeMSt(STB, St_q, asDataIndex, DataOnto)

1.  RS=Ø

2.  A₁=computeAS_in(St_q), B₁=computeAS_out(St_q);   /^*获取St_q的输入锚集合A₁, 输出锚集合B₁ ^*/

3.  get the set RS of streams accurately matching St_q in STB with asDataIndex, A₁, B₁;   /^*精确匹配^*/

4.  if RS≠Ø then return RS;

5.  else get RS of streams generalized matching St_q in STB with asDataIndex, A₁, B₁;   /^*泛化匹配^*/

6.    if RS≠Ø then return RS;

7.    else  /^*嵌入匹配^*/

8.      RS_in=STB, RS_out=STB;

9.      for each ad∈A₁ do

10.        S₁=computeSpecCSet(ad, IN);

11.        RS_in=RS_in∩(S₁∪{ad.list_in});

12.      end for

13.      if RS_in==Ø then return Ø;

14.      else

15.        for each ad∈B₁ do

16.          S₂=computeSpecCSet(ad, OUT);

17.          RS_out=RS_out∩(S₂∪{ad.list_out});

18.        end for

19.      end if

20.      RS=RS_in∩RS_out, return RS;

21.    end if

22.  end if

函数computeSpecCSet(ad, flag):

输入:数据对象ad, 数据对象本体DataOnto.

输出:包含ad的一步特化数据对象的stream集合SP.

1.  SP=Ø;

2.  Sub=oneStepSpecCSet(ad, DataOnto);   /^*在DataOnto中获取ad的一步特化数据对象集^*/

3.  if flag=IN then

4.    for each ad₁∈Sub do

5.      if asDataIndex contains ad₁ and ad₁.list_in≠Ø then SP=SP∪ad₁.list_in;

6.      else continue;

7.      end if

8.    end for

9.  else  /^* flag=OUT ^*/

10.    for each ad₁∈Sub do

11.      if asDataIndex contains ad₁ and ad₁.list_out≠Ø then SP=SP∪ad₁.list_out;

12.        SP=SP∪ad₁.list_out;

13.      else continue;

14.      end if

15.    end for

16. end if

17. retrun SP.

算法2的第3行基于asDataIndex, 通过计算St_q的输入/输出锚集合中每个数据对象ad对应的stream集合ad.list_in或ad.list_out的交集来计算与St_q精确匹配的stream集合.第5行用于检索与St_q泛化匹配的stream集合; 先基于asDataIndex从STB中过滤出包含St_q的输入/输出锚集合中每个数据对象或其一步特化数据对象的候选stream集, 然后再使用改编的Ullmann算法^[18]来检验候选stream与St_q是否满足泛化匹配.第7行~第20行用于检索与St_q嵌入匹配的stream集.其中, RS_in是包含输入锚集合的每个数据对象或其一步特化数据对象的stream集, RS_out是包含输出锚集合的每个数据对象或其一步特化数据对象的stream集.第10行、第16行的函数computeSpecCSet(ad, flag)用于获取包含ad的一步特化数据对象的stream集合.flag∈{IN, OUT}用于指明ad来自输入锚集合还是输出锚集合.执行算法2, 可以得到与St_q精确匹配、泛化匹配或嵌入匹配的stream集合.

函数computeSpecCSet(ad, flag)的主要计算是第2行的求一步特化数据对象集操作和第5行的求并集操作.由于数据对象本体DataOnto形式上为一棵多叉树, 第2行操作的最差情况是需要遍历这棵树.假设DataOnto对应的多叉树有k个节点, 则第2行的时间复杂度的上限为O(k), 空间复杂度的上限为O(k).假设ad的一步特化概念的个数为p, 则第5行求并集的时间复杂度为O(p).因为p≤k, 从而函数computeSpecCSet(ad, flag)的时间复杂度为O(k).对于STB中的每一个stream和查询stream St_q的每一个数据对象, 算法2都可能执行1次函数computeSpecCSet(ad, flag).假设stream库STB规模为n, 即n=|STB|, 而查询stream St_q的最大数据对象的数量为m, 则算法2的时间复杂度的上限为O(nmk), 空间复杂度的上限为O(nmk).

2.1.3 工作流stream的行为相似性

执行算法2可能得到多个候选匹配stream.为了确定最佳匹配stream, 根据它们与查询stream的相似性对其进行排序是一个好方法.本文使用stream的行为相似性来表示stream之间的相似性.使用行为特征——任务紧邻关系集合^[9]刻画stream的执行行为, 然后, 基于两个stream的任务紧邻关系集合的相似性来表示stream之间的行为相似性.

定义 10(任务紧邻关系).假定TrS是语义工作流SW=(N, E, S, τ)的所有可能轨迹的集合, 〈a, b〉为SW的一个任务紧邻关系TAR, 其中, a, b∈N_T, N_T是任务节点的集合, 当且仅当存在一个轨迹trace=〈t₁, t₂, t₃, ..., t_i, t_i+1, ..., t_n〉(i∈{1, 2, ..., n-1})满足trace∈TrS, t_i=a并且t_i+1=b.SW的所有TAR的集合记为SW的任务紧邻关系集(TAR set, 简称TARS).

由于stream的图规模较小, 可以通过遍历它的语义标注有向图来得到它的TAR集.例如在图 3中, stream S₁, S₂, S₃, S₄的TAR集均可容易得到.

定义 11(任务紧邻关系的相似性).对于语义工作流SW₁=(N₁, E₁, S₁, τ), SW₂=(N₂, E₂, S₂, τ), 任务节点a, b∈N_T1; c, d∈N_T2, 其中, N_T1, N_T2分别是SW₁, SW₂的任务节点集合; tar₁=〈a, b〉, tar₂=〈c, d〉分别是SW₁, SW₂的任务紧邻关系; C₁, C₂, C₃, C₄分别是a, b, c, d的语义描述对应于领域任务本体的语义概念.如果C₁⊑C₃, C₂⊑C₄, 则sim(tar₁, tar₂)=1;否则,

$ sim\left( {ta{r_1}, ta{r_2}} \right) = \left( {sim\left( {{C_1}, {C_3}} \right) + sim\left( {{C_2}, {C_4}} \right)} \right)/2 $

(2)

其中, sim(C₁, C₃), sim(C₂, C₄)的计算方法如公式(1).

定义11中的C₁⊑C₃, C₂⊑C₄, 而不是C₁⊑^*C₃, C₂⊑^*C₄是为了获取更多的行为相似stream.根据领域专家意见, 设定了任务紧邻关系的相似性阈值cut-off₁.当sim(tar₁, tar₂)≥cut-off₁时, 可认为tar₁, tar₂相同, 否则不相同.在计算过程模型中功能(function)的标签间的语义相似性时, 使用了同义词相似性方法, 通过实验获得最优相似性阈值0.89.在引入领域知识的前提下, 语义概念之间的相关性增大, 本文参照的最优相似性阈值确定方法并做调整, 取相似性阈值cut-off₁=0.8.

定义12(工作流stream的行为相似性).对于工作流stream St₁, St₂, 如果St₂, St₁是精确匹配或者泛化匹配, 即St₂⊆^*St₁, 则St₁, St₂的行为相似性sim_b(St₁, St₂)=1.如果St₂, St₁是嵌入匹配, 设St₁的TAR集为TS₁, St₂的TAR集为TS₂, 则St₁, St₂的行为相似性为

$ si{m_{\rm{b}}}\left( {S{t_1}, S{t_2}} \right) = |T{S_1} \cap T{S_2}\left| / \right|T{S_1} \cup T{S_2}| $

(3)

否则, sim_b(St₁, St₂)=0.

由于为TAR的相似性设定了相似性阈值, 故TS₁∩TS₂和TS₁∪TS₂容易得到.计算sim_b(St₁, St₂)还需要获得TS₁, TS₂的最优匹配, 该问题可以使用Kuhn-Munkres^[22]算法来解决.由于St₁, St₂的图规模较小, 故获取最优匹配的计算量也较小.

2.1.4 结合变更请求检索相似的匹配工作流stream

在语义工作流重用过程中, 查询中的特殊需求一般为在检索工作流中需要包含或不需要包含的任务或数据对象集合.它可被转换成对检索工作流的变更要求, 即需要在检索工作流中删除或加入的任务节点和数据对象节点的集合.变更请求可形式化表示为chReq=Delete_T∧Delete_D∧Add_T∧Add_D.其中, Delete_T=(¬task₁∧¬task₂∧…∧¬task_m), Delete_D=(¬data₁∧¬data₂∧…∧¬data_q), $ Ad{d_{\rm{T}}} = (tas{k'_1} \wedge tas{k'_2} \wedge ... \wedge tas{k'_n}), Ad{d_{\rm{D}}} = (dat{a'_1} \wedge dat{a'_2} \wedge ... \wedge dat{a'_p}). $task₁, task₂, …, task_m是需要删除的任务节点; $ tas{k'_1}, tas{k'_2}, ..., tas{k'_n} $是需要加入的任务节点; data₁, data₂, …, data_q是需要删除的数据对象; $ dat{a'_1}, dat{a'_2}, ..., dat{a'_p} $是需要加入的数据对象.

目前, 本修正算法仅支持需要在检索工作流中删除或加入数据对象的变更请求, 即chReq=Delete_D∧Add_D.为计算方便, 分别把Delete_D, Add_D转化为需要删除的数据对象集DE、需要加入的数据对象集AD.

对于检索语义工作流中的每个查询stream, 由算法2可以获得与之匹配的stream集.本节基于变更请求和stream行为相似性对匹配stream集验证, 从中检索出需替换的stream和最符合变更请求chReq并与该stream足够行为相似的匹配stream.“需替换的查询stream”是指该stream包含当前chReq的DE中的数据对象, 或者针对该stream可以检索到最符合变更请求chReq且与它足够行为相似的匹配stream.“最符合变更请求chReq”指的是stream不包含chReq的DE中的数据对象, 并且包含chReq的AD中的数据对象的数量最多.

检索算法的流程如图 9所示.

检索算法首先分解检索语义工作流SW, 得到查询stream集合WS₀; 然后, 对于WS₀中的每个查询stream St_q, 使用算法2过滤stream库得到匹配stream集WS₁; 接着, 从WS₀和WS₁中检索出需替换的stream St_a和最符合变更请求chReq并与St_a足够行为相似的匹配stream St_m, 组成序偶〈St_a, St_m〉; 最后, 得到序偶〈St_a, St_m〉的集合.

检索算法的伪代码如算法3所示.

算法3.获取检索语义工作流中的需替换的stream及其对应的匹配stream.

输入:工作流stream库STB, 检索语义工作流SW, 索引asDataIndex, 变更请求chReq.

输出:SW中的需替换的stream及其对应的匹配stream映射的集合map_s.

1.  WS₀=Ø, WS₁=Ø, map_s=Ø;

2.  WS₀=computeST(SW), DE=getDE(chReq), AD=getAD(chReq);

3.  while WS₀≠Ø do

4.    select a stream St_q∈WS₀;

5.    WS₁=computeMSt(STB, St_q, asDataIndex, DataOnto);   /^*运行算法2, 获取St_q的匹配stream集合^*/

6.    WS₂=Ø;

7.    for each St₁∈WS₁ do

8.      D₁=computeDS(St₁);   /^*获取St₁的数据对象集^*/

9.      if D₁∩DE== then WS₂=WS₂∪{St₁};

10.      end if

11.    end for

12.    priQueue=getPriQueue(WS₂, AD);

13.    while priQueue≠Ø do

14.      St₂=priQueue.get(0), D₂=computeDS(St_q), D₃=computeDS(St₂);

15.      if D₂∩DE≠Ø∨D₃∩AD≠Ø and sim_b(St_q, St₂)≥cut-off₂ then map_s.put(〈St_q, St₂〉), WS₀=WS₀–St_q, AD=AD-D₃, break;

16.      priQueue.pop();

17.      end if

18.    end while

19.    WS₀=WS₀–St_q,

20. end while

21. return map_s.

在算法3中, 第2行的函数computeST(SW), getDE(chReq), getAD(chReq)分别用于获取SW的stream集合、chReq的DE和AD.第7行~第11行用于获取与DE不矛盾的stream集合WS₂.第12行用于将WS₂中的stream按包含AD中的数据对象的数量从多到少进行排序, 得到优先队列priQueue.第13行~第18行用于获取需替换的stream St_q与priQueue中的对应stream的映射集合map_s.第15行保证只有至少包含DE中的一个数据对象的查询stream St_q或AD中一个数据对象的匹配stream St₂才进行行为相似性检验.此时与St_q行为相似性足够高的St₂被用于替换St_q, 目的是保证替换操作对修正SW的缺陷有促进作用.在stream替换阶段, 可以根据map_s中的匹配stream对, 使用匹配stream来替换对应的查询stream.如果运行算法3不能得到这样的映射集合map_s, 则可以适当放松约束条件获取一个可以接受的映射集合map_s, 如减小行为相似性阈值cut-off₂或放松变更请求的约束等.

算法3的主要计算在于第5行的匹配stream检索、第12行的优先队列生成和第13行~第18行的获取映射集合map_s.其中, 第5行的时间复杂度的上限为O(nmk), 第13行的时间复杂度的上限为O(n²), 第13行~第18行的时间复杂度的上限为O(n).设检索语义工作流SW中的stream数量为q, 则算法3的时间复杂度为O(qnmk+qn²+qn)=O(qnmk+qn²).由于第5行的空间复杂度的上限为O(nmk)、第12行的空间复杂度的上限O(n)、第13行~第18行的空间复杂度为O(n), 故算法3的空间复杂度的上限为O(qnmk).

为了便于评判检索到的查询stream与匹配stream之间是否行为相似, 本文设置了一个行为相似性阈值cut-off₂.当查询stream与匹配的stream行为相似性大于cut-off₂时, 认为二者行为相似, 否则不相似.提出:可以根据相似性算法的检索性能指标之一——F测度(F-measure)的最优值确定相似性阈值的最优值, 指出, 基于有代表性轨迹的集合的行为相似性算法的最优相似性阈值在0.70附近.与不同, 本文在已知两个stream匹配的前提下确定cut-off₂的数值.根据实际情况并参考领域专家意见, 本文设定行为相似性阈值cut-off₂≥0.55.暂取cut-off₂=0.55, 可以根据实际情况对其进行调整.例如, 认为行为相似性为0.65的一对匹配stream、行为相似性为0.85的一对匹配stream均为行为相似, 但是两对匹配stream的相似程度不同.使用类似的方法确定匹配stream间的结构相似性阈值cut-off₃≥0.55, 暂取cut-off₃=0.55.

2.2 修正检索语义工作流

执行算法3, 可以得到查询stream St_a与其对应匹配stream St_m的映射集合map_s.之后, 检索语义工作流SW的修正由每个St_m替换对应的St_a完成.具体操作:先在SW中删除St_a，然后将St_m插入SW中.插入St_m的位置是SW中St_a的最后一个顺序节点处^[2].

假定图 4中的语义工作流SW₁是基于结构或行为相似性检索到的最相似语义工作流, 变更请求chReq=¬Cheddar∧Vermicelli, 故SW₁的stream S₄是缺陷stream.即需要在SW₁中需要删除语义描述为Cheddar的数据对象节点, 加入语义描述为Vermicelli的数据对象节点.现在对SW₁进行修正.Müller等人^[2]的方法完成修正的前提是在stream库中存在与查询stream结构相似的stream.假设目前在stream库中存在与S₄结构相似性最高的stream St₄, 如图 10所示.由Müller等人^[2]的方法得S₄, St₄的结构相似性sim_s(S₄, St₄)=0.26 < cut-off₃, 从而Müller等人^[2]的方法在相似的匹配stream检索时会忽略St₄, 所以会检索不到合适的匹配stream, 因而无法修正工作流SW₁.

由定义8得, stream St₄, S₄是嵌入匹配类型, 故可以用St₄替换S₄.为了简化, 此处以语义描述指代所属的任务节点.由得, S₄的任务紧邻关系集TS₁={〈Simmer, Place〉, 〈Place, Pour〉}, St₄的任务紧邻关系集TS₂={〈Stew, Place〉, 〈Boil, Place〉, 〈Place, Top〉}.由定义11得, sim(〈Simmer, Place〉, 〈Stew, Place〉)=0.85 > 0.8, 故可视〈Simmer, Place〉与〈Stew, Place〉等价.从而由定义12得, TS₁∩TS₂={〈Simmer, Place〉, 〈Place, Pour〉}, TS₁∪TS₂={〈Simmer, Place〉, 〈Boil, Place〉, 〈Place, Top〉}.所以sim_b(S₄, St₄)=|TS₁∩TS₂|/|TS₁∪TS₂|=0.67 > cut-off₂, 故当前的St₄是行为相似的匹配stream.于是, 可以使用St₄替换S₄, 对语义工作流SW₁进行修正.

使用stream St₄替换stream S₄的过程如下:

1) 从语义工作流SW₁中删除工作流stream S₄(如图 11所示);

2) 将工作流stream St₄加入到语义工作流SW₁中(如图 12所示).

使用行为最相似的匹配stream替换查询stream可能带来检索语义工作流结构上的改变, 但只要修正后的语义工作流能够满足数据流连接的约束, 均认为修正是可行的.传统工作流的任务节点不包含输入/输出数据对象, 无法根据输入/输出数据对象对它们进行分解得到stream集合.这样, 对不能直接复用的传统工作流无法进行修正.在工作流变更时, 为了能够重用现有的传统工作流中有意义的片段——stream, 对它们进行分解, 得到stream库是必要的.可用的分解方法有结合人类专家的经验确定分割点进行分解、依据有意义的最小控制流块进行分解等.这样, 在重用传统工作流时, 可以通过检索行为相似的stream来修正检索工作流.

3 实验与结果分析 3.1 实验设计

本文的实验基于如下环境:Intel Core(TM) CPU2.2 GHz, 8.0GB RAM, Windows7 64位操作系统, JDK1.6环境的计算机.目前, 专用的语义工作流的实验数据集还较少.本文的实验数据集选自WikiTaaable(http://wikitaaable.loria.fr)的Recipe和Recipesource(http://www.recipesource.com), 其中, 共有1 000多个意大利面食(pasta)食谱.实验中的领域任务本体TaskOnto来自WikiTaaable的Culinary actions本体, 有100个左右节点; 领域数据对象本体DataOnto来自WikiTaaable的Food本体, 有200个左右节点.WikiTaaable, Recipesource及其中的本体是ICCBR会议为计算机烹饪比赛(computer cooking contest, 简称CCC)建立的.

本文从意大利面食食谱数据集中选取100个食谱^[14], 根据定义1, 将食谱的烹饪说明(cooking instruction)表示成如图 1的语义工作流^{[1, 14]}, 组成规模为100的烹饪语义工作流库SWB₀.本实验从SWB₀中随机选取50个语义工作流, 组成测试语义工作流库SWB₁.SWB₁的基本结构特征见表 1.

同时, 请3位烹饪专家组成领域专家组来评价检索到的匹配工作流stream和修正语义工作流的质量.

3.2 本文的修正方法与基于结构特征的修正方法比较

首先开展实验1:比较基于行为特征的stream相似性方法和基于结构特征的stream相似性方法^[2]对相似的匹配stream的检索性能.从SWB₁任选10个工作流组成测试工作流集QSW₁.对每一个测试语义工作流, 任选它的一个stream记录下来.对该stream做如下改变:如果为顺序结构, 则为它的某个任务节点添加包含一个语义描述相似的任务节点的并发和选择分支; 如果为并发或选择结构, 则任选其中的两个任务节点, 将其改变为语义描述相似的任务节点.这样共记录10个stream并组成检索stream集QST, 同时可以得到20个改变后的语义工作流.这20个改变后的语义工作流与余下的40个语义工作流一起组成规模为60的新语义工作流库SWB₂.对SWB₂中的每个语义工作流进行分解, 共得到215个stream, 组成工作流stream库STB₁.

针对检索stream集QST, 在STB₁中检索相似的匹配stream.具体如下:对于QST中的每个stream(称为查询stream), 首先, 在STB₁中检索匹配stream集合MS₁; 然后, 在MS₁中检索行为特征相似的stream.

对于定义12的stream的行为相似性, 采用基于相似性的检索(similarity based retrieval)方法执行上述检索过程.记录每个查询stream的检索结果集中的相似匹配stream的数量, 并对所有查询stream的相似匹配stream的数量求均值.使用基于结构特征的修正方法^[2]中的stream相似性方法执行相同的检索过程.检索结果见表 2.

由表 2得, 基于行为特征的相似方法的检索结果集中, 匹配stream的平均数量高于基于结构特征的相似方法^[2].这是因为基于stream行为特征的方法不但检索出了结构相似的匹配stream, 而且检索出了行为相似的匹配stream.这样可以在结构相似的匹配stream不存在的情况下, 选用行为相似的匹配stream来完成语义工作流修正任务.

同时, 请领域专家组评价检索到的stream的质量, 分别绘制两种相似性方法对应的P-R曲线.如图 13所示.P-R(precision-recall)曲线是评价检索系统的整体检索性能的方法之一.整体检索性能较好的检索系统的P-R曲线全部或绝大部分处于整体检索性能一般的检索系统.

由图 13可以得出, 基于行为特征相似性的匹配stream检索方法的P-R曲线整体处于基于结构特征相似性的检索方法^[2]的P-R曲线上方.这说明基于行为特征相似性的匹配stream检索方法的检索性能要好于基于结构特征相似性的检索方法^[2].

接下来开展实验2:检验本文的基于stream行为特征的工作流修正方法是否执行了变更要求.从测试工作流集SWB₂中任选10个工作流组成测试工作流集QSW₂.针对QSW₂中的每个测试工作流TW_i, 首先删除1~2个数据对象节点, 并将其1~2个数据对象节点的语义描述替换为相似的语义描述, 得到语义工作流TW_i'.在SWB₂中, 用TW_i'替换TW_i.然后, 对QSW₂中的每个测试工作流TW_i, 使用语义工作流的结构相似性方法^[1]在SWB₂中检索一个相似的语义工作流RW_i, 以使得可以通过执行一组删除(delete)和加入(add)数据对象节点的操作将RW_i转变为TW_i^[2].这些删除和加入操作由手工得出, 作为工作流修正时的变更要求chReq.然后, 对于每个语义工作流RW_i及其对应的chReq, 执行本文的工作流修正算法, 可以得到10个修正语义工作流.分析10个修正语义工作流, 并请领域专家组对它们进行评价.结果表明, 测试语义工作流均完成了修正过程, 并且与变更请求chReq基本一致.

最后开展实验3:比较基于stream行为特征的修正方法和基于stream结构特征的修正方法^[2]得到的修正工作流的质量.将实验2中的测试工作流集QSW₂中的每个测试工作流TW_i与其对应的修正语义工作流RW_i混在一起, 这样得到包含20个工作流的工作流集合RWS.在事先不告诉每个工作流是测试工作流还是修正语义工作流的前提下, 请3位领域专家使用Likert评分方法(1~5分)对RWS中的每个工作流的合理性进行评分.然后将每个测试工作流TW_i和对应修正语义工作流RW_i组成一对(TW_i, RW_i), 这样共得到30对.比较每对(TW_i, RW_i)中两个工作流评分的高低.同时, 对测试工作流集QSW₂中的每个语义工作流TW_i及其对应的变更要求chReq, 使用基于stream结构特征的修正方法^[2]执行工作流修正操作.对得到的修正工作流进行相同的评分过程.结果如图 14所示.

图 14的横坐标分别为在语义工作流修正结束后, 领域专家对修正语义工作流的评分高于、低于对测试语义工作流的评分和领域专家对二者的评分相等这3种情况; 纵坐标为3种情况对应的修正工作流数量.

由图 14可以看出, 对于基于stream行为特征的修正方法, 共有15个修正语义工作流的评分不低于(高于或等于)测试工作流, 比例为50%.而基于stream结构特征的修正方法^[2]共有13个修正语义工作流的评分不低于(高于或等于)测试工作流, 比例约为43%.基于行为特征的修正方法的评分比基于结构特征的修正方法高出7%.从而与基于stream结构特征的修正方法^[2]相比, 基于stream行为特征的修正方法得到了整体质量更好的修正语义工作流集合.

从以上3个实验可得:与基于stream结构特征的修正方法^[2]相比, 基于stream行为特征的修正方法提高了修正算法的适应能力, 较好地改善了修正语义工作流的质量.同时也可以得出:基于stream结构特征的修正方法^[2]更适合于科学工作流的修正, 而本文的基于stream行为特征的修正方法更适合于业务工作流的修正.

4 总结与展望

本文提出了一种不需要修正知识、基于工作流stream行为特征的语义工作流修正算法, 该算法适用的前提是具有一定规模的语义工作流库.该算法以引入领域知识的块结构化语义工作流为研究对象, 使用任务紧邻关系集刻画工作流stream的执行行为.结合领域数据知识构造了工作流stream库的锚集合数据索引ASDataIndex.针对检索语义工作流中的每个查询工作流stream, 先基于ASDataIndex和工作流stream匹配规则对工作流stream库进行过滤, 得到候选匹配工作流stream集; 然后, 基于行为特征的相似性和变更请求对候选工作流stream集进行验证, 得到与当前变更请求一致程度最高和相似的匹配工作流stream; 接着, 使用检索到的匹配工作流stream替换原查询工作流stream, 逐步对检索语义工作流进行修正; 最后得到修正语义工作流.实验结果表明, 与基于工作流stream结构特征的修正算法^[2]相比, 本文的基于工作流stream行为特征的语义工作流修正算法可以在不存在结构足够相似的匹配工作流stream的情况下, 使用行为足够相似的匹配工作流stream完成检索工作流修正; 并且得到了整体质量更好的修正语义工作流集.本文的工作流修正算法为业务过程管理人员为适应新业务需求而进行的工作流变更提供了具有较好参考价值的修正语义工作流, 对提高实际业务工作流管理中的工作流重用的效率和质量有较大帮助.

在未来的工作中, 将致力于将本文的工作流修正算法应用于其他领域的业务流程修正; 研究更高效的工作流stream的行为特征刻画方法和优化的修正操作, 进一步提高基于行为特征的语义工作流修正算法的效率.