Fang Zhao,Dongming Xiang,Guanjun Liu,Changjun Jiang and Honghao Zhu

1School of Electronics and Information Engineering,Tongji University,Shanghai,201804,China

2School of Information Science and Technology,Zhejiang Sci-Tech University,Hangzhou,310018,China

3School of Computer Engineering,Bengbu University,Bengbu,233030,China

ABSTRACT Workflow system has become a standard solution for managing a complex business process.How to guarantee its correctness is a key requirement.Many methods only focus on the control-flow verification,while they neglect the modeling and checking of data-flows.Although some studies are presented to repair the data-flow errors,they do not consider the effect of delete operations or weak circulation relations on the repairing results.What’s more,repairing some data-flow errors may bring in new errors.In order to solve these problems,we use workflow net with data(WFD-net)systems to model and analyze a workflow system.Based on weak behavioral relations and order relations in a WFD-net system,we formalize four kinds of data-flow errors.After then,we reveal the relations between these errors and organize them into a hierarchy.Furthermore,we propose some new methods to repair data-flow errors in a WFD-net system based on system requirements and repair strategies.Finally,a case study of campus-card recharging shows the applicability of our methods,and a group of experiments show their advantages and effectiveness.

KEYWORDS Data-flow errors;WFD-net;weak behavioral relations;system requirements

Nomenclature

NSet of Positive Integers

∈or/∈

RDRedundant Data

MDMissing Data

LDLost Data

INDInconsistent Data

1 Introduction

A business process is considered as “the specific ordering of work activities across time and place,with a beginning,an end,and clearly identified input and output” [1].As an information technology of process automation,workflow systems have become a standard solution for managing complex business process models,such as loan approval management [2],supply chain management [3],and knowledge management [4].In other words,workflow systems can be used to automate,manage,and optimize different kinds of business processes.In general,the design of a workflow system needs to describe control-/data-flows,and then detect their errors [5].A successful workflow system depends on error-free modeling and analyzing methods.Therefore,it is necessary to keep the correctness of control-/data-flows in a workflow system.Control-flows mainly focus on the partial orders of business activities,while data-flows mainly involve data operations (e.g.,read,write,and delete) and guard functions [6–8].

There are many modeling methods that can be used to describe workflow systems,such as Business Process Modeling Notation (BPMN) [9],Business Process Execution Language(BPEL) [10],Event-Driven Process Chains (EPCs) [11],UML Activity Diagrams [11],and Workflow Net with Data (WFD-net) [12].Compared with these methods,WFD-nets are much suitable to describe and analyze control-/data-flows due to their data labeling functions and guards.

In order to guarantee the correctness of workflow systems,some methods are developed to detect and repair errors.Unfortunately,most of them only focus on the verifications of controlflows while ignoring the checking of data-flows.In fact,data-flows play an important role in workflow design.This is because routing constraints in a workflow are usually based on data operations and guard functions.Moreover,data-flow errors (e.g.,redundant data,missing data,lost data,and inconsistent data) may arise even if control-flows are correct [5,13].Once a workflow model suffers from missing data,it may need high costs to repair unexpected process interruptions.To repair data-flow errors in workflow systems,many studies are done.Awad et al.[9] presented a method to repair missing data in BPMN.After then,Song et al.[10] provided some methods to preserve data-flow correctness in BPEL.Later on,Sharma et al.[14] presented a method to repair data-flow errors in workflows.However,these methods do not consider data-flow errors caused by delete operations,and their workflow models are usually simple (e.g.,no loop structures).In order to remove a kind of data-flow error,they may bring in another one.Therefore,they need multiple attempts to repair these errors.What’s worse,they may get an incorrect workflow model.

In this paper,we use WFD-net systems to analyze the correctness of control-/data-flows in workflow systems.It is assumed that our control-flows in WFD-net systems are sound (i.e.,no deadlocks [9,15,16] or livelocks [17–19]),without taking data operations into consideration[12,20,21].The aim of this paper is to detect and repair four kinds of data-flow errors (i.e.,redundant data,missing data,lost data,and inconsistent data) in WFD-net systems.

The contributions of this paper are given as follows:

1) Based on weak behavioral relations (i.e.,weak sequence relation,weak exclusiveness relation,weak circulation relation,and weak concurrency relation) and order relation,we formalize four kinds of data-flow errors in WFD-net systems.

2) We reveal the relations between different kinds of data-flow errors,and further organize them into a hierarchy,which can contribute to correctly repairing data-flow errors without repeated work.

3) We present some methods to repair data-flow errors in WFD-net systems according to several system requirements and repair strategies.

The rest of this paper is organized as follows.In Section 2,we present some related work about data-flow errors.Then,we introduce workflow system modeling and a motivation example in Section 3.In Section 4,we formalize data-flow errors in WFD-net systems,and provide some new methods to repair them.In Section 5,a case study of campus-card recharging is conducted.In Section 6,we do a group of experiments to show the effectiveness of our methods.Finally,conclusion and future work are given in Section 7.

2 Related Work

2.1 Detecting Methods for Data-Flow Errors

There have been many methods to detect data-flow errors.Sun et al.[2] provided three basic types of data-flow errors in UML activity diagram,namely missing data,conflicting data,and redundant data.Sundari et al.[22] presented a graph traversal algorithm called GT to detect data-flow errors in workflows.It systematically traversed every workflow route to detect errors like redundant data,missing data,and lost data.Based on the work provided in [2],Sun et al.[23]analyzed the dependencies among different transitions based on the input and output data of activities in a workflow model.Meda et al.[24] provided missing data,inconsistent data,lost data,and redundant data.They also presented a graph traversal algorithm to detect the data-flow errors in unstructured and nested workflows.Sidorova et al.[25] defined the may/must-soundness of a WFD-net system.Haddar et al.[26] provided a data-centric method to manage business processes.Dolean et al.[27] presented a survey of researches on modeling data-flows of business processes,and pointed out that the control-flows cannot be executed without data operations.Kabbaj et al.[5] pointed out that the role of data in a workflow is very important because routing constraints are closely related to data elements.Therefore,a workflow easily leads to an interruption once it contains data-flow errors.In order to solve this problem,they provided a method to detect redundant data,missing data,and lost data (or conflict data).Xiang et al.[6]proposed Petri Net with Data Operations (PN-DO),such as read,write,and delete operations.They formalized redundant data,missing data,lost data,and inconsistent data.Dramski [28]presented missing data in event logs and gave some ways to make some data recovery.Trcka et al.[29,30] put forward six kinds of data-flow errors in WFD-nets,namely missing data,strongly redundant data,weakly redundant data,strongly lost data,weakly lost data,and inconsistent data.von Stackelberg et al.[31] proposed a method to detect strongly redundant data,weakly redundant data,missing data,strongly lost data,weakly lost data,and inconsistent data in BPMN 2.0.Song et al.[32] utilized supervised learning algorithms to predict data-flow errors in an unseen BPEL process.Moreover,they provided an empirical study on data-flow errors in BPEL processes.Mülle et al.[33] considered that the correctness of data-flows in BPMN 2.0 is a challenge.As for the above studies,they did not consider the relations between different kinds of data-flow errors.

