Generating process models from workflow logs

• US 6,038,538 A
• Filed: 12/15/1997
• Issued: 03/14/2000
• Est. Priority Date: 09/15/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gunopulos, Dimitrios, Roller, Dieter Helmut, Agrawal, Rakesh, Leymann, Frank
• Primary Examiner(s): Poinvil, Frantzy
• Assistant Examiner(s): Alvarez, Raquel
• Application Number:
  US08/990,104
• Time in Patent Office: 820 Days
• Field of Search: 705/1, 705/7, 705/8, 705/9, 705/11, 707/9, 707/10, 707/104, 395/500, 395/681, 395/682, 364/147, 364/472.06, 709/201, 709/202, 709/244
• US Class Current: 705/7.11
• CPC Class Codes: G06Q 10/063 Operations research, analysis or management
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 10/103 Workflow collaboration or project management
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

A computer-implemented method, apparatus, and article of manufacture that constructs graph models from logs of past, unstructured executions of the given process. The graph model so produced conforms to the dependencies and past executions present in the log. By providing graph models that capture the previous executions of the process, this technique allows easier introduction of a workflow system and evaluation and evolution of existing processes.

Claims

1. A method of generating a graph model of a process executed by a computer, comprising the steps of:

(a) under control of the computer, automatically identifying one or more records of activities representing one or more executions of the process from a log stored in the computer to determine patterns in the executions of the process; and

(b) under control of the computer, automatically analyzing the log to identify relationships between the activities to create the graph model of the process.

2. The method of claim 1 above, wherein the graph model is a single graph.

3. The method of claim 1 above, wherein the graph model is compatible with all activities of the process.

4. The method of claim 1 above, wherein the graph model represents a control flow of a business process.

5. The method of claim 1 above, wherein the graph model preserves all dependencies between activities that are present in the log.

6. The method of claim 1 above, wherein the graph model permits all the activities of the process present in the log.

7. The method of claim 1 above, wherein the graph model does not introduce spurious dependencies between activities in the log.

8. The method of claim 1 above, wherein the process is defined as a set of activities V_P =V₁, . . . , V_n, a graph model G_p =(V_P,E_P), an output function O_P :

V_P →

N^k, ∀

(u,v)ε

E_P, and a Boolean function f.sub.(u,v) ;

N^k →

{0,1}.

9. The method of claim 1 above, wherein the record of one of the executions of the process is a list of event records (P, A, E, T, O ), where P is a name of the process'"'"'s execution, A is a name of the activity, Eε

{START, END} is a type of an event associated with the activity, T is a time the event occurred, and O=o(A) is an output of the activity when E=END and a null vector otherwise.

10. The method of claim 1 above, wherein when a second activity starts after a first activity terminates in the log, then the second activity directly follows the first activity.

11. The method of claim 1 above, wherein a second activity follows a first activity in the log when either the second activity directly follows the first activity or there exists a third activity such that the third activity follows the first activity and the second activity follows the third activity.

12. The method of claim 1 above, wherein when a second activity follows a first activity but the first activity does not follow the second activity in the log, then the second activity depends on the first activity.

13. The method of claim 1 above, wherein when the first activity follows a second activity and the second activity follows the first activity in the log, then the first and second activity are independent.

14. The method of claim 1 above, wherein the activities are defined as V and the log is defined as L, and the graph model is defined as G_VL, the graph model is a dependency graph when there exists a path from activity u to activity v in G_VL, if and only if v depends on u.

