麻亞翰

（西安工程大學(xué)，陜西 西安 710048）

工作流中檢測異常數(shù)據(jù)流的系統(tǒng)遍歷圖算法研究

麻亞翰

（西安工程大學(xué)，陜西 西安 710048）

工作流技術(shù)已經(jīng)成為管理日益復(fù)雜業(yè)務(wù)流程的標(biāo)準(zhǔn)方案。成功的業(yè)務(wù)流程管理依賴于有效的工作流模型，而工作流模型主要限制控制流和數(shù)據(jù)流方面。但是大量分析和算法的存在是用來驗(yàn)證控制流的正確性，只有相對較少的方案可用于驗(yàn)證數(shù)據(jù)流的正確性。文章針對工作流中的異常數(shù)據(jù)流，對異常數(shù)據(jù)流進(jìn)行定義和分類，并提出一種異常數(shù)據(jù)流驗(yàn)證算法—系統(tǒng)遍歷圖算法，其可以在工作流建模時避免異常數(shù)據(jù)流，有效減少企業(yè)經(jīng)濟(jì)活動的風(fēng)險(xiǎn)，幫助企業(yè)高效地作出決策。

工作流；異常數(shù)據(jù)流；控制流

工作流是一類能夠完成或者部分自動執(zhí)行的經(jīng)營過程，根據(jù)一系列過程規(guī)則，文檔、信息或任務(wù)能夠在不同的執(zhí)行者之間傳遞、執(zhí)行，實(shí)現(xiàn)組織成員間的協(xié)調(diào)工作，以達(dá)到業(yè)務(wù)的整體目標(biāo)。而業(yè)務(wù)過程中活動間的有序交互執(zhí)行最終都表現(xiàn)為加工數(shù)據(jù)間的交互，隨著業(yè)務(wù)過程的推進(jìn)，產(chǎn)生數(shù)據(jù)流。與靜態(tài)數(shù)據(jù)相比，數(shù)據(jù)流具有實(shí)時性、連續(xù)性和無限性的特點(diǎn)。目前多種圖形化的形式可用來描述工作流的控制流，包括有向圖，Petri Nets，UML Activity Diagrams和BPMN，能夠直觀看到業(yè)務(wù)流程的走向、活動、以及活動間的依賴關(guān)系，為工作流建模提供了實(shí)現(xiàn)基礎(chǔ)。然而即使工作流規(guī)格無控制流異常，由于錯誤的數(shù)據(jù)流（指異常數(shù)據(jù)流），仍然會導(dǎo)致企業(yè)業(yè)務(wù)流程產(chǎn)生異常。本文提出系統(tǒng)遍歷圖算法，采用有向圖表示工作流流程，并根據(jù)具體工作流情況增減連接器（包括AND連接器和XOR連接器），通過完整遍歷工作流中的每個實(shí)例，檢測出異常數(shù)據(jù)流且不受錯誤控制流的干擾，可以更好地協(xié)助企業(yè)管理控制以及做出科學(xué)決策，并預(yù)期給企業(yè)帶來經(jīng)濟(jì)利益。

1 系統(tǒng)遍歷圖算法

目前，工作流設(shè)計(jì)的主要方法有以下兩種：（1）用元圖或文檔驅(qū)動方法設(shè)計(jì)工作流時，數(shù)據(jù)流驅(qū)動控制流。這種模式對數(shù)據(jù)的要求已經(jīng)被正確指定，所以錯誤數(shù)據(jù)流不會出現(xiàn)。（2）先創(chuàng)建控制流結(jié)構(gòu)，即確定流程的起始和終止條件、活動數(shù)目以及活動間的關(guān)系，然后確認(rèn)控制流的正確性，隨后將數(shù)據(jù)流引入控制流。但若是活動和XOR splits存在不規(guī)范數(shù)據(jù)需求，會導(dǎo)致XOR splits產(chǎn)生錯誤分支或任務(wù)無法成功執(zhí)行。由于設(shè)計(jì)工作流的主流做法通常是第二種，即首先新建控制流結(jié)構(gòu)，然后合并數(shù)據(jù)流。如此即使控制流結(jié)構(gòu)是正確的，仍然會導(dǎo)致錯誤數(shù)據(jù)流產(chǎn)生。給出3類基本的異常數(shù)據(jù)流類型，分別為：缺失數(shù)據(jù)異常、冗余數(shù)據(jù)異常和損失數(shù)據(jù)異常。

1.1 問題描述

1.1.1 缺失數(shù)據(jù)異常