2.2 Repairing Methods for Data-Flow Errors

There are many studies on repairing data-flow errors.Awad et al.[9] presented a method to repair missing data.Song et al.[10] provided preserve data-flow correctness in process adaptation.They proposed three criteria to make the process free of missing data,redundant data,and lost data.Technically,they assumed that each activity has 0/1 output.Later on,Sharma et al.[14]presented methods to repair redundant data,missing data,lost data,and inconsistent data in workflows.After then,Jovanovikj et al.[34] provided methods to compare and merge two different models with different data operations.The methods are activity inserted,activity deletion,data object creation,data object to read,data object updated,and data object deletion.These methods can contribute to providing possible ways for the designer to repair data-flow errors in a WFDnet system.As mentioned above,these studies did not consider data-flow errors caused by delete operations,and their workflow models are usually without loop structures.What’s more,repairing some kinds of data-flow errors may bring in new data-flow errors.In order to solve these problems,we propose some new methods to repair different kinds of data-flow errors according to several system requirements in this paper.

3 Preliminaries

3.1 Workflow System Modeling

A Petri net is a 3-tupleN=(P,T,F),wherePis a limited non-empty set of places,Tis a limited non-empty set of transitions,P∩T=?,andF?(P×T)∪(T×P)is the flow relationship inN[35–38].A Petri net system is a netN=(P,T,F)with an initial markingM0.A marking function of a net is a mappingM:P→N1,where N1is the set of non-negative integers.Given a nodex∈P∪T,its pre-set and post-set are denoted by·x={y|(y∈P∪T)∧(y,x)∈F} andx·={y|(y∈P∪T)∧(x,y)∈F},respectively [39].Ifxis a source place,then·x=?;Ifxis a sink place,thenx·=?.Given a set of nodesX?P∪T,andx∈X,its pre-set and post-set are denoted by·X={Y|(Y?P∪T)∧(y∈Y)∧(y,x)∈F} andX·={Y|(Y?P∪T)∧(y∈Y)∧(x,y)∈F},respectively.For the example of Fig.1,ifX={t2,t3},then we have·X=·t2∪·t3={p2,p3},andX·=t·2∪t·3={p3,p4}.Furthermore,we usekto denote the pre-set number for convenience.Therefore,we have(·)1t3=·t3={p3},(·)3t3=·(·(·t3))={p2},(·)5t3=·(·(·(·(·t3))))={p1,p4},and(·)1t3∪(·)3t3∪(·)5t3={p1,p2,p3,p4},wherek=1,3,5,respectively.With respect to the set of post-sets,it is defined analogously.A Petri netNis called a safe Petri net if all places are marked at most one token.In this paper,our Petri nets are safe by default.

Figure 1:A WFD-net system of campus-card recharging

We model the control-flows of a workflow system as a dedicated class of Petri nets,thereby modeling activities by transitions,conditions by places,and cases as tokens.A typical workflow has a well-defined starting point,and a well-defined ending point imposes syntactic restrictions on Petri nets that result in the following definition of a workflow net (WF-net).

Definition 1 (WF-net[40,41]) A Petri netN=(P,T,F)is a workflow net (WF-net) if it satisfies:

(1) There is only one source placepI∈Pand only one sink placepo∈PinN;and

(2) ?x∈P∪T:(pI,x)∈F*and(x,po)∈F*,whereF*is the reflexive-transitive closure ofF.

A WF-net is used as a basic description of control-flows in a workflow process.A WF-net system(N,M0)is a WF-net extended with an initial markingM0.In order to model the actual process (including control-/data-flows) of workflow systems,we define a workflow net with data(WFD-net) [29,30] as follows.

Definition 2(WFD-net[29,30]) A Petri netND=(P,T,F,D,Guard,R,W,De,Gd)is a WF-net with data (WFD-net) iff:

(1)(P,T,F)is a WF-net;

(2)Dis a set of data items;

(3)Guardis a set of guards overD;

(4)R:T→2Dis a labeling function of reading data;

(5)W:T→2Dis a labeling function of writing data;

(6)De:T→2Dis a labeling function of deleting data;and

(7)Gd:T→Guardis a function of assigning guards to transitions.

A WFD-net system(ND,M0)=(P,T,F,M0,D,Guard,R,W,De,Gd)is a WFD-net with a markingM0in the source place.The functionType:D→{Cons,Vari}denotes the value type of data items.That is,ifd∈Dis a constant,then we haveType(d)=Cons(resp.ifd∈Dis a variable,then we haveType(d)=Vari).A guard function is a boolean expression related to data items.In this paper,we suppose that guard functions in each branch are related to the same data items.For the sake of readability,when saying “data itemdis read”,it means “data itemdis read or used for the evaluation of a guard function” [30].Therefore,a guard function can be considered as read operations on a transition.For example,we haveGd(t4)=＜high(d3)＞,Gd(t5)=＜middle(d3)＞,Gd(t6)=＜low(d3)＞,Gd(t9)=＜high(d6)＞,Gd(t10)=＜middle(d6)＞,andGd(t11)=＜low(d6)＞in Fig.1.The data itemd3(resp.d6) can be considered as read operations on transitionst4,t5,andt6(resp.t9,t10,andt11).

3.2 Motivation Example

This part introduces a campus-card recharging process as a motivation example.As shown in Fig.1,there are 14 places,16 transitions,8 data items,34 data operations (including 19 read operations,12 write operations,and 3 delete operations),and 6 guard functions.Table 1 illustrates the transitions and data items.

Table 1:Transitions and data items

Fig.1 describes a WFD-net system as follows.Firstly,users log into the system,and produce two data items,i.e.,IDandLogin Password.Then,they click on the application and campus wallet.After these operations,there are three transitions in weak exclusiveness relations.If the balance of the account is high,users can recharge the campus smart cart.If the balance of the account is middle,they can pay the electricity.Otherwise,they go back to the application.Then,they need to submit orders.After submitting orders,users can choose payment methods,e.g.,bank card,Wechat,or Alipay.If the payment amount is high,they can choose bank cards.If the payment amount is middle,they can choose Wechat.Otherwise,they only choose Alipay.After then,they submit and pay for orders.Users need to input account numbers and payment passwords.Finally,they close this deal.

There are some data-flow errors in Fig.1.For example,the data itemd4on the write operation oft3is weakly redundant,and the data itemd1on the read operation oft3is strongly missing.More details about data-flow errors are given in Sections 4 and 5.

