孫晉永 古天龍 聞立杰 錢俊彥 孟 瑜

1(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院 西安 710071)2(廣西可信軟件重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué)) 廣西桂林 541004)3 (清華大學(xué)軟件學(xué)院 北京 100084)

基于行為和結(jié)構(gòu)特征的相似語義工作流檢索

孫晉永1,2古天龍2聞立杰3錢俊彥2孟 瑜2

1(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院 西安 710071)2(廣西可信軟件重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué)) 廣西桂林 541004)3(清華大學(xué)軟件學(xué)院 北京 100084)

(sunjy@guet.edu.cn)

相似語義工作流檢索是語義工作流重用的首要任務(wù).現(xiàn)有的相似語義工作流檢索方法僅關(guān)注結(jié)構(gòu)特征，忽略了行為特征，影響了檢索到的相似語義工作流的整體質(zhì)量，提高了語義工作流重用的代價(jià).為此，提出一種結(jié)合行為和結(jié)構(gòu)特征的2階段相似語義工作流檢索算法.使用任務(wù)緊鄰關(guān)系集表達(dá)語義工作流的執(zhí)行行為，結(jié)合領(lǐng)域知識(shí)構(gòu)造語義工作流庫的任務(wù)緊鄰關(guān)系樹索引和數(shù)據(jù)索引.針對(duì)查詢語義工作流，先基于任務(wù)緊鄰關(guān)系樹索引和數(shù)據(jù)索引進(jìn)行過濾得到候選語義工作流集;然后使用圖匹配相似性算法對(duì)候選語義工作流集進(jìn)行驗(yàn)證，得到排序的候選語義工作流集.實(shí)驗(yàn)結(jié)果表明，較主流的語義工作流檢索算法，該方法的檢索性能有較大提升，可以為工作流重用提供更高質(zhì)量的語義工作流.

工作流重用；語義工作流；相似性檢索；結(jié)構(gòu)特征；行為特征；任務(wù)緊鄰關(guān)系樹索引

業(yè)務(wù)過程運(yùn)行的效率和質(zhì)量是現(xiàn)代企業(yè)和組織在競(jìng)爭(zhēng)中保持優(yōu)勢(shì)的關(guān)鍵因素之一.隨著業(yè)務(wù)過程管理的廣泛應(yīng)用，大量業(yè)務(wù)過程被積累下來.工作流重用是現(xiàn)代企業(yè)和組織提高業(yè)務(wù)過程管理效率的重要方式.近年來，研究者提出了基于知識(shí)的工作流管理，將基于事例推理(case-based reasoning, CBR)引入業(yè)務(wù)工作流管理中，提出了面向過程CBR(process-oriented CBR, POCBR).POCBR使用工作流案例記錄過去的工作流建模和執(zhí)行活動(dòng)的經(jīng)驗(yàn)知識(shí)，進(jìn)行推理以支持領(lǐng)域?qū)＜覄?chuàng)建、修正和重用工作流.

基于知識(shí)的工作流管理需要以領(lǐng)域知識(shí)為背景.語義工作流[1]作為一種基于知識(shí)的工作流，為工作流重用提供了更充足的語義和數(shù)據(jù)或資源信息，可以提高工作流重用的效率.當(dāng)前語義工作流重用是工作流重用研究的熱點(diǎn)之一.目前語義工作流的應(yīng)用已經(jīng)從最初的業(yè)務(wù)過程領(lǐng)域擴(kuò)展到電子商務(wù)、醫(yī)療、軟件開發(fā)和科學(xué)分析等領(lǐng)域.

從語義工作流庫中檢索出滿足需求的相似語義工作流是語義工作流重用研究的首要任務(wù).然而現(xiàn)有的相似語義工作流檢索方法僅關(guān)注結(jié)構(gòu)特征，忽略了行為特征，影響了檢索語義工作流的整體質(zhì)量，也提高了語義工作流重用的代價(jià).Bergmann等人[1]將基于圖結(jié)構(gòu)匹配的相似性方法用于語義工作流案例檢索.該方法采用遍歷語義工作流庫的方式進(jìn)行檢索，計(jì)算量較大.對(duì)于小規(guī)模工作流庫，該方法可以得出滿意的檢索性能；對(duì)于規(guī)模較大的語義工作流庫，實(shí)際上是不可行的.索引技術(shù)是解決大規(guī)模數(shù)據(jù)庫檢索問題的有效方法.但語義工作流所對(duì)應(yīng)的語義標(biāo)注有向圖是稀疏圖，其中的頻繁子圖并不多，并且頻繁子圖不能覆蓋所有的工作流模型[2].從而圖索引的檢索技術(shù)不能直接用于相似語義工作流檢索.

Forbus等人[3]提出一種用于相似性檢索的MACFAC(many are called, but few are chosen)模型.該模型由2個(gè)階段構(gòu)成：1)MAC階段使用計(jì)算量較小的非結(jié)構(gòu)匹配算法從項(xiàng)目池中過濾出候選項(xiàng)目集；2)FAC階段使用結(jié)構(gòu)匹配算法從候選項(xiàng)目集中找出最匹配的項(xiàng)目.Bergmann等人[4]提出基于MACFAC模型的語義工作流檢索方法.MAC階段基于語義工作流的語義特征和語法特征進(jìn)行過濾，F(xiàn)AC階段使用圖檢索方法選出最匹配的語義工作流.接著，Bergmann等人[5]在MAC階段建立路徑索引：Path-k(k為路徑長(zhǎng)度)進(jìn)行語義工作流過濾.Müller等人[6]使用聚類方法建立索引結(jié)構(gòu)，提出了基于排隊(duì)的檢索算法.Müller等人[7]還提出了用于POCBR的相似語義工作流檢索語言POQL，可以表達(dá)泛化的檢索項(xiàng)目.Jin等人[8]使用標(biāo)簽Petri網(wǎng)建模業(yè)務(wù)過程，提出了基于變遷路徑索引LnP(n為路徑長(zhǎng)度，與路徑索引Path-k[5]的本質(zhì)相同).以上檢索方法僅關(guān)注語義工作流或業(yè)務(wù)過程模型的結(jié)構(gòu)特征，沒有考慮它們的執(zhí)行行為，因而檢索的準(zhǔn)確性有待提高.

Zha等人[9]提出了基于標(biāo)簽Petri網(wǎng)建模的過程模型的變遷緊鄰關(guān)系(transition adjacency relation, TAR)的概念.變遷緊鄰關(guān)系集(transition adjacency relations set, TARS)是過程模型的所有TAR的集合.Jin等人[10]構(gòu)造基于標(biāo)簽Petri網(wǎng)的過程模型的行為特征索引TARIndex，提出了2階段的過程模型檢索方法.該方法關(guān)注了業(yè)務(wù)模型的執(zhí)行行為，但不能區(qū)分循環(huán)和順序結(jié)構(gòu).Weidlich等人[11]指出在過程模型檢索的一致性檢查中應(yīng)該考慮業(yè)務(wù)過程的數(shù)據(jù)和資源.由于標(biāo)簽Petri網(wǎng)不含數(shù)據(jù)流，故針對(duì)標(biāo)簽Petri網(wǎng)的檢索方法不能直接用于相似語義工作流檢索.

