Studies on the
Discovery of Declarative Control Flows
from Error-prone Data
Claudio Di Ciccio12‡ and Massimo Mecella1†
1
Sapienza – Università di Roma, Rome, Italy
†
mecella@dis.uniroma1.it
2
Wirtschaftsuniversität Wien, Vienna, Austria
‡
claudio.di.ciccio@wu.ac.at
Abstract. The declarative modeling of workflows has been introduced
to cope with flexibility in processes. Its rationale is based on the idea
of stating some basic rules (named constraints), tying the execution of
some activities to the enabling, requiring or disabling of other activities.
What is not explicitly prohibited by such constraints is implicitly consid-
ered legal, w.r.t. the specification of the process. Declarative models for
workflows are based on a taxonomy of constraint templates. Constraints
are thus instances of constraint templates, applied to specific activities.
Many algorithms for the automated discovery of declarative workflows
associate to each constraint a support. The support is a statistical mea-
sure assessing to what extent a constraint was respected during the enact-
ment(s) of the process. In current state-of-the-art literature, constraints
having a support below a user-defined threshold are considered not valid
for the process. Thresholds are useful for filtering out guesses based on
possible misleading events, reported in logs either because of errors in
the execution, unlikely process deviations, or wrong recordings in logs.
The latter circumstance can be considered extremely relevant when logs
are not written down directly by machines reporting their work, but ex-
tracted from other source of information. Here, we present an insight on
the actual capacity of filtering constraints by modifying the threshold for
support, on the basis of real data. Then, taking a cue from the results
performed on such analysis, we consider the trend of support when con-
trolled errors are injected into the log, w.r.t. individual constraint tem-
plates. Through these tests, we demonstrate by experiment that each
constraint template reveal to be less or more robust to different kinds of
error, according to its nature.
Keywords: process mining, artful process, declarative workflow, noisy
event log
1 Introduction
Processes are typically represented as graphs, delineating their possible execu-
tions altogether, from the beginning up to the end. Most of the used notations are
indeed derived by Petri Nets [2], such as Workflow Nets [1], BPMN [8], YAWL
31
[4]. The classical approach is called “imperative” because it explicitly represents
every step allowed by the process model at hand. This leads to the likely increase
of graphical objects as the process allows more alternative executions. The size
of the model, though, has undesirable effects on the understandability and also
on the likelihood of errors (see [18] for an insight of the Seven Process Model-
ing Guidelines): larger models tend to be more difficult to understand [19], not
to mention the higher error probability which they suffer from, with respect to
small models [17].
The declarative workflow models [22] have been introduced to cope with
flexibility in processes. Its rationale is based on the idea of stating some ba-
sic rules (named constraints), tying the execution of some activities to either
the enabling, requiring or disabling of other activities. What is not explicitly
prohibited by such constraints is implicitly considered legal, w.r.t. the specifica-
tion of the process. Declarative models for workflows are based on a taxonomy
of constraint templates. Constraints are thus instances of constraint templates,
applied to specific activities. A collection of constraints constitute altogether a
declarative workflow. ConDec [20], now renamed Declare, is the most used lan-
guage for modeling declarative workflows in the community of Business Process
Management. It provides an extendible list of constraint templates, which we
will consider in the remainder of this paper. Declarative models are particularly
effective with some non-conventional kinds of process. For instance, professors,
researchers, information engineers and all those professionals contributing to the
production of a valuable but intangible products, such as knowledge, are com-
monly defined “knowledge workers” [23]. They are used to dealing with rapid
decisions among multiple choices, based on their expertise, competence and in-
tuition. There is an art in the management of their work. This is the reason for
the name assigned to their processes: artful processes [14], which belong to the
larger category of knowledge-intensive processes [9]. Artful processes are thus
very flexible, dynamic and subject to change. Due to their characteristics, the
declarative approach suits to their modeling [5]. Mining their workflow would be
of extreme interest for understanding the best practices and winning strategies
adopted by expert knowledge workers.
Process Mining [3], a.k.a. Workflow Mining [2], is the set of techniques that
allow the extraction of process descriptions, stemming from a set of recorded real
executions. Such executions are intended to be stored in so called event logs, i.e.,
textual representations of a temporarily ordered linear sequence of tasks. Many
techniques have been proposed for mining Declare workflows ([16,15,10,11,7,6]).
Most of them associate to each discovered constraint a support, i.e., a statis-
tical measure assessing to what extent a constraint was respected during the
enactment(s) of the process. Those discovered constraints having a support be-
low a user-defined threshold are considered not valid for the process. Thresholds
are useful for filtering out guesses based on possible misleading events, reported
in event logs either because of errors in the execution, or due to very unlikely
process deviations, or caused by wrong registrations of events in logs. The lat-
ter circumstance can be considered extremely relevant when event logs are not
written down directly by machines reporting their work, but extracted from
other sources of information. Artful processes, e.g., are known to be scarcely
32
automated [9]. Therefore, there are few possibilities to rely on classical system
logs, keeping track of their executions. As a matter of fact, despite the advent of
structured case management tools, many enterprise processes are still “run” over
email messages. Artful processes, for instance, often require the collaboration of
many actors, who usually share their information by means of email messages.
Thus, email messages are a valuable source of information and event logs can be
extracted out of them, relying on their content and meta-data (e.g., the delivery
timestamp). [12] presents a novel approach and a tool, named MailOfMine, de-
signed to mine declarative workflows for artful processes out of email collections.
First, MailOfMine inspects subjects, bodies and headers of given archives of
email messages: assuming that reading about the execution of an activity can
be interpreted as the reporting of its actual enactment, it searches the email
messages where one among a list of user-defined expressions is found. Each is
considered an event. Then, considering the temporal ordering of email messages
in every archive, a trace in the log is built accordingly. Such log is passed to the
MailOfMine control flow discovery algorithm (MINERful), which returns the
declarative model for the artful process laying behind the email communications
analyzed. Extracting logs out of email messages leads to possible errors though,
due to the automated interpretation of semi-structured texts. Hence, such ex-
tracted logs are intrinsically prone to errors. Thereby, mistakes in the discovered
workflow are likely to increase.
This is actually the question we search an answer for in this paper: what
happens to unknown models when they are discovered on the basis of logs which
are affected by errors. [13] investigates an approach for repairing process models
basing on event data. Conversely, we consider the possible unreliability of data
which process models are discovered from, supposing that process models were
not previously known at all. In this paper, we first report the analysis of the
results obtained by applying MailOfMine to real data, focused on the precision
of the inferred model with respect to the support threshold. Then, we present an
insight on the trend of the support in presence of errors, injected into synthetic
logs. We focus on different types of errors (insertion or deletion of events) and
spreading policies (a given percentage per each trace or all over the log). We
repeat our experiments for each of the possible constraint templates that the
MINERful algorithm is able to discover. Thus, we aim at understanding the
different levels of robustness that constraint templates show w.r.t. the different
types of errors.
The remainder of the paper is as follows. Section 2 describes the constraint
templates of Declare and their usage for describing a declarative process model.
Section 3 reports the results of tests on real data (Section 3.1) and experiments
conducted on the basis of tunable injection of errors into synthetic logs (Sec-
tion 3.2). Section 4 concludes this paper and outlines the future paths for our
investigation that this paper sheds light on.
2 The declarative process model
Here we abstract activities as symbols (e.g., ρ, σ) of an alphabet Σ, appearing
in finite strings, which, in turn, represent process traces. We will interchange-
33
ably use the terms “activity”, “character” and “symbol”, as well as “trace”
and “string”, then. We adopt the subset of Declare taxonomy of constraints for
modeling processes, as in [16]. For a comprehensive analysis of all the constraint
templates in Declare, the reader can refer to [20,21].
Constraints are temporal rules constraining the execution of activities.
E.g., Response(ρ, σ) is a constraint on the activities ρ and σ, forcing σ
to be executed if the ρ activity was completed before. Such rules are
meant to adhere to specific constraint templates. RespondedExistence is the
template of RespondedExistence(ρ, σ). We further categorize constraint tem-
plates into constraint types. For instance, RespondedExistence belongs to the
RelationConstraint type. Figure 1 depicts the subsumption hierarchy of Declare
constraints.
Declare constraints are always referred to an activity at least, which we call
“implying”: if it is executed, the constraint is triggered – vice-versa, if it does
not appear in the trace, the constraint has no effect on the trace itself. The
Existence(M, ρ) constraint imposes ρ to appear at least M times in the trace.
We rename Existence(1, ρ) as Participation(ρ). The Absence(N, ρ) constraint
holds if ρ occurs at most N − 1 times in the trace. We call Absence(2, ρ) as
Uniqueness(ρ). Init(ρ) makes each trace start with ρ.
The aforementioned constraints fall under the type of ExistenceConstraints,
as they relate to an “implying” activity only. The following are named
RelationConstraints, since the execution of the implying imposes some condi-
tions on another activity, namely the “implied”.
RespondedExistence(ρ, σ) holds if, whenever ρ is read, σ was either al-
ready read or going to occur (i.e., no matter if before or afterwards). In-
stead, Response(ρ, σ) enforces it by requiring a σ to appear after ρ, if ρ was
read. Precedence(ρ, σ) forces σ to occur after ρ as well, but the condition
to be verified is that σ was read - namely, you can not have any σ if you
did not read a ρ before. AlternateResponse(ρ, σ) and AlternatePrecedence(ρ, σ)
strengthen respectively Response(ρ, σ) and Precedence(ρ, σ) by stating that each
ρ (σ) must be followed (preceded) by at least one occurrence of σ (ρ). The
“alternation” is in that you can not have two ρ’s (σ’s) in a row before σ
(after ρ). ChainResponse(ρ, σ) and ChainPrecedence(ρ, σ), in turn, specialize
AlternateResponse(ρ, σ) and AlternatePrecedence(ρ, σ), both declaring that no
other symbol can occur between ρ and σ. The difference between the two is
in that the former is verified for each occurrence of ρ, the latter for each oc-
currence of σ. The reader should note that the hierarchy under the Precedence
constraint template does not inherit the base and implied symbols from the
RespondedExistence parent; it overrides them both by inverting the two, instead.
This is due to the semantics of the constraints themselves.
The MutualRelation constraints follow: they are verified iff two
RespondedExistence (or descendant) constraints (resp., (forward
and backward , in Figure 1) are satisfied. CoExistence(ρ, σ) holds
if both RespondedExistence(ρ, σ) and RespondedExistence(σ, ρ) hold.
Succession(ρ, σ) is valid if Response(ρ, σ) and Precedence(ρ, σ) are ver-
ified. The same holds with AlternateSuccession(ρ, σ), equivalent to the
conjunction of AlternateResponse(ρ, σ) and AlternatePrecedence(ρ, σ),
34
and ChainSuccession(ρ, σ), with respect to ChainResponse(ρ, σ) and
ChainPrecedence(ρ, σ).
Finally, we consider NegativeRelation constraints: they are satisfied iff the re-
lated MutualRelations (negated , in Figure 1) are not. NotChainSuccession(ρ, σ)
expresses the impossibility for σ to occur immediately after ρ (the opposite
of ChainSuccession(ρ, σ)). NotSuccession(ρ, σ) generalizes the previous by im-
posing that, if ρ is read, no other σ can be read until the end of the trace
(Succession(ρ, σ) is the negated constraint). NotCoExistence(ρ, σ) is even more
restrictive: if ρ appears, not any σ can be in the same trace (the contrary of
CoExistence(ρ, σ)).
Fig. 1: The declarative process model’s hierarchy of constraints. Taking into ac-
count the UML Class Diagram graphical notations, the Generalization (“is-a”)
relationship represents the subsumption between constraint templates. The sub-
sumed is on the tail, the subsuming on the head. The Realization relationships
indicate that the constraint template (and the subsumed in the hierarchy) be-
long to a specific type. Constraint templates are drawn as solid boxes, whereas
the constraint types’ boxes are dashed.
As a brief example, we may want to model the process of defining an agenda
for a research project meeting. The schedule is discussed by email among the
participants. We suppose that a final agenda will be committed (“confirm” –
n) after that requests for a new proposal (“request” – r), proposals themselves
(“propose” – p) and comments (“comment” – c) have been circulated.
The aforementioned activities are bound to the following constraints, then.
If a request is sent, then a proposal is expected to be prepared afterwards (cf.
Response(r, p)). Comments can be given in order to review a proposed agenda,
or for soliciting the formulation of a new proposal. Thus, the presence of c in the
trace is constrained to the presence of p (cf. RespondedExistence(c, p)). A con-
firmation is supposed to be mandatorily given after the proposal, and vice-versa
any proposal is expected to precede a confirmation (cf. Succession(p, n)). We
35
suppose the confirmation to be the f inal activity (cf. End (n)). This mandatory
task (cf. Participation(n)) is not expected to be executed more than once (cf.
Uniqueness(n)).
Hence, the example process consists in the six aforementioned constraints:
Response(r, p), RespondedExistence(c, p), Succession(p, n), Participation(n),
U niqueness(n) and End(n). As an example, the following traces would be com-
pliant to the workflow: pn, pcn, rpcn, rpcpn, rrpcrpcrcpcn, rpprpcccrpcn.
3 Experiments and evaluation
In order to inspect the quality of the control flow discovery in presence of error-
prone logs, we first verified the whole MailOfMine system on real data (Sec-
tion 3.1). There, data were extracted from the mailbox of an authors’ colleague,
known to be an expert in the area of the process to discover. As usual for art-
ful processes, the process behind the analyzed email messages was not known
a priori. Therefore, we could not apply an automated comparison between the
resulting workflow model and the originating process, since no definition for
the originating process was available at all. Thus, the expert was requested to
analyze and assess the discovered workflow model by categorizing the mined
constraints. Being real data, the presence of errors in the phase of the extraction
of event logs out of email messages was not tunable.
Thereafter, we created synthetic logs, where errors of different kinds were
injected into event logs. Every event log was created as adhering to the specifi-
cation of declarative processes comprising a single constraint at a time. For each
log, i.e., a different constraint template was considered. Being known a priori
the only constraint to be considered valid, when mined out of the synthetic log,
we focused on the trend of its support, in order to monitor the robustness of the
template w.r.t. given types of errors. We outline the results of that analysis in
Section 3.2.
3.1 A real case study
As real data to conduct the experiments on, we took 6 mailbox IMAP fold-
ers containing email messages which concerned the management of 5 different
European research projects (Figure 1a). Such folders belonged to a domain ex-
pert. Our aim was to use MailOfMine in order to discover the artful process
of managing European research projects and validate the result, together with
him.
In order to ease the revision process of the gathered results, we restricted
the number of activities for the process to discover to 13. 8.998% of the total
amount of email messages were considered related to the execution of an activity.
The setup and the results of the inspection of email messages for extracting a
log is quantitatively summarized in Table 1b. The log was passed to the control
flow discovery algorithm, which returned a process model comprising c.a. 200
constraints. Each was verified to hold true within the log and associated to a
support exceeding the user-defined threshold of 80%.
36
Mailbox
1 2 3 4 5 6 Total
Messages 3523 39 844 4 746 1 479 60 8 770
(a) The input
Activities 13 Noticeably right discovered constraints 14 (6.422%)
Traces 6 Right discovered constraints 173 (69.725%)
Events 139 Wrong discovered constraints 45 (20.642%)
Discovered constraints 218 Utterly wrong discovered constraints 7 (3.211%)
(b) Retrieved information and mined constraints
Table 1: Evaluation of MailOfMine on real data: setup and results
In order to assess the validity of the mined process, we checked every con-
straint with the expert. This allowed us for a quantitative evaluation.For each
constraint in the list, we asked him whether it was either: (i) right, i.e., it
made sense with respect to his experience; (ii) noticeably right, i.e., it not only
made sense but also suggested some surprising mechanisms in the workflow; (iii)
wrong, i.e., not necessarily corresponding to reality; (iv) utterly wrong, i.e., not
corresponding to reality, unreasonable. The last level was assigned to quite few
constraints (7 out of 218), a half of how many were considered noticeably right
(14). The model is not known a priori, but the expert could classify as right or
wrong a guessed constraint. Then, the analysis helped us find only true positives
(TP , i.e., right or noticeably right) and false positives (FP , i.e., wrong or utterly
wrong). As a matter of fact, such situation of partial knowledge of the workflow
reproduces a real case, where the artful process had not ever been formalized
before.
TP
Recalling that Precision = TP+FP , the algorithm was proven to obtain a
Precision degree of 0.794 over the real case study. Table 1b summarizes the
encouraging results of this real case study evaluation. More than 75% of the
constraints inferred were compliant to a realistic model of the process. Figure 2
shows the trend of true positives, false positives and overall (i.e., the sum of
the preceding) constraints found, scaled in percentage by their total amount,
with respect to their support. The quantities on the ordinates are cumulative,
i.e., they represent the sum of the values which are gained up to the current
abscissa. The curves show how, as the support increases, the distance between
the cumulated false positives and the true positives grow. A line puts in evidence
where the relative percentage of confirmed constraints overtakes the wrong, i.e.,
a “breakpoint” after which the rate of hits, in terms of accepted guesses, is higher
than the rate of misses, in terms of wrong guesses. Such breakpoint corresponds
to a support value of 0.85 (i.e., 5% higher than the threshold established a pri-
ori), which is little enough to limit the number of true positives below that soil
to less than 10%. The same graph, although, depicts that more than 90% of
errors are given a support exceeding that soil as well. Thus, shifting the thresh-
old altogether would not lead to significant improvements in the quality of the
returned process. Hence, we studied the trend of support for error-injected logs,
taking into account and isolating the behavior of every constraint template to
different types of errors.
37
100
75
Constraints Discovered [%]
Constraints Discovered
Total
50
False positives
True positives
25 0.85
0
0.80 0.85 0.90 0.95 1.00
Support
Fig. 2: The trend of the cumulative sum of constraints discovered, scaled by their
total amount, w.r.t. the assigned support
3.2 Experiments over artificial error-injected logs
In order to test the robustness of MINERful with respect to the presence of
errors in logs, we built an additional testing module, which injected a controlled
amount of noise in the sequences of traces.
We identified three possible types of error injection:
1. insertion of spurious events in the log;
2. deletion of events from the log;
3. random insertion/deletion of events.
The errors were spread according to a given percentage3 . The tester could
also specify whether errors had to refer to a given activity, or not. In the latter
case, every insertion or deletion was applied to an event picked each time at
random.
In order to define how many errors had to be injected, and where, a spreading
policy was requested too. It could be either:
1. to calculate the number of errors to inject w.r.t. the whole log, and distribute
the error injections accordingly, or
2. to calculate the number of errors to inject w.r.t. every single trace, case by
case.
In the latter case, every trace was made affected by a number of errors, computed
on the basis of the number of target events in that trace. This reproduces a
systematic error, taking place in every registered enactment of the process. In
the former, some traces could remain untouched.
3
In case the calculated number of errors to inject resulted in a non-integer number,
the actual amount of errors was rounded up to the next integer (e.g., 0.2 was rounded
to 1 error to inject).
38
Thereupon, we conducted an extensive analysis on the reaction of MINERful,
the control flow discovery algorithm of MailOfMine, through an experiment
set up as summarized in Table 2.
Activities (target) 8 (1) Spreading policies 3
Generating constraints 18 Error types 3
Trace length [0, 30] Runs per combination 50
Log size 1 000 Error injection percentage [0, 30]
Total runs 167 400
Table 2: Setup of the experiments for monitoring the reaction of MINERful to
the controlled error injection into logs
We created 18 groups of 9 300 synthetic logs each. Every group was generated
so to comply to one constraint at a time, among the 18 templates involving a, as
the implying activity, and (optionally) b, as the implied (i.e., Participation(a),
Uniqueness(a), . . . , RespondedExistence(a, b), Response(a, b), . . . ). The alphabet
comprised 6 more non-constrained activities (c, d, . . . , h), totalling 8. We chose
a as the target activity for the injection of errors. Then, we injected errors in
the synthetic logs, with all of the possible combinations of the aforementioned
parameters ((i) insertion, deletion or random error type, (ii) over-string or over-
collection spreading policy, (iii) error injection percentage ranging between 0
and 30%) and ran the control flow discovery algorithm of MailOfMine on the
resulting altered logs. We collected the results and, for each of the 18 groups
of logs, analyzed the trend of the support for the generating constraint. I.e., we
looked at how the support for the only constraint which had to be verified all
over the log lowered, w.r.t. the increasing percentage of errors injected. We also
hightlighted those other constraints whose topmost computed support exceeded
the value of 0.754 , being them the most likely candidates to be false positives in
the discovery.
The analysis of within-trace error-injected logs revealed to be more effective
in stressing the resilience of constraints with respect to certain types of errors. In
other words, it showed the structural weaknesses of constraint templates w.r.t.
some types of error even for small percentages of injected errors. For instance,
the support of End (a)’s (Figure 3) is not affected by the insertion of spurious a’s
in the traces (see Figure 3a), whereas it suffers from deletions of a’s (Figure 3b).
In Section 2 we described the mechanism tying MutualRelation constraints to
forward and backward -related constraints, as in the case of AlternateSuccession
w.r.t. AlternateResponse and AlternatePrecedence. Then, here we remark that
since (i) the support for AlternateResponse(a, b) remains unchanged in case of
spurious inserted a’s (Figure 4a), but not in case of deleted a’s (Figure 4b), whilst
4
We recall that assigning a constraint the support of 0.5 would be equivalent to
asserting that such constraint would hold if, tossing a coin, a cross was shown in the
end. Thereby, 0.75 is the least value of the topmost half of the “reliable” range.
39
(ii) conversely, the support for AlternatePrecedence(a, b) remains unchanged in
case of deleted a’s (Figure 4c), but not in case of inserted spurious a’s (Figure 4d),
AlternateSuccession inherits the sensitivity towards errors of both, resulting in
a decreasing support for both faulty insertions and deletions of a’s (Figure 5).
The analysis of over-collection error-injected logs showed smoother changes
in curves, since errors are spread on a wider area of appearances, for the tar-
geted activity. Therefore, it reveals a more realistic trend for the assessment of
discovered constraints in presence of errors. We reasonably expect to have sparse
errors in logs, rather than a fixed percentage of faults for every trace, as a matter
of fact.
Along a branch in the constraints hierarchy (see Figure 1), we expect that
the more a constraint is restrictive, the more its support decreases in terms of
deviations from the expected behavior. We can prove it by evidence in, e.g.,
Figure 6, where the curve’s slope gets steeper as we analyze the subsumed
constraints along the MutualRelation constraints (i.e., CoExistence, Succession,
AlternateSuccession, ChainSuccession).
The interested reader can download the whole collection of graphs depicting
the gathered results at the following address:
http://www.dis.uniroma1.it/~cdc/code/minerful/latest/
errorinjectiontestresults.zip
End_a trend: End_a trend:
'a'−targeted, insertion 'a'−targeted, deletion
over strings errors over strings errors
100 100
100 Ear
P
R nd
estic
po
_aip
nd
ns
100
ate_
ed
ion_ Res
100 b_
Exia
_a
sten po
nd
Not
U ce U ed
A C
niqu
Nlte _b Nni Exi
otCrnha __ Rot
esqu
Cha sten
atin
en
ha eR
esSuc a
Not po
en ce
ines
in s_ ce
Ses b ss
ucpo Chanse_ Ss_
ucb _b
__
cension_ inS b_ce ss a
sse_ a_
ion_
b_ _b Par uc _a ion_
_a tic ce a_
b_ ipat ss
_a ion_ _b
ion_ b_
Alte a _a
rnat
Pre eR
ce es
de End po
nc ns
Not e_ _a e_
S a_ Not b_
Alte ucce _a
75 rnat ssio
_b
75 78.652 Suc
ce
eP n_a_ ss
ion_
rece _b
de Pre a_
Not nc ce _b
Suc e_ de
ce a_ nc
ss _b e_
ion_ a_
_b
b_
_a
Mean Support [%]
Mean Support [%]
Alte
rnat
eP
rece
de
nc
e_
a_
_b
50 50
25 25
0 0
0 10 20 30 0 10 20 30
Error percentage [%] Error percentage [%]
(a) The trend of the support for End (a), (b) The trend of the support for End (a),
w.r.t. the percentage of spurious events w.r.t. the percentage of events deleted
inserted into every string from every string
Fig. 3: The trend of the support for End , w.r.t. the errors injected in the log,
within every trace
40
AlternateResponse_a__b trend: AlternateResponse_a__b trend:
'a'−targeted, insertion 'a'−targeted, deletion
over strings errors over strings errors
100 100
100 R
Ces
R
R
S oEpo
es
Puc
re xistnd
po
esce
100 Rlte
A es
rn
poat
ndeR
ns
pode
ce nded
nsen
ss edceExi
io
nc 100 e_
edes
a_
Exi
po
e_n_E_a
a__b
e_ sten
xist _b
stns
_b__
a_
a__benabce
_b
ene_
cea_
ce_a _a_b
_b__ __
__b b
a
CoE
xist
en
Res ce
Suc po _a
_b
__
ce nd ab
ss ed
ion_Exi
a_sten
Alte Pre _b ce
rnat ce _b
de __
eR a
80.94604 es
po
ns Uni
nc
e_
a_
e_ _b
75 a_
_b 75 qu
en
es
Not s_
Cha a
inS
uc
ce
ss
ion_
a_
_b
Mean Support [%]
Mean Support [%]
50 50
25 25
0 0
0 10 20 30 0 10 20 30
Error percentage [%] Error percentage [%]
(a) The trend of the support for (b) The trend of the support for
AlternateResponse(a, b), w.r.t. the per- AlternateResponse(a, b), w.r.t. the per-
centage of spurious events inserted into centage of spurious events inserted into
every string every string
AlternatePrecedence_a__b trend: AlternatePrecedence_a__b trend:
'a'−targeted, insertion 'a'−targeted, deletion
over strings errors over strings errors
100 100
100 Rre
A
P lte
esce
rn
pode
at
ndeP
100
nc
edre
100 e_
Ece
xi
a_st
de
_b
en
ncce
e__b
Uni a___ Uni
_ba qu
qu Res
en
es poenes
s_ nd s_
b ed b
Exi
sten
Pre ce
Not _b
ce __
Cha de a
inS Not nc
C e_
Cha uc A oErnhain a__b
Clte
CoE ce
inP ss xiat
stenS
xistre ion_ eP ucce
encede
ce nc
b_
_a 80.77024
Res
rece ss
ce
_ade io
_b
__ncn_
Res _a e_
_b po ab e_b_
75 po
nd
__ a_
ab _b 75 nd
ed
Exi
a__a
_b
Not ed sten
Exi Uni
Cha sten ce
inS ce qu _a
uc _a en __
ce __ es b
ss b s_
ion_ a
a_
_b
Mean Support [%]
Mean Support [%]
Cha
inP
rece
de
nc
e_
a_
_b
50 50
25 25
0 0
0 10 20 30 0 10 20 30
Error percentage [%] Error percentage [%]
(c) The trend of the support for (d) The trend of the support for
AlternatePrecedence(a, b), w.r.t. the per- AlternatePrecedence(a, b), w.r.t. the per-
centage of events deleted from every centage of events deleted from every
string string
Fig. 4: The trend of the support for AlternateResponse and AlternatePrecedence,
w.r.t. the errors injected in the log. The error injection policies under exam are
both the insertion and deletion of a events, within each trace.
41
AlternateSuccession_a__b trend: AlternateSuccession_a__b trend:
'a'−targeted, insertion 'a'−targeted, deletion
over strings errors over strings errors
100 100
100 P
R
Are
C lte
es
oEce
rn
po
xide
at
stndeP
100 Alte
R es
rn
poat
ndeR
ns
Suc en nc
edce
re
e_ e_
edes
ce Ece
_a
_b
xi
a_st a_
Exi
po
Res ssio de
__
_b _b
stns
enab ene_
po n_a_ nc ce
e__b
_a
cea_
_a_b
ns a___ __
e_ _b _bab b
a_
_b
Uni
qu
en
es
s_
Alte a
CoE
rn Uni xist
Uni ateS
Sucquenence
84.10916 qu
en ucce
es ce ess__b _a
s_ ssion_ ss
ion_ b __ab
b a_
_b Alte a_
_b
rnat
75 75 Not
R
76.6286 Cha uc
eS
N
Alte
otC Nes
otSpondinS cess
rnha
atin uc educ io
eR Ses ce Exi ce n_a_
uc Pre ss stss
po
ce ce ion_ enion_ _b
Not ss
ns io
e_n_ de b_ ce_b
b_
Suc a_b_ nc _a __ _a
ce _b_a e_ a
ss a_
_b
Mean Support [%]
Mean Support [%]
ion_
b_ Alte
_a
rnat
eP
rece
Uni de
qu nc
en e_
es a_
s_ _b
a
50 50
25 25
0 0
0 10 20 30 0 10 20 30
Error percentage [%] Error percentage [%]
(a) The trend of the support for (b) The trend of the support for
AlternateSuccession(a, b), w.r.t. the per- AlternateSuccession(a, b), w.r.t. the per-
centage of spurious events inserted into centage of events deleted from every
every string string
AlternateSuccession_a__b trend:
'a'−targeted, insertion/deletion (random proportion)
over strings errors
100
100 Res
po
nd
ed
Exi
sten
Res ce
CoE po _a
xistnse_ __
b
en a_
ce _b
_a
_b
Suc __
ab
Rescess
po ion_
nd a_
ed _b
P Exi
Ure
niqu sten
ce ce
de
ennc _b
ese_ __
A s_ a_ a
Alte
A ltern b _b
lte rnat
rn ateP
at eSre
eR
75 78.16596 Uot
N
uc
esce
ce
pode
ss
niqu nsnc
io e_
Cha e_n_
enin a_
a_a_
es
Ss_ _b
_b_b
uca
ce
Not ss
ion_
Suc b_
ce _a
ss
ion_
Mean Support [%]
b_
_a
50
25
0
0 10 20 30
Error percentage [%]
(c) The trend of the support for
AlternateSuccession(a, b), w.r.t. the per-
centage of both deletions and insertions,
applied to every string
Fig. 5: The trend of the support for AlternateSuccession, w.r.t. the errors injected
in the log, within each trace.
42
CoExistence_a__b trend: Succession_a__b trend:
'a'−targeted, insertion/deletion (random proportion) 'a'−targeted, insertion/deletion (random proportion)
over collection errors over collection errors
100 100
100 R
C es
RoE
espo
xistnd
po
100 Res
CoEpo
R
P es xi nd
re
ndened Succepost ed
de E
99.1705 edceExi R esce nden
E_b
_a
xist
st__en possncedce xist
e_
E_b
_a
xi en
enabce nsion_ a_st__ ce
ce_b
_a__ 96.88432
A
e_ a_ _b
a_ _b enab _b
_b ce_a__
__a
b lte
rnat __a
b
eP
rece
de
nc
e_
a_
_b
Pre
Succede
R
Par
escessnc
po io e_
tic Not
Par ipns a_
ate_n_a_ _b Cha
Notticip ion_a_ _b inS
75 Chaatio a
inS n_b
_b
75 uc
ce
ss
uc ion_
ce b_
ss _a
ion_
b_
_a
Mean Support [%]
Mean Support [%]
50 50
25 25
0 0
0 10 20 30 0 10 20 30
Error percentage [%] Error percentage [%]
(a) The trend of the support for (b) The trend of the support for
CoExistence(a, b), w.r.t. the percentage Succession(a, b), w.r.t. the percentage
of both event deletions and insertions, of both event deletions and insertions,
spread over the whole log spread over the whole log
AlternateSuccession_a__b trend: ChainSuccession_a__b trend:
'a'−targeted, insertion/deletion (random proportion) 'a'−targeted, insertion/deletion (random proportion)
over collection errors over collection errors
100 100
100 100 Res
CoEpo
R
Ces
oEpo
xistnd Res xistnded
ened Pre pondenceExist
ceE Succede edE_b _a en
Pre _a
_b
xist
Suc ce __en
abce Resce nc xist__abce_b
Rescedenc _a
_b possio e_a_ ence __a
possio e_ __ ns n_ _b _a
ns n_ a_ ba e_ a_ __
Alte e_ a_ _b a_ _b b
_b
rnat a__b_b A
eP Clte
harn
rece inPateP
Alte de recere
rnat nc A dece
Uni eS e_ Clte
harn ncde
a_ nc
84.48992
Altequ
rnen es
uc
ce
ss
_b
A
inSateS
uc uc
e_ e_
a_ a_
_b _b
ateRs_
Uni esb
ion_
a_
82.29786Clte
harn
inR
ce ce
ateR ioss
ss
n_ion_
qu po _b es es a_ a_
Not en ns po po _b _b
e_
75 Cha ess_ a_
_b 75 ns ns
e_ e_
inS a a_ a_
uc _b _b
ce
ss
Not ion_
Suc b_
_a
ce
ss
ion_
b_
Mean Support [%]
Mean Support [%]
_a
50 50
25 25
0 0
0 10 20 30 0 10 20 30
Error percentage [%] Error percentage [%]
(c) The trend of the support for (d) The trend of the support for
AlternateSuccession(a, b), w.r.t. the per- ChainSuccession(a, b), w.r.t. the percent-
centage of both event deletions and inser- age of both event deletions and insertions,
tions, spread over into the whole log spread over into the whole log
Fig. 6: The trend of the support for the MutualRelation constraints, w.r.t. the
errors injected in the log. The error injection policy under exam is the random
insertion/deletion of a events, over the whole log.
43
4 Conclusions
Throughout this paper, we have analyzed the problem of discovering declara-
tive workflows out of event logs which are affected by errors. To this aim, we
first assessed the quality of a model, mined out of real data. We used a single
threshold level for the estimated support of discovered constraints, in order to
determine whether they could be considered valid for the mined process or not.
The obtained results suggested that adjusting the level of such threshold did not
considerably enhance the quality of the mined process altogether. Therefore, for
each constraint in the set of Declare templates, we investigated the trend of its
own estimated support with respect to the amount of errors injected into logs.
By means of experiments carried out on synthetic data, we showed that the se-
mantics of constraint templates actually affect their degree of robustness w.r.t.
the presence or spurious events or the absence of expected ones in the log.
Starting from these results, we will investigate the problem of defining an
automated approach for the self-adjustment of user-defined thresholds, on the
basis of the nature of each discovered constraint. Intuitively, indeed, a more
“robust” constraint should be considered valid in the log (and therefore for the
process) if its support exceeds a higher threshold. On the contrary, the threshold
should be diminished for more “sensitive” ones. We also aim at mixing such an
approach with the analysis of different metrics, pertaining to the number of times
an event occurred in the log. The intuition is that the more an event is frequent
in the log, the less it can be considered subject to errors. Such metrics have been
already considered in literature ([15]) for assessing the relevance of discovered
constraints. We want to exploit them for estimating the reliability of constraints
in mined processes as well.
References
1. van der Aalst, W.M.P.: Verification of workflow nets. In: Azéma, P., Balbo, G.
(eds.) ICATPN. Lecture Notes in Computer Science, vol. 1248, pp. 407–426.
Springer (1997).
2. van der Aalst, W.M.P.: The application of petri nets to workflow management.
Journal of Circuits, Systems, and Computers 8(1), 21–66 (1998).
3. van der Aalst, W.M.P.: Process Mining: Discovery, Conformance and Enhancement
of Business Processes. Springer (2011).
4. van der Aalst, W.M.P., ter Hofstede, A.H.M.: YAWL: yet another workflow lan-
guage. Inf. Syst. 30(4), 245–275 (2005).
5. van der Aalst, W.M.P., Pesic, M., Schonenberg, H.: Declarative workflows: Bal-
ancing between flexibility and support. Computer Science - R&D 23(2), 99–113
(2009).
6. Alberti, M., Chesani, F., Gavanelli, M., Lamma, E., Mello, P., Torroni, P.: Veri-
fiable agent interaction in abductive logic programming: The SCIFF framework.
ACM Trans. Comput. Log. 9(4), 29:1–29:43 (August 2008).
7. Chesani, F., Lamma, E., Mello, P., Montali, M., Riguzzi, F., Storari, S.: Exploiting
inductive logic programming techniques for declarative process mining. T. Petri
Nets and Other Models of Concurrency 2, 278–295 (2009).
44
8. Decker, G., Dijkman, R.M., Dumas, M., Garcı́a-Bañuelos, L.: The business process
modeling notation. In: ter Hofstede, A.M., van der Aalst, W.M.P., Adamns, M.,
Russell, N. (eds.) Modern Business Process Automation, pp. 347–368. Springer
(2010).
9. Di Ciccio, C., Marrella, A., Russo, A.: Knowledge-intensive processes: An overview
of contemporary approaches. In: ter Hofstede, A.H., Mecella, M., Sardina, S., Mar-
rella, A. (eds.) KiBP. vol. 861, pp. 33–47. CEUR Workshop Proceedings (06 2012).
10. Di Ciccio, C., Mecella, M.: Mining constraints for artful processes. In: Abramow-
icz, W., Kriksciuniene, D., Sakalauskas, V. (eds.) BIS. Lecture Notes in Business
Information Processing, vol. 117, pp. 11–23. Springer (05 2012).
11. Di Ciccio, C., Mecella, M.: A two-step fast algorithm for the automated discovery
of declarative workflows. In: CIDM. IEEE (04 2013).
12. Di Ciccio, C., Mecella, M., Scannapieco, M., Zardetto, D., Catarci, T.: MailOfMine
– analyzing mail messages for mining artful collaborative processes. In: Aberer, K.,
Damiani, E., Dillon, T. (eds.) Data-Driven Process Discovery and Analysis, Lecture
Notes in Business Information Processing, vol. 116, pp. 55–81. Springer (10 2012).
13. Fahland, D., van der Aalst, W.M.P.: Repairing process models to reflect reality. In:
Barros, A.P., Gal, A., Kindler, E. (eds.) BPM. Lecture Notes in Computer Science,
vol. 7481, pp. 229–245. Springer (2012).
14. Hill, C., Yates, R., Jones, C., Kogan, S.L.: Beyond predictable workflows: Enhanc-
ing productivity in artful business processes. IBM Systems Journal 45(4), 663–682
(2006).
15. Maggi, F.M., Bose, R.P.J.C., van der Aalst, W.M.P.: Efficient discovery of under-
standable declarative process models from event logs. In: Ralyté, J., Franch, X.,
Brinkkemper, S., Wrycza, S. (eds.) CAiSE. Lecture Notes in Computer Science,
vol. 7328, pp. 270–285. Springer (2012).
16. Maggi, F.M., Mooij, A.J., van der Aalst, W.M.P.: User-guided discovery of declar-
ative process models. In: CIDM. pp. 192–199. IEEE (2011).
17. Mendling, J., Neumann, G., van der Aalst, W.M.P.: Understanding the occur-
rence of errors in process models based on metrics. In: Meersman, R., Tari, Z.
(eds.) CoopIS. Lecture Notes in Computer Science, vol. 4803, pp. 113–130. Springer
(2007).
18. Mendling, J., Reijers, H.A., van der Aalst, W.M.P.: Seven process modeling guide-
lines (7PMG). Information & Software Technology 52(2), 127–136 (2010).
19. Mendling, J., Reijers, H.A., Cardoso, J.: What makes process models understand-
able? In: Alonso, G., Dadam, P., Rosemann, M. (eds.) BPM. Lecture Notes in
Computer Science, vol. 4714, pp. 48–63. Springer (2007).
20. Pesic, M.: Constraint-based Workflow Management Systems: Shifting Control
to Users. Ph.D. thesis, Technische Universiteit Eindhoven (10 2008), http://
repository.tue.nl/638413
21. Pesic, M., Schonenberg, H., van der Aalst, W.M.P.: Declare: Full support for
loosely-structured processes. In: EDOC. pp. 287–300. IEEE Computer Society
(2007).
22. Pesic, M., Schonenberg, M.H., Sidorova, N., van der Aalst, W.M.P.: Constraint-
based workflow models: Change made easy. In: Meersman, R., Tari, Z. (eds.)
CoopIS. Lecture Notes in Computer Science, vol. 4803, pp. 77–94. Springer (2007).
23. Warren, P., Kings, N., Thurlow, I., Davies, J., Buerger, T., Simperl, E., Ruiz, C.,
Gomez-Perez, J.M., Ermolayev, V., Ghani, R., Tilly, M., Bösser, T., Imtiaz, A.:
Improving knowledge worker productivity - the Active integrated approach. BT
Technologiy Journal 26(2), 165–176 (2009).
45