Efficient and Customisable Declarative Process Mining with SQL

Efficient and Customisable Declarative Process Mining with SQL Stefan Sch¨onig1, Andreas Rogge-Solti1, Cristina Cabanillas1, Stefan Jablonski2, and Jan Mendling1 1Vienna University of Economics and Business, Austria {firstname.surname}@wu.ac.at 2University of Bayreuth, Germany {stefan.jablonski}@uni-bayreuth.de Abstract. Flexible business processes can often be modelled more easily using a declarative rather than a procedural modelling approach. Process mining aims at automating the discovery of business process models. Existing declarative process mining approaches either suffer from performance issues with real-life event logs or limit their expressiveness to a specific set of constaint types. Lately, RelationalXES, a relational database architecture for storing event log data, has been introduced. In this paper, we introduce a mining approach that directly works on relational event data by querying the log with conventional SQL. By leveraging database performance technology, the mining procedure is fast without limiting itself to detecting certain control-flow constraints. Queries can be customised and cover process perspectives beyond control flow, e.g., organisational aspects. We evaluated the performance and the capabilities of our approach with regard to several real-life event logs. Keywords: Declarative Process Mining, Relational Databases, SQL 1 Introduction Process mining is the area of research that embraces the automated discovery, conformance checking and enhancement of process models. All involved techniques are evidence-based, as the input is event logs that comprise a collection of computer recorded information that track the executions of process instances. Two different types of processes can be distinguished [1]: well-structured routine processes with exactly predescribed control flow and flexible processes whose control flow evolves at run time without being fully predefined a priori. Likewise, two different representational paradigms can be distinguished: procedural models describe which activities can be executed next and declarative models define execution constraints that the process has to satisfy. The more constraints we add to the model, the less possible execution alternatives remain. As flexible This work was funded by the European Unions Seventh Framework Programme (FP7/2007-2013) grant 612052 (SERAMIS) and the Austrian Research Promotion Agency (FFG) grant 845638 (SHAPE). processes may not be completely known a priori, they can often be captured more easily using a declarative rather than a procedural modelling approach [2– 4]. Declarative languages like Declare [5], Dynamic Condition Response (DCR) graphs [6] or Declarative Process Intermediate Language (DPIL) [7] can be used to represent these models, and tools like DeclareMiner [8], MINERful [9] or DPILMiner [10] offer capabilities to automatically discover such models from event logs. Existing declarative process mining approaches either suffer from performance issues with real-life event logs or limit their search space to a specific and fixed set of constaints to be able to cope with the size of real-life event logs. Both issues are highlighted in current literature, e.g., [9–12]. To the best of our knowledge an approach that is fast and customisable does not exist. We fill this research gap by introducing a declarative mining approach that works on event data that is stored in relational databases by querying the log with conventional SQL. An overview of the approach is given in Fig 1. Process mining by means of SQL queries turns out to be an integrated and language overspanning solution to process discovery. By leveraging relational database performance technology, e.g., indexes on data columns, it is relatively fast without limiting itself to certain predefined constraints. Queries can be tailored to arbitrary aspects of a process, e.g., control flow as well as organisational issues. Furthermore, the results can be transformed to each of the mentioned process modelling languages. We evaluated the performance using several real-life event logs. Moreover, we demonstrate capabilities, expressiveness and additional insights of our approach by providing a list of queries for discovering commonly used process constraints. All queries are published in a technical report [13]. Further material as well as a screencast are accessible online at http://sqlminer.kppq.de. Summing up the contributions of this work, we introduce a (i) customisable,(ii) language independent and (iii) performant declarative process mining technique. The remainder of this paper is structured as follows: Section 2 describes the input data, fundamentals of declarative process mining and related work. In Section 3 we introduce our approach to discover process constraints using SQL queries. The approach is evaluated in Section 4, and Section 5 concludes the paper. PROCESS CONSTRAINTS RXES RELATIONAL DATABASE EVENT LOGEVENT DATA SQL QUERIES CONSTRAINT TEMPLATES Fig. 1: Overview of the SQL-based process mining approach 2 Background and Related Work Next, we describe the input data for our approach as well as fundamentals of declarative process modelling and automated discovery of models. 2.1 Storing Event Log Data in Relational Databases Our process mining approach takes as input (i) an event log, i.e., a machinereadable file that reports on the execution of activities during the enactment of the instances of a given process, and optionally (ii) organisational background knowledge, i.e., prior knowledge about the roles, capabilities and the assignment of resources to organisational units. In an event log, every process instance corresponds to a sequence (trace) of recorded entries, namely, events. We require that events contain an explicit reference to the enacted activity. For discovering resource-related aspects we additionally require an explicit reference to the operating resource. Typically, these requirements are met when business processes are enacted by information systems [14]. The standardised, extensible storage format OpenXES was developed for the purpose of storing event data [15]. Lately, with RelationalXES (RXES) a relational database architecture for storing event log data has been introduced [16]. The RXES architecture uses a database to store the event log where traces and events are represented by tables with identifiers (IDs). RXES provides a full implementation of all OpenXES interfaces using the database as a backend. The database schema used in RXES allows for a significant reduction of redundancy by storing frequently occurring attributes only once rather than repeating them for every occurrence. In this paper, we consider an event log to be available according to the RXES architecture and therefore to be stored in a conventional relational database. For readability we use a denormalised event log table like in Table 1, capturing only the attributes EventID (unique identifier for each recorded event), TraceID (unique identifier for the corresponding trace), ActivityID (name of the corresponding activity the event refers to), Time (date and time the event has occurred) as well as Identity (identifier of the performing resource or person). In the remainder of the paper, we will use the shorthand notation (a,idx) for indicating an event of activity athat has been executed by an identity idx. The given events are ordered temporally so that timestamps are not encoded explicitly. The following example event log contains four traces comprising events of four different activities and executed by five different resources: h(a,id1),(b,id1),(c,id2)i,h(b,id2),(c,id2)i,h(a,id2),(d,id4),(c,id2)i, h(a,id5),(a,id5),(b,id1),(c,id3)i. In the case that correlations between process execution and resource characteristics should be examined, organisational background information, e.g., in form of an organisational model must also be given in a relational database table. We build upon the generic organisational meta-model defined in [17]. A Event ID Trace ID Activity ID Time Identity 1 1 a 2015-11-06 15:31:00 id1 2 1 b 2015-11-06 15:35:00 id1 3 1 c 2015-11-06 15:37:00 id2 4 2 b 2015-11-06 16:22:00 id2 5 2 c 2015-11-06 16:45:00 id2 ... Table 1: Event log excerpt stored in a denormalized relational database table Identity represents an individual person that can be directly assigned to activities. A Group describes several resources as a whole. A Relation represents the interplay between Identity and Group. For Relations, a RelationType specifies its interpretation. For instance, an organisation may have three Groups (Professor, Student, Admin), five Identities (id1,id2,id3,id4and id5) and the following four Relations of RelationType “role” describing the roles that are assigned to each resource: (id1,role,Student),(id2,role,Professor),(id3,role,Professor),(id4,role,Admin), (id5,role,Student). This knowledge can help us to identify resource allocation rules as well as control flow rules that only apply to certain groups. 2.2 Fundamentals of Declarative Process Mining In the following, we describe the basic aspects of declarative process modelling and the principle of automated discovery of such models from event log data. Declarative Process Modelling Languages During the last decade several declarative process modelling languages have been developed [5–7]. These languages are based on so-called constraint templates. A constraint template captures frequently occurring relations and defines a particular type of constraint. Templates have formal semantics specified through logical formulae and are equipped either with user-friendly graphical representations (e.g., in Declare [5]) or macros in textual languages (e.g., in DPIL [7]) that make the model easier to understand. A constraint template consists of placeholders, i.e., typed variables. It is instantiated by providing concrete values for these placeholders. Concrete constraints are rules constraining, e.g., the execution of activities. For example, Response(a,b)of the Declare language is a constraint on the activities aand b, forcing bto be executed eventually if activity awas performed before. The ChainResponse(a,b) constraint is stronger and forces activity bto be executed directly after activity awas executed. Some languages allow in addition to control-flow aspects the definition of constraints concerning the assignment of certain resources to activites. RoleBasedAllocation(a,r) of the DPIL language is a constraint on activity a, demanding a, if executed, to be performed by a person in a specific role r. As shown, constraint templates can be categorized into different groups depending on the process perspective they concern or their cardinality, i.e., the number of activities affected. For example, instances of the Response(A,B)template are pure control flow constraints that describe the temporal relation between two activities. On the other hand, the RoleBasedAllocation(A,R) template refers to the resource perspective and constrains the resources that are assigned to one certain activity. Declarative Process Mining For almost each declarative process modelling language a corresponding mining approach exists. The first approach to extract declarative constraints from event logs introduced by Maggi et al. is the DeclareMiner [8]. Here, the user can select from a set of predefined Declare constraint templates the ones to be discovered. The system then generates all possible constraints by instantiating the chosen set of constraint templates with all possible combinations of occurring process elements provided in the event log. For example, the Response(A,B)template consists of two placeholders for activities. Assuming that |A|different activities occur in the event log, |A|2con- straint candidates are generated. All the resulting candidates are subsequently checked w.r.t. the event log. Additional mining parameters like PoE (Percentage of Events) or PoI (Percentage of Instances) are used to distinguish between valid and non-valid constraint candidates. Maggi et al. propose an evaluation of this algorithm with the adoption of a two-phase approach [11]. During the first phase, frequent sets of correlated activities are identified. The candidate constraints are only generated on the basis of these activities. In the second phase, the candidates are then checked in the same way as in [8]. Additionally, there are post-processing approaches that aim at simplifying the resulting Declare models in terms of, a.o., redundancy elimination [18, 9] and disambiguation [19]. In essence, the focus of these approaches is control flow with extensions to cover data dependencies [20]. The DPILMiner [10] proposes a declarative mining approach to incorporate the resource perspective and to mine for a set of predefined resource assignment constraints. All the mentioned approaches suffer from performance issues w.r.t. real-life event logs. Furthermore, the set of constraint templates to be analysed is predefined, i.e., cannot be customised by the user. Efficient algorithms to discover Declare models are presented in [21, 12]. Westergaard presents the UnconstrainedMiner [12], whose outstanding performance is obtained by constraint checking parallelisation and by relying on efficient data structures. The MINERful approach [9] that has been implemented [21] in the ProM framework has shown to be the most efficient algorithm to discover control-flow constraints using the Declare language. Both approaches, however, are limited to discover control-flow constraints of the Declare language. Mining Metrics Checking constraint candidates provides for every constraint candidate the number of satisfactions in the event log. The constraint Response(a,b), e.g., is satisfied three times in the example event log since in three cases of an occurrence of a,beventually follows in the same trace. Based on the number of satisfactions two metrics Support and Confidence are calculated that express the probability of a constraint to hold in the process. Constraints are considered valid, if their Support and Confidence measures are above a user defined threshold. In literature, there are two different definitions of support and confidence in the context of process mining. For our approach we adopt the most recent definition by Di Ciccio et al. [9] where the metrics are defined as follows: – Support: It is the number of fulfilments of a constraint divided by the number of occurrences of the condition of a constraint. In the example log, the support of Response(a,b)is 0.75, as 3 a’s out of 4 fulfil the constraint. In case of constraints that do not depict implications like Existence constraints in Declare, the Support is defined as the number of fulfilments divided by the number of traces in the log. – Confidence: It is the product of the support and the fraction of traces in the log where the condition (implications) or the constrained activity (not implications) occurs. The confidence of Response(a,b)is 0.75 ·0.75 = 0.5625, since condition aoccurs in 3 traces out of 4. The definitions above show that for discovering a certain constraint three different constraint specific values need to be extracted from event logs: (i) the number of occurrences of the condition of the constraint,(ii) the number of fulfilments of the constraint, and (iii) the fraction of traces in the log where the condition holds. 3 Declarative Process Mining with SQL With RXES a standardised architecture for storing event log data in relational databases was introduced. In this section we show that it is possible to extract relevant process knowledge from event logs stored in relational tables by applying conventional database queries without any parsing or data conversion. The Structured Query Language (SQL) is a declarative language designed for managing data held in a relational database. It is based upon relational algebra. For space reasons we cannot explain language details and therefore refer to one of the available SQL handbooks [22]. In the following we introduce a procedure to map constraint templates from various declarative process modelling languages to SQL queries. First, we describe the general query assembly by means of the Response constraint template. Subsequently, we describe the mapping of a more complex control flow constraint template. Finally, we show that it is possible to map and discover customised constraints involving different process perspectives apart from control flow. SELECT FROM WHERE GROUP BY HAVING Name, Parameter 1, 2,…, n Support Confidence Constraint Expression n Constraint Expression 1 Parameter 1, 2,…, n Support >minSupp Confidence >minConf … Log, (Organisational Model), Activity Combinations Output Source Tables Constraint Expressions Grouping Thresholds Fig. 2: SQL query assembly for querying declarative constraint templates 3.1 General Query Assembly Fig. 2 depicts the basic structure of an SQL query that discovers all constraints of a certain template under consideration of two thresholds minSupp and min- Conf. Here, subqueries are marked with a symbol on the upper right corner. We describe the different SQL directives in the order they get executed. We show the approach with an example, namely, the Response(A,B)constraint template, which aims at discovering all the activity combinations (a,b) where bis forced to be executed if awas completed at some point before. As depicted in Fig. 2, the query for discovering Response constraints is organised as follows: SELECT ‘response’, A, B, [Support], [Confidence] FROM Log l1, [ActivityCombinations] c l1.Activity = c.A AND EXISTS(SELECT * FROM Log l2 WHERE l2.Activity = c.B AND l2.Instance = l1.Instance AND l2.Time > l1.Time) GROUP BY c.A, c.B HAVING [Support] > minSupp AND [Confidence] > minConf FROM clause: Here, the data source tables are joined together, i.e., the table of the analysed event Log where every tuple depicts a single event and, if available, the table of the OrganisationalModel. Furthermore, the clause contains a subquery ActivityCombinations that provides a table with the activity combinations that should be checked. In case of constraints that comprise two activities like Response, this subquery looks as follows: SELECT l1.Activity AS A, l2.Activity AS B FROM Log l1, Log l2 WHERE l1.Activity != l2.Activity GROUP BY l1.Activity, l2.Activity Every source table gets an abbreviation assigned to be referable in other clauses, e.g., “l1” for the event log table or “c” for the combination table. WHERE clause: This clause contains the different constraint expressions that have to hold for activities and their events, i.e., the constraint activation condition as well as their fulfilment requirements. If an expression cannot be derived directly, a corresponding subquery is used. For Response constraints the condition activation is any occurrence of an event of the currently selected activity a. In order to be fulfilled the constraint expression has to hold: activity b must occur in the same instance and it must occur eventually after a. Therefore, the WHERE clause for querying Response constraints contains a subquery: l1.Activity = c.A AND EXISTS(SELECT * FROM Log l2 WHERE l2.Activity = c.B AND l2.Instance = l1.Instance AND l2.Time > l1.Time) It tests if at least one event of an activity bexists that is executed after the currently observed event of a. In case all logical terms in the clause evaluate to true, the currently observed tuple depicts one fulfilment of the constraint. The resulting set of tuples depicts all fulfilments of the analysed constraint template. GROUP BY clause: After deriving the fulfilments, the tuples are grouped by the set of parameters of the constraint template. Hence, in the query to discover Response constraints, we group w.r.t. the two parameters referring to activities Aand B. HAVING clause: As described in Section 2.2 the number of fulfilments of each constraint needs to be computed in order to calculate the support and confidence values. After grouping, the number of tuples corresponding to a certain parameter combination can be extracted using the SQL aggregate function COUNT(*). In addition, a subquery computes the number of occurrences of the condition of the constraint. This way, the Support value of each constraint can be derived. In case of Response constraints the condition is depicted by the number of occurrences of the currently selected activity a. The SQL expression for calculating the Support of Response constraints is given as: COUNT(*) / (SELECT COUNT(*) FROM Log WHERE Activity = A) The Confidence of each parameter combination can be calculated in a similar way. Recall that Confidence is defined as the product of Support and the fraction of traces in the log where the condition occurs. Therefore, in case of Response, we calculate the fraction of the outcome of two subqueries to (i) extract the number of instances where aoccurs at least once and (ii) to extract the number of traces in the log. Support * ((SELECT COUNT(*) FROM (SELECT Instance FROM Log WHERE Activity = A GROUP BY Instance) t ) / (SELECT COUNT(*) FROM (SELECT Instance FROM Log GROUP BY Instance) t2 )) ID Name A B Support Confidence 1 Response a b 0.75 0.5625 2 Response a c 1 0.75 3 Response b c 1 0.75 4 Response d c 1 0.25 Table 2: Result table of the Response query w.r.t. the example log The resulting values of both queries can then be filtered by user-defined thresholds. SELECT clause: In the last step the query output is selected, i.e., the parameter combination and its corresponding Support and Confidence values. The result set contains tuples for each parameter combination that fulfils the constraint under consideration of the given thresholds. Table 2 results from applying the Response query to the example event log of Section 2.2 with the thresholds minSupp=0.7 and minConf=0.2. 3.2 Mining Complex Control-Flow Constraints More complex control flow constraint templates can be mapped to SQL queries by adding the additional constraint expressions of the constraint template to the WHERE-clause of the query. Consider for example the ChainResponse(A,B) constraint template of the Declare language which states that an activity bis always executed directly after an activity ahas been completed. In addition to the fulfilment requirements of a Response constraint, a ChainResponse requires that bhas to follow awithout any other activity in-between. This additional requirement is implemented by adding another subquery to the WHERE-clause: [Response Constraint Expressions Subquery] AND NOT EXISTS(SELECT * FROM Log l2, Log l3 WHERE l3.Instance = l1.Instance AND l2.Instance = l1.Instance AND l2.Activity = c.B AND l3.Time > l1.Time AND l3.Time < l2.Time) The subquery provides all events that temporally took place in-between the currently selected event of an activity aand any event of an activity bin the same instance. The constraint is only fulfilled for a certain activity combination (a,b), if there exists no event of any activity between any occurrence of aand b. Other constraint templates of the Declare language, like AlternateResponse,Precedence or NotSuccession can be mapped in an analogous manner. Subsequently, the result set can be post-processed with existing pruning methods for declarative process mining, like pruning based on constraint hierarchies [23].