鑒于執(zhí)行行為等價(jià)的語義工作流，其結(jié)構(gòu)可能差異較大；而結(jié)構(gòu)相似度高的語義工作流，其執(zhí)行行為卻可能差異較大.因而在相似語義工作流檢索時(shí)，僅考慮結(jié)構(gòu)特征或行為特征中的1種，得到的檢索語義工作流結(jié)果集的整體質(zhì)量自然不高，進(jìn)而會(huì)提高語義工作流重用的代價(jià).目前，對(duì)結(jié)合結(jié)構(gòu)和行為特征的語義工作流檢索研究還很少，特別是需要考慮領(lǐng)域知識(shí)時(shí).因此本文以考慮領(lǐng)域知識(shí)的語義工作流為研究對(duì)象，引入任務(wù)緊鄰關(guān)系樹索引的概念，研究結(jié)合結(jié)構(gòu)和行為特征的2階段相似語義工作流檢索方法，以期得到整體質(zhì)量更高的檢索語義工作流結(jié)果集，為語義工作流重用提供更高質(zhì)量的候選語義工作流.

Fig. 1 The semantic workflow SW1圖1 語義工作流SW1

本文的主要貢獻(xiàn)如下：

1) 提出語義工作流的任務(wù)緊鄰關(guān)系概念，構(gòu)造了結(jié)合領(lǐng)域知識(shí)的任務(wù)緊鄰關(guān)系樹索引TARTree-Index，用于過濾得到具有指定行為特征的語義工作流；

2) 構(gòu)造了結(jié)合領(lǐng)域知識(shí)的數(shù)據(jù)索引DataIndex，用于過濾得到包含指定數(shù)據(jù)的語義工作流；

3) 提出了使用TARTreeIndex和DataIndex進(jìn)行過濾，圖匹配相似性算法進(jìn)行驗(yàn)證的2階段相似語義工作流檢索算法；

4) 通過實(shí)驗(yàn)比較得出，本文算法以可接受的代價(jià)改善了相似語義工作流的檢索性能.

1 預(yù)備知識(shí)

語義工作流最初由Bergmann等人[1]提出.為工作流的任務(wù)結(jié)點(diǎn)及其輸入輸出數(shù)據(jù)對(duì)象增加語義描述，為邊增加語義描述使得工作流同時(shí)包含控制流、數(shù)據(jù)流和語義約束，得到了語義工作流.與傳統(tǒng)工作流相比，語義工作流不但描述了業(yè)務(wù)過程中的任務(wù)及其連接關(guān)系，而且描述了任務(wù)的語義、數(shù)據(jù)或資源以及任務(wù)間連接關(guān)系的語義等重要信息.語義工作流可以表達(dá)業(yè)務(wù)工作流和科學(xué)工作流[1].

1.1 語義工作流

定義1. 語義工作流[1,12].語義工作流可以形式化為語義標(biāo)注有向圖SW=(N,E,S,τ).其中，N=NT∪NC∪ND，NT是任務(wù)節(jié)點(diǎn)的集合；NC是控制流節(jié)點(diǎn)(路由節(jié)點(diǎn))的集合；ND是數(shù)據(jù)節(jié)點(diǎn)集合.E?N×N是邊的集合；S:N∪E→Σ將節(jié)點(diǎn)或邊映射為語義描述；Σ是一個(gè)與領(lǐng)域相關(guān)的語義元數(shù)據(jù)語言.τ:N∪E→Ω將每個(gè)節(jié)點(diǎn)或邊映射為1個(gè)類型，Ω={task node,data node,control-flow node,control-flow edge,dataflow edge}.

為了表述簡(jiǎn)便，本文僅把以控制流為中心的業(yè)務(wù)工作流作為研究對(duì)象，將其表示為語義工作流，探討相似語義工作流的檢索方法.

例1. 圖1是描述意大利面食Baked Spaghetti的烹飪過程的語義工作流SW1[13].

在圖1中，控制流邊的語義描述為Control-flow，為了簡(jiǎn)潔，圖1中省略了它們.輸入數(shù)據(jù)流邊的語義描述為Input.任務(wù)節(jié)點(diǎn)以其語義描述指示的方式消耗了輸入數(shù)據(jù)對(duì)象，生成了輸出數(shù)據(jù)對(duì)象，這個(gè)過程與函數(shù)映射類似.由于任務(wù)節(jié)點(diǎn)及其輸入數(shù)據(jù)對(duì)象的語義描述均基于準(zhǔn)確的領(lǐng)域知識(shí)，故可以僅使用它和輸入數(shù)據(jù)對(duì)象的語義描述來刻畫它，而省略它的輸出數(shù)據(jù)對(duì)象.如在圖1中省略了任務(wù)節(jié)點(diǎn)的輸出數(shù)據(jù)對(duì)象.

由定義1，SW1可表示為：SW1=(N1,E1,S1,τ1)，其中，

N1=NT，1∪NC，1∪ND，1,

NT，1={t1,t2,t3,t4,t5,t6,t7,t8,t9};

NC，1={c1,c2,c3,c4,c5,c6};

ND，1={d1,d2,d3,d4,d5,d6,d7,

d8,d9,d10,d11,d12};

E1={(c1,c2),(c2,c3),(c2,t6),(c3,t1),

(c3,t2),(t1,c4),(t2,c4),(c4,t3),(t3,t4),

(t4,t5),(t5,c5),(t6,c5),(c5,t7),(t7,t8),

(t8,t9),(t9,c6),(d1,t1),(d2,t1),(d3,t1),

(d1,t2),(d2,t2),(d3,t2),(d4,t3),(d5,t3),

(d6,t3),(d7,t3),(d8,t5),(d9,t5),(d10,t6),

(d11,t6),(d12,t8)};

S1={(t1,Saute),(t2,Fry),(t3,Add),(t4,Simmer),

(t5,Place),(t6,Mix),(t7,Pour),(t8,Sprinkle),

(t9,Bake),(d1,Onion),(d2,Green_pepper),

(d3,Butter),(d4,Tomatoes),(d5,Mushrooms),

(d6,Olives),(d7,Ground_beef),(d8,Spaghetti),

(d9,Cheddar),(d10,Mushroom_soup),

(d11,Water),(d12,Parmesan),

(c1,Start),(c2,AndSplit),(c3,XORSplit),

(c4,XORJoin),(c5,AndJoin),(c6,End),

((c1,c2),Control-flow),((c2,c3),Control-flow),

((c2,t6),Control-flow),((c3,t1),Control-flow),

((c3,t2),Control-flow),((t1,c4),Control-flow),

((t2,c4),Control-flow),((c4,t3),Control-flow),

((t3,t4),Control-flow),(t4,t5),Control-flow),

((t5,c5),Control-flow),((t6,c5),Control-flow),