在給定工作流下，數(shù)據(jù)項(xiàng)d是活動v的輸入數(shù)據(jù)，但是數(shù)據(jù)流需求并沒有規(guī)定d作為v的輸入項(xiàng)，那么活動v就不能執(zhí)行，產(chǎn)生缺失數(shù)據(jù)異常。

1.1.2 冗余數(shù)據(jù)異常

在給定工作流下，數(shù)據(jù)項(xiàng)d1，d2，d3是活動v1的輸出數(shù)據(jù)，但是沒有后續(xù)活動使用d3且工作流輸出最終數(shù)據(jù)也不需使用d3，如此d3是冗余項(xiàng)，產(chǎn)生冗余數(shù)據(jù)異常。

1.1.3 損失數(shù)據(jù)異常

在給定工作流下，活動v2和活動v3并行執(zhí)行，二者的輸出數(shù)據(jù)均為d4，但是AND Join連接器只需要一個d4，產(chǎn)生損失數(shù)據(jù)異常。

如圖1所示，工作流模型片段中，活動A和B是連接器的一部分。A和B分別產(chǎn)生數(shù)據(jù)項(xiàng)X。然而由于A和B間沒有相關(guān)控制且AND Join只需要一個X，所以無法確定哪個活動先執(zhí)行完成，因此不能確定后續(xù)活動C。

圖1 損失數(shù)據(jù)

1.2 算法思想

該算法系統(tǒng)地穿過給定的工作流G，可以檢測出異常數(shù)據(jù)流。將G視為工作流實(shí)例的集合，遍歷工作流時不同的XOR splits特定分支路徑會導(dǎo)致產(chǎn)生不同的工作流實(shí)例。系統(tǒng)遍歷圖算法假定G不受錯誤控制流的影響，且可同時檢查G中的工作流實(shí)例。對于G中的每個活動t，會預(yù)先指定輸入數(shù)據(jù)集I（t）和輸出數(shù)據(jù)集O（t），并且在執(zhí)行該算法過程中不變化。在連接器中，只有XOR splits需要輸入數(shù)據(jù)，且已經(jīng)預(yù)指定輸入數(shù)據(jù)。其他連接器不需要輸入數(shù)據(jù)，且所有連接器（包括XOR splits）不產(chǎn)生輸出數(shù)據(jù)。純輸入是指活動和XOR splits需要其作為輸入項(xiàng)，但是由企業(yè)數(shù)據(jù)庫或者外部數(shù)據(jù)源提供的，且為了確保數(shù)據(jù)流正確性而預(yù)先初始化的數(shù)據(jù)項(xiàng)。純輸入構(gòu)成START開始節(jié)點(diǎn)的輸入數(shù)據(jù)集。類似地，工作流的最終輸出數(shù)據(jù)項(xiàng)構(gòu)成END結(jié)束節(jié)點(diǎn)的輸出數(shù)據(jù)集合。

一個節(jié)點(diǎn)即一個任務(wù)或者一個連接器。該算法執(zhí)行工作流的任意實(shí)例過程中，未被處理的節(jié)點(diǎn)存在OPEN中。OPEN中的每個節(jié)點(diǎn)存在如下數(shù)據(jù)集：

SI（n）：輸入和輸出數(shù)據(jù)項(xiàng)的累積集，在n執(zhí)行之前可以作為n的輸入數(shù)據(jù)。

SO（n）：輸入和輸出數(shù)據(jù)項(xiàng)的累積集，在n執(zhí)行之后可以作為n的輸出數(shù)據(jù)。

A（n）：節(jié)點(diǎn)n的輸入數(shù)據(jù)項(xiàng)累積集（由節(jié)點(diǎn)的輸入數(shù)據(jù)集確定）。

假定若一個數(shù)據(jù)項(xiàng)可作為節(jié)點(diǎn)的輸入項(xiàng)，那么也可以作為輸出項(xiàng)。然而活動可以修改此數(shù)據(jù)項(xiàng)的值。為了確定一個循環(huán)，在遍歷當(dāng)前工作流實(shí)例時，確保CLOSED列表中包含所有已經(jīng)遍歷到的XOR joins。如果再次遇到相同XOR joins，就確定找到一個循環(huán)。開始遍歷工作流實(shí)例前，同時初始化OPEN和CLOSED為空集。