Although some methods are used to repair these errors,e.g.,Criteria 1－3 [10] and CorrDF [14],they have some limitations.The method of Criteria 1－3 can repair data-flow errors with transition pairs in weak sequence relations.Each transition reads/writes 0/1 data item.The method of CorrDF can repair data-flow errors caused by incorrect read and write operations in process models with transition pairs in weak sequence relations,weak exclusiveness relations,and weak concurrency relations (Section 4).Unfortunately,they cannot repair data-flow errors caused by delete operations,and their workflow models are usually simple (e.g.,no loop structures).What’s more,repairing one error may bring in some new kinds of errors.For the example of Fig.4h,when we repair the error of missing data,we may bring in some redundant data.Therefore,we need to reveal the scope of different kinds of data-flow errors,and present new methods to check and repair data-flow errors according to the real system requirements.

4 Data-flow Errors Checking and Repairing Methods

In this section,we first defineenabled conditionsof WFD-net systems,and their weak behavioral relations.Then,we present some methods to check and repair data-flow errors.

4.1 Firing Transitions and Weak Behavioral Relations

Definition 3(Enabled Conditions)Given a WFD-net system(ND,M0)=(P,T,F,M0,D,Guard,R,W,De,Gd),t∈Tis enabled at a markingMif it satisfies the following conditions:

(1)tis control-enabled atMsuch that ?p∈·t:M(p)≥1,denoted byM[ct＞;and

(2)tis data-enabled atMsuch that each data item read bytmust be defined and its guards are evaluated to true,which is denoted byM[dt＞.The firing of an enabled transitiont(i.e.,control-enabled [42] and data-enabled) at a markingMdoes not only affect the values of data items and guard functions but also yields a new markingM′[25],which is denoted byM[t＞M′.That is,

A new markingMkis reachable from the initial markingM0,if and only if there exists a firing sequenceσk=t1t2···tksuch thatM0[t1＞M1[t2＞M2···Mk－1[tk＞Mk.

Notice that if a transitiont∈Tis control-enabled atM,we say it is weakly enabled,and its related firing sequence is a weak firing sequence.

Due to the fact that the modeling of a workflow system is process-oriented in reality,we need to analyze itsweak order relation[43].

Definition 4(Weak Order Relation[43]) Let(ND,M0)=(P,T,F,M0,D,Guard,R,W,De,Gd)be a WFD-net system.The weak order relation ?c?T×Tcontains all pairs of transitions(tα,tβ),such that there exists a weak firing sequence (without taking the data operations and guard functions into consideration)σx=t1t2···txsatisfying(ND,M0)[σx＞,α∈{1,···,x－1},α＜β≤x,andx－1 ∈N.

In this paper,the set of all weak firing subsequences is denoted byT*,andT*={σ(1)}∪{σ(2)}∪···∪{σ(ε)},whereσ(ε)=ta1ta2···taε,andta1,ta2,···,taε∈T.

Based on the weak order relation,we defineweak behavioral relationsas follows.

Definition 5(Weak Behavioral Relations)Given a WFD-net system(ND,M0)=(P,T,F,M0,D,Guard,R,W,De,Gd),the transition pair(tα,tβ)is in one of the following weak behavioral relations,wherek∈{1,3,···,n},n=2m+1,andm+1 ∈N:

(1)tαandtβare in weak sequence relation,which is denoted bytα→ctβ,iff(tα?ctβ)∧(tβ／?ctα);

(2)tαandtβare in weak exclusiveness relation,which is denoted bytα?ctβ,iff(tα／?ctβ)∧(tβ／?ctα);

(3)tαandtβare in weak circulation relation,which is denoted bytα?ctβ,iff(tα?ctβ)∧

(4)tαandtβare in weak concurrency relation,which is denoted bytα⊕ctβ,iff(tα?ctβ)∧

Generally speaking,tα→ctβrepresents the transitiontβcannot execute beforetαin any traces.tα?ctβmeans the transitionstαandtβexecute exclusively in any traces.tα?ctβillustrates the transitionstαandtβare in a loop structure.tα⊕ctβdenotes the transitionstαandtβcan execute in different orders.Obviously,these four kinds of weak behavioral relations are mutually exclusive.Iftαandtβare in weak sequence relation and they are in the same branch (i.e.,(tα→ctβ)∧wherek1∈{1,3,···,n1},n1=2m1+1,andm1+1 ∈N),then we denote it astαctβ.For the example of Fig.1,we havet1→ct2,t4?ct5,t3?ct6,t12ct13,andt14⊕ct15,respectively.

Definition 6 (Concurrency Relation)Given a WFD-net system(ND,M0)=(P,T,F,M0,D,Guard,R,W,De,Gd),the transitionstαandtβare inconcurrency relation,which is denoted bytα⊕cdtβ,iff:

(1)tα⊕ctβ;and

(2) The guard functions related totαandtβare satisfied at the same time.

For the example of Fig.2a,we can find thattα⊕cdtβifGd(tα)andGd(tβ)are evaluated to TRUE at the same time.

Figure 2:Two WFD-net systems.(a) The behavioral relation of tα and tβ depends on their guard functions;(b) tα and tβ are in weak circulation relation (i.e.,tα?ctβ)

Definition 7 (Distance of Transitions in Weak Circulation Relation)Given a WFD-net system(ND,M0)=(P,T,F,M0,D,Guard,R,W,De,Gd),?tα,tβ∈T:tα?ctβ,tα∈t(·)k1,andtβ∈t(·)k2,wheretis a transition outside the weak circulation relation,k1andk2are the minimum number of post-sets,such thatk1,k2∈{2,4,···,2m},andm∈N.The distance betweentαandtβis defined asδ(tβ,tα)=|k2－k1|.

Based on the definitions of weak behavioral relations,concurrency relation,and distance of transitions in weak circulation relation,we further formalize theorder relationof transition pairs in a WFD-net system.

Definition 8(Order Relation)Given a WFD-net system(ND,M0)=(P,T,F,M0,D,Guard,R,W,De,Gd),the order relationtα?tβcontains all pairs of transitions(tα,tβ),and they satisfy one of the following conditions:

(1)tα→ctβ;

(2)tα⊕cdtβ;or

(3)(tα?ctβ)∧(k2≥k1).

For the example of Fig.2b,we havet→ctα,t→ctβ,tα?ctβ,andδ(tβ,tα)=|k2－k1|=2.

4.2 Four Kinds of Data-Flow Errors

Based on order relation,we formalizeredundant data,missing data,lost data,andinconsistent data.Before we define these errors,we useA＜＞Bto denoteA∈BorA /∈B.

Definition 9(RedundantData,RD)Given a WFD-net system(ND,M0)=(P,T,F,M0,D,Guard,R,W,De,Gd),T*is the set of all weak firing subsequences,and ?σ∈T*,?to∈σ:po∈.A data itemd∈Dis redundant if it satisfies ?t∈T,?t′∈σ:(t?t′)∧(d∈W(t))∧which is denoted byd＜·RD.

Notice that if there existt,t′∈Tsuch that(t?t′)∧[d∈W(t)∩R(t′)] ∧(d /∈De(t))∧thendmay be redundant.For the example of Fig.3e,we have(t1?t2)∧[d∈W(t1)∩R(t2)]∧(d /∈De(t1))∧[d /∈W(t2)∪De(t2)],andd＜·RD.

Figure 3:The data item d is redundant,where Type(d)= Cons or Type(d)= Vari.(a)–(c)d＜· SRD;(d)–(f) d＜·WRD

A data itemdis strongly redundant data (SRD) if the written values ofdin all possible execution paths are never read before it is deleted,or the workflow process is completed.A data itemdis weakly redundant data (WRD) if there exist some execution paths in which it is written but never read afterward,i.e.,before it is deleted,or the workflow process is completed [30].SRDandWRDbelong to redundant data (RD).As shown in Fig.3,the data itemdis redundant,where (a)–(c) suffer from strongly redundant data,and (d)–(f) suffer from weakly redundant data.

Definition 10(Missing Data,MD)Given a WFD-net system(ND,M0)=(P,T,F,M0,D,Guard,R,W,De,Gd),T*is the set of all weak firing subsequences,?σ∈T*,and ?ti∈σ:pI∈·ti.A data itemd∈Dis missing if it satisfies one of the following conditions:

(1) ?t′∈T,?t∈σ:(t?t′)∧[((d /∈W(t))∧(d∈De(t)∪R(t′)))∨((d /∈W(t)∪W(t′))∧(d∈De(t′)))],which is denoted byd＜·MD;or

(2) ?t∈σ,?t′′∈T,?t′∈T:(t?t′′)∧(t?t′)∧(t′?t′′)∧[d∈W(t)∩(De(t)∪De(t′))∩(R(t′′)which is denoted byd＜·MD.

Notice that if there existt,t′∈Tsuch that(t?t′)∧[d∈W(t)∩(R(t′)∪De(t′))] ∧[d /∈De(t)∪W(t′)],thendmay be missing,e.g.,Figs.4c,4d and 4f.

Figure 4:The data item d is missing,where Type(d)=Cons or Type(d)=Vari.(a)–(c) d＜·SMD;(d)–(h) d＜·WMD

A data itemdis strongly missing data (SMD) if the read or deleted values ofdin all possible execution paths are never written before.A data itemdis weakly missing data (WMD) if there exist some execution paths where it is read or deleted but never written before [30].SMDandWMDbelong to the missing data (MD).It is a terminal error for the execution of workflow systems [24].For example,the data itemdis strongly missing in Figs.4a–4c,and it is weakly missing in Figs.4d–4h.

Definition 11(Lost Data,LD) Given a WFD-net system(ND,M0)=(P,T,F,M0,D,Guard,R,W,De,Gd),a data itemd∈Dis lost if it satisfies one of the following conditions:

(1) ?t,t′∈T,t·∩·t′／=?:[d∈W(t)∩W(t′)]∧[d /∈De(t)∪R(t′)],which is denoted byd＜·LD;or

(2) ?t,t′′∈T,?t′∈T:(t?t′′)∧(t?t′)∧(t′?t′′)∧[d∈W(t)∩W(t′′)]∧[d /∈De(t)∪R(t′)∪W(t′)∪De(t′)∪R(t′′)],which is denoted byd＜·LD.

A data itemdis strongly lost data (SLD) if the written values ofdin all possible execution paths are overwritten without being read or deleted first.A data itemdis weakly lost data (WLD)if there is an execution path where it is overwritten without being read or deleted first [30].TheSLDandWLDall belong to the lost data (LD).In Figs.5a–5c,the data itemdis strongly lost and strongly redundant.Sometimes,weakly redundant in weak circulation relation can lead to weakly lost,as shown in Fig.5d.In Fig.5e,the data itemdis weakly lost and weakly redundant.In fact,ifd＜·LD,thend＜·RD[24].The lost data is also called conflicting data [2].

Figure 5:The data item d is lost,where Type(d)=Cons or Type(d)=Vari.(a)–(c) d＜·SLD;(d)–(e) d＜·WLD

Definition 12(Inconsistent Data,IND)Given a WFD-net system(ND,M0)=(P,T,F,M0,D,Guard,R,W,De,Gd),a data itemd∈Dis inconsistent if it satisfies ?t,t′∈T:(t⊕cdt′)∧(Type(d)=Vari)∧[d∈(R(t)∪W(t)∪De(t))∩(W(t′)∪De(t′))],which is denoted byd＜·IND.

In Fig.6,the data itemdis inconsistent whenType(d)=Vari.Meanwhile,the data itemdis weakly lost and strongly redundant in Figs.6a and 6c,anddis also strongly lost and strongly redundant in Fig.6b.The error of inconsistent data comes up when a transition accesses a data item while its concurrent transitions write or delete the same data item (there is no locking mechanism [19]).Notice that,ifType(d)=Cons,there is no inconsistent data on the data itemd.

Figure 6:The data item d is inconsistent,where Type(d)=Vari.(a)－(e)d＜· IND

A data item written by one transition may belong to several kinds of data-flow errors.The errors of inconsistent data sometimes lead to redundant,missing,or lost data.Lost data causes redundant data.In order to distinguish their relations,we reveal their scopes,as shown in Fig.7a.

Figure 7:Four kinds of data-flow errors,i.e.,redundant data (RD),missing data (MD),lost data(LD),and inconsistent data (IND).(a) The scopes of data-flow errors;(b) The hierarchy of these errors

According to the scopes of data-flow errors,we propose Algorithm 1 to detect them.This algorithm is an iterative procedure,and it consists of seven conditions.It can be used as a road map for implementing data-flow errors detection in a WFD-net system [2].

Algorithm 1: Data-flow errors detection algorithm Require: A WFD-net system (ND,M0),a data item d ∈D Ensure: Data-flow errors in (ND,M0).(1) For each d ∈D Do(2) Traverse the firing subsequences σ ∈T* in the state space of (ND,M0);(3) If there exist t,t′∈T such that (t⊕cdt′) ∧(Type(d)=Vari) ∧[d ∈(R(t)∪W(t)∪De(t)) ∩(W(t′)∪De(t′))] Then(4) Print d＜·IND;(5) Else if there exist t′∈T and ti ∈σ satisfying pI∈·ti Then(6) For each t ∈σ such that (t ?t′)∧[((d /∈W(t))∧(d ∈De(t)∪R(t′)))∨((d /∈W(t)∪W(t′))∧(d ∈De(t′)))]Do(7) Print d＜·MD;(8) End for(9) Else if there exist ∈σ,t′′∈T,and ti ∈σ satisfying pI∈·ti Then(10) For each t′ ∈T such that (t ?t′′) ∧(t ?t′) ∧(t′?t′′) ∧[d ∈W(t) ∩(De(t)∪De(t′)) ∩(R(t′′)∪De(t′′))]∧images/BZ_151_629_1982_647_2028.pngd＜＞R(t′)images/BZ_151_794_1982_812_2028.png∧[d /∈W(t′)∪W(t′′)] Do(11) Print d＜·MD;(12) End for(13) Else if there exist t,t′∈T,and t·∩·t′／=? such that [d ∈W(t)∩W(t′)]∧[d /∈De(t)∪R(t′)]Then(14) Print d＜·LD and d＜·RD;(15) Else if there exist t,t′′∈T Then(16) For each t′ ∈T such that (t ?t′′) ∧(t ?t′) ∧(t′?t′′) ∧[d ∈W(t)∩W(t′′)] ∧[d /∈De(t)∪R(t′)∪W(t′)∪De(t′)∪R(t′′)] Do(17) Print d＜·LD and d＜·RD;(18) End for(19) Else if there exist t ∈T and to ∈σ satisfying po ∈t·o Then(20) For each t′∈σ such that (t ?t′)∧(d ∈W(t))∧images/BZ_151_1344_2630_1362_2676.pngd＜＞De(t)images/BZ_151_1520_2630_1538_2676.png∨images/BZ_151_1585_2630_1603_2676.pngd＜＞W(wǎng)(t′)∪De(t′)images/BZ_151_1926_2630_1944_2676.png∧(d /∈R(t′))Do(21) Print d＜·RD;(22) End for(Continued)

Algorithm 1: (Continued)(23) Else(24) Print No data-flow errors;(25) End if(26) End for

4.3 Repairing Data-flow Errors

In order to guarantee the correctness of WFD-net systems,we should provide effective methods to repair different kinds of data-flow errors.However,it is unnecessary to delete the read operation in an original WFD-net system because some transitions can fire only through reading these data items [10].More importantly,we should not change the value we need to repair all kinds of data-flow errors.When a data item in a WFD-net system only consists of a read,write,or delete operation,we need to add a write operation,remove a write operation,or remove a delete operation.How to place these read,write,and delete operations means configuring the data-flow reasonably.In detail,we need to consider the positions of a data item.If the read and write operations are in inappropriate positions,there may appear new data-flow errors.Therefore,we give the following repair strategies according to the real system requirements to repair different kinds of data-flow errors.

System requirements:

(1) Take the value of data items into consideration;

(2) Avoid bringing in any new data-flow errors as far as possible;

(3) Do not lead to any control-flow errors,e.g.,deadlock and livelock;

(4) Do not remove the read operation in an original WFD-net system;

(5) Do not bring in more data operations in order to repair the weakly redundant;

(6) Do not repair some kinds of weakly lost data so as to satisfy the non-determinacy of some read operations afterward;

(7) Avoid some data-flow errors caused by the delete operation;and

(8) Make sure that there is no inconsistent data by taking the locking mechanism.

Repair strategies:

(1) Change the firing sequence of transitions;

(2) Combine several transitions into one transition;

(3) Remove redundant write operations;

(4) Remove some undesirable delete operations;

(5) Divide one transition into several transitions;and

(6) Create new transitions with write operations.

As we know,inconsistent data often exists in concurrent programs.We can adopt the locking mechanism [18] to block the executions of multiple threads,e.g.,a thread runs in a concurrent program without intervening in other threads.That is,the data item read/deleted by a thread only comes from the main thread or itself.Therefore,we do not provide related algorithms to repair this kind of error in this paper.After then,we propose Algorithms 2–4 to repair missing data,lost data,and redundant data,respectively.In the following algorithms,when we add or remove a transition,we need to add or remove its related places and arcs.

4.3.1 Repairing Missing Data(MD)

In order to repair missing data,we need to add a write operation,or remove a delete operation.It is unnecessary to remove read operations in an actual net as some transitions can fire only through reading these data items.Therefore,we propose Algorithm 2 to repair this kind of error.Its basic solutions are to introduce a transition that can write a required data itemdat some point where the error occurs (i.e.,Steps (1)–(12) and Steps (23)–(28) in Algorithm 2).Meanwhile,we remove some undesirabledin a delete operation (i.e.,Steps (1)–(28) in Algorithm 2),and put the existingdjust before all the branches where the error occurs (i.e.,Steps (18)–(22) and(27)–(36) in Algorithm 2).After Steps (1)–(12),the missing data in Figs.4a,4b,4d,4e,4g and 4h can be repaired.As for the errors in Fig.4c (resp.Fig.4f),we can take Steps (18)–(22) (resp.Steps (34)–(36)) to repair them.Fig.8 shows the repairing results of missing data in Fig.4.

Algorithm 2: Repairing missing data (MD) in a WFD-net system Require: A WFD-net system (ND,M0),a data item d ∈D Ensure: A WFD-net system without missing data (MD).(1) For each t ∈σ,where σ ∈T* and ti ∈σ satisfying pI∈·ti Do(2) If there exists t′∈T such that (t ?t′)∧(d /∈W(t))∧[d ∈De(t)∪R(t′)] Then(3) Analyze the value type of d;(4) If there exist t′′∈T and d such that (Type(d)=Cons)∧(t′?ct′′)∧(d ∈R(t′′)) Then(5) Remove d from De(t) (if it exists),and add a new transition tk into T satisfying(tk→ct′)∧(tk→ct′′)∧(d ∈W(tk));(6) Else if there exist t′′∈T and d such that (Type(d)=Vari)∧(t′?ct′′)∧(d ∈R(t′′))Then(7) Remove d from De(t) (if it exists),and add two new transitions tk and tk′ into T satisfying(tkimages/BZ_394_264_1659_297_1705.pngct′) ∧(tk′images/BZ_394_264_1659_297_1705.pngct′′)∧[d ∈W(tk)∩W(tk′)];(8) Else(9) Remove d from De(t) (if it exists),and add a new transition tk into T satisfying(tkimages/BZ_394_264_1659_297_1705.pngct′)∧(d ∈W(tk));(10) End if(11) End if(12) End for(13) For each t ∈σ Do(14) If there exists t′∈T such that (t ?t′)∧[d /∈W(t)∪W(t′)]∧(d ∈De(t′)) Then(15) Remove d from De(t′);(16) End if(17) End for(18) For each t′∈T Do(19) If there exist t ∈ σ and t′′ ∈ T such that (t ?t′′) ∧ (t ?t′) ∧ (t′?t′′) ∧images/BZ_394_264_1659_297_1705.pngd ∈W(t)∩(De(t)∪De(t′))∩(R(t′′)∪De(t′′))images/BZ_394_264_1659_297_1705.png∧images/BZ_153_1196_2371_1214_2417.pngd ≤R(t′)images/BZ_153_1386_2371_1404_2417.png∧[d /∈W(t′)∪W(t′′)] Then(20) Analyze the value type of d and data operations on t,t′,and t′′;(21) If (Type(d)=Cons) ∧ [d ∈W(t)∩(De(t)∪De(t′))∩(R(t′′)∪De(t′′))] ∧images/BZ_153_1894_2569_1934_2615.pngimages/BZ_153_1934_2533_1952_2579.pngd＞R(t′)images/BZ_153_2125_2533_2143_2579.png ∧[d /∈W(t′)∪W(t′′)]Then(22) Remove d from De(t) and De(t′) (if there exist),and divide t into two transitions tk and tk′,such that {tk′}=(·)x1t′=(·)x2t′′,where x1,x2 ∈{1,3,···,n1},n1=2m1 － 1,and m1 ∈N,R(tk)=R(t)－Γ(d),W(tk)=W(t)－ntv55vl,De(tk)=De(t)－Γ(d),R(tk′)=Γ(d),W(tk′)=p3ff5rz,and De(tk′)=Γ(d);/*Γ(d) is a set of data items only related to d on t */(Continued)

Algorithm 2: (Continued)(23) Else if (Type(d)=Vari) ∧ [d ∈W(t)∩De(t)∩R(t′)∩(R(t′′)∪De(t′′))] ∧images/BZ_154_1914_483_1948_529.pngimages/BZ_154_1948_447_1966_493.pngd＜＞De(t′)images/BZ_154_2135_447_2153_493.png ∧[d /∈W(t′)∪W(t′′)] Then(24) Remove d from W(t) and De(t),and add two new transitions tk1 and tk2 into T satisfying(tk1images/BZ_394_264_1659_297_1705.pngct′) ∧(tk2images/BZ_394_264_1659_297_1705.pngct′′)∧[d ∈W(tk1)∩W(tk2)];(25) Else if(Type(d)=Vari) ∧ [d ∈W(t)∩(De(t)∪De(t′))∩(R(t′′)∪De(t′′))] ∧[d /∈R(t′)∪W(t′)∪W(t′′)] Then(26) Remove d from W(t),De(t),and De(t′)(if it exists),and add a new transition tk1 into T satisfying (tk1images/BZ_394_264_1659_297_1705.pngct′′)∧(d ∈W(tk1));(27) Else if (Type(d)=Vari) ∧ [d ∈W(t)∩R(t′)∩De(t′)∩(R(t′′)∪De(t′′))] ∧[d /∈De(t)∪W(t′)∪W(t′′)] Then(28) Divide t into two transitions tk and tk′,and add a new transition tk1 into T,with tk′images/BZ_394_264_1659_297_1705.pngct′,tk1images/BZ_394_264_1659_297_1705.pngct′′,R(tk)=R(t)－Γ(d),W(tk)=W(t)－555h3hd,De(tk)=De(t)－Γ(d),R(tk′)=Γ(d),W(tk′)=zjhttrl,De(tk′)=Γ(d),and d ∈W(tk1);(29) Else(30) No missing data;(31) End if(32) End if(33) End for(34) If there exist t,t′ ∈T such that (d＜·MD) ∧(t ?t′) ∧[d ∈W(t)∩(R(t′)∪De(t′))] ∧[d /∈De(t)∪W(t′)] Then(35) Divide t into two transitions tk and tk′,with tk′images/BZ_394_264_1659_297_1705.pngct′,R(tk)=R(t)－Γ(d),W(tk)=W(t)－pl5b5hn,De(tk)=De(t)－Γ(d),R(tk′)=Γ(d),W(tk′)=lttrh5p,and De(tk′)=Γ(d);(36) End if

Figure 8:(Continued)

Figure 8:The repairing results of Figs.4a–4g are shown in (a)–(g),and the repairing result of Fig.4h is shown in (h1) if Type(d)=Cons (resp.(h2) if Type(d)=Vari)

4.3.2 Repairing Unnecessary Lost Data(LD)

In order to repair lost data,we need to remove a write operation [10].However,some kinds of lost data should not be repaired,especially when the type of a data itemdis a variable.

If a data item is lost,it must be redundant,but not vice versa.Therefore,we propose Algorithm 3 to repair lost data before repairing redundant data.Figs.5a–5e illustrates the cases of lost data.Its basic solutions are to remove the unnecessary data item in a write operation(i.e.,Steps (1)–(4),(7)–(8),(11)–(15),and (18)–(19) in Algorithm 3) or not repair (i.e.,Steps(5)–(6) and (16)–(17) in Algorithm 3).If a data itemdsatisfiesType(d)=Cons,the lost data in Figs.5a–5e can be repaired after Steps (1)–(4).If a data itemdsatisfiesType(d)=Vari,the lost data in Figs.5a,5c and 5d can be repaired after Steps (7)–(8).However,if a data itemdsatisfiesType(d)=Vari,the lost data in Figs.5b and 5e should not be repaired because the data itemdread by a transitiont4depends on the branch to fire (Steps (5)–(6) in Algorithm 3).Fig.9 shows the repairing results of lost data in Fig.5.

Algorithm 3: Repairing unnecessary lost data (LD) in a WFD-net system Require: A WFD-net system (ND,M0),and a data item d ∈D Ensure: A WFD-net system without any unnecessary lost data (LD).(1) If there exist t,t′∈T,and t·∩·t′／=? satisfying [d ∈W(t)∩W(t′)]∧[d /∈De(t)∪R(t′)] Then(2) Analyze the value type of d;(3) If Type(d)=Cons Then(4) Remove d from W(t) or W(t′) without bringing in a missing data;(5) Else if Type(d)=Vari and there exists t′′∈T such that (t ?t′′)∧(t′?t′′),where d ∈W(t)∩R(t′′)or d ∈W(t′)∩R(t′′) Then(6) Not repair;(7) Else(8) Remove d from W(t);(9) End if(10) End if(Continued)

Algorithm 3: (Continued)(11) For each t′∈T Do(12) If there exist t,t′′ ∈T such that (t ?t′′) ∧(t ?t′) ∧(t′?t′′) ∧[d ∈W(t)∩W(t′′)] ∧[d /∈De(t)∪R(t′)∪W(t′)∪De(t′)∪R(t′′)] Then(13) Analyze the value type of d;(14) If Type(d)= Cons,and there exists t′′′ ∈ T such that (t→ct′′′) ∧ (t′′⊕cdt′′′) ∧(d ∈R(t′′′)∪De(t′′′)) Then(15) Remove d from W(t′′);(16) Else if Type(d)= Vari,and there exists t′′′ ∈T satisfying (t→ct′′′) ∧(t′′⊕cdt′′′) ∧[d ∈R(t′′′)∪De(t′′′)] Then(17) d＜·IND,and we should adopt the locking mechanisms and not repair;(18) Else(19) Remove d from W(t);(20) End if(21) End if(22) End for

Figure 9:The repairing results of Figs.5a–5d,are shown in (a)–(d),and the repairing result of Fig.5e is shown in (e1) if Type(d)=Cons (resp.(e2) if Type(d)=Vari)

4.3.3 Repairing Unnecessary Redundant Data(RD)

If a data itemdis redundant,it may reduce the efficiency of programs.In order to repair this error,we need to remove a write operation [10].However,some kinds of weakly redundant may make programs consume less memory and time.That is to say,the existence of some weakly redundant may be more convenient,and a moderate amount of weakly redundant are required,as shown in Figs.10a–10b.Notice that we should not change the value we need when we repair this kind of error,as shown in Fig.10c.Therefore,the following three kinds of weakly redundant should not be repaired,as shown in Fig.10.

(1) A data itemdis weakly redundant,but it is also read by more than one branch.We usen(R)to denote the number of branches that can readd.For the example of Fig.10a,we haven(R)=2 corresponding to the transitionst2andt3;

(2) The write operation ofdis not in a weak circulation relation while the read operation is in a weak circulation relation.For the example of Fig.10b,we use?(W(t1))to denote the number of times of transitions liket1that can writed,and we use?(R(t2))to denote the number of times of transitions liket2that can readd.Therefore,we have?(W(t1))=1 and?(R(t2))≥1;and

(3) The data itemdsatisfiesType(d)=Vari,and the transitions which write and readdare in weak circulation relation.For the example of Fig.10c,we have(t2?ct3)∧(d∈W(t1)∩R(t2)∩W(t2)∩R(t3))and the value ofdmay change asd∈W(t1)∩W(t2).If we put the write operation oft2into the same branch just beforet3,we may change the value ofdbecauset3may not fire.

Figure 10:Three kinds of weakly redundant shouldn’t be repaired.(a) d ∈W(t1)∩R(t2)∩R(t3);(b) t1 is not in a weak circulation relation,while t2 is in a weak circulation relation;(c) Type(d)=Vari

Figs.3a–3f illustrates the cases of redundant data.We propose Algorithm 4 to repair this kind of data-flow error.Its basic solutions are to remove some undesirable data itemdin a write operation and delete operation (i.e.,Steps (1)–(5) in Algorithm 4).Meanwhile,we divide the transition that producesdinto some branches,the transition withdin a write operation just before the transition read it (i.e.,Steps (6)–(9) in Algorithm 4),or not repair (i.e.,Steps (10)–(11)in Algorithm 4).After Steps (1)–(5),the redundant data in Figs.3a–3d and 3f can be repaired.As for the errors in Fig.3e,we can take Steps (6)–(9) to repair them.Fig.11 shows the repairing results of redundant data in Fig.3.

Algorithm 4: Repairing unnecessary redundant data (RD) in a WFD-net system Require: A WFD-net system (ND,M0),a data item d ∈D Ensure: A WFD-net system without any unnecessary redundant data (RD).(1) For each t′∈σ,where σ ∈T* and to ∈σ satisfying po ∈t·o Do(2) If there exists t ∈T satisfying (t ?t′)∧(d ∈W(t))∧images/BZ_394_264_1659_297_1705.pngimages/BZ_157_1356_2516_1374_2562.pngd＜＞De(t)images/BZ_157_1532_2516_1550_2562.png∨images/BZ_157_1597_2516_1615_2562.pngd＜＞W(wǎng)(t′)∪De(t′)images/BZ_157_1939_2516_1957_2562.pngimages/BZ_394_264_1659_297_1705.png∧(d /∈R(t′))Then(3) Remove d from W(t),De(t),and W(t′)∪De(t′) if there exist;(4) End if(5) End for(Continued)

Algorithm 4: (Continued)(6) If there exist t,t′ ∈T such that (d＜·RD) ∧(t ?t′) ∧[d ∈W(t)∩R(t′)] ∧(d /∈De(t)) ∧images/BZ_394_264_1659_297_1705.pngd＜＞W(wǎng)(t′)∪De(t′)images/BZ_394_264_1659_297_1705.pngThen(7) Analyze d,n(R),?(W(t)),and ?(R(t′));(8) If (n(R)=1) ∧ [(Type(d)=Cons)∨((Type(d)=Vari)∧((t→ct′)∨(t⊕cdt′)))] ∧[?(W(t))≥?(R(t′))],and there is no t′′∈T such that (t ?t′′)∧(t′?t′′) ∧(d ∈De(t′′)) Then(9) Divide t into two transitions tk and tk′,with tk′images/BZ_394_264_1659_297_1705.pngct′,R(tk)=R(t)－Γ(d),W(tk)=W(t)－xrdnlh5,De(tk)=De(t)－Γ(d),R(tk′)=Γ(d),W(tk′)=55rtfnt,and De(tk′)=Γ(d);(10) Else(11) Not repair;(12) End if(13) End if

Figure 11:The repairing results of Figs.3(a)–(f) are shown in (a)–(f)

As we know,the error of inconsistent data exists in weak concurrency relations,and can be avoided by taking a locking mechanism.It needs to be repaired firstly.The errors of redundant data,missing data,and lost data may exist in weak concurrency relations,weak sequence relations,weak exclusiveness relations,and weak circulation relations.For the example of Fig.4h,we haved＜·WMD.IfType(d)=Cons,we need to add a new transitiontkintoTsatisfying(tk→ct2)∧(tk→ct3)∧(d∈W(tk))(i.e.,Steps (4)–(5) in Algorithm 2),as shown in Fig.8h1.However,this would bring in weakly redundant data (i.e.,d＜·WRD).Based on the Steps (1)–(36) in Algorithm 2 and Steps (1)–(22) in Algorithm 3,when we repair missing data,we haven’t brought in lost data,and vice versa.For the example of Fig.5a,we haved＜·SLD.We need to remove the data itemdfromW(t1)(i.e.,Steps (1)–(10) in Algorithm 3).However,after taking this algorithm to repair,there are still exist weakly redundant data (i.e.,d＜·WRD),as shown in Fig.9a.The lost data belongs to redundant data.After repairing lost data,the redundant data may still exist.Based on Steps (1)–(13) in Algorithm 4,when we repair redundant data,we have not brought in lost data or missing data.As we know,the transitions with missing data have no right to fire,and possibly making WFD-net systems stop at a nonterminal state.In other words,missing data may lead to terminal errors [24].Compared with missing data,lost data and redundant data are not terminal errors.Therefore,the missing data needs to be repaired secondly and the lost data needs to be repaired thirdly.Based on these analyses,we organize the data-flow errors into a hierarchy,as shown in Fig.7b.This hierarchy can help us avoid bringing in new unnecessary data-flow errors as far as possible when we repair one kind of error.

5 Case Study

This paper aims to detect and repair data-flow errors,and guarantees the correctness of a WFD-net system.For the example of Fig.1,we can find that the data itemd7is a missing data inR(t9),i.e.,d7＜·MD.Obviously,the transitiont9cannot fire if we do not repair this kind of error.

Based on Definitions 9–12,we analyze the data-flow errors in Fig.1.By taking Algorithms 2–4,we repair these errors,and their results are shown in Fig.12.

(1) Data itemsd2,d3,d8are not in any data-flow errors;

(2) Due to the fact that(d1＜·SMD)∧(Type(d)=Cons)inR(t3)andR(t7),we can removed1∈De(t2)(Steps (18)–(22) in Algorithm 2);

(3) Sinced7＜·WMDinR(t9),we can add a transitiontkwithd7∈W(tk)and related places as well as arcs in the same branch just beforet9(Steps (1)–(12) in Algorithm 2);

(4) Givend5＜·IND∧SLD∧SRDinW(t13)∩W(t14)∩R(t15),we can adopt the locking mechanism to avoid ofINDandSLD(Steps (16)–(17) in Algorithm 3).Therefore,the data itemd5read byt15can only come fromW(t13).After then,we haved5＜·SRDinW(t14),and we should removed5∈W(t14)(Steps (1)–(5) in Algorithm 4);

(5) Consideringd6＜·SLD∧SRDinW(t12)∩W(t13)∩R(t14)∩R(t15),we can removed6∈W(t12)to avoidSLDandSRD(Steps (1)–(10) in Algorithm 3 or Steps (1)–(5) in Algorithm 4);and

(6) Givend4＜·WRDinW(t3),we can divide the transitiont3into two transitionst3kandt3k′.The transitiont3k′ is in the same branch just beforet4(Steps (6)–(9) in Algorithm 4).

Figure 12:A repaired WFD-net system of Fig.1

After taking these methods,a repaired WFD-net system is shown in Fig.12.It is a new WFD-net system without any control-flow or data-flow errors.

6 Evaluation and Experiment

6.1 Functional Evaluation

In this subsection,we compare our methods with some state-of-the-art methods in terms of repairing functions for data-flow errors (Fig.13).The method of Criterias 1–3 [10] can repair data-flow errors caused by transition pairs only in weak sequence relations,and its transitions read/write at most one data item.The method of CorrDF [14] can repair data-flow errors caused by transition pairs in weak sequence relations,weak exclusiveness relations,or weak concurrency relations.Unfortunately,these methods cannot repair data-flow errors in weak circulation relations and errors caused by delete operations.By comparison,our methods overcome these deficiencies,as shown in Fig.13.

Figure 13:A comparison with some state-of-the-art methods (e.g.,Criterias 1–3 [10] and CorrDF [14]) in terms of repairing functions for data-flow errors.In this figure,N(Read)(resp.N(Write) or N(Delete)) denotes the maximum number of data items on the read (resp.write or delete) operations of a transition,where n ∈N. WSR denotes weak sequence relation,WER stands for weak exclusiveness relation,WCR represents weak concurrency relation,and WCIR means weak circulation relation

6.2 Experiments

In reality,a simple pseudo-code easily suffers from different kinds of data-flow errors.In this part,some experimental cases are given to show the advantages of our methods.Their detailed procedures are proceeding as follows.Firstly,we use a WFD-net system to model the real pseudo-code.Secondly,we check the data-flow errors based on Algorithm 1.After that,we use Algorithms 2–4 to repair these data-flow errors in a WFD-net system.Finally,we can obtain the repaired WFD-net system.According to the repaired WFD-net system,we can further repair the errors in the pseudo-code.

6.2.1 Repairing Missing Data(MD)

In the first experiment,we use a WFD-net system to model a simple pseudo-code with missing data,as shown in Figs.14a and 15a.Due to the fact that the data itemaread byt10is deleted byt4,we can find(a＜·MD)∧(Type(a)=Cons).Therefore,it is important to repair this kind of data-flow error in a suitable position.We utilize Algorithm 2 (Steps (18)–(22)) to do this work,and its result is shown in Fig.15b.Furthermore,we can repair this pseudo-code according to the WFD-net system without missing data,as shown in Fig.14b.

Figure 14:(a) Pseudo-code with missing data (MD) and (b) after being repaired

Figure 15:(a) and (b) are the WFD-net systems of Figs.14a and 14b

6.2.2 Repairing Unnecessary Lost Data(LD)

In the second experiment,we use a WFD-net system to model a simple pseudo-code with unnecessary lost data,as shown in Figs.16a and 17a.Due to the fact that the data itemais overwritten without being read or deleted first.Therefore,we havea＜·LD.We utilize Algorithm 3 (Steps (1)–(10)) to do this work,and its result is shown in Fig.17b.Furthermore,we can repair this pseudo-code according to the WFD-net system without unnecessary lost data,as shown in Fig.16b.

Figure 16:(a) Pseudo-code with Lost data (LD) and (b) after being repaired

Figure 17:(a) and (b) are the WFD-net systems of Figs.16a and 16b

6.2.3 Repairing Unnecessary Redundant Data(RD)

In the third experiment,we use a WFD-net system to model a simple pseudo-code with redundant data,as shown in Figs.18a and 19a.Due to the fact that the data itema2wrote byt3is only read byt6,we can finda2＜·RD.We utilize Algorithm 4 (Steps (6)–(9)) to do this work,and its result is shown in Fig.19b.Furthermore,we can repair this pseudo-code according to the WFD-net system without redundant data,as shown in Fig.18b.

Figure 18:(a) Pseudo-code with redundant data (RD) and (b) after being repaired

Figure 19:(a) and (b) are the WFD-net systems of Figs.18a and 18b

6.2.4 Repairing Results of Existing Examples

In the following experiment,we consider examples from the existing references.We present the advantages of our methods in repairing four kinds of data-flow errors.Fig.20 is the result of our experiment.It shows the numbers of data items on read/write/delete operations,the numbers of guards and transitions,and the numbers of data-flow errors before and after repairing.We can find that after taking our Algorithms 2–4,most of the data-flow errors can be repaired.However,as shown in Algorithm 4,some kinds of redundant data should not be repaired,e.g.,redundant data itemeshown in Fig.1 in [30].Therefore,our methods are more effective.

Figure 20:Our experiment result in terms of the numbers of data items on read/write/delete operations,the numbers of guards and transitions,and the numbers of data-flow errors before and after repairing

7 Conclusion and Future Work

WFD-net is a formal functional method to describe the control-/data-flows of workflow systems.It extends WF-net systems with three kinds of data operations (i.e.,read,write,and delete operations) and guard functions.A good modeling method and efficient detecting and repairing technique are crucial for the correctness of workflow systems.Based on weak behavioral relations (i.e.,weak sequence relation,weak exclusiveness relation,weak circulation relation,and weak concurrency relation) and order relation,we formalize four kinds of data-flow errors (e.g.,redundant data,missing data,lost data,and inconsistent data) in a WFD-net system.Then,we reveal the relations between these data-flow errors,and organize them into a hierarchy,which is conducive to correctly repairing data-flow errors without repeated work.Furthermore,some algorithms are developed to detect and repair data-flow errors in WFD-net systems according to system requirements and repair strategies.Compared with the existing methods,our methods can repair data-flow errors in weak circulation relations and errors caused by delete operations.What’s more,our methods can avoid bringing in new unnecessary errors when repairing some kinds of data-flow errors.

In the future,we plan to do the following studies:

(1) We analyze the behavioral consistency of WFD-net systems,and study what kind of dataflow error affects the behavioral consistency degree;

(2) We develop a tool to repair some unnecessary data-flow errors automatically based on system requirements;and

(3) We intend to consider the process mining with timestamps in the workflow processes,and use the unfolding-based technique [7] to detect and repair their data-flow errors.

Funding Statement: This work was supported in part by the Shanghai Science and Technology Innovation Action Plan (Grant No.19511101300),in part by the Key Laboratory of EMBEDded System and Service Computing (Ministry of Education) (Grant Nos.ESSCKF201902 and ESSCKF202102),and in part by the National Nature Science Foundation of China (Grant Nos.62172299 and 62032019).

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.