((c5,t7),Control-flow),((t7,t8),Control-flow),

((t8,t9),Control-flow),((t9,c6),Control-flow),

((d1,t1),Input),((d2,t1),Input),((d3,t1),Input),

((d1,t2),Input),((d2,t2),Input),((d3,t2),Input),

(d4,t3),Input),((d5,t3),Input),((d6,t3),Input),

((d7,t3),Input),((d8,t5),Input),((d9,t5),Input),

((d10,t6),Input),((d11,t6),Input),

((d12,t8),Input)};

τ1={(t1,TN),(t2,TN),(t3,TN),(t4,TN),

(t5,TN),(t6,TN),(t7,TN),(t8,TN),(t9,TN),

(d1,DN),(d2,DN),(d3,DN),(d4,DN),(d5,DN),

(d6,DN),(d7,DN),(d8,DN),(d9,DN),(d10,DN),

(d11,DN),(d12,DN),(c1,CN),(c2,CN),

(c3,CN),(c4,CN),(c5,CN),(c6,CN),

((c1,c2),CE),((c2,c3),CE),((c2,t6),CE),

((c3,t1),CE),((c3,t2),CE),((t1,c4),CE),

((t2,c4),CE),((c4,t3),CE),((t3,t4),CE),

(t4,t5),CE),((t5,c5),CE),((t6,c5),CE),

((c5,t7),CE),((t7,t8),CE),((t8,t9),CE),

((t9,c6),CE),((d1,t1),DE),((d2,t1),DE),

((d3,t1),DE),((d1,t2),DE),((d2,t2),DE),

((d3,t2),DE),((d4,t3),DE),((d5,t3),DE),

((d6,t3),DE),((d7,t3),DE),((d8,t5),DE),

((d9,t5),DE),((d10,t6),DE),

((d11,t6),DE),((d12,t8),DE)}.

τ1中的TN指代task node類型，CN指代control-flow node類型，DN指代data node類型，CE指代control-flow edge類型,DE指代dataflow edge類型.

為了限定問題的范圍，本文假定所研究的語義工作流是塊結(jié)構(gòu)化的(block-structured).當(dāng)一個(gè)語義工作流中的順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)都具有明確的開始和結(jié)束的塊表示時(shí)，稱該語義工作流是塊結(jié)構(gòu)化的[14].在下文中，如不特別指出，所提到的語義工作流均指的是塊結(jié)構(gòu)化的語義工作流.

1.2 任務(wù)緊鄰關(guān)系

借鑒標(biāo)簽Petri網(wǎng)的變遷緊鄰關(guān)系[9]，本文提出語義工作流的任務(wù)緊鄰關(guān)系(TAR)和任務(wù)緊鄰關(guān)系集(TARS)概念.

定義2. 任務(wù)緊鄰關(guān)系.假定TrS是塊結(jié)構(gòu)化的語義工作流SW=(N,E,S,τ)的所有可能軌跡的集合，a,b為SW的1個(gè)任務(wù)緊鄰關(guān)系，其中a,b∈NT，NT是任務(wù)節(jié)點(diǎn)的集合，當(dāng)且僅當(dāng)存在1個(gè)軌跡trace=t1,t2,…,tn滿足trace∈TrS，ti=a并且ti+1=b(i∈{1,2,…,n-1}).SW的所有TAR的集合記為SW的任務(wù)緊鄰關(guān)系集TARS.

與標(biāo)簽Petri網(wǎng)的變遷緊鄰關(guān)系相似，任務(wù)緊鄰關(guān)系不能區(qū)分循環(huán)和順序結(jié)構(gòu).但與路徑索引中的路徑集合[5]相比，任務(wù)緊鄰關(guān)系集TARS較好地刻畫了語義工作流的執(zhí)行行為，更能反映語義工作流的本質(zhì)，因而適合用于構(gòu)造基于行為特征的索引.由于語義工作流中存在路由節(jié)點(diǎn)，對(duì)于較復(fù)雜的語義工作流，直接根據(jù)其結(jié)構(gòu)獲取TARS一般是很困難的.Mcmillan等人[15]最先提出使用完全有限前綴來展開Petri網(wǎng)系統(tǒng).該算法有著較高的效率和比較小的展開規(guī)模，在解決Petri網(wǎng)狀態(tài)空間爆炸問題方面有比較出色的表現(xiàn).Esparza等人[16]對(duì)此進(jìn)行了改進(jìn)，提出了一種規(guī)模更小的展開方法，即完全前綴展開.更多相關(guān)概念和示例詳見文獻(xiàn)[15-18].

例2. 圖2為圖1所示的語義工作流SW1的完全前綴展開.

Fig. 2 The complete prefix unfolding of the semantic workflow SW1圖2 語義工作流SW1的完全前綴展開

易得，SW1的TARStarS1={t1,t3,t2,t3,t3,t4,t4,t5,t1,t6,t6,t1,t2,t6,t6,t2,t3,t6,t6,t3,t4,t6,t6,t4,t5,t6,t6,t5,t5,t7,t6,t7,t7,t8,t8,t9}.

2 2階段的相似語義工作流檢索方法

在進(jìn)行相似語義工作流檢索時(shí)，一般需要檢索出包含指定數(shù)據(jù)對(duì)象或滿足指定行為和結(jié)構(gòu)特征的相似語義工作流.例如可能有如下的需求或者這些需求的組合.

R1：找出包含某個(gè)任務(wù)節(jié)點(diǎn)的相似語義工作流；

R2：找出包含某個(gè)任務(wù)緊鄰關(guān)系的相似語義工作流；

R3：找出包含某些輸入數(shù)據(jù)對(duì)象或者不含另一些輸入數(shù)據(jù)對(duì)象的相似語義工作流；

R4：找出包含某個(gè)語義工作流片段的相似語義工作流.

易得，需求R1～R3是需求R4的子問題,從而本文以需求R4為主要檢索需求.針對(duì)R4，提出了基于MACFAC模型的2階段相似語義工作流檢索方法.第1階段，即MAC階段包含2步過濾操作：1)針對(duì)具體語義工作流庫，結(jié)合領(lǐng)域任務(wù)本體構(gòu)造任務(wù)緊鄰關(guān)系樹索引TARTreeIndex，結(jié)合領(lǐng)域數(shù)據(jù)本體構(gòu)造數(shù)據(jù)索引DataIndex.2)計(jì)算查詢語義工作流的TARS，基于TARTreeIndex對(duì)語義工作流庫進(jìn)行過濾獲取包含此TARS的粗選語義工作流集合；接著基于DataIndex對(duì)粗選語義工作流集合進(jìn)行過濾，獲取包含查詢語義工作流的輸入數(shù)據(jù)的精選語義工作流集合，稱之為候選語義工作流集合.第2階段，即FAC階段利用基于圖編輯距離的圖匹配[20]相似性方法對(duì)候選語義工作流集合進(jìn)行驗(yàn)證，根據(jù)相似性對(duì)候選語義工作流進(jìn)行排序.