如果OPEN中的一個節(jié)點(diǎn)沒有前任節(jié)點(diǎn)，那么這個節(jié)點(diǎn)是活躍節(jié)點(diǎn)。每次迭代，該算法檢查活躍節(jié)點(diǎn)n并更新數(shù)據(jù)集SI（n），SO（n）和A（n）。如果n無法使用所需輸入I（n），就會輸出一個缺失數(shù)據(jù)錯誤。如果遍歷工作流實(shí)例時END節(jié)點(diǎn)在結(jié)束端點(diǎn)，算法會根據(jù)冗余數(shù)據(jù)流定義決定是否產(chǎn)生冗余數(shù)據(jù)，這不是終端異常數(shù)據(jù)流，且一個工作流實(shí)例的冗余數(shù)據(jù)可以是另一個實(shí)例所需的輸入數(shù)據(jù)。如果檢測到一個循環(huán)，則對冗余數(shù)據(jù)進(jìn)行再次檢查，但是這些額外數(shù)據(jù)項(xiàng)會在實(shí)際執(zhí)行期間引起AND join處的丟失數(shù)據(jù)異常。除去循環(huán)中的數(shù)據(jù)冗余異常，工作流實(shí)例中的循環(huán)間還會相互關(guān)聯(lián)。這種情況下，該算法會繼續(xù)擴(kuò)大查詢集合OPEN中的活躍節(jié)點(diǎn)；如果沒有活躍節(jié)點(diǎn)則轉(zhuǎn)移到下一個工作實(shí)例。

若遍歷到AND join就對丟失數(shù)據(jù)進(jìn)行檢查且AND split中的兩個并行路徑里最新生成的數(shù)據(jù)項(xiàng)沒有共同的元素。如果相同的元素出現(xiàn)在這兩個集合里，其中一個數(shù)據(jù)集合就會丟失。為了實(shí)現(xiàn)嵌套工作流中的丟失數(shù)據(jù)異常檢查，需要清楚AND split-join連接器的所有相應(yīng)對。若工作流是非嵌套的（即非結(jié)構(gòu)的），需要使用AND split-join連接器的相應(yīng)對概念。文獻(xiàn)[5]中定義相應(yīng)對（cp）為G中AND連接器的一對（X，Y），其中X是split連接器，Y是join連接器，例如：（i）X有兩個出路并可在第一次就遇到Y(jié)（ii）沒有其他連接器連接Z，Z是G中Y的先驅(qū)，且G組成了相應(yīng)對（X，Z）。該算法的核心步驟如圖2所示。

圖2 系統(tǒng)遍歷圖算法

該算法的最壞情況下的時間復(fù)雜度是k×E（成正比），其中k是G中工作流實(shí)例的數(shù)量，E是G中的邊數(shù)；G中的XOR splits的數(shù)量和工作流的結(jié)構(gòu)共同決定k的值。

若工作流中存在缺失數(shù)據(jù)，該算法可以在遍歷某些實(shí)例時抓取缺失數(shù)據(jù)。若是一個無循環(huán)的工作流則可在END節(jié)點(diǎn)抓取冗余數(shù)據(jù)。一個有循環(huán)工作流中，檢測冗余數(shù)據(jù)的關(guān)鍵是遍歷到作為循環(huán)開始的XOR join連接器。

當(dāng)遇到以下錯誤情況時系統(tǒng)遍歷圖算法終止：（1）檢測到缺失數(shù)據(jù)；（2）檢測到損失數(shù)據(jù)；（3）工作流實(shí)例沒有產(chǎn)出預(yù)期輸出數(shù)據(jù)。若檢測到冗余數(shù)據(jù)，就開始遍歷下一個工作流實(shí)例。

1.3 實(shí)驗(yàn)結(jié)果

采用公司員工報(bào)告審核過程，系統(tǒng)圖遍歷算法遍歷此工作流的每個實(shí)例，實(shí)驗(yàn)結(jié)果如表2所示。工作流流程如圖3所示，每個活動的輸入以及輸出如表1所示。

圖3 員工審核報(bào)告工作流

表1 輸入輸出數(shù)據(jù)項(xiàng)

開始：節(jié)點(diǎn)1 輸入數(shù)據(jù)：D0，D8 結(jié)束：節(jié)點(diǎn)23

輸出數(shù)據(jù)：D11

XOR Split 的輸入數(shù)據(jù) 7：D6 12：D9 15：D10 18：D12 D0：郵箱號碼 D1：郵箱 D2：報(bào)告 D3：員工號D4：團(tuán)隊(duì)名稱 D5：GM回復(fù) D6：GM審閱（通過/修訂）D7：發(fā)布網(wǎng)上/簡報(bào)上 D8：DH的指南/反饋 D9：DH審閱（通過/修訂） D10：遞交給GM（是/否） D11：文章號D12：編輯審閱

表2 算法執(zhí)行結(jié)果