15. The method of claim 1 above, wherein the process is defined as P, one of the executions is defined as R, the graph model is defined as G=(V, E), R is consistent with G when the activities in R are a subset V'"'"' of the activities in G, the induced subgraph G'"'"'=(V'"'"', {(u,v)ε

E|u,vε

V'"'"'}) is connected, the first and last activities in R are process initiating and terminating activities, respectively, all nodes in V'"'"' can be reached from the initiating activity, and no dependency in the graph is violated by the ordering of the activities in R.

16. The method of claim 1 above, wherein the log of all executions is defined as L, the graph model is defined as G, and G is conformed with L if all of the following hold:

for each dependency in L, there exists a path in G;

there is no path in G between independent activities in L; and

G is consistent with every execution in L.

17. The method of claim 1 above, wherein the process is acyclic, its executions contain exactly one instance of every activity, and the graph model represents a directed acyclic graph.

18. The method of claim 17 above, wherein each activity appears exactly once in each execution in the log of executions of the acyclic process, the graph model is conformal, and the graph model contains a minimal a number of edges.

19. The method of claim 1 above, wherein each activity appears exactly once in each execution in the log of executions of the acyclic process, and a second activity depends on a first activity when the second activity starts after the first activity terminates in every execution recorded in the log.

20. The method of claim 1 above, wherein two graph models have a same transitive closure and the two graph models are consistent with a same set of executions if each activity appears exactly once in each execution.

21. The method of claim 1 above, wherein the graph model is conformal because all of the activities appear in each execution once.

22. The method of claim 1 above, wherein the process is acyclic and every execution of the process does not necessarily include all of the activities.

23. The method of claim 1 above, wherein a cycle in the graph model results in multiple appearances of an activity in a single execution of the process.

24. The method of claim 23 above, further comprising the step of labeling activities recorded in the log to differentiate multiple appearances of an activity.

25. The method of claim 24 above, wherein the graph contains, for each activity, an equivalent set of vertices that correspond to the activity.

26. The method of claim 25 above, further comprising the steps of merging the vertices of each equivalent set of vertices into one vertex and placing an edge in the graph model when there exists an edge between two vertices of different equivalent sets of vertices.

27. The method of claim 1 above, wherein the analyzing step further comprises the step of eliminating noise from the log.

28. The method of claim 27 above, wherein the eliminating step further comprises the steps of counting how many times each edge appears in the graph model and removing all edges from the graph model with a count below a specified threshold.

29. The method of claim 1 above, wherein the graph model is a directed acyclic graph and the computing step further comprises the step of computing a transitive reduction of the graph model.

30. A method of generating a graph model of a process executed by a computer, comprising the steps of:

(a) retrieving one or more records of activities representing one or more executions of the process from a log stored in the computer to determine patterns in the executions of the process; and

(b) analyzing the patterns in the computer to create the graph model of the process, wherein the graph model is defined as G=(V, E), V is a set of activities of the process, E is a set of edges of the graph model, the log is defined as L, and the analyzing step further comprises the steps;

(1) initializing the graph model, wherein E is initially empty;

(2) for each process in the log L and for each pair of activities u,v in the log L such that the activity u terminates before the activity v starts, add an edge (u,v) to E;

(3) removing edges from E that appear in both directions; and

(4) computing a transitive reduction of G, wherein the transitive reduction is a smallest sub-graph of G that has a same closure as G.

31. A method of generating a graph model of a process executed by a computer, comprising the steps of:

(a) retrieving one or more records of activities representing one or more executions of the process from a log stored in the computer to determine patterns in the executions of the process; and

(b) analyzing the patterns in the computer to create the graph model of the process, wherein the graph model is defined as G=(V, E), V is a set of activities of the process, E is a set of edges of the graph model, the log is defined as L, and the analyzing step further comprises the steps;

(1) initializing the graph model, where E is initially empty;

(2) for each process execution in the log L, and for each pair of activities u,v such that the activity u terminates before the activity v starts, add an edge (u,v) to E;

(3) removing edges from E that appear in both directions;

(4) for each strongly connected component of the graph model G, removing all edges from E that are between vertices in the strongly connected component;

(5) for each process execution in the log L;

(i) finding an induced sub-graph of G;

(ii) computing a transitive reduction of the induced sub-graph of G; and

(iii) marking those edges in E that are present in the transitive reduction; and

(6) removing unmarked edges from E.

32. The method of claim 31 above, wherein there are no cycles in the graph model.

33. A method of generating a graph model of a process executed by a computer, comprising the steps of:

(a) retrieving one or more records of activities representing one or more executions of the process from a log stored in the computer to determine patterns in the executions of the process; and

(b) analyzing the patterns in the computer to create the graph model of the process, wherein the graph model is defined as G=(V, E), V is a set of activities of the process, E is a set of edges of the graph model, the log is defined as L, and the analyzing step further comprises the steps;

(1) initializing the graph model, where E is initially empty;

(2) examining each execution in the log L and uniquely identifying each activity recorded in the log L, so as to create a new set of vertices defined as V'"'"' and a new graph model defined as G=(V'"'"',E'"'"');

(3) for each process execution in the log L and for each pair of activities u,v such that the activity u terminates before the activity v starts, adding an edge (u,v) to E'"'"';

(4) removing edges from E'"'"' that appear in both directions;

(5) for each strongly connected component of the graph model G, removing all edges from E'"'"' that are between vertices in the strongly connected component;

(6) for each process execution present in the log L;

(i) finding an induced sub-graph of the graph model G'"'"';

(ii) computing a transitive reduction of the sub-graph; and

(iii) marking those edges in E'"'"' that are present in the transitive reduction;

(7) removing unmarked edges from E'"'"'; and

(8) in the graph model so obtained by steps (1)-(7) above, merging the vertices that correspond to different instances of a same activity in the graph model, thus reverting to an original act of vertices V.

34. A method of generating a graph model of a process executed by a computer, comprising the steps of:

(a) retrieving one or more records of activities representing one or more executions of the process from a log stored in the computer to determine patterns in the executions of the process; and

(b) analyzing the patterns in the computer to create the graph model of the process, wherein the analyzing step further comprises the steps of;

(1) finding a topological order of the graph model;

(2) maintaining two arrays for each vertex v of the graph model, wherein a first array stores descendants of the vertex v, and a second array stores successors of vertex v; and

(3) visiting each vertex in the graph model in reverse topological order.

35. The method of claim 34 above, wherein the analyzing step further comprises the steps of:

(1) finding the topological ordering of the graph model

(2) for each vertex v, identifying the successors of v as succ(v)={u|(v,u)ε

E}; and

(3) for each vertex v and in reverse topological order;

(i) setting the descendants of the vertex v equal to a union of the descendants of the successors of vertex v;

(ii) if the successor of the vertex v is also the descendant of the vertex v, removing the successor of the vertex v; and

(iii) adding any remaining successors of the vertex v to the descendants of the vertex v.

36. A computer-implemented apparatus for generating a graph model of a process executed by a computer, comprising:

(a) a computer having a monitor attached thereto; and

(b) means, performed by the computer, for;

(1) under control of the computer, automatically identifying one or more records of activities representing one or more executions of the process from a log stored in the computer to determine patterns in the executions of the process; and

(2) under control of the computer, automatically analyzing the log to identify relationships between the activities to create the graph model of the process.

37. An article of manufacture comprising a computer program carrier readable by a computer and embodying one or more instructions executable by the computer to perform method steps of generating a graph model of a process executed by a computer, the method comprising the steps of:

(a) under control of the computer, automatically identifying one or more records of activities representing one or more executions of the process from a log stored in the computer to determine patterns in the executions of the process; and

(b) under control of the computer, automatically analyzing the log to identify relationships between the activities to create the graph model of the process.

38. A computer-implemented apparatus for generating a graph model of a process executed by a computer, comprising:

(a) a computer having a monitor attached thereto; and

(b) means, performed by the computer, for;

(i) retrieving one or more records of activities representing one or more executions of the process from a log stored in the computer to determine patterns in the executions of the process; and

(ii) analyzing the patterns in the computer to create the graph model of the process wherein the graph model is defined as G=(V, E), V is a set of activities of the process, E is a set of edges of the graph model, the log is defined as L, and the analyzing means further comprises means for;

(1) initializing the graph model, wherein E is initially empty;

(2) for each process in the log L and for each pair of activities u,v in the log L such that the activity u terminates before the activity v starts, add an edge (u,v) to E;

(3) removing edges from E that appear in both directions; and

(4) computing a transitive reduction of G, wherein the transitive reduction is a smallest sub-graph of G that has a same closure as G.

39. A computer-implemented apparatus for generating a graph model of a process executed by a computer, comprising:

(a) a computer having a monitor attached thereto; and

(b) means, performed by the computer, for;

(i) retrieving one or more records of activities representing one or more executions of the process from a log stored in the computer to determine patterns in the executions of the process; and

(ii) analyzing the patterns in the computer to create the graph model of the process, wherein the graph model is defined as G=(V, E), V is a set of activities of the process, E is a set of edges of the graph model, the log is defined as L, and the analyzing means further comprises means for;

(1) initializing the graph model, where E is initially empty;

(2) for each process execution in the log L, and for each pair of activities u,v such that the activity u terminates before the activity v starts, add an edge (u,v) to E;

(3) removing edges from E that appear in both directions;

(4) for each strongly connected component of the graph model G, removing all edges from E that are between vertices in the strongly connected component;

(5) for each process execution in the log L;

(i) finding an induced sub-graph of G;

(ii) computing a transitive reduction of the induced sub-graph of G; and

(iii) marking those edges in E that are present in the transitive reduction; and

(6) removing unmarked edges from E.

40. The apparatus of claim 39 above, wherein there are no cycles in the graph model.

41. A computer-implemented apparatus for generating a graph model of a process executed by a computer, comprising:

(a) a computer having a monitor attached thereto; and

(b) means, performed by the computer, for;

(i) retrieving one or more records of activities representing one or more executions of the process from a log stored in the computer to determine patterns in the executions of the process; and

(ii) analyzing the patterns in the computer to create the graph model of the process, wherein the graph model is defined as G=(V, E), V is a set of activities of the process, E is a set of edges of the graph model, the log is defined as L, and wherein the analyzing means further comprises means for;

(1) initializing the graph model, where E is initially empty;

(2) examining each execution in the log L and uniquely identifying each activity recorded in the log L, so as to create a new set of vertices defined as V'"'"' and a new graph model defined as G=(V'"'"',E'"'"');

(3) for each process execution in the log L and for each pair of activities u,v such that the activity u terminates before the activity v starts, adding an edge (u,v) to E'"'"';

(4) removing edges from E'"'"' that appear in both directions;

(5) for each strongly connected component of the graph model G, removing all edges from E'"'"' that are between vertices in the strongly connected component;

(6) for each process execution present in the log L;

(i) finding an induced sub-graph of the graph model G'"'"';

(ii) computing a transitive reduction of the sub-graph; and

(iii) marking those edges in E'"'"' that are present in the transitive reduction;

(7) removing unmarked edges from E'"'"'; and

(8) in the graph model so obtained by means (1)-(7) above, merging the vertices that correspond to different instances of a same activity in the graph model, thus reverting to an original act of vertices V.

42. A computer-implemented apparatus for generating a graph model of a process executed by a computer, comprising:

(a) a computer having a monitor attached thereto; and

(b) means, performed by the computer, for;

(i) retrieving one or more records of activities representing one or more executions of the process from a log stored in the computer to determine patterns in the executions of the process; and

(ii) analyzing the patterns in the computer to create the graph model of the process, wherein the analyzing means further comprises means for;

(1) finding a topological order of the graph model;

(2) maintaining two arrays for each vertex v of the graph model, wherein a first array stores descendants of the vertex v, and a second array stores successors of vertex v; and

(3) visiting each vertex in the graph model in reverse topological order.

43. The apparatus of claim 42 above, wherein the analyzing means further comprises means for:

(1) finding the topological ordering of the graph model

(2) for each vertex v, identifying the successors of v as such(v)={u|(v,u)ε

E}; and

(3) for each vertex v and in reverse topological order;

(i) setting the descendants of the vertex v equal to a union of the descendants of the successors of vertex v;

(ii) if the successor of the vertex v is also the descendant of the vertex v, removing the successor of the vertex v; and

(iii) adding any remaining successors of the vertex v to the descendants of the vertex v.

44. An article of manufacture comprising a computer program carrier readable by a computer and embodying one or more instructions executable by the computer to perform method steps of generating a graph model of a process executed by a computer, the method comprising the steps of:

(a) retrieving one or more records of activities representing one or more executions of the process from a log stored in the computer to determine patterns in the executions of the process; and

(b) analyzing the patterns in the computer to create the graph model of the process, wherein the graph model is defined as G=(V, E), V is a set of activities of the process, E is a set of edges of the graph model, the log is defined as L, and the analyzing step further comprises the steps;

(1) initializing the graph model, wherein E is initially empty;

(2) for each process in the log L and for each pair of activities u,v in the log L such that the activity u terminates before the activity v starts, add an edge (u,v) to E;

(3) removing edges from E that appear in both directions; and

(4) computing a transitive reduction of G, wherein the transitive reduction is a smallest sub-graph of G that has a same closure as G.

45. An article of manufacture comprising a computer program carrier readable by a computer and embodying one or more instructions executable by the computer to perform method steps of generating a graph model of a process executed by a computer, the method comprising the steps of:

(a) retrieving one or more records of activities representing one or more executions of the process from a log stored in the computer to determine patterns in the executions of the process; and

(b) analyzing the patterns in the computer to create the graph model of the process, wherein the graph model is defined as G=(V, E), V is a set of activities of the process, E is a set of edges of the graph model, the log is defined as L, and the analyzing step further comprises the steps;

(1) initializing the graph model, where E is initially empty;

(2) for each process execution in the log L, and for each pair of activities u,v such that the activity u terminates before the activity v starts, add an edge (u,v) to E;

(3) removing edges from L that appear in both directions;

(4) for each strongly connected component of the graph model G, removing all edges from E that are between vertices in the strongly connected component;

(5) for each process execution in the log L;

(i) finding an induced sub-graph of G;

(ii) computing a transitive reduction of the induced sub-graph of G; and

(iii) marking those edges in E that are present in the transitive reduction; and

(6) removing unmarked edges from E.

46. The article of manufacture of claim 45 above, wherein there are no cycles in the graph model.

47. An article of manufacture comprising a computer program carrier readable by a computer and embodying one or more instructions executable by the computer to perform method steps of generating a graph model of a process executed by a computer, the method comprising the steps of:

(a) retrieving one or more records of activities representing one or more executions of the process from a log stored in the computer to determine patterns in the executions of the process; and

(b) analyzing the patterns in the computer to create the graph model of the process, wherein the graph model is defined as G=(V, E), V is a set of activities of the process, E is a set of edges of the graph model, the log is defined as L, and the analyzing step further comprises the steps;

(1) initializing the graph model, where E is initially empty;

(2) examining each execution in the log L and uniquely identifying each activity recorded in the log L, so as to create a new set of vertices defined as V'"'"' and a new graph model defined as G=(V'"'"',E'"'"');

(3) for each process execution in the log L and for each pair of activities u,v such that the activity u terminates before the activity v starts, adding an edge (u,v) to E'"'"';

(4) removing edges from E'"'"' that appear in both directions;

(5) for each strongly connected component of the graph model G, removing all edges from E'"'"' that are between vertices in the strongly connected component;

(6) for each process execution present in the log L;

(i) finding an induced sub-graph of the graph model G'"'"';

(ii) computing a transitive reduction of the sub-graph; and

(iii) marking those edges in E'"'"' that are present in the transitive reduction;

(7) removing unmarked edges from E'"'"'; and

(8) in the graph model so obtained by steps (1)-(7) above, merging the vertices that correspond to different instances of a same activity in the graph model, thus reverting to an original act of vertices V.

48. An article of manufacture comprising a computer program carrier readable by a computer and embodying one or more instructions executable by the computer to perform method steps of generating a graph model of a process executed by a computer, the method comprising the steps of:

(a) retrieving one or more records of activities representing one or more executions of the process from a log stored in the computer to determine patterns in the executions of the process; and

(b) analyzing the patterns in the computer to create the graph model of the process, wherein the analyzing step further comprises the steps of;

(1) finding a topological order of the graph model;

(2) maintaining two arrays for each vertex v of the graph model, wherein a first array stores descendants of the vertex v, and a second array stores successors of vertex v; and

(3) visiting each vertex in the graph model in reverse topological order.

49. The article of manufacture of claim 48 above, wherein the analyzing step further comprises the steps of:

(1) finding the topological ordering of the graph model

(2) for each vertex v, identifying the successors of v as succ(v)={u|(v,u)ε

E}; and

(3) for each vertex v and in reverse topological order;

(i) setting the descendants of the vertex v equal to a union of the descendants of the successors of vertex v;

(ii) if the successor of the vertex v is also the descendant of the vertex v, removing the successor of the vertex v; and

(iii) adding any remaining successors of the vertex v to the descendants of the vertex v.