2.1 任務(wù)緊鄰關(guān)系樹索引TARTreeIndex

在相似語義工作流檢索中，大多數(shù)情況下檢索不到執(zhí)行行為完全一致的語義工作流,這時(shí)檢索到執(zhí)行行為足夠相似的語義工作流往往是最佳選擇.在基于知識(shí)的語義工作流環(huán)境中，任務(wù)緊鄰關(guān)系之間不再僅僅是相同或者不同這2種情況，而是還可能有包含或被包含關(guān)系、既不包含或也不被包含關(guān)系.

定義3. 任務(wù)緊鄰關(guān)系的包含關(guān)系.對(duì)于語義工作流SW1=(N1,E1,S1,τ1),SW2=(N2,E2,S2,τ2)，任務(wù)節(jié)點(diǎn)a,b∈NT,1?N1,任務(wù)節(jié)點(diǎn)c,d∈NT,2?N2,tar1=a,b,tar2=c,d分別是SW1,SW2的任務(wù)緊鄰關(guān)系，C1,C2,C3,C4分別是a,b,c,d的語義描述所對(duì)應(yīng)的領(lǐng)域任務(wù)本體概念.如果C1C3且C2C4，則稱任務(wù)緊鄰關(guān)系c,d包含a,b，記為a,bc,d或tar1tar2,稱tar2為父TAR，稱tar1為子TAR.

任務(wù)緊鄰關(guān)系的包含關(guān)系也可以稱為任務(wù)緊鄰關(guān)系的泛化關(guān)系.如果tar1tar2，則稱tar2是tar1的泛化，tar1是tar2的特化.在相似語義工作流檢索中，如果包含指定TAR的語義工作流不存在，則可以根據(jù)TAR的包含關(guān)系選擇檢索包含該TAR的父TAR或子TAR的語義工作流.為了簡(jiǎn)化，本文優(yōu)先選擇父TAR.當(dāng)父TAR不存在時(shí)，選擇1個(gè)子TAR來執(zhí)行檢索.

定義4. 任務(wù)緊鄰關(guān)系的相似性.對(duì)于語義工作流SW1=(N1,E1,S1,τ1),SW2=(N2,E2,S2,τ2)，任務(wù)節(jié)點(diǎn)a,b∈NT,1?N1,任務(wù)節(jié)點(diǎn)c,d∈NT,2?N2,tar1=a,b,tar2=c,d分別是SW1,SW2的任務(wù)緊鄰關(guān)系，C1,C2,C3,C4分別是a,b,c,d的語義描述所對(duì)應(yīng)的領(lǐng)域任務(wù)本體概念.如果tar1tar2，則sim(tar1,tar2)=1;否則

sim(tar1,tar2)=(sim(C1,C3)+

sim(C2,C4))

(1)

其中，sim(Ci,Cj)的計(jì)算方法可參考文獻(xiàn)[21]，Ci,Cj(i,j∈{1,2})為領(lǐng)域任務(wù)本體概念.

定義4用于計(jì)算當(dāng)前TAR與父TAR或子TAR的相似性.只有相似性超過給定閾值的父TAR或子TAR才會(huì)被選擇替換當(dāng)前TAR.

定義5. 任務(wù)緊鄰關(guān)系樹.語義工作流的任務(wù)緊鄰關(guān)系樹TARTree是基于任務(wù)緊鄰關(guān)系的包含關(guān)系建立的一棵多叉樹.它的每個(gè)節(jié)點(diǎn)為形如(tar,tar.list)的項(xiàng)，建立了從tar到語義工作流集合的映射.其中tar為任務(wù)緊鄰關(guān)系，tar.list為含有tar的語義工作流集合.

一棵任務(wù)緊鄰關(guān)系樹TARTree的片段如圖3所示.TARTree中TAR之間的包含關(guān)系對(duì)語義工作流重用中可重用組件的選取具有參考價(jià)值.

Fig. 3 A segment of TARTree圖3 任務(wù)緊鄰關(guān)系樹的片段

定義6. 任務(wù)緊鄰關(guān)系樹索引.語義工作流的任務(wù)緊鄰關(guān)系樹索引TARTreeIndex是任務(wù)緊鄰關(guān)系樹TARTree的集合.TARTreeIndex用于獲取包含指定任務(wù)緊鄰關(guān)系集合的語義工作流的集合.

任務(wù)緊鄰關(guān)系樹索引TARTreeIndex構(gòu)造算法的偽代碼如算法1所示：

算法1. 任務(wù)緊鄰關(guān)系樹索引TARTreeIndex構(gòu)造算法.

輸入：語義工作流庫SWB、領(lǐng)域任務(wù)本體TaskOnto；

輸出：任務(wù)緊鄰關(guān)系樹索引tarTreeIndex.

①tarTreeIndex=?;

② ifSWB==? then

③ returntarTreeIndex;

④ end if

⑤ foreachSW∈SWBdo

⑥tarS=computeTARS(SW);

⑦ foreachtar∈tarSdo

⑧ iftarTreeIndex==? then

⑨t(yī)ree1.root=newnode(tar),tree1.root.list.add(SW),tarTreeIndex=tarTreeIndex∪{tree1};

⑩ elsen1=newnode(tar),n1.list.add(SW),insertTARTreeIndex(SW,n1);

函數(shù)1.insertTARTreeIndex(SW,tarNode)的偽代碼.

輸入：語義工作流SW、任務(wù)緊鄰關(guān)系樹節(jié)點(diǎn)tarNode；

輸出：任務(wù)緊鄰關(guān)系樹索引tarTreeIndex.

① foreachtree∈tarTreeIndexdo

② iftarNode.tartree.root.tarortree.root.tartarNode.tarthen

③tree2.root=tarNode,tarTreeIndex=tarTreeIndex∪{tree2};

④ else iftarNode.tar==tree.root.tarthen

⑤tree.root.list.add(tarNode.list);

⑥ else iftarNode.tartree.root.tarthen

⑦insertTARTree(tree.root,SW,tarNode);

⑧ else iftree.root.tartarNode.tarthen

⑨t(yī)arNode.childList.add(tree.root.list);

⑩ end if

函數(shù)2.insertTARTree(treeRoot,SW,tarNode)的偽代碼.

輸入：任務(wù)緊鄰關(guān)系樹的根節(jié)點(diǎn)treeRoot、語義工作流SW、任務(wù)緊鄰關(guān)系樹節(jié)點(diǎn)tarNode；

輸出：任務(wù)緊鄰關(guān)系樹索引tarTreeIndex.

① iftreeRoot.childList==? then

②treeRoot.childList.add(tarNode);

③ else foreachchild∈treeRoot.childListdo

④ ifchild.tartarNode.tarthen

⑤tarNode.childList.add(child),treeRoot.childList.add(tarNode),treeRoot.childList.delete(child);

⑥ else iftarNode.tarchild.tarthen

⑦insertTARTree(child,SW,tarNode);

⑧ elsetreeRoot.childList.add(tarNode);

⑨ end if

⑩ end if

