工作流中檢測異常數據流的系統遍歷圖算法研究

麻亞翰

（西安工程大學，陜西 西安 710048）

工作流中檢測異常數據流的系統遍歷圖算法研究

麻亞翰

（西安工程大學，陜西 西安 710048）

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

工作流；異常數據流；控制流

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

1 系統遍歷圖算法

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

1.1 問題描述

1.1.1 缺失數據異常

在給定工作流下，數據項d是活動v的輸入數據，但是數據流需求并沒有規定d作為v的輸入項，那么活動v就不能執行，產生缺失數據異常。

1.1.2 冗余數據異常

在給定工作流下，數據項d1，d2，d3是活動v1的輸出數據，但是沒有后續活動使用d3且工作流輸出最終數據也不需使用d3，如此d3是冗余項，產生冗余數據異常。

1.1.3 損失數據異常

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

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

圖1 損失數據

1.2 算法思想

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

一個節點即一個任務或者一個連接器。該算法執行工作流的任意實例過程中，未被處理的節點存在OPEN中。OPEN中的每個節點存在如下數據集：

SI（n）：輸入和輸出數據項的累積集，在n執行之前可以作為n的輸入數據。

SO（n）：輸入和輸出數據項的累積集，在n執行之后可以作為n的輸出數據。

A（n）：節點n的輸入數據項累積集（由節點的輸入數據集確定）。

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

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

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

圖2 系統遍歷圖算法

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

若工作流中存在缺失數據，該算法可以在遍歷某些實例時抓取缺失數據。若是一個無循環的工作流則可在END節點抓取冗余數據。一個有循環工作流中，檢測冗余數據的關鍵是遍歷到作為循環開始的XOR join連接器。

當遇到以下錯誤情況時系統遍歷圖算法終止：（1）檢測到缺失數據；（2）檢測到損失數據；（3）工作流實例沒有產出預期輸出數據。若檢測到冗余數據，就開始遍歷下一個工作流實例。

1.3 實驗結果

采用公司員工報告審核過程，系統圖遍歷算法遍歷此工作流的每個實例，實驗結果如表2所示。工作流流程如圖3所示，每個活動的輸入以及輸出如表1所示。

圖3 員工審核報告工作流

表1 輸入輸出數據項

開始：節點1 輸入數據：D0，D8 結束：節點23

輸出數據：D11

XOR Split 的輸入數據 7：D6 12：D9 15：D10 18：D12 D0：郵箱號碼 D1：郵箱 D2：報告 D3：員工號D4：團隊名稱 D5：GM回復 D6：GM審閱（通過/修訂）D7：發布網上/簡報上 D8：DH的指南/反饋 D9：DH審閱（通過/修訂） D10：遞交給GM（是/否） D11：文章號D12：編輯審閱

表2 算法執行結果

算法執行：系統遍歷圖算法遍歷員工審核報告工作流中的每個實例后，會檢測出如表2所示的錯誤。遍歷未經過節點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}是非空的，故是循環中的冗余數據項。注意，SI（1）= SO（1）=A（1）={D0，D8}，O（23）= {D11}。節點22是AND并行器，由于[SO（20）-SO（16）]∩[SO（21）-SO（16）]={D11}是非空的，根據算法思想，故在節點22處輸出一個損失數據異常。由于A（23）={ D0，D1，D2，D3，D4，D5，D6，D7，D8，D9，D12}，[SI（23）-O（23）-A（23）]={D10}是非空的。根據算法思想，故在節點23處輸出冗余數據異常。假定數據流需求沒有規定D0作為活動2的輸入項，那么2就不能執行，算法遍歷到此處，輸出缺失數據異常。

2 結語

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

[1]羅海濱，范玉順，吳澄.工作流技術綜述[J].軟件學報，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]魏曉菁，陳峰，董媛媛.數據資產可信度評估模型研究[J].計算機應用，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— ），女，山西大同，碩士研究生；研究方向：數據質量。