Hybrid Diagnosis Applied to Multiple Instances in Business Processes

Hybrid Diagnosis Applied to Multiple Instances in Business Processes Rafael Ceballos(B), Diana Borrego, Mar´ıa Teresa G´omez-L´opez, and Rafael M. Gasca Universidad de Sevilla, Seville, Spain {ceball,dianabn,maytegomez,gasca}@us.es Abstract. Business Process compliance is an important issue in controlflow and data-flow perspectives. Control-flow correctness can be analysed at design time, whereas data-flow accuracy should be verified at runtime, since data is accessed and modified during execution. Compliance validation should consider the conformance of data to business rules. Business compliance rules are policies or statements that govern corporate behaviour. Since business compliance rules and data change during process execution, faults can appear due to the erroneous inclusion of rules and/or data in the process. A hybrid diagnosis therefore needs to be performed regarding the likelihood of faults in data vs. business rules. In order to achieve the correct diagnosis, it is fundamental to attain the best assumption concerning the degree of likelihood. In this paper, we present an automatic process to diagnose possible faults that simultaneously combines business rules and data of multiple process instances. This process is based on Constraint Programming paradigm to efficiently ascertain a minimal diagnosis. Furthermore, a methodology for calculation of the most appropriate degree of likelihood of faults in data vs. business rules is proposed. Keywords: Business process analysis ·Diagnosis ·Business rules · Business data constraints ·Constraint programming ·Databases 1 Introduction Business processes (BPs) permit the description of the activities necessary to achieve an objective in a company. This description includes, among other things: a workflow model, a set of business rules or policies, and the data interchanged during the execution. The correctness of an execution implies the correctness of these three aspects. Frequently, BPs are supported by Process Aware Information Systems (PAISs) [23]. A PAIS is a software system that manages and executes operational processes involving people, applications, and/or information sources on the basis of process models. This type of system provides a way to manage data stored in a repository layer that is read and written by a BP. The diagnosis of the workflow tends to be performed at design time to prevent errors after process deployment. However, the updating of business rules, such as compliance rules, and the management of data at runtime is common practice. Since data and compliance rules may be modified at runtime, their diagnosis cannot be included in only the design phase. The development an efficient diagnosis of possible faults is essential, since these faults appear at runtime and a great quantity of data and business compliance rules are probably involved. The special problem faced in BP diagnosis is that the data is not involved in only one instance, and it is not isolated from other instances executed in the past or in the future. The data written or read in an instance can be shared with other instances, or even with another process, such as when the data involved is stored in a repository, typically in a relational database. These relations must be used in the diagnosis process, since the isolation of a fault that explains a failure of an instance cannot contradict the diagnoses found for other instances. In previous work [8], the importance of data correctness in BPs is studied, including relational databases as the main source of data. This previous work, however, only includes the possibility of faults in data, but fails to consider defects in business compliance rules. Derived from the modification of business compliance rules and data, certain faults can be produced due to the erroneous inclusion of the rules and/or data in the process. The importance of verifying the correctness of data in PAISs is known [12], although how to combine faults in business compliance rules and data at the same time remains a challenge. In this paper, we propose an automatic model-based diagnosis methodology to verify the compliance to the business rules by data in multiple instances, and to isolate the origin of the faults. Since data is more numerous and even more frequently updated, it is more likely a fault appearing due to incorrect data than due to an erroneous business compliance rule. In order to obtain the best assumption about this degree of likelihood, we propose a methodology for calculating the most appropriate degree of likelihood of faults between data vs. business compliance rules. The paper is organised as follows. Section 2presents a motivating example to illustrate the concepts. Section 3introduces the adaptation of model-based diagnosis methodology. Section 4presents the Constraints Programming paradigm used to perform the diagnosis. In Sect. 5, the diagnosis of the motivating example is performed. Section 6presents an overview of related work found in the literature. And finally, conclusions are drawn and future work is proposed. 2 Using Business Data Constraints. A Motivating Example In this paper, a real example of a financial economic application is used to illustrate the hybrid diagnosis. The activities of the company are oriented towards negotiating collaborative projects developed over a number of years. The process consists of the management of costs of projects, during their execution, as detailed in [8], and is represented in Fig. 1. All these tasks are carried out by a total of 25 employees, who modify the stored information for more than Fig. 1. Business Process example 300 projects. Each employee is responsible for certain activities of the process. The persistence layer that supports this business process is formed of a database with 86 tables. Each employee can introduce an average of 200 items of data per project, during the 4 years that a project can last. BPs with a high level of human interaction demand a more frequent data validation and diagnosis, since humans are more likely to introduce intermittent faults. The intermittence of faults complicates the detection and diagnosis of model violations, since an inconsistency detected during the execution of an activity does not necessarily imply a failure in the activity, neither does it imply that this fault may appear again in the future. Our paper focuses on the concept of Business Data Constraints (BDCs), which was introduced in [8]. Definition 1. Business Data Constraints are a subset of business compliance rules that represent the compliance relation between the values of data during a business process instance. In this paper, we assume that the BDCs specification can be incorrect, and therefore inconsistent with the introduced data, where the data is correct. The use of BDCs hugely facilitates the data consistency analysis, and the diagnosis of the origin of an inconsistency. The diagnosis methodology must consider the following characteristics: – Data involved in the diagnosis is not strictly flowing through the process, some of them may also be stored in databases. This implies that the quantity of data involved in the diagnosis of each instance can be very large. – The data managed in an instance is not independent from the data of other instances, since data can be shared between instances. Fig. 2. Subset of relational model of the example Fig. 3. Subset of tables of the example – The BDCs tend to be updated in order to represent new conditions. Therefore, it is necessary to include these modified rules as possible faults. The activities of a BP can modify certain data from a relational database, thereby making it necessary to evaluate certain BDCs. For the example, the BDCs must be satisfied with the various values of the project data. In order to express the BDCs, we use the grammar proposed in [8], which is based on numerical constraints over natural, integer, and float variables. A subset of BDCs for the activities is presented below: 1. Execute final application: (a) humanCost + subsidisedCost = totalCost (BDC1) (b) 3 ·humanCost ≤totalCost (BDC6) 2. Accept contract: (a) subsidisedCost ≥2·subsidisedPerYear (BDC2) (b) humanCost ≥4·humanCostPerYear (BDC3) 3. Recovery and payment: (a) subsidisedPerYear ≤maximumSubsidised (BDC4) (b) humanCostPerYear ≤maximumHuman (BDC5) The variables in the previous BDCs are stored in a database whose relational model is shown in Fig. 2. The three tables represent the information about the project (Project), the details for each project in each year ProjectPerYear,and the maximum spending limit allowed in each year and for each cost item (MaximumCostPerYear). Examples of the stored data are shown in Fig. 3. In order to show our diagnosis methodology, in this example, we introduce 3 defects: 2 erroneous items of data, and 1 incorrect BDC. The following section shows how to adapt model-based diagnosis to the hybrid problem. 3 Applying Model-Based Diagnosis to Business Processes 3.1 Fundamentals of Model-Based Diagnosis Model-based diagnosis enables the identification of the parts that fail in a system. It is performed by comparing the expected behaviour of the system with real behaviour. The expected behaviour is modelled using the knowledge of the system to diagnose, whereas real behaviour is known by analysing the events produced. This implies that model-based diagnosis is considered by the pair {SD, OM}, where SD is the System Description and OM is the Observational Model. The SD is a set of constraints, and the OM is a set of values of the observable data. A fault is visible when a discrepancy between the expected behaviour (SD) and the observed behaviour (OM) is found. Model-based diagnosis is based on the parsimony principle [17], in order to attain a minimal diagnosis that explains the conflicts in an efficient way. This principle states that among competing hypotheses, the one with the fewest assumptions should be selected. For example, a conflict is detected in the following SD and OM:{a+b=c,a+2·b=d},{a=7,b=5,c=9,d=14}.If the assumption {a=7}is false (i.e. it is modified, a= 4), then the remaining assumptions are satisfied between them. Model-based diagnosis identifies the smallest assumption that causes conflicts. In this example, there are other possible hypotheses, but these imply the modification of more than one assumption. The following subsections analyse: (1) how to design the model to be diagnosed (SD); and (2) how to obtain the observational model (OM). 3.2 System Description: Relational Database Model and Business Data Constraints Since the stored data participates in the BDCs, it is necessary to include the BDCs and the relational database scheme into the model to be diagnosed. Business Data Constraints describe the semantic relation between the data values that are introduced, read and modified during the BP instances. It should be borne in mind that the variables participating in the constraints can come from the database or from the data-flow. A Relational Database is a collection of predicates over a finite set of variables described by means of a set of relations. A relation Ris a data structure which consists of a heading and an unordered set of tuples which share the same type, where A1,A2,...,Anare attributes of the domains D1,D2,...,Dn.Anumber of the attributes of a relation can be described as Primary Key Attributes.The relation between two tables is described by a referential integrity. Two tables can be related by means of their Primary and Foreign Key Attributes, described in the literature as the relational model. 3.3 Observational Model: Tuples of the Database In a PAIS, the information is typically stored in a relational database, and therefore the tuples of the tables compose the OM. Since the variables involved in Fig. 4. Denormalized tuples a BDC have different origins, it is possible that attributes from various tables are related in a single BDC. The location of the data in various tables is due to the necessity to follow the Normal Forms defined in relational database theory. The normalization rules are designed to prevent update anomalies and data inconsistencies. Since data is stored in various tables, to ascertain the full tuple of values for an OM, a denormalization process needs to be carried out. This denormalization process is only used for the purpose of diagnosing; the relational database undergoes no changes at all, only a new join relation is obtained with all related attributes together used for the diagnosis in a temporal way. Although normalization methods are applied at schema level, it is possible to apply the opposite methods to ascertain the denormalized relations between the data. The related attributes are those that appear in the same BDC together with the primary-foreign key attributes necessary to join the related attributes that belong to various tables. For the example in Fig. 2, the obtained join-table is shown in Fig. 4. In the figure, the related BDCs are shown at the top of each column. Although the details of how the join-table is created are described in [8], the general idea can be understood by analysing the relational model in Fig. 2, and by observing the specific values for the example introduced in Fig. 3. Since the attribute idProject of the table ProjectPerYear is a foreign key of table Project, then each tuple of ProjectPerYear is related to the tuple of Project whose foreign and primary keys are equal. In a similar way, these are relation between the variables MaximumPerYear and ProjectPerYear. In the denormalization process, a column is included for each attribute to distinguish between the provenance of the values. Distinction is made due to the fact that it is necessary to know whether two values correspond to the same attribute after the denormalization, since two equal values in a column do not imply they represent the same variable. In the denormalization process, the same value can appear in various tuples, derived from the 1..n relation between the tables, such as the value associated to the human cost of project 223 (Variable humanCost1) that appears in the two first tuples of Fig. 4, since this project was developed over two years. 4 Constraint Programming for Hybrid Business Process Diagnosis Models 4.1 Fundamentals of Constraint Programming In order to find the minimal incorrect part of the SD and OM in an automatic and efficient way, we propose using Constraint Programming, since the definition of BDCs is very close to the definition of the logic and arithmetic constraint modelled in a Constraint Satisfaction Problem (CSP). A CSP [18] represents a reasoning framework consisting of variables, domains and constraints V,D,C, where Vis a set of nvariables v1,v 2, ..., vnwhose values are taken from finite domains Dv1,D v2, ..., Dvn respectively, and Cis a set of constraints on their values. The constraint ck(xk1,...,x kn) is a predicate that is defined on the Cartesian product Dk1×...×Dkj. This predicate is true iff the value assignment of these variables satisfies the constraint ck. If the model represented by {SD,OM}is satisfiable, then the OM conforms to the BDCs that describe the SD. However, if no solution is found, the minimal non-conformance parts of the model should be determined. In order to ascertain the minimal explanation regarding faults, it is necessary to find a minimal subset ss ⊂{OM ∪BDCs}that satisfies {SD ∪OM}−ss. Since BDCs are applied by various tuples with different values, all instances of BDCimust be included in the search. This search is performed using a Constraint Optimization Problem (COP), which is solved as a Min-CSP. A Min-CSP is a COP, where the goal is to minimize an optimization function. The application of a Min-COP to a modelbased diagnosis problem implies defining an optimization function in order to minimize the subset ss. 4.2 Compliance Verification by Means of the Observational Model In order to verify the compliance of the BDCs, we have applied the obtained tuples to instantiate the BDCs. For the tuples shown in Fig. 4, the BDCs of the example have been instantiated, and the results are shown in Table 1. Analysing each BDC according to the tuples: Table 1. Results of the compliance verification of the BDCs BDC Tuple 12345 1BDC1 1✓BDC2 1✗ 2BDC1 2✓BDC2 2✓BDC3 2✓BDC4 2✓BDC5 2✓ 3BDC1 3✗BDC2 3✗BDC3 3✗BDC4 3✓BDC5 3✗ 4BDC1 4✓BDC2 4✗BDC3 4✓BDC4 4✗BDC5 4✓ 5BDC1 5✓BDC2 5✓BDC3 5✓BDC4 5✓BDC5 5✓ 6BDC1 6✓BDC2 6✓ –BDC 1: two different instances of this BDC can be obtained (BDC1 1and BDC2 1) for the five tuples ({1, 2, 3}and {4, 5}). BDC1 1is satisfiable (tuples 1, 2 and 3), but BDC2 1is non-compliant (tuples 4 and 5). An error in one single input: humanCost2,subsidisedCost2 or totalCost2, can explain this abnormal behaviour. It is less likely that there is a fault in a BDC (usually written by a business expert), than in an input (usually typed in by an user). –BDC 2,BDC 5and BDC6are consistent for all tuples. –BDC 3: Only BDC4 3is satisfiable. There are several explanations for this behaviour: (a) related to the data values, and (b) related to the BDC. An error committed on writing BDC3could provide a single explanation. As mentioned earlier, it is less likely that a BDC is erroneous than data. The question is, in what percentage should this likelihood be described? The analysis of this percentage of likelihood is part of our methodology and is detailed in the following subsection. –BDC 4:BDC 2 4and BDC4 4are not satisfied. The failure can be explained with a single variable,{maximumSubsidised2}, whose value is 10000 and is shared by these two instances. Although the possible diagnosis has been explained separately for each BDCi, it is necessary to ascertain the minimal diagnosis that explains all discrepancies for the whole problem. Our methodology is able to obtain the minimal diagnosis that explains all this non-compliant behaviour. Fig. 5. Min-CSP example 4.3 Min-CSP Applied to Model-Based Diagnosis The execution of the diagnosis entails the translation of the problem into a CSP, including BDCs and tuples for each execution instance. Figure 5shows the Min- CSP created to diagnose the example. Below, the modelling of the parts of the CSP are detailed (variables, domains, constraints and objective function). In order to declare the Variables of the problem, a new variable is added to the Min-CSP for each variable obtained in BDCi jas explained in Subsect. 3.3 following the syntax: type var1 k,...,varm k. Furthermore, in order to provide the Min-CSP with the ability to distinguish between different sources of faults (i.e. data and/or BDCs), we use reified constraints. A reified constraint relies on a variable that denotes its truth value. It is therefore necessary to add new variables to the CSP, whose domain is reduced to values 0 (false value) and 1 (true value). These variables are associated to each BDCi,BDC j i(Constraints to represent the instantiation of BDCs) and assignments of value to an input (Constraints to represent the instantiation of Variables), in order to denote whether they are satisfiable. Both rBDCiand rBDCj iare included to differentiate the BDC from its application for each tuple. The proposed syntax is: //Reified variables to ascertain the satisfiability of the BDCs integer[0,1] rVar1 k,...,rVarm k integer[0,1] rBDCi,rBDC 1 i,...,rBDCn i //Constraints to represent the reified variables assignment rVarj k=¬(varj k=value j k) //Constraints to represent the reified BDCs rBDC1 i=¬(BusinessRuleiinstantiated by tuple 1) ... rBDCn i=¬(BusinessRuleiinstantiated by tuple n) The reified variables are equalized to the negated constraints since the objective function is to minimize the number of elements with abnormal behaviour (non-compliant). In order to ascertain when a defect in a BDC is less likely than in data errors, the following constraint is added for each BDC: rBDCi=rBDC 1 i+...+rBDC n i=n jrBDCj i≥minLiki These constraints incorporate the likelihood concept into the CSP, by using the parameter minLiki. Definition 2. The parameter minLikiis the minimum number of faults (noncompliant instances of a BDCi) that is set as the threshold to indicate that there is a defect in a BDCi. For example, if there are 5 tuples where BDCiis involved, minLikican take a value between 1 and 5. If at least the minLikithreshold number of instances are 23. Weber, B., Sadiq, S.W., Reichert, M.: Beyond rigidity - dynamic process lifecycle support. Comput. Sci. - R&D 23(2), 47–65 (2009) 24. Weber, I., Hoffmann, J., Mendling, J.: Semantic business process validation. In: SBPM 2008: 3rd International Workshop on Semantic Business Process Management at ESWC 2008, June 2008 25. Weidlich, M., Ziekow, H., Mendling, J., G¨unther, O., Weske, M., Desai, N.: Eventbased monitoring of process execution violations. In: Rinderle-Ma, S., Toumani, F., Wolf, K. (eds.) BPM 2011. LNCS, vol. 6896, pp. 182–198. Springer, Heidelberg (2011) 26. Yongchareon, S., Liu, C., Zhao, X.: A framework for behavior-consistent specialization of artifact-centric business processes. In: Barros, A., Gal, A., Kindler, E. (eds.) BPM 2012. LNCS, vol. 7481, pp. 285–301. Springer, Heidelberg (2012)