算法1中，函數(shù)computeTARS(SW)用于計(jì)算語義工作流SW的TARStarS，函數(shù)insertTARTree-Index(SW,tarNode)用于將SW的TAR節(jié)點(diǎn)tarNode插入索引tarTreeIndex中，函數(shù)insertTARTree(treeRoot,SW,tarNode)用于將SW的TAR節(jié)點(diǎn)tarNode插入以treeRoot為根節(jié)點(diǎn)的任務(wù)緊鄰關(guān)系樹TARTree中.在構(gòu)造tarTreeIndex的過程中，tarS中的每個(gè)TAR被插入到1個(gè)TARTree中或者成為1個(gè)新TARTree的根節(jié)點(diǎn).

當(dāng)有新語義工作流加入語義工作流庫時(shí)，tarTreeIndex的更新過程與其建立過程基本一致，也是基于TAR的包含關(guān)系將新語義工作流的TARS插入到tarTreeIndex中.當(dāng)某一語義工作流從庫中刪除時(shí)，需要進(jìn)行TARTree相應(yīng)節(jié)點(diǎn)的刪除，這可以立刻執(zhí)行或當(dāng)需要?jiǎng)h除的語義工作流達(dá)到一定數(shù)量時(shí)，一次性刪除所有相應(yīng)的節(jié)點(diǎn).

基于TARTreeIndex檢索與某個(gè)查詢語義工作流相似的語義工作流，實(shí)質(zhì)上可轉(zhuǎn)化為在語義工作流庫中檢索與查詢語義工作流執(zhí)行行為相似的語義工作流.算法的偽代碼如算法2所示：

算法2. 檢索與某個(gè)查詢語義工作流相似的語義工作流.

輸入：語義工作流庫SWB、任務(wù)緊鄰關(guān)系樹索引tarTreeIndex、查詢語義工作流SWq、任務(wù)緊鄰關(guān)系的相似性閾值θ1；

輸出：與SWq的執(zhí)行行為相似的語義工作流集WFS.

①WFS=?;

②tarSq=computeTARS(SWq);

③ foreachtar∈tarSqdo

④tarNode=newnode(tar),tarNode.list.add(SW),insertTARTreeIndex(null,tarNode);

⑤ if ?treeNode∈tarTreeIndexsuch thattreeNode.tar=tarNode.tarthen

⑥WFS=WFS∪treeNode.list;

⑦ else iftarNode.parent.list≠? then

⑧WFS=WFS∪tarNode.parent.list;

⑨ else iftarNode.childList≠? then

⑩ selectchildsuch thatchild.list≠? andsim(tarNode.tar,child.tar)≥θ1,WFS=WFS∪child.list;

算法2的檢索過程與將新語義工作流入庫相似，只是在向TARTree插入相應(yīng)節(jié)點(diǎn)時(shí)，將TAR所屬的語義工作流置為null，如算法2的行④.這樣檢索得到的語義工作流集即為所求的集合，而不包含查詢語義工作流本身.在檢索后對(duì)TARTreeIndex進(jìn)行的恢復(fù)操作是刪除剛插入的TARNode節(jié)點(diǎn)，這點(diǎn)沒有體現(xiàn)在算法2中.算法2首先檢索至少包含tarSq中1個(gè)TAR的語義工作流集，然后對(duì)這些集合取并集.選擇并集的目的是為了獲取與SWq執(zhí)行行為相似的語義工作流.在第⑤行，如果已經(jīng)存在1個(gè)TAR節(jié)點(diǎn)treeNode，則treeNode.list即為所求的語義工作流集合；如果不存在這樣1個(gè)TAR節(jié)點(diǎn)，則優(yōu)先選擇父TAR節(jié)點(diǎn)的語義工作流集合，次之選擇某個(gè)子TAR節(jié)點(diǎn)的語義工作流集合.

2.2 數(shù)據(jù)索引DataIndex

定義7. 數(shù)據(jù)索引.語義工作流庫的數(shù)據(jù)索引DataIndex，結(jié)構(gòu)形如(data,data.list).其中data表示輸入數(shù)據(jù)對(duì)象，data.list表示包含data的語義工作流集.

建立該索引的算法的偽代碼如算法3所示：

算法3. 數(shù)據(jù)索引DataIndex構(gòu)造算法.

輸入：語義工作流庫SWB；

輸出：數(shù)據(jù)索引dataIndex.

①dataIndex=?；

② ifSWB==? then

③ returndataIndex;

④ end if

⑤ foreachSW∈SWBdo

⑥dataS=computeDS(SW);

⑦ foreachdata∈dataSdo

⑧ ifdata?dataIndexthen

⑨data.list.add(SW),dataIndex.add(data);

⑩ elsedata.list.add(SW);

算法3中，函數(shù)computeDS(SW)用于獲取語義工作流SW的輸入數(shù)據(jù)對(duì)象集dataS.數(shù)據(jù)索引dataIndex采用Map結(jié)構(gòu)實(shí)現(xiàn)，其更新較簡(jiǎn)單.當(dāng)檢索包含某一數(shù)據(jù)對(duì)象data的相似語義工作流集合時(shí)，可以使用data作為key在dataIndex中檢索，返回value為data.list；若不存在該data，則先在領(lǐng)域數(shù)據(jù)本體DataOnto中查找與它相似的父數(shù)據(jù)對(duì)象或子數(shù)據(jù)對(duì)象data′，然后查找包含data′的相似語義工作流集合.算法偽代碼如算法4所示：

算法4. 檢索包含某個(gè)查詢語義工作流的輸入數(shù)據(jù)對(duì)象的相似語義工作流.

輸入：數(shù)據(jù)索引dataIndex、查詢語義工作流SWq、領(lǐng)域數(shù)據(jù)本體DataOnto、數(shù)據(jù)對(duì)象的相似性閾值θ2；

輸出：包含SWq的數(shù)據(jù)對(duì)象集的相似語義工作流集合WFS.

①WFS=?;

②dataSq=computeDS(SWq);

③ foreachdata∈dataSqdo

④ ifdata∈dataIndexanddata.list≠? then

⑤WFS=WFS∪data.list;

⑥ else searchdata’sparentinDataOnto；

⑦ ifparent.list≠? then

⑧WFS=WFS∪parent.list;

⑨ else searchdata’schildListinDataOnto;

⑩ foreachchild∈childListdo

算法4中，對(duì)包含每個(gè)數(shù)據(jù)對(duì)象的語義工作流集合求并集操作是為了獲取與SWq的輸入數(shù)據(jù)對(duì)象相似的語義工作流.

2.3 2階段的相似語義工作流檢索方法

2.3.1 語義工作流過濾

對(duì)于查詢語義工作流SWq，過濾操作可以由算法2和算法4實(shí)現(xiàn).首先使用任務(wù)緊鄰關(guān)系樹索引TARTreeIndex進(jìn)行粗選過濾操作，由算法2完成，得到語義工作流集WFS1;接著使用數(shù)據(jù)對(duì)象索引DataIndex對(duì)WFS1進(jìn)行精選過濾操作，由算法4完成，得到語義工作流集WFS2,稱WFS2為候選語義工作流集.

