This paper presents the idea of a compendium of process technologies, i.e., a concise but comprehensive collection of techniques for process model analysis that support research on the design, execution, and evaluation of processes. The idea originated from observations on the evolution of process-related research disciplines. Based on these observations, we derive design goals for a compendium. Then, we present the jBPT library, which addresses these goals by means of an implementation of common analysis techniques in an open source codebase.
Study of processes, i.e., orderings of observed events, is integral to the eld of information systems. Usually, processes are studied by means of models. A process model is a particular representation of processes of the same nature. A work ow model and a business process model are examples of process models within the information systems discipline. Many research activities that deal with the design, execution, and evaluation of processes, rely on analysis of process models. Results of these endeavors are often validated by means of prototypical implementations. Such prototypes serve as a proof of concept and provide other researchers with a reference to enter competition for better results.
Unfortunately, such prototyping is usually hindered by di erent programming languages, frameworks, availability of other scienti c prototypes and their reusability. Moreover, a considerable portion of a researcher's time must often be spent on making results applicable for di erent contexts, e.g., for process models captured in di erent modeling languages, such as BPMN and EPC. This holds even though these di erent contexts usually share similar characteristics. For instance, languages for specifying process models are rather similar w.r.t. the core modeling elements and their semantics.
This paper proposes design principles for a compendium of process technologies and discusses a concrete instantiation of these principles in the jBPT project1. The project develops a library of often used resources and algorithms when 1 jBPT stands for \Business Process Technologies for Java". dealing with analysis of process models. The library is implemented in Java and published2 as open source under the GNU Lesser GPL license. The Java language is often chosen as a programming language for scienti c prototypes due to its \architecture-neutral and portable" principle, which is also summarized in the Java promise of \write once, run anywhere" (despite of the fact that this claim is still arguably questionable). The jBPT project enjoys the cross-platform bene ts of Java but also incorporates its own design philosophy which aims at maximal reuse of developed techniques.
The core design principle of the compendium is to bridge the heterogeneity of di erent process modeling languages by a uni ed framework that builds upon the most generic notions of graph theory. The methods and techniques included in the jBPT library are implemented for the common entities of di erent modeling languages and, thus, often can be reused for models captured in di erent languages. This principle has found its wide use in numerous research prototypes.
The next section lists observations on research that led to the idea of a compendium of process technologies. Sect. 3 summarizes design goals for the compendium. Sect. 4 presents the jBPT library (an instantiation of the compendium design), gives a usage example, outlines its functionality, and illustrates its maturity by enumerating research projects which rely on the library. Sect. 5 positions jBPT among other research frameworks, before we conclude the paper. 2
In order to derive requirements for a compendium of process technologies, we start with a number of observations on process-related research.
The Nucleus of Process Modeling Languages. First and foremost, we observe that the plethora of process modeling languages, all de ning their own syntax, semantics, and notation, largely hides the fact that most languages have a common conceptual root. On the one hand, they can essentially be seen as control ow graphs, with nodes relating to functional entities (what is done?) and edges de ning the coordination for process execution (how is it done?). Clearly, process models capture more than the functional and the control ow perspective. However, most other perspectives, such as data handling and organizational structures, are often attached to the control ow graph (e.g., by partitioning the graph with swimlanes for organizational roles). Hence, the control ow graph can be seen as the backbone of any process model. On the other hand, we observe that control ow graphs are not arbitrary graphs, but are structured by `common behaviors' of processes. Execution alternatives, concurrency, repetitive behavior, and hierarchical re nement are basic behavioral patterns that are supported by all major process modeling languages. Although languages de ne di erent mechanisms for realizing these patterns, they lead to similar control ow graphs.
The Need for Evaluation. In recent years, there has been a clear trend towards empirical evaluation of process research. Depending on the type of the concept that is to be validated, user studies or experiments with large
(and often real-world) datasets are conducted. Consequently, virtually all newly
proposed concepts and techniques are implemented at least in prototypes. Yet,
most evaluations reported in research papers are not reproducible. This is only
partly due to the non-availability of non-disclosed datasets. Often, the actual
implementations are either not available or are hard to run and extend in the
absence of a generic research framework for process model analysis. Also, we
observe that a lot of functionality clones exist across these research prototypes,
a result of redundant development e orts. Generic research frameworks may
overcome these problems as successfully demonstrated in certain areas, e.g., by
the ProM framework [
Broad Applicability of Structural or Behavioral Concepts. Another
remarkable trend in process research is the broad applicability of certain concept
and techniques for a large number of research questions. That is, a number of
structural and behavioral concepts and techniques are on the one hand speci c to
process models (and thus not covered by frameworks for graph analysis), but on
the other hand general enough to address a variety of research issues. Prominent
examples are the Re ned Process Structure Tree [
Based on the observations outlined in the previous section, this section enumerates design goals for a compendium of process technologies.
Reuse of Resources and Algorithms. The core idea behind the design of a compendium is reuse of functionality in all possible contexts. Resources and algorithms needed to conduct process model analysis should be applicable in di erent contexts. Here, di erent contexts are often dictated by di erent modeling languages. As detailed above, these languages usually operate within the common notion of a control ow graph. Therefore, the support of several abstraction levels when working with the notion of a control ow graph, which might range from a concrete syntax speci cation of a modeling notation to a generic graph-based formalism, is identi ed as a fundamental requirement for the design of a compendium. Every resource and every algorithm from a compendium should address the most abstract level of the control ow notion possible. This principle allows maximal reuse of techniques across all contexts that share the same abstraction level of concepts under consideration.
Don't Repeat Yourself. Every implementation of an analysis technique should be unique within a compendium. All tests and optimizations should target this unique implementation.
E ective Modularity. It is expected that a concrete realization of a compendium will comprise a large collection of methods and techniques. Therefore, the availability of mechanisms for its e ective modularization is essential. A compendium should allow natural identi cation of its independent functional components, which may be separated and/or recombined.
Utility Functionality. Research prototypes often require utility
functionality besides the actual implementation of the analysis technique. An example
would be the support of di erent serialization formats. In particular, serialization
formats for common modeling notations and means to generate graph de nitions
used by standard software for graph visualization, e.g., dot graph description
language [
Publishing Philosophy. To support researchers during the implementation of research prototypes, a compendium of process technologies needs to be publicly available with little restrictions on it usage. Further, extensions and future developments of a compendium are fostered by an open source publishing philosophy. In particular, a compendium published under the GNU Lesser GPL3 ensures that any extensions will be available for the research community. 4
To achieve the design goals for a compendium of process technologies, we developed the jBPT library. In this section, we review the essentials of this library by rst sketching its architecture and giving an illustrative example of how the library can facilitate development of process model analysis techniques. Finally, we lists some of the most used functionality of the library and give an overview of its application in concrete research projects.
Architecture. An excerpt of the core structure of jBPT is shown in Fig. 1. It illustrates the interface and class hierarchy to capture di erent types of graphs, starting with multi-hypergraphs as the most general model. It also shows that all graph models are typed with generics, which allows, for instance, to de ne a PetriNet as an AbstractDirectedGraph with parameter E being bound to Flow classes and parameter V to Node classes. A Flow class represents a specialization of a directed edge, i.e., a AbstractDirectedEdge with V being bound to Node classes. The de nition of process model classes, or more speci c classes for BPMN or EPC models, and Petri nets as specializations of di erent kinds of graphs is the basis for extensive reuse of analysis algorithms. Those may be implemented on the according level of the graph hierarchy and then be used for all specializations.
Illustrative Example. To illustrate how jBPT facilitates the development
of research prototypes, we consider two properties of process models. First,
structural soundness 4 relates to the structure of a process model, see [
V extends IVertex> AbstractMultiHyperGraph
GObject <E extends IDirectedHyperEdge<V>,
V extends IVertex> AbstractMultiDirectedHyperGraph
<E exVteenxdtsenIdDsirIeVcetretdeExd>ge<V>, AbstractMultiDirectedGraph
<E exVteenxdtsenIdDsirIeVcetretdeExd>ge<V>, AbstractDirectedGraph ProcessModel
PetriNet
Vertex Node
IGObject IVertex
<V extends IVertex> IHyperEdge
<V extends IVertex>
IDirectedHyperEdge <V extends IVertex> AbstractHyperEdge
<V extends IVertex> AbstractDirectedHyperEdge
<V extends IVertex> AbstractDirectedEdge
<V extends IVertex> IDirectedEdge
<V extends IVertex> IEdge Bpmn
Epc
NetSystem
Place
Transition
Flow
execution of the model. Second, we consider testing a Petri net for the structure
of a Work ow net [
Checking for structural soundness is equivalent to a check of strong
connectedness5 of an enhanced version of the directed graph which is used to describe a
process model, see one possible implementation in the isMultiTerminal function
in DGA.java listing below. The enhanced graph is obtained by introducing a fresh
source vertex (src) and a fresh sink vertex (snk), lines 8{10, to the graph, and
then adding a fresh edge from the fresh sink to the fresh source. A directed graph
describes a structurally correct process model if its enhanced version is strongly
connected. A directed graph is strongly connected if it constitutes a single strongly
connected component (SCC)6. Strongly connected components of directed graphs
are discovered in O(SV S+SES) time with V and E as the sets of vertices and edges of
the graph [
DGA.java { Collection of algorithms to manipulate directed graphs. public boolean isTwoTerminal(IDirectedGraph<E,V> g) { if (g==null) return false; if (this.getSources(g).size()!=1 || this.getSinks(g).size()!=1) return false; return this.isMultiTerminal(g); Below, the generic usage of the outlined functionality is illustrated by the Work ow net check for PetriNet objects. Function isWorkflowNet simply wraps the isTwoTerminal function for PetriNet objects, see lines 5{6 below. PetriNetStructuralClassChecks.java { Structural tests for Petri nets. 1 : public class PetriNetStructuralClassChecks { 2 : ... 3 : public static boolean isWorkflowNet(PetriNet net) { 4 : if (net==null) return false; 5 : DGA<Flow,Node> dga = new DGA<Flow,Node>(); 6 : return dga.isTwoTerminal(net); 7 : } 8 : }
jBPT Functionality. Besides already mentioned object models for various
process modeling languages, the jBPT library o ers a collection of supporting
management routines, such as parsing and serialization to standard formats.
Further, the functionality of the jBPT library comprises, among others, basic
graph algorithms, connectivity-based decompositions of graphs and related
process model related applications, e.g., the RPST [
Applications. The idea of a compendium of process technologies as
implemented by jBPT proved indeed valuable for the implementation of various
research prototypes. Among others, the following projects are based on jBPT.
bpstruct7 is a collection of techniques proposed in [
BPM Academic Initiative8 is an academic version of a professional business process management tool. It integrates bpstruct through a REST API. apromore9 is an open source repository to store and disclose process models of a variety of languages, such as BPMN, EPCs, YAWL, Work ow nets, etc. The jBPT initiative provides core functionality for the apromore platform. It underpins the canonical process model format of apromore and many of its core features and functionalities.
Flexab [
There are several other research frameworks that have been designed in the spirit
of a compendium of process technologies, yet with a di erent focus. A prominent
example is the ProM framework [
Various process model analysis techniques are available on demand in the
Business Process Services10 portal developed by IBM Research. These services can
be invoked for a process model description and, for instance, conduct control ow
analysis or refactor the model. The analysis of interactions between processes
is at the core of the ServiceTechnology toolset11, see also [
8 http://academic.signavio.com/ 9 http://code.google.com/p/apromore/ 10 http://business-services.researchlabs.ibm.com 11 http://www.service-technology.org/ implement techniques for service composition, discovery, and substitution. Both toolsets support the development of research prototypes by providing speci c, encapsulated functionality and, thus, have a di erent focus compared to jBPT, which aims at supporting the actual development of prototypes with basic data structures and algorithms. 6
In this paper, we argued for the creation of a compendium of process technologies. The idea is to have a comprehensive collection of techniques for process model analysis, thereby supporting the implementation of research prototypes. Based on observations on process research, we derived design goals for a compendium. Further, we presented the jBPT library as a rst implementation of that idea. This library o ers a broad range of basis analysis and utility functionality and, due to its open publishing model, can easily be extended. It regularly attracts over 250 unique Internet visitors per month from more than 50 countries. Acknowledgments. We highly appreciate the contributions to jBPT made by the community as detailed at http://code.google.com/p/jbpt/people/list.