工作流中检测异常数据流的系统遍历图算法研究

麻亚翰

（西安工程大学，陕西 西安 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— ），女，山西大同，硕士研究生；研究方向：数据质量。