2.3.2 候選語義工作流集驗(yàn)證

在驗(yàn)證階段，針對(duì)查詢語義工作流SWq，使用語義工作流的圖匹配相似性方法對(duì)候選語義工作流集WFS2進(jìn)行驗(yàn)證，并按與SWq的相似程度進(jìn)行排序.語義工作流的圖匹配相似性基于圖編輯距離得到，而圖編輯距離反映了語義工作流間的結(jié)構(gòu)特征差別.

定義8. 語義工作流的圖編輯距離.對(duì)于語義工作流SW1=(N1,E1,S1,τ1),SW2=(N2,E2,S2,τ2)，SW1與SW2的圖編輯距離是將SW1轉(zhuǎn)換成SW2所需的最小編輯操作數(shù).編輯操作包括節(jié)點(diǎn)和邊的替換、插入和刪除操作.

Dijkman等人[20]給出了尋求過程模型的活動(dòng)節(jié)點(diǎn)間最優(yōu)匹配的方法，基于此確定節(jié)點(diǎn)和邊的編輯操作(替換、插入和刪除)次數(shù)，進(jìn)而確定過程模型間的圖編輯距離.最后根據(jù)圖編輯距離計(jì)算圖編輯相似性，稱之為圖匹配(graph matching)相似性.然而該方法省略了過程模型中的路由節(jié)點(diǎn)，無法真實(shí)反映過程模型原有的路由情況，從而得出的圖匹配相似性也不夠準(zhǔn)確.在獲取語義工作流的圖匹配時(shí)，本文改進(jìn)使用貪婪策略的圖匹配方法[20]，保留語義工作流中的路由節(jié)點(diǎn)，基于上下文相似性優(yōu)先進(jìn)行路由節(jié)點(diǎn)的匹配.來自2個(gè)語義工作流的路由節(jié)點(diǎn)的上下文相似性越高，則它們?cè)谧顑?yōu)匹配中出現(xiàn)的概率就越高.

定義9. 路由結(jié)點(diǎn)的上下文相似性.對(duì)于語義工作流SW1=(N1,E1,S1,τ1),SW2=(N2,E2,S2,τ2)，假設(shè)路由節(jié)點(diǎn)u∈NC,1?N1,v∈NC,2?N2的直接前驅(qū)節(jié)點(diǎn)集合分別為Pu,Pv，直接后繼節(jié)點(diǎn)集合分別為Su,Sv，如果u,v為相同類型的開節(jié)點(diǎn)或閉節(jié)點(diǎn)，則u,v的上下文相似性

simC(u,v)=k1×sim(Pu,Pv)+

(2)

其中，k1+k2=1，一般取k1=k2=0.5；否則simC(u,v)=0.

式(2)中，sim(Pu,Pv),sim(Su,Sv)由KM算法[22]計(jì)算得出.在獲取語義工作流的圖匹配時(shí)，優(yōu)先進(jìn)行語義工作流的路由節(jié)點(diǎn)的匹配，基于此再進(jìn)行任務(wù)節(jié)點(diǎn)的匹配，最后得到所有節(jié)點(diǎn)間的映射.任務(wù)節(jié)點(diǎn)的相似性采用其語義描述的語義相似性.由于使用貪婪策略可能生成非最優(yōu)匹配，但在MAC階段的2步過濾操作后，這種概率大大降低.此處省略語義工作流的圖匹配算法的偽代碼.

第1階段(MAC階段)基于行為特征進(jìn)行語義工作流過濾，獲得執(zhí)行行為相似的候選語義工作流集;第2階段(FAC階段)基于結(jié)構(gòu)特征對(duì)候選語義工作流集進(jìn)行驗(yàn)證，通過選擇適當(dāng)?shù)膱D匹配相似性閾值可以獲得不但執(zhí)行行為相似而且結(jié)構(gòu)特征也相似的語義工作流集.這樣，在檢索過程中把語義工作流的行為特征和結(jié)構(gòu)特征結(jié)合起來，可以得到整體質(zhì)量更高的檢索語義工作流集，從而為語義工作流重用提供更高質(zhì)量的備選語義工作流.

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)建立

本文的所有實(shí)驗(yàn)基于如下環(huán)境：Intel CoreTMCPU 2.2 GHz，4.0 GB RAM，Windows7 64位操作系統(tǒng)，JDK1.6環(huán)境的筆記本計(jì)算機(jī).目前，基于知識(shí)的語義工作流的數(shù)據(jù)集還較少.本文的實(shí)驗(yàn)數(shù)據(jù)集選自WikiTaaable*http:wikitaaable.loria.fr的Recipe和Recipesource*http:www.recipesource.com，其中共有1 000多個(gè)意大利面食(pasta)食譜.實(shí)驗(yàn)中的領(lǐng)域任務(wù)本體TaskOnto來自WikiTaaable的Culinary actions ontology，領(lǐng)域數(shù)據(jù)對(duì)象本體DataOnto來自WikiTaaable的Food ontology.該數(shù)據(jù)集及上述本體是ICCBR會(huì)議為計(jì)算機(jī)烹飪比賽(computer cooking contest, CCC)建立的.

本文從數(shù)據(jù)集中隨機(jī)選取50個(gè)意大利面食的食譜，根據(jù)定義1將食譜的烹飪說明(cooking instructions)表示成如圖1所示的語義工作流[13]，組成規(guī)模為50的語義工作流庫.

3.2 實(shí)驗(yàn)結(jié)果對(duì)比

3.2.1 檢索的準(zhǔn)確率比較

本實(shí)驗(yàn)在語義工作流庫中隨機(jī)選取10個(gè)語義工作流并對(duì)之做一定的改動(dòng)[21]，組成大小為10的查詢語義工作流集.取任務(wù)緊鄰關(guān)系的相似性閾值θ1=0.6，數(shù)據(jù)對(duì)象的相似性閾值θ2=0.5，語義工作流的相似性閾值θ3=0.5.針對(duì)每個(gè)查詢語義工作流分別執(zhí)行檢索，繪制本文的TARTreeIndex+Data-Index算法和Path-1算法[5]的P-R(precision-recall)曲線.這里取k=1,因?yàn)殚L(zhǎng)度為1的路徑索引可以獲得較好的檢索性能[5].將TARIndex算法[10]、基于貪婪策略的圖匹配相似性算法[20]的研究方法應(yīng)用于相似語義工作流檢索，如采用忽略數(shù)據(jù)流的語義工作流的TARS、任務(wù)節(jié)點(diǎn)的語義相似性等.繪制由TARIndex算法和圖匹配算法得到的P-R曲線,如圖4所示：

Fig. 4 P-R curves of four retrieval algorithms圖4 4種檢索算法的P-R曲線

