Software engineers constantly deal with problems of designing, analyzing, and improving process specifications, e.g., source code, service compositions, or process models. Process specifications are abstractions of behavior observed or intended to be implemented in reality which result from creative engineering practice. Usually, process specifications are formalized as directed graphs in which edges capture temporal relations between decisions, synchronization points, and work activities. Every process specification is a compromise between two points: On the one hand engineers strive to operate with less modeling constructs which conceal irrelevant details, while on the other hand the details are required to achieve the desired level of customization for envisioned process scenarios. In our research, we approach the problem of varying abstraction levels of process specifications. Formally, developed abstraction mechanisms exploit the structure of a process specification and allow the generalization of low-level details into concepts of a higher abstraction level. The reverse procedure can be addressed as process specialization.
Process specifications represent exponential amounts of process execution scenarios with linear numbers of modeling constructs, e.g., service compositions and business process models. Nevertheless, real world process specifications cannot be grasped quickly by software engineers due to their size and sophisticated structures, leading to a demand for techniques to deal with this complexity. The research topic of process abstraction emerged from a joint research project with a health insurance company. Operational processes of the company are captured in about 4 000 EPCs. The company faced the problem of information overload in the process specifications when employing the models in use cases other than process execution, e.g., process analysis by management. To reduce the modeling effort, the company requested to develop automated mechanisms to derive abstract, i.e., simplified, process specifications from the existing ones. The research results derived during the project are summarized in [1].
Abstraction is the result of the generalization or elimination of properties in an entity or a phenomenon in order to reduce it to a set of essential characteristics. Information loss is the fundamental property of abstraction and is its intended outcome. When working with process specifications, engineers operate with abstractions of real world concepts. Process specifications are special types of entities that describe principles of observed or intended behavior. In our research, we develop mechanisms to perform abstractions of formal process specifications. The challenge lies in identifying what the units of process logic suitable for abstraction are, and then performing the abstraction afterwards. Once abstraction artifacts are identified, they can be eliminated or replaced by concepts of higher abstraction levels which conceal, but also represent, abstracted detailed process behavior. Finally, individual abstractions must be controlled in order to achieve an abstraction goal—a process specification that suits the needs of a use case.
Fig. 1 shows an example goifvtewnoasprBoPceMssNsppreoccifiecssatmioonds-, Roercdeeivre In stock proSdhuipcts Sbeinlld pRaeycmeievnet els, which are in the abstrac- Make tion relation. The example is Not in stock products aaaatbtdsattthphreteaecbtdtoopvftrteooormmsfito.h[nA2e]ob.fifsTgttruhhareecetmmitsooatdsdhkeeesll Abstraction Order Not in stock pPrmouMadrrcaatuehwkcraetiiasolen Mapnroudfauccttusre iabnrageckchgoirgnohculeniagdlhe;tdetdhferawcgiomtrhreenastpsgoarnerdye- Aonradlyezre CshtoecckIkn stock pplraoSndhuipcts Sbeinlld pRaeycmeievnet enclosed within the regions Fig. 1. Process abstraction with a dashed borderline. The fragments have structures that result in an abstract process which captures the core process behavior of the detailed one. The abstract process has dedicated routing and work activity modeling constructs and conceals detailed behavior descriptions, i.e., each abstracted fragment is composed of several work activities. The research challenge lies in proposing mechanisms which allow examining every process fragment prior to performing abstraction and suggesting mechanisms which coordinate individual abstractions, i.e., assign higher priority to abstracting certain fragments rather than the others.
The rest of the paper is organized as follows: The next section presents the connectivity-based framework designed to approach the discovery of process fragments suitable for abstraction. Sect. 3 discusses issues relevant to the control of process abstraction. The paper closes with conclusions which summarize our findings and ideas on further research steps. 2
A necessary part of a solution for process abstraction is a mechanism for the discovery of process fragments, i.e., parts of process logic suitable for abstraction. The chances of making a correct decision on which part of a process specification to abstract from can only be maximized if all the potential fragment candidates for conducting an abstraction are considered. To achieve this completeness, we employ the connectivity property of process graphs—directed graphs used to capture process specifications.
Connectivity is a property of a graph. A graph is k-connected if there exists no set of k − 1 elements, each a vertex or an edge, whose removal makes the graph disconnected, i.e., there is no path between some pair of elements in a graph. Such a set is called a separating (k − 1)-set. 1-, 2-, and 3-connected graphs are referred to as connected, biconnected, and triconnected, respectively. Each separating set of a process graph can be addressed as a set of boundary elements of a process fragment, where a boundary element is incident with elements inside and outside the fragment and connects the fragment to the main flow of the process. Let m be a parameter, the discovery of all separating m-sets (graph decomposition) of the process graph leads to the discovery of all process fragments with m boundary elements—potential abstraction candidates.
The vertex (edge) connectivity of a graph is the size of the smallest separating
set of the graph that is composed only of vertices (edges). For an arbitrary graph it
holds that its vertex connectivity is less than or equal to its edge connectivity [3].
Intuitively, removal of an edge, when testing the edge connectivity, can be
substituted with removal of an incident vertex, which implies removal of all
incident edges. In general, one can speak about (n, e)-connectivity of a graph.
A graph is (n, e)-connected if there exists no set of n nodes and there exists no
set of e edges whose removal makes the graph disconnected. Observe, an (n,
e)connected graph is (n + e + 1)-connected. A lot of research was carried out by the
compiler theory community to gain value from the triconnected decomposition
of process specifications, i.e., the discovery of triconnected fragments in process
graphs. The decompositions which proved useful were (
Fig. 2 shows an example of a process graph. Routing decisions and synchronization points can be distinguished by the degree of the corresponding vertex, i.e., the number of incident edges, and orientation of the incident edges, i.e., incoming or outgoing. Process starts (ends) have no incoming (outgoing) edges. More
A
B
Q
R
S
T E
L
P Fig. 2. Process graph, its SESE fragments
C D
F G
H J K
I
M N O C D
F G
JN KO (a) ELP
C D
F G (b)
JNK
OQR ELP
S
T A
B
Q
R
S
T
A
B
over, Fig. 2 visualizes the triconnected fragments of the graph (SESE fragments).
Each triconnected fragment is enclosed in the region and is formed by edges
inside or intersecting the region. Fragments enclosed by regions with dotted
borderlines can be discovered after performing (
The abstract process graph, obtained from the graph shown in Fig. 2, is given in Fig. 3(a). The abstraction is performed following the principles from [11], i.e., by aggregating the triconnected fragments into concepts of a higher abstraction level. The graph from Fig. 3(a) has a single separating pair B, S. Next abstractions of the triconnected fragments of the graph will result in aggregation of either the unstructured fragment composed of nodes {C, ..., R} \ {E, L, P }, or the fragment with entry node B and exit node S. To increase the granularity of process fragments used to perform abstractions, one can start looking for multiple-entriesmultiple-exits (MEME) fragments within the triconnected fragments.
Fig. 4 visualizes a connectivity-based process (0,0)
graph decomposition framework, i.e., the scheme
for process fragment discovery. In the figure, each (
A careful reader might notice that Fig. 4 does not suggest all the possibilities
for accomplishing decomposition. For instance, (
An (n, e)-decomposition (n + e ≥ 3) allows to decompose unstructured process
graphs into MEME fragments with n + e entries and exits. A process graph
in Fig. 3(b) is obtained by abstracting a (
When performing the (n + 1, e)- or (n, e + 1)-decomposition of an (n,
e)connected graph, one can remove a vertex or, respectively, an edge from the graph
and run the same algorithm that was used when obtaining the (n, e)-connected
graph; the procedure should be repeated for each vertex or, respectively, edge.
The (
By following the principles of the connectivity-based decomposition framework, we not only discover process fragments used to perform process abstraction, but also learn their structural characteristics. Structural information is useful at other stages of abstraction, e.g., when introducing control over abstraction. Initial work on classifying and checking the correctness of process specifications based on discovered process fragments was accomplished in [8,12]. 3 The task of adjusting the abstraction level of process specifications requires intensive intellectual work and in most cases can only be accomplished by process analysts manually. However, for certain use cases it is possible to derive automated or to support semi-automated abstraction control mechanisms. The task of abstraction control lies in telling significant process elements from insignificant ones and to abstract the latter. In [1], work activities are classified as insignificant if they are rarely observed during process execution. We were able to establish the abstraction control when investigated processes were annotated with information on the average time required to execute activities. Process fragments which contain insignificant activities get abstracted. Hence, we actually deal with the significance of fragments which represent detailed work specifications.
Significant and insignificant process fragments can be distinguished once a technique for fragment comparison is in place, i.e., a partial order relation is defined for process fragments. The average time required to execute activities in the process provides an opportunity to derive a partial order relation, i.e., fragments which require less time are considered insignificant. Other examples of criteria and the corresponding abstraction use cases are discussed in [13].
Once an abstraction criterion, e.g., the average execution time of activities, is accepted for abstraction, one can identify a minimal and a maximal values of the criterion for a given process specification. In our example, the minimal value corresponds to the most rarely observed activity of the process and the maximal value corresponds to the average execution time of the whole process. By specifying a criterion value from the interval, one identifies insignificant process fragments—those that contain activities for which the criterion value is lower than the specified value. Afterwards, insignificant fragments get abstracted. In [13], we proposed an abstraction slider as a mechanism to control abstraction. An abstraction slider is an object that can be described by a slider interval defined by a minimal and a maximal allowed values for an abstraction criterion, has a state—a value that defines the desired abstraction level of a process specification, and exposes behavior—an operation that changes its state. 4
In our research, we develop methods which allow the derivation of high abstraction level process specifications from detailed ones. In order to discover fragments suitable for abstraction, we employ the structure of process specifications, which are usually formalized as directed graphs. As an outcome, developed techniques can be generalized to any process modeling notation which uses directed graphs as the underlying formalism.
It is a highly intellectual task to bring a process specification to a level of abstraction that fulfills emergent engineering needs, and one without a single perfect solution. By employing the technique for the discovery of abstraction fragments, one can approach the problem as a manual engineering effort. Besides, when it is sufficient to fulfill certain use case, cf., [1], one can define principles for a semi-automated or fully automated composition of individual abstractions.
As future steps aimed at strengthening the achieved results, we plan to validate the applicability of the connectivity-based process graph decomposition framework for the purpose of process abstraction with industry partners and to look for process abstraction use cases for which automated control mechanisms can be proposed. Finally, studies regarding the methodology of abstractions need to complement the technical results.