Given the events modeled by a business process, it may happen in the presence of alternative execution paths that the data required by a certain event determines somehow what event is executed next. Then, the process can be modeled by using an approximate functional dependency between the data required by both events. We apply this approach in the context of conformance checking: given a business process model with a functional dependency (FD) that no longer corresponds to the observed reality, we propose corrections to the FD to make it exact or at least to improve its confidence and produce a more accurate model.
Conformance checking aims at determining whether the actual execution of a
business process, as recorded within an event log, conforms to its model. This
approach helps bridge the gap between process specifications and their
implementation, by detecting deviations between models and reality [
In contrast, our work addresses conformance checking by considering an
artifact-centric perspective of process definition where the data is represented
by a UML class diagram and the processes are described in BPMN. So, we
use standard and common formalisms for conceptual representation of data and
processes, and are aligned with recent proposals aimed at specifying business
process conceptually to facilitate understanding of these models by the domain
experts [
With our approach, not only can we identify current deviations between the model and the actual execution of the process, but we can also propose modifications to the models to correct this misalignment. This is achieved by analyzing, for each event in the log, the functional dependency holding between its contextual data and the next branch after it.
The following example illustrates our contribution. Assume that a Taxi Service has developed an application to coordinate its taxi drivers. When they are in service, they may receive offers for new rides. Then, depending on the distance and the price of the offer, the drivers decide to accept/reject it. The BPMN model in Figure 1 shows this behavior. Visual Paradigm for UML CoImnmuonritydEedritiotno[noet xfoerccoumtmeeraciarltuisfea]ct-centric approaches, activities need to handle data.
In particular, the data required by previous activities is shown in the UML
diagram in Figure 1. Note that it contains information regarding the taxi and its
driver, and also regarding the offers and the clients that make them. Additionally,
we include an OCL operation that defines how the activity check new offer shown
in the BPMN updates the data represented in the class diagram [
1 Driver
Person id name reputation {i}
Taxi drives 1 licensePlate
currentLocation 0..1
* takes * takenRoute *
Offer 1 makes * iniPlace client sdtisatratTnicmee : DateTime offeredPrice is offered offeredRoute {i}
CompletedOffer endTime : DateTime Operation : checkNewOffer ( O f f e r o , Taxi t ) post : t . o f f e r e d R o u t e >i n c l u d e s ( o )
When the application is running, it may come up with the log in Table 1, which shows the attributes related to the new offer event (as given by the class Offer in Figure 1), and the name of the branch taken in the BPMN diagram (i.e. the decision made by the Taxi driver).
From the log we observe that some offers with distances and prices similar to those that are accepted are instead rejected, thus actually taxi drivers DO NOT necessarily decide to accept or reject an offer just based on the distance and price: clearly, this implies that the previous BPMN model is incorrect. At a closer observation of the data in the log, we eventually note that the decision depends also on the client’s reputation. While this seems rather obvious with few data, in practice, with huge amounts of data, a manual analysis is unfeasible, and error prone because of the difficulty of the analysis itself.
In this paper we propose an approach that uses the techniques for evolving
approximate functional dependencies proposed in [
Conformance Checking It receives as input a business process model and the footprints of the processes executed in the information system in terms of an event log. An execution of a process (also known as process instance or case) is represented as a sequence of activities called trace. We assume, without loss of generality, that each trace can be identified with a (surrogate) id, and each activity within the trace with a timestamp and activity name. An event log is a set of traces, representing the behavior observed in the information system during the execution of the process.
Definition 1 (Trace, Event Log). Let A UA be a set of events A over a
universe of events UA. A trace 2 A is a sequence of events. An event log
L 2 P(A ) is a set of traces, where P(A ) represents the power set of A .
Functional Dependencies Let r be an instance of relation R(A1; A2; :::; An),
jrj denotes the number of tuples in r, t[Ai] the value of the attribute Ai in the
tuple t and X (r) is the projection of r on the attributes of X. A functional
dependency F over R has the form F : X ! Y where X and Y are two subsets
of the attributes of R. Given an instance r of R, r satisfies an FD F defined on
R if, for every pair of tuples t1, t2 in r, if t1[X] = t2[X] then t1[Y ] = t2[Y ]. An
instance r is inconsistent with respect to F if it does not satisfy it. Each FD can
be characterized by its confidence cF;r and its goodness gF;r [
Depending on the confidence value we have the following definition: Definition 3. Given a relation R, an instance r of R, a functional dependency F over R and its confidence cF;r, we say that F is an exact functional dependency iff cF;r = 1, otherwise it is an approximate functional dependency. 3
We start from the signature of the events of the BPMN to be analyzed and from the database storing the data of the process. Then, we automatically build the enriched log table, which is a new database table that essentially contains the contextual data of the initial event applied, together with the subsequent events. At runtime, the enriched log is filled with the real data of the processes. Then, to have the data ready for analysis, we have to discretize the continuous values of the enriched log since we are not interested in how a particular continuous value determines the next event, but on how a kind of values does. The resulting discrete enriched log is the basis for our conformance checking analysis. 3.1
Enriching the Log The enriched log table should contain all necessary attributes to store the contextual data of each event execution, plus an additional attribute to store the name of the successive event. The contextual data consist of the values given in the event’s input, together with all those values from the database that can be obtained through joins following the foreign keys.
We obtain these contextual attributes by looking at the UML types of the event’s arguments. Then, we pick the attributes in the relational tables implementing these UML types and chase the foreign keys of these tables recursively to obtain more tables (and attributes). Note that, since this process is essentially a chase of foreign keys, we need to pay special attention to foreign key cycles. Indeed, chasing foreign key cycles never stops, thus, we should eventually break these cycles at some predefined point. Intuitively, this is done by deciding how many nested levels of joins we want to perform.
This process can be performed at compile time since the contextual attributes are fully determined by the user’s given operation signature, the database schema, and the mapping between the UML schema and the underlying relational schema. At runtime we store each execution of the transition under study in a single row (tuple) of the enriched log. That is, whenever we detect an execution of the targeted transition, we query the database using the given event argument values to obtain the values for all its attributes. In the same row, we also store the next event applied by the user. 3.2
Discretization The existence of a functional dependency (FD) depends, of course, on the data, and indeed, two different discretizations of the data may affect the fact that the dependency holds or not in the obtained table. Consider the FD F : Distance ! Outcome, meaning that a taxi driver decides to accept or reject a request only based on the distance. Suppose that the attribute Distance has been discretized to assume the values fshort; longg and that the data satisfy the FD. If we change the discretization of the Distance to the domain fshort; medium; longg, then it is likely that the data will not satisfy the FD any longer, because now some tuples having medium distance will belong to the accepted category, while others with different, but still medium, distance, will be among the rejected ones.
These observations also hold for FDs that involve more than one attribute. Consider F : Distance; P rice ! Outcome, that is, a taxi driver decides to accept or reject a request based on the distance and price of the offer. It is also possible that we find an “appropriate” discretization of the two attributes Distance and P rice such that the tuples satisfy the FD. Note that most discretization techniques are univariate, that is, they consider only one feature at a time and can be used to discretize Distance and P rice independently of one another. However, the two attributes are involved in the FD together, thus a multivariate discretization, performed on the two attributes together, would be more appropriate.
One way to perform multivariate discretization is by means of clustering techniques: data can be clustered according to the values of the attributes Distance and P rice, thus, each cluster contains data with a certain combination of ranges of the domains of the two attributes. Then each cluster can be given a label that is the symbolic representation of such combination of domain ranges. This label can be interpreted as a single categorical attribute, that takes the place of the two attributes Distance and P rice. Therefore, a FD is influenced by the discretization process, but can also be used, conversely, to guide the discretization task. In fact, given a FD, we can try and find a discretization of the antecedent such that the FD would hold on the current data: for the FD to hold on the data, the antecedent must have at least the same amount of distinct values as the consequent (ideally each of them should be related to exactly one of the distinct values of the consequent) or more (more than one distinct value of the antecedent is related to the same value of the consequent). If this is true, then the confidence of the FD will be 1 (thus an exact FD) otherwise it will be less than 1 (thus an approximate FD). The greater the amount of distinct values of the antecedent and of the consequent, the worse the goodness of the FD.
Let r be an instance of a relation R, F : X ! Y an FD defined on it and K = j Y (r)j the number of distinct values of the consequent of the FD. The process of discretization, under the guidance of F , consists in finding K homogeneous clusters of the tuples based on their values of X. If such clustering exists it represents a multivariate discretization of X such that F holds on the discretized data. 3.3
Applying Functional Dependency Evolution
Given a FD that is no longer valid, there are two ways to capture the modeled
reality again: (i) try to change the way the attributes in the FD antecedent are
discretized, so that the dependency holds again, (ii) keep the same discretization
and “strengthen” the antecedent of the FD by adding an attribute to it.
Consider the example of Section 3.2 and suppose both price and distance vary in the
range [
Fig. 3. Taxi service running example the tuples in Figure 3(1)(A). After discretization we obtain the data in (2)(A) satisfying F with cF =1 and gF =0. By running the K-means algorithm (with K=2) we find two homogeneous clusters: C1 with centroid distance=29 and of f eredP rice=79.333 where all tuples have accepted=1 and C2 with centroid distance=75 and of f eredP rice=25 where all tuples have accepted=0. Thus, C1 represents (accepted) offers with short distance and high price while C2 represents (rejected) offers with long distance and low price. We can also discretize the data assigning them the label of the cluster to which they belong (as shown in Figure 3(3)(A)).
Now, suppose that the two tuples in Figure 3(1)(B) arrive. The first tuple still satisfies the FD but the second one does not. Therefore, the FD is not satisfied any longer. By running the K-means algorithm again on the data we find C1 (centroid distance=29, of f eredP rice=79.333), where all tuples have accepted=1; and C2 (centroid distance=75, of f eredP rice=25), where 60% of tuples have accepted=0 and the rest accepted=1, i.e., a non-homogeneous cluster. Thus, C1 still represents accepted offers with short distance and high price while C2 mixes tuples having different ranges of distance and price and different outcomes.
Now, we can choose different strategies: (i) accept approximate FDs, and decide that cF =2/3 is still a good confidence for the FD: nothing should be changed in this case; (ii) try to find a different discretization of the data such that the FD would hold on them: the data discretization should be changed; (iii) choose to evolve the FD by looking for attributes that can be added to its antecedent in order to repair it: the FD should be changed.
Suppose that we decide that the new confidence of the FD is too low and try
to re-cluster the data with K=3. Then, we find 3 homogeneous clusters whose
centroids are: C1: distance=27.5 and of f eredP rice=74 with accepted=1; C2:
distance=80 and of f eredP rice=20 with accepted=0; C3: distance=32.5 and
of f eredP rice=12.5 with accepted=1. In fact, if we associate each tuple with
the label of the cluster it belongs to (see Figure 3(4)(A-B)), instead of distance
and of f eredP rice, we can see that the functional dependency F holds on these
data with cF =1 and gF =1. As data continue to arrive the confidence of the FD
might continue to decrease: we could try to change the discretization again but
there might be a point where this would not be possible anymore. For example,
suppose the two new tuples shown in Figure 3(1)(C) are added to the data: a
homogeneous clustering is found only at K=9, when each cluster contains only one
tuple! Thus, no discretization can bring the data to satisfy the FD. At this point
we can choose to change the FD, looking for a minimal set of attributes that can
be added to its antecedent in order to restore a high confidence value. To this
end we apply the technique for evolving FD in [
Several proposals perform conformance checking over process models and logs
considering the data. Most of them use procedural models [
Our approach for conformance checking of artifact-centric BPMN models determines whether the actual execution of a business process conforms to the model and, by analyzing the data dependencies, proposes changes to the model accordingly.