由圖4可以看出，TARTreeIndex+DataIndex算法和TARIndex算法的P-R曲線完全處于Path-1算法和圖匹配算法的P-R曲線的上方，表明引入基于行為特征的索引確實(shí)提高了相似語義工作流的檢索性能.TARIndex算法的P-R曲線在R=0.7處高于TARTreeIndex+DataIndex算法，這是由于語義工作流庫中存在了2個(gè)執(zhí)行行為足夠相似而數(shù)據(jù)集有一定差異的可接受語義工作流.TARIndex算法忽略了數(shù)據(jù)流使得在排序的檢索結(jié)果中這2個(gè)語義工作流相隔很近，而在考慮數(shù)據(jù)流的TARTree-Index+DataIndex算法的排序的檢索結(jié)果中它們相隔較遠(yuǎn).這樣使得TARIndex算法在R=0.7處準(zhǔn)確率P高于TARTreeIndex+DataIndex算法.但TARTreeIndex+DataIndex算法的P-R曲線的大部分處于TARIndex算法的P-R曲線的上方，表明結(jié)合結(jié)構(gòu)特征并引入數(shù)據(jù)對(duì)象索引從整體上提高了相似語義工作流的檢索性能.以上表明TARTree-Index+DataIndex算法的相似語義工作流檢索性能好于其他3種算法.

3.2.2 檢索時(shí)間比較

本實(shí)驗(yàn)從查詢語義工作流集中任選5個(gè)語義工作流，在語義工作流庫中語義工作流數(shù)量從10開始以步長(zhǎng)10增加到50時(shí)，分別執(zhí)行檢索.記錄每次的檢索時(shí)間，并計(jì)算每個(gè)語義工作流數(shù)量的檢索時(shí)間的平均值.將本文TARTreeIndex+DataIndex算法的檢索時(shí)間與TARIndex算法、Path-1算法、圖匹配算法的檢索時(shí)間作比較，如圖5所示：

Fig. 5 Retrieval time of four retrieval algorithms圖5 4種檢索算法的檢索時(shí)間

由圖5看出，圖匹配算法的檢索時(shí)間多于其他3種算法，原因是該算法采用遍歷語義工作流庫的方法進(jìn)行檢索，這也說明了引入索引的必要性.而TARTreeIndex+DataIndex算法的檢索時(shí)間多于TARIndex算法和Path-1算法，原因是構(gòu)造任務(wù)緊鄰關(guān)系樹索引TARTreeIndex和數(shù)據(jù)索引DataIndex也增加了檢索時(shí)間.因此，將索引TARTreeIndex和DataIndex離線構(gòu)造并存儲(chǔ)在文件中以及使用一定的緩存技術(shù)是必要的.

3.2.3 索引構(gòu)造時(shí)間比較

Fig. 6 Index construction time of three retrieval algorithms圖6 3種算法的索引構(gòu)造時(shí)間

對(duì)于本文的TARTreeIndex+DataIndex算法，在語義工作流庫中語義工作流數(shù)量從10開始以步長(zhǎng)10增加到50時(shí)，本實(shí)驗(yàn)分別記錄索引構(gòu)造時(shí)間.將本文TARTreeIndex+DataIndex算法的索引構(gòu)造時(shí)間與TARIndex算法、Path-1算法的索引構(gòu)造時(shí)間作比較，如圖6所示.

由圖6看出，TARTreeIndex+DataIndex算法的索引構(gòu)造時(shí)間多于TARIndex算法和Path-1算法，原因是構(gòu)造索引TARTreeIndex和索引DataIndex使用的時(shí)間比構(gòu)造索引TARIndex或Path-1要多.但由于索引TARTreeIndex和索引DataIndex都可以增量更新，當(dāng)有新的語義工作流加入庫中時(shí)，索引更新所用時(shí)間較少.

從以上實(shí)驗(yàn)可以看出，本文的結(jié)合行為和結(jié)構(gòu)特征的2階段相似語義工作流檢索算法在檢索性能上得到了改善，但檢索時(shí)間和索引構(gòu)造時(shí)間較長(zhǎng).其索引技術(shù)需要進(jìn)一步完善以減少檢索時(shí)間和索引構(gòu)造時(shí)間.由于語義工作流的重用一般是離線完成的，因此也可以接受這種檢索時(shí)間.從而本文提出的算法以可接受的代價(jià)改善了相似語義工作流的檢索性能.

4 總結(jié)與展望

在未來的工作中，將致力于研究更高效的語義工作流行為特征索引，以進(jìn)一步提高結(jié)合結(jié)構(gòu)和行為特征的相似語義工作流檢索算法的效率；設(shè)計(jì)以語義工作流修正代價(jià)最少為導(dǎo)向的相似語義工作流檢索方法，以期為語義工作流重用提供更適于重用的檢索語義工作流集.語義工作流庫的內(nèi)容及其組織結(jié)構(gòu)對(duì)語義工作流的檢索與修正效率有重要影響，因而語義工作流庫維護(hù)也是未來的工作之一.

[1]Bergmann R, Gil Y. Similarity assessment and efficient retrieval of semantic workflows[J]. Information Systems, 2014, 40(1): 115-127

