Doctoral Thesis DIS-2009-09

BibliographyVanhatalo, Jussi: Process Structure Tress.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Doctoral Thesis (2009).
247 pages, english.
CR-SchemaH.4.1 (Office Automation)
Abstract

In this thesis, we present two complementary techniques that each decomposes a business process model into a hierarchy of single-entry-single-exit fragments. The obtained decompositions we call process structure trees. We represent a business process model as a workflow graph that is a model of the control-flow of the business process model. We study the problem of parsing, that is, how to make the structure of the workflow graph explicit. More precisely, our goal is to decompose a workflow graph into a hierarchy of workflow graphs that are subgraphs having a single entry and a single exit of control. We say that such a subgraph is a fragment of the original workflow graph. Finding such a decomposition is an important step, for example, for translating a business process model designed in a graph-based language, such as the Business Process Modeling Notation (BPMN), into a business process model represented in a more structured language than BPMN, such as the Web Services Business Process Execution Language (BPEL). For this and other applications, it is essential that the decomposition be unique and modular, where modular means that a local change of the workflow graph can only cause a local change in the decomposition. In addition, it is desirable that the decomposition is as fine-grained as possible, to maximize the structural information it represents. Moreover, it is beneficial for practical applications if the decomposition can be computed fast. We propose a decomposition called the refined process structure tree that meets these requirements. We show that it is unique, modular, and finer-grained than the decompositions in previous work. Moreover, we present an algorithm that computes it in linear time. Our solution is based on and extends similar work on a parse tree of a sequential program by Tarjan and Valdes [74, 5]. Their and our work builds on earlier work from graph theory on a decomposition called the tree of triconnected components. In fact, the graph theory behind our decomposition is related to the connected, biconnected, and triconnected components of a graph. We present two independent characterizations of the refined process structure tree, which we prove to be equivalent: (1) a simple descriptive characterization that justifies our particular choice of the decomposition, and (2) a constructive characterization that allows us to compute the decomposition in linear time. The finer-grained granularity of the refined process structure tree comes at a cost if it is compared to another earlier parse tree for sequential programs called the program structure tree (presented by Johnson et al. [33, 32]), which is also unique and computed with a linear time algorithm. The cost is that in the program structure tree, each node and edge belong to exactly one fragment, whereas in the refined process structure tree each edge belong to exactly one fragment, but nodes may be shared between multiple fragments. We slightly improve the granularity of the program structure tree with our normal process structure tree without losing its above-mentioned desirable properties. In addition, we unify the theory of the normal process structure tree with the theory of the refined process structure tree. For instance, we justify the particular choices of the decompositions with analogous descriptive characterizations. The normal and the refined process structure tree are, in a sense, dual notions: the former is a decomposition based on the nodes, whereas the latter is a decomposition based on the edges. Moreover, we show how the advantages of the process structure trees can be combined by using them together. We define the process structure trees for workflow graphs that have exactly one start event (source), exactly one end event (sink), and every node on a path from the start to the end event. Such a connected graph is also known as a two-terminal graph. Earlier decomposition techniques are also defined for this class of graphs. However, a business process model may have multiple start and end events. Therefore, we extend the applicability of the process structure trees for a more general class of graphs that we call multi-terminal graphs. Such a graph may be disconnected and have multiple sources and sinks, but every node must be on a path from a source to a sink. We present the theory on the process structure trees for multi-terminal graphs in general, not only specifically to workflow graphs. Therefore, the theory can also be applied to other similar directed graphs, such as a flowchart, a control-flow graph of a program, or a Petri net. We demonstrate the usefulness of the process structure trees with applications dealing with business process models. We use the refined process structure tree as basis for a refactoring technique that transforms a workflow graph into a normal form that is better-structured in general and thus easier to comprehend than the original workflow graph. We also present a technique that completes a workflow graph with multiple end events into a workflow graph that represents the same business process model and has only one end event. Our technique is based on the refined process structure tree. Furthermore, we show how the process structure trees can speed up control-flow analysis of a workflow graph. We use soundness as the notion of correctness of the control-flow. The process structure trees give rise to a divide-and-conquer technique that can speed up soundness checkers, such as a state-space explorer. We have implemented the process structure trees and describe our implementation. We show in a case study that the process structure trees can significantly speed up the soundness checking of workflow graphs originating from industrial business process models.

Department(s)University of Stuttgart, Institute of Architecture of Application Systems
Entry dateApril 8, 2016
   Publ. Computer Science