BPMN Presentations Process Analysis

Detecting Frequently Recurring Structures in BPMN 2.0 Process Models (SummerSOC 2015)

Description

Skouradaki, Marigianna; Leymann, Frank: Detecting Frequently Recurring Structures in BPMN 2.0 Process Models. In: Proceedings of the 9th Symposium and Summer School On Service-Oriented Computing: SummerSOC’15; Heraklion, Greece, June 28 – July 04, 2015.
==========================================
Abstract
Reusability of process models is frequently discussed in the
literature. Practices of reusability are expected to increase the performance
of the designers, because they do not need to start everything from scratch,
and the usage of best practices is reinforced. However, the detection of
reusable parts and best practices in collections of BPMN 2.0 process
models is currently only defined through the experience of experts in
this field. In this work we extend an algorithm that detects the recurring
structures in a collection of process models. The extended algorithm
counts the number of times that a recurring structure appears in a
collection of process models, and assigns the corresponding number to
its semantics. Moreover, the dublicate entries are eliminated from the
collection that contains the extracted recurring structures. In this way,
we assert that the resulting collection contains only unique entries. We
validate our methodology by applying it on a collection of BPMN 2.0
process models and analyze the results. As shown in the analysis the
methodology does not only detect applied practices, but also leads to
conclusions of our collection’s special characteristics.

Transcript

University of Stuttgart
Universitätsstr. 38
70569 Stuttgart
Germany
Phone +49-711-685 88477
Fax +49-711-685 88472
Research
Marigianna Skouradaki, Frank Leymann
Institute of Architecture of Application Systems
{firstname.lastname}@iaas.uni-stuttgart.de
“Detecting Frequently Recurring
Structures in
BPMN 2.0 Process Models”
SummerSOC 2015
22
Research
© Marigianna Skouradaki
BPMN 2.0
Process Models
Collection
Fragments
Repository
Workload
Mix
Graph
Matching
Selection
Criteria
Composition
Criteria
80%
20%
Motivation: Generation of Realistic Workload
33
Research
© Marigianna Skouradaki
Agenda
 Process Model Matching
 Basic Concepts
 Algorithms
 Validation & Discussion
 Conclusions & Outlook
4
Process Model Matching
55
Research
© Marigianna Skouradaki
BPMN 2.0 Collection Characteristics
 Detect the reoccurring structures on BPMN 2.0 process
models which:
 Might be anonymized (no text information available)
 Might be mock-up models (non-executable)
66
Research
© Marigianna Skouradaki
Text Matching
 Cannot be applied to anonymized models
77
Research
© Marigianna Skouradaki
Behavioral Matching
log
 Cannot be applied on mock-up models
log
2
88
Research
© Marigianna Skouradaki
Structural Matching
99
Research
© Marigianna Skouradaki
The Challenge of Graph Isomorphism
NonDeterministic Polynomial
Time
(NP – Complete)
The time required to solve the
problem using any currently
known algorithm increases very
quickly as the size of the
problem grows.
1010
Research
© Marigianna Skouradaki
Subgraph Isomorphism on BPMN 2.0 Process Models
BPMN 2.0 Process Models are special types of graphs
Subgraph isomorphism can be applied in lower complexity1
1 R. M Verma.; and S. W. Reyner; “An analysis of a good algorithm for the subtree problem, correlated,” SIAM J. Comput., vol. 18, no. 5,
pp. 906–908, Oct. 1989.
11
Basic Concepts
1212
Research
© Marigianna Skouradaki
Exiting Attributes: Nested
1313
Research
© Marigianna Skouradaki
Exiting Attributes: Different Positions
1414
Research
© Marigianna Skouradaki
Exiting Attributes: Partially Similar
1515
Research
© Marigianna Skouradaki
Process Fragment
A Process Fragment is a piece of process model with loose
completeness and consistency. The existence of process
graph elements (start, end, activities, context etc.) is
possible but not imperative in a process fragment.
However, a process fragment must have at least one
activity and there must be a way to convert it to an
executable process graph.2
1. It is not necessarily related with a complete process model
2. A starting point is not defined
3. Existence of split, merge node or event is optional
2D. Schumm, F. Leymann, Z. Ma, T. Scheibler, and S. Strauch, “Integrating Compliance into Business Processes: Process Fragments as
Reusable Compliance Controls” in MKWI’10, Göttingen, Germany, February 23-25, 2010, Ed., Conference Paper, pp. 2125–2137.
1616
Research
© Marigianna Skouradaki
Checkpoints & Relevant Process Fragments (RPFs)
 Checkpoint (the starting points)
 A pre-configured type of node that is used as start point of