[2]Jin Tao, Wang Jianmin, Wen Lijie. Indexing technology for business process models[J]. Computer Integrated Manufacturing Systems, 2011, 17(8): 1580-1586 (in Chinese)(金濤, 王建民, 聞立杰. 業(yè)務(wù)過程模型庫索引技術(shù)[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2011, 17(8): 1580-1586)

[3]Forbus K D, Gentner D, Law K. MACFAC: A model of similarity based retrieval[J]. Cognitive Science, 1995, 19(2): 141-205

[4]Bergmann R, Minor M, Islam S, et al. Scaling similarity-based retrieval of semantic workflows[C]Proc of ICCBR-Workshop on Process-oriented Case-Based Reasoning. Berlin: Springer, 2012: 15-24

[5]Kendall-Morwick J, Leake D. A study of two-phase retrieval for process-oriented case-based reasoning[G]Successful Case-Based Reasoning Applications-2. Berlin: Springer, 2014: 7-27

[6]Müller G, Bergmann R. A cluster-based approach to improve similarity-based retrieval for process-oriented case-based reasoning [J]. Frontiers in Artificial Intelligence & Applications, 2014, 263: 639-644

[7]Müller G, Bergmann R. POQL: A new query language for process-oriented case-based reasoning[COL]Proc of LWA 2015 Workshops: KDML, FGWM, IR, and FGDB. [2016-10-24]. http:ceur-ws.orgVol-1458F06_CRC59_Mueller.pdf

[8]Jin Tao, Wang Jianming, Wu Nianhua, et al. Efficient and accurate retrieval of business process models through indexing[G]LNCS 6426: Proc of Conf on the Move to Meaningful Internet Systems (OTM 2010). Berlin: Springer, 2010: 402-409

[9]Zha Haiping, Wang Jianmin, Wen Lijie, et al. A workflow net similarity measure based on transition adjacency relations [J]. Computers in Industry, 2010, 61(5): 463-471

[10]Jin Tao, Wang Jianmin, Wen Lijie. Efficient retrieval of similar workflow models based on behavior[G]Web Technologies and Applications. Berlin: Springer, 2012: 677-684

[11]Weidlich M, Mendling J, Weske M. Efficient consistency measurement based on behavioral profiles of process models [J]. IEEE Trans on Software Engineering, 2011, 37(3): 410-429

[12]Bergmann R, Müller G, Wittkowsky D. Workflow clustering using semantic similarity measures[G]Advances in Artificial Intelligence. Berlin: Springer, 2013: 13-24

[13]Dufour-Lussier V, Leber F, Lieber J, et al. Automatic case acquisition from texts for process-oriented case-based reasoning[J]. Information Systems, 2014, 40(1): 153-167

[14]Kiepuszewski B, Hofstede A H M, Bussler C J. On structured workflow modelling[G]Seminal Contributions to Information Systems Engineering. Berlin: Springer, 1999: 241-256

[15]Mcmillan K L, Probst D K. A technique of state space search based on unfolding[J]. Formal Methods in System Design, 1995, 6(1): 45-65

[16]Esparza J, R?mer S, Vogler W. An improvement of McMillan's unfolding algorithm[G]Tools and Algorithms for the Construction and Analysis of Systems. Berlin: Springer, 1996: 87-106

[17]Engelfriet J. Branching processes of Petri nets[J]. Acta Informatica, 1991, 28(6): 575-591

[18]Du Yuyue, Sun Ya’nan, Liu Wei. Petri nets based recognition of model deviation domains and model repair[J]. Journal of Computer Research and Development, 2016, 53(8): 1766-1780 (in Chinese)(杜玉越, 孫亞男, 劉偉. 基于Petri網(wǎng)的模型偏差域識(shí)別與模型修正[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(8): 1766-1780)

[19]Song Jinfeng, Wen Lijie, Wang Jianmin. A similarity measure for process models based on the occurrence relations of tasks[J]. Journal of Computer Research and Development, 2017, 54(4): 832-843 (in Chinese) (宋金鳳, 聞立杰, 王建民. 基于任務(wù)發(fā)生關(guān)系的流程模型相似性度量[J]. 計(jì)算機(jī)研究與發(fā)展, 2017, 54(4): 832-843)

[20]Dijkman R, Dumas M, Garcíabauelos L. Graph matching algorithms for business process model similarity search [C]Proc of the 7th Int Conf on Business Process Management. Berlin: Springer, 2009: 48-63

[21]Sun Jinyong，Gu Tianlong，Wen Lijie，et al. Similarity algorithm for semantic workflows used in process-oriented case-based reasoning[J]. Computer Integrated Manufacturing Systems 2016, 22(2): 381-394 (in Chinese)

(孫晉永, 古天龍, 聞立杰, 等. 用于面向過程的基于實(shí)例推理的語義工作流相似性算法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2016, 22(2): 381-394)

[22]Munkres J. Algorithms for the assignment and transportation problems[J]. Journal of the Society for Industrial and Applied Mathematics, 1957, 5(1): 32-38

Sun Jinyong, born in 1978. Master. Student member of CCF. His main research interests include business process management and workflow technology, knowledge representation and reasoning, etc.

Gu Tianlong, born in 1964. PhD. Professor, PhD supervisor. His main research interests include formal methods, data and knowledge engineering, software engineer-ing, etc.

Wen Lijie, born in 1977. PhD, associate professor, PhD supervisor. His main research interests include process mining, process data management, workflow for big data analysis (wenlj@tsinghua.edu.cn).

Qian Junyan, born in 1973. PhD. Professor. Senior member of CCF. His main research interests include software engineering, model checking and program verification, etc (qjy2000@gmail.com).

Meng Yu, born in 1976. PhD candidate. Associate professor. Member of CCF. Her main research interests include intelligent planning, knowledge representation and reasoning, and formal method, etc (mengyu@guet.edu.cn).

Retrieval of Similar Semantic Workflows Based on Behavioral and Structural Characteristics

Sun Jinyong1,2, Gu Tianlong2, Wen Lijie3, Qian Junyan2, and Meng Yu2

1(SchoolofComputerScienceandTechnology,XidianUniversity,Xi’an710071)2(GuangxiKeyLaboratoryofTrustedSoftware(GuilinUniversityofElectronicTechnology),Guilin,Guangxi541004)3(SchoolofSoftware,TsinghuaUniversity,Beijing100084)

Workflow reuse is an important method for modern enterprises and organizations to improve the efficiency of business process management (BPM). Semantic workflows are domain knowledge-based workflows. The retrieval of similar semantic workflows is the first step for semantic workflow reuse. Existing retrieval algorithms of similar semantic workflows only focus on semantic workflows’ structural characteristics while ignoring their behavioral characteristics, which affects the overall quality of retrieved similar semantic workflows and increases the cost of semantic workflow reuse. To address this issue, a two-phase retrieval algorithm of similar semantic workflows is put forward based on behavioral and structural characteristics. A task adjacency relations (TARs) set is used to express a semantic workflow’s behavior. A TARs trees index named TARTreeIndex and a data index named DataIndex are constructed combined with domain knowledge for the semantic workflows case base. For a given query semantic workflow, firstly, candidate semantic workflows are obtained by filtering the semantic workflows case base with the TARTreeIndex and DataIndex, then candidate semantic workflows are verified and ranked with the graph matching similarity algorithm. Experiments show that the proposed algorithm improves the retrieval performance of similar semantic workflows compared with the existing popular retrieval algorithms for similar semantic workflows, so it can provide high-quality semantic workflows for semantic workflow reuse.

workflow reuse; semantic workflow; similarity-based retrieval; structural characteristics; behavioral characteristics; task adjacency relations trees index (TARTreeIndex)

2016-10-24；

2017-02-13

國(guó)家自然科學(xué)基金項(xiàng)目(61562015,61572146,U1501252)；廣西自然科學(xué)基金項(xiàng)目(2015GXNSFDA139038,2016GXNSFDA380006)；廣西可信軟件重點(diǎn)實(shí)驗(yàn)室項(xiàng)目(KX201627)；廣西高等學(xué)校高水平創(chuàng)新團(tuán)隊(duì)及卓越學(xué)者計(jì)劃項(xiàng)目；桂林電子科技大學(xué)創(chuàng)新團(tuán)隊(duì)項(xiàng)目；廣西精密導(dǎo)航技術(shù)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室項(xiàng)目(DH201508) This work was supported by the National Natural Science Foundation of China (61562015, 61572146, U1501252), the Natural Science Foundation of Guangxi of China (2015GXNSFDA139038, 2016GXNSFDA380006), the Project of Guangxi Key Laboratory of Trusted Software (KX201627), the Project of High Level of Innovation Team of Colleges and Universities in Guangxi and Outstanding Scholars Program, and the Program for Innovative Research Team of Guilin University of Electronic Technology, and the Project of Guangxi Key Laboratory of Precision Navigation Technology and Application (DH201508).

古天龍(cctlgu@guet.edu.cn)

TP315; TP18