算法執(zhí)行：系統(tǒng)遍歷圖算法遍歷員工審核報(bào)告工作流中的每個實(shí)例后，會檢測出如表2所示的錯誤。遍歷未經(jīng)過節(jié)點(diǎn)16的工作流時，SO（15）={D0，D1，D2，D3，D4，D5，D6，D7，D8，D9，D10}，A（15）={D0，D1，D2，D3，D5，D6，D7，D8，D9，D10}，且[（SO（15）- A（15））]={14}是非空的，故是循環(huán)中的冗余數(shù)據(jù)項(xiàng)。注意，SI（1）= SO（1）=A（1）={D0，D8}，O（23）= {D11}。節(jié)點(diǎn)22是AND并行器，由于[SO（20）-SO（16）]∩[SO（21）-SO（16）]={D11}是非空的，根據(jù)算法思想，故在節(jié)點(diǎn)22處輸出一個損失數(shù)據(jù)異常。由于A（23）={ D0，D1，D2，D3，D4，D5，D6，D7，D8，D9，D12}，[SI（23）-O（23）-A（23）]={D10}是非空的。根據(jù)算法思想，故在節(jié)點(diǎn)23處輸出冗余數(shù)據(jù)異常。假定數(shù)據(jù)流需求沒有規(guī)定D0作為活動2的輸入項(xiàng)，那么2就不能執(zhí)行，算法遍歷到此處，輸出缺失數(shù)據(jù)異常。

2 結(jié)語

本文針對工作流中的異常數(shù)據(jù)流，提出系統(tǒng)遍歷圖算法并給出工作流中3類基本的異常數(shù)據(jù)流，該算法通過系統(tǒng)遍歷工作流中的每個實(shí)例，檢測出3種類型的數(shù)據(jù)流錯誤。每檢測下一個數(shù)據(jù)流問題時，可以根據(jù)前例實(shí)例對算法進(jìn)行必要的修改，這樣會使算法更加復(fù)雜但是同時也更加有效率。

[1]羅海濱，范玉順，吳澄.工作流技術(shù)綜述[J].軟件學(xué)報(bào)，2000（7）：899-907.

[2]AALST W VAN DER, HEE K VAN.Work fl ow management：models, methods and systems[M].Cambridge：Massachusetts Institute of Technology Press, 2002.

[3]BOOCH G, RUMBAUGH J, JACOBSON I.The UML user guide[J].National Aeronautics & Space Administration, 1999（4）：206-207.

[4]OMG. Business process modeling notation speci fi cation[M].USA：Business Process Model, 2006.

[5]魏曉菁，陳峰，董媛媛.數(shù)據(jù)資產(chǎn)可信度評估模型研究[J].計(jì)算機(jī)應(yīng)用，2015（S2）：170-173.

[6]BI H H, ZHAO J L. Applying propositional logic to work fl ow veri fi cation[J].Information Technology & Management：Spec Issue on Work fl ow and e-Busines, 2004（3）：293-318.

[7]LIU R, KUMAR A. An analysis and taxonomy of unstructured workflows[C].International Conference on Business Process Management, 2005（5）：268-284.

[8]SADIQ W, ORLOWSKA M E. Analyzing process models using graph reduction techniques[J].Information Systems, 2000（2）：117-134.

[9]SADIQ S, ORLOWSKA M, SADIQ W.Data flow and validation in workflow modeling[C].15th Australasian Database Conference, 2004：207-214.

[10]SUN SHERRY X，ZHAO L, NUNAMAKER J. Formulating the data flow perspective for business process management[J]. Information Systems Research, 2006（4）：374-391.

[11]CHOI Y, ZHAO J L. Matrix-based abstraction and veri fi cation for e-Business processes[J].Barcelona：Workshop on e-Business, 2002（12）：154-165.

Research on algorithm of systematic ergodic graph detecting abnormal data fl ow in work fl ow

Ma Yahan
（Xi’an Polytechnic University, Xi’an 710048, China）

Work fl ow technology has become a standard scheme of managing increasingly complex business process. Successful business work fl ow process management depends on effective work fl ow model, the main limitation of work fl ow model is control fl ow and data fl ow. However, lots of analysis and algorithm is used to verify the correctness of the control fl ow, only few scheme can be used to verify the correctness of data fl ow. This paper focuses on the abnormal data fl ow in work fl ow, de fi nes and classi fi es the exception data fl ow, and puts forward a veri fi cation algorithm：systematic ergodic graph algorithm for abnormal data fl ow, which can avoid abnormal data fl ow when work fl ow modeling, so as to effectively reduce the risk of enterprise economic activities, and help enterprises to make decisions ef fi ciently.

work fl ow; abnormal data fl ow; control fl ow

麻亞翰（1993— ），女，山西大同，碩士研究生；研究方向：數(shù)據(jù)質(zhì)量。