the “extended” process fragments
 Relevant Process Fragment
 Exists in at least K business processes
 Starts with a checkpoint
 Has at least N nodes including the checkpoint
 Contains at least one activity
1717
Research
© Marigianna Skouradaki
Checkpoints & Relevant Process Fragments
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
1818
Research
© Marigianna Skouradaki
Checkpoints & Relevant Process Fragments
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
1919
Research
© Marigianna Skouradaki
Checkpoints & Relevant Process Fragments
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
RPF
RPF
2020
Research
© Marigianna Skouradaki
Checkpoints & Relevant Process Fragments
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
2121
Research
© Marigianna Skouradaki
Checkpoints & Relevant Process Fragments
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
RPF
RPF
2222
Research
© Marigianna Skouradaki
Checkpoints & Relevant Process Fragments
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
2323
Research
© Marigianna Skouradaki
Checkpoints & Relevant Process Fragments
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
RPF
24
Algorithms
2525
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
2626
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
2727
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
2828
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
2929
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
3030
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
3131
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
3232
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
3333
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
3434
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
3535
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
3636
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
3737
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
3838
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
3939
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
4040
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
4141
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
4242
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
4343
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
4444
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
4545
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
4646
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
4747
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
4848
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
4949
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
5050
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
5151
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
5252
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
5353
Research
© Marigianna Skouradaki
Algorithm: Discovery of RPFs
K = 2 Process ModelsCheckpoints: Events, Gateways N = 3 Nodes
…continue likewise..
 Will not work for cycles
5454
Research
© Marigianna Skouradaki
Discover Duplicates and Count Appearance
RPF
Collection
Newly Discovered RPF
5555
Research
© Marigianna Skouradaki
Discover Duplicates and Count Appearance
RPF
Collection
Newly Discovered RPF
5656
Research
© Marigianna Skouradaki
Discover Duplicates and Count Appearance
RPF
Collection
Newly Discovered RPF
For each RPF in Collection:
If RPF have the same size:
COMPARE
5757
Research
© Marigianna Skouradaki
Discover Duplicates and Count Appearance
RPF
Collection
Newly Discovered RPF
5858
Research
© Marigianna Skouradaki
Discover Duplicates and Count Appearance
RPF
Collection
Newly Discovered RPF
2
5959
Research
© Marigianna Skouradaki
Discover Duplicates and Count Appearance
RPF
Collection
Newly Discovered RPF
6060
Research
© Marigianna Skouradaki
Discover Duplicates and Count Appearance
RPF
Collection
Newly Discovered RPF
1
61
Validation and Discussion
6262
Research
© Marigianna Skouradaki
Validation
 43 BPMN 2.0 Process Models
 BPMN 2.0 Standard Example Processes
 Models used in Pietsch and Wenzel, 2012
 903 Comparisons
 1544 non-filtered RPFs
 83.22% decrease of results when filtering duplicates
(259 RPFs)
 54 RPF appear > 1 time
Median = Threshold = 14
 27 RPFs with re-appearance rate above the threshold
6363
Research
© Marigianna Skouradaki
Some Representative RPF and Number of Appearance
ID Fragment Count
1 178
2 169
3 117
4 101
5 62
6 60
7 44
8 42
9 42
6464
Research
© Marigianna Skouradaki
Conclusions & Outlook
 Extension of RPF Discovery algorithm
 Automatic count of the RPF appearance in collection
 We have evaluated the approach on 43 BPMN 2.0 process models
 Conclusions on frequently used structures (best practices)
 Conclusions for collection’s special characteristics
 Extend the algorithms for the complete set of BPMN 2.0
 Apply to thousands real world BPMN 2.0 process models and
execute thorough analysis
 Implement the prototype for process synthesizing methodology
Thank You!!!
Marigianna Skouradaki: skourama@iaas.uni-stuttgart.de

Leave a Comment

Get the BPI Web Feed

Using the HTML code below, you can display this Business Process Incubator page content with the current filter and sorting inside your web site for FREE.

Copy/Paste this code in your website html code:

<iframe src="https://www.businessprocessincubator.com/content/detecting-frequently-recurring-structures-in-bpmn-2-0-process-models-summersoc-2015/?feed=html" frameborder="0" scrolling="auto" width="100%" height="700">

Customizing your BPI Web Feed

You can click on the Get the BPI Web Feed link on any of our page to create the best possible feed for your site. Here are a few tips to customize your BPI Web Feed.

Customizing the Content Filter
On any page, you can add filter criteria using the MORE FILTERS interface:

Customizing the Content Filter

Customizing the Content Sorting
Clicking on the sorting options will also change the way your BPI Web Feed will be ordered on your site:

Get the BPI Web Feed

Some integration examples

BPMN.org

XPDL.org

×