Incremental workflow mining is a technique for automatically deriving a process model from the on-going executions of a process. This way, the process model becomes more and more accurate, and is automatically adapted when the process is being changed. Therefore, incremental workflow mining could help in flexible workflow support: In this paper, we describe a setting that combines incremental workflow mining with gradually increasing the control of a workflow system. Process mining is an active research area. Most of the existing process mining algorithms need a log of the activities resp. the tasks of the process executions. In practice, however, many systems used for executing the processes are not aware of the activities - they see only the documents and how they are changed. Therefore, they do not provide activity logs. In order to make process mining available for this kind of systems, this paper improves an algorithm that identifies the activities from the accesses to documents. We call this algorithm task mining. In combination with our incremental workflow mining approach, task mining makes process mining available for many areas that use document management systems, version management systems or product data management systems. Originally, our incremental workflow mining approach aimed at increasing the maturity level of software enterprises. But, the methods can be applied to any kind of processes that are supported by some kind of system that is aware of documents and document changes during the execution of the processes.
Process mining [
Some process mining techniques do not require that all executions of the
processes need to be there right from the beginning. Rather, the process model
is changed, once new information on the execution of some of its instances is
available. This way, a process model will incrementally be changed when its
executions change. Therefore, process mining is one technique for automatically
achieving process flexibility and, in particular, incremental process type
evolution [
Most process mining techniques rely on the fact that there are logs of the tasks that are executed while a process is running. In our terminology, a task denotes a unit of works represented in a process model. We call an execution of a task, i. e. its instance, an activity. Therefore, we call a log of executed tasks an activity log. A process mining algorithm extracts the order in which the activities have been executed from the activity log and reconstructs a process model from this information. The problem, however, is that many systems that are used for executing the processes do not provide activity logs. For example, document management systems such as software configuration management (SCM) systems or product data management (PDM) systems or version management systems integrated in enterprise resource planning (ERP) systems are aware of the documents and the changes made; but, they are not aware of the tasks resp. activities of the underlying processes. Therefore, the event logs or audit information of these systems do not provide the information on activities that is needed for traditional process mining techniques.
In order to improve this situation, we had a fresh look to process mining and
devised a set of algorithms for mining processes from document versioning logs,
which we called incremental workflow mining [
In this paper, we present the task mining technique – which is the missing ingredient for completing our incremental workflow mining approach. More importantly, however, we discuss how the incremental workflow mining approach in combination with gradual workflow support can be exploited for achieving flexible workflow support.
The paper is structured as follows: We start with an overview of related work. In Sect. 3, we discuss the relation of process mining and flexible workflow support and how flexible workflow support could benefit from workflow mining. Then, we discuss which information is available in typical document management systems (Sect. 4) and how this information could be exploited for identifying the activities (Sect. 5).
A lot of work has been done in the area of process flexibility since the 90ties [
The research in the area of process mining started in the mid 90ties with new
approaches to the grammar inference problem proposed by Cook and Wolf [
The mining-based approach for process evolution and aligning the model and
the instance flexibility is researched by Weber et al. [
So, current process mining approaches start dealing with rich and complex
sources of information about process instances. In this context, the problem of
type discovering discussed in Sect. 5 becomes more and more important.
Similar problems were also discovered in the other research areas, such as reverse
engineering and clustering. In reverse engineering, people use a program
runtime information (execution history) to assist building the class diagram that
reflects the real implementation [
In this section, we describe our incremental workflow mining approach (for
further details, see [
The incremental workflow mining is useful for companies that utilize document management systems for a collaborative work of their employees. We use versioning logs of these document management systems (see Sect. 4) as a source of information about process instances. So, the approach consists of the following steps, see Fig. 1:
First, we do activity mining from the versioning logs. As a result, we get a set of activities.
Second, we take the set of discovered activities and do reverse engineering - derive the overall pro cess mo del in a system internal formalism (Petri nets). This mo del contains b ehavioural, informational and organizational p ersp ectives of the pro cess.
Third, we make the transformation from the system internal mo del to the
external mo del (UML2.0 Activity Diagrams [
Document Management
System A 01.01.05 14:30 W status: initial B 01.0A10.015.015. 0:0501X4:s3t0atWuss:tgaetunse:rainteitidal C 05.B010.015.010.0:0501Y5:0st0atXu s:t aint uitsia:lgenerated D 07.C010.055.A0101. 01:05.01Z.0:s05t0a1tY4u:3s:0tapWteunsds:tiangtiutisa:l initial A 01.0D20.075.B0101.01:05.01W1.0:05s0t1aZ5tu:s0t0:aitnXuitsia:t alpteunsd:ignegnerated B 15.0A20.015.C01270.0:505.01X1. 0:s05t0a1tW0u:s0s:0tgaeYtunset:raitnueitsida:linitial D 20.B021.055.D00209.07:05.01Z7. 0:s05t0a1tX1u:s0:t0aintZuitisa:tlagteunse:rpaetending C 28.D022.05.A01208. 01:45.0502Y9.0:s05t0a1tZ1u:s0:t0aptWeunssd:tiangtiuiasl: initial
C 28.B021.055.0128.0:4551Y7:0s0taXtus:tapteunsd:ignegnerated
D 20.02.05 09:00 Z status: initial C 28.02.05 18:45 Y status: pending
1 Activities 2
Company Employee
Manager 3 Process
Model
So, in the context of changing pro cesses, the approach is aimed to fill the gap b etween process type evolution and process instance evolution. Our activity mining and reverse engineering algorithms provide an automatic supp ort for redesigning the pro cess. They use the information ab out deviation in the pro cess instances for this redesign.
The approach works incrementally, i.e. as so on as new pro cess instance is executed and, consequently, new records are added to the versioning log, we refine the set of activities and the pro cess mo del derived on the previous step. Thus, starting with revolutionary changes in the first step, when there is no pro cess mo del at all, in a consecutive manner we come to incremental changes in the further steps.
Following our approach, after the pro cess mo dels are discovered, they can b e inserted to the Workflow Management System (WfMS), where they are maintained and executed. But the role of the WfMS and its user supp ort evolves with the time. Thus, on the first steps, it is utilized only for storing the newly discovered mo dels; after further refinements, when pro cess mo dels b ecome more faithful, the WfMS starts advising and guiding the users in the company. This increasingly changing control of the WfMS in the company is called gradual workflow support. So, introducing incremental workflow mining and gradual workflow support in the company enables dealing with the flexibility in a formal and documented manner. 4
In this section, we deal with the sources, from which the audit information on the process instances can be obtained. It can be obtained from different types of Document Management Systems: Software Configuration Management systems (SCM), Product Data Management systems (PDM), Version Management systems integrated in Enterprise Resource Planning systems (ERP). All these systems are widely used in companies working in the areas of software engineering, mechanical engineering, electrical engineering, telecommunications and others. For example, SCM systems are an essential part of modern software engineering environments and their use is stipulated in widely accepted software process improvement frameworks, such as Capability Maturity Model (CMM).
However, the problem is that these systems do not provide logs of activities, but data about the informational and the organizational perspectives of the process. In the rest of the paper, we focus on the area of software processes; but our approach is general and applicable to the other areas, where document management systems are used for collaborative work of employees in the product development process.
In spite of the fact that there is such a variety of different document
management systems, their typical auditing capabilities, such as history, logging and
traceability [
In order to extract this format we have looked at the versioning logs
containing information about commits of documents in several SCM and PDM systems,
such as: CVS [
An example of a versioning log with the information which is generally available in these systems is presented in Table 1. The log consists of records (rows). Each record contains information about the name of the committed document, e.g. “A”, the timestamp of the commit – “01.01.05 14:30”, the name of the user who did it – “W” and the comment of the user – “status: initial”. The versioning log contains many records related to different executions of different processes. For example, the versioning log in Table 1 contains two executions of one process, they are separated with a double line. The set of records, that belong to one execution of one process is called the execution log.
When dealing with the versioning logs the following problems occur: which records belong to which execution logs and which execution logs belong to which process; do all the execution logs use the same naming conventions; how big are differences between timestamps of two records when they belong to the same commit, etc. In this paper, we assume that we know the structure of execution logs, naming conventions are the same in the whole log and records with different timestamps belong to different commits.
Here, we deal with the following problem: versioning logs do not contain information about document types, but only information about concrete names of concrete documents and sequence of their commits. The incremental workflow mining algorithms discover the behaviour of the process from such versioning logs and combine it with informational and organizational perspectives. But deriving the input and the output of activities is not fully covered by these algorithms because of the missing type information. Thus, the process model, which can be mined from the logs, can be neither reused in the other projects, nor changed by the people that were not involved in the concrete process. 5
In this section, we propose a solution to the problem described above and raise the following questions: 1. how do the informational models (document type models) look like? 2. is there an algorithm for assigning the types to concrete documents using these models? Informational Model One of the most important requirements for modern SCM and PDM systems is the capability of informational modelling. In the area of PDM, for example, there is a STEP (Standard for the Exchange of Product Model Data) ISO standard (ISO DIS 10303), which includes the EXPRESS language for defining the product models.
Like for versioning logs, different systems have different informational
models. But there are typical relationships used in most of these models [
An example of the informational model is shown in Fig. 2 as a UML class diagram. In the example, Code depends on the Design. In our case, this is also a lifecycle dependency – the document Code can appear in the system only after the Design document.
<<dt>> Design dep <<dt>> Code dep dep <<dt>> Review <<dt>>
TestResults Now, besides the versioning log with document names, we also have a set of document types and a dependency relationship on this set. Here, we propose a principal algorithm for assigning the types to the documents in the log.
Let D be a set of documents in the log with cardinality k = |D|, DT be a set of document types with cardinality n = |DT | and dep ⊆ DT × DT be a dependency relationship on the set of document types. The type discovering algorithm is the following: – If k <= n, find all possible assignments of types to the documents, i.e. find all the k-subsets on DT . – If k > n, find all possible assignments of types to the documents so, that every type is assigned at least once. In this case, we will get several documents of the same type. – For each assignment, for each execution log, check whether dependency relationship is fulfilled (so that dependent document does not appear earlier than the document it depends on). If at least one execution log exists, where dependency relationship is not fulfilled, the assignment is wrong and should be deleted.
Thus, as a result, we assign the types, which do not contradict with the dependencies, to the documents.
For the log in Table 1 and document types in Fig. 2, if we take the 4subset {Design, Review, TestResults, Code} and add this type information to the document names (we use “:” notation to separate the name and the type), we get the following orders of documents in the logs: (A:Design, B:Review, C:TestResults, D:Code) for the first execution log and (A:Design, B:Review, D:Code, C:TestResults) for the second.
In the first execution log, the document of type T estResults appears earlier than the Code document, but it contradicts the dependency (TestResults,Code), which shows that T estResults is dependent on Code and not vice versa. So, the selected subset is not correct. The same way, we can check all the other subsets and detect, that the only correct subsets are {Design, Code, TestResults, Review} and {Design, Code, Review, TestResults}. If we had another execution log containing additional order, for example {A, D, B, C}, we could see, that the only correct assignment of types is {Design, Code, TestResults, Review}.
The success of the type detection algorithm is dependent on the number of execution logs and the number of dependencies. If the numbers of logs and dependencies are not sufficient, we do not come to an unambiguous set of types in spite of the fact that we are checking all the possible type permutations. In this case, we need interaction with a user, who has to give us the types of some documents. 6
In this paper, we have presented the advantages of the incremental workflow mining approach and gradual workflow support in the context of flexible processes. This semi-automatic approach uses information about the changing process instances and derives the process model compliant to them. The information about instances is obtained from the logs of document management systems. We have also looked at different document management systems and proposed a uniform format for these logs.
In the second part of the paper, we have presented the problem of discovering the types of documents in the logs of document management systems and proposed a solution for it. This solution is used to augment the incremental workflow mining approach with information about tasks and, therefore, to enable task mining.
In order to deal with this problem, we need other information in addition to the versioning logs. This information contains the types of documents and dependencies between them. After executing the type discovering algorithm and possibly interacting with the user, we get the assignment of types to the documents in the log. The type discovering algorithm was implemented in our research prototype and tried out on several examples from the software process domain, see Fig. 3.
Neither the advantages of incremental process mining techniques in the context of changing processes, nor the problem of discovering the types were discussed in details in the areas of process flexibility and process mining. But using new process management and new support systems and obtaining more and more complex multi perspective log information there makes the stated problems more and more prominent.
So, the future research in this area must deal with the user role in incremental workflow mining and in guiding process flexibility in the company. Since the input information for the algorithms is defined manually and the logs can contain noise or be incomplete, the role of interactive type detection and mining, which lead to unambiguous solutions, will become more and more important.