Compiling business processes: untangling unstructured loops in irreducible flow graphs

Wei Zhao, Rainer Hauser, Kamal Bhattacharya, Barrett R. Bryant, Fei CaoInternational Journal of Web and Grid Services 2006 · DOI

TL;DR

This paper tackles the challenge of translating unstructured business process models, often described with "goto"-like constructs, into structured executable code like BPEL. They introduce a novel method using Regular Expressions (REL) to systematically untangle irreducible loops, ensuring the generated code is both correct and manageable in complexity. This is crucial for bridging the gap between business analysts' intuitive modeling and the strict requirements of execution languages.

What Problem Does This Paper Address?

Business processes are often modeled using visual languages that allow for flexible, almost "goto"-like control flow. However, when these models need to be translated into executable languages like BPEL (Business Process Execution Language), which enforce structured control flow (e.g., if-else, while loops), a significant challenge arises. Specifically, "unstructured loops" and "irreducible flow graphs" – situations where loops have multiple entry points or complex interdependencies – are difficult to map directly to structured constructs without generating overly complex or incorrect code. This paper aims to provide a systematic and optimized method for compiling these problematic, unstructured business process models into structured, executable representations.

Methods

The core of the paper's contribution lies in their Regular Expression Language (REL) approach. This method involves two main steps:

  1. Translation from Finite Automaton (FA) to Regular Expression (RE): They first represent the business process model as a Finite Automaton. Then, they use a system of right-linear set equations, derived from the FA, to generate a Regular Expression. This RE serves as an intermediate, textual representation of the process logic.
  2. Compilation from REL to BPEL: The generated RE is then compiled into BPEL code. This step leverages an attribute grammar to map REL constructs to BPEL constructs.

A key aspect of their method is the focus on optimizations at the RE level to control code complexity. They employ strategies like:

  • Arden's Rule: For removing self-recursion in REs.
  • Dominator Tree Analysis: To determine an optimal substitution order for solving the set equations, which directly impacts the complexity of the generated RE and thus the BPEL code.
  • Loop Exit Optimization: To handle multiple loop exits gracefully.
  • Common Sub-expression Elimination: To reduce code redundancy.

They specifically address the problem of irreducible graphs by defining them based on the presence of unstructured loops where entries don't dominate each other. Their approach aims to generate an "optimal" RE, meaning one with minimal loops and constructs, leading to more manageable BPEL code.

Datasets

Not discussed in the paper. The authors use a sample "online product purchase system" as an illustrative example throughout the paper. They also mention using a "freely available UML tool 'Poseidon for UML'" to draw activity diagrams and a "random XMI file generator" for experimentation.

Key Insights and Ideas

  • Bridging the Unstructured-to-Structured Gap: The paper highlights that business users often prefer intuitive, unstructured modeling, but execution requires structured code. Their REL approach provides a systematic way to bridge this gap, especially for complex cases involving irreducible loops.
  • Regular Expressions as an Intermediate Representation: Using REs as an intermediate step offers a powerful way to linearize graphical models and apply logic-based optimizations before generating target code.
  • Optimality through Equation Solving Strategy: The choice of substitution order when solving the set equations derived from the FA is critical for generating an optimal RE. Their dominator tree-based strategy ensures this optimality, leading to simpler code.
  • Irreducible Loops are the Core Challenge: The paper clearly defines and addresses the problem of irreducible loops, which are the primary obstacle in transforming unstructured flow graphs into structured code.
  • BPEL as a Target Language: The work is demonstrated with BPEL, a standard for web service orchestration, making the findings directly relevant to modern enterprise systems.

Key Results

The paper presents a method that can compile irreducible business process models into structured BPEL code with controlled complexity. While specific quantitative results are presented in Table 2, they focus on the performance of their REL algorithm in terms of execution time and output BPEL size.

  • Performance: The algorithm's execution time is generally linear with respect to the number of nodes and edges for reducible graphs. For graphs with irreducible loops, the runtime increases. For a graph with 100 nodes and 134 edges, the algorithm took 980 milliseconds and generated 810 lines of BPEL code.
  • BPEL Size: The size of the generated BPEL code is also influenced by the complexity of the graph, particularly the presence of irreducible loops. For strongly connected components, the output size can be exponential. However, for graphs with some irreducible loops but not strongly connected components, the REL algorithm generates BPEL of an optimal size.

Limitations and Future Work

  • OR Semantics: The current algorithm assumes XOR and AND transition semantics. It fails for OR semantics, which are not standard in all business modeling tools and are represented differently in BPEL (e.g., using WSFL links).
  • Concurrency: While the abstract mentions supporting concurrent flows, the detailed algorithm presented focuses on non-concurrent processes.
  • Platform-Specific Optimizations: The generated target code can be further optimized for platform-specific concerns, but this aspect is not discussed in detail.
  • Future Work:
    • Extending the algorithm to handle OR semantics.
  • Exploring patterns like "Multiple Choice," "Implicit Termination," "Interleaved Parallel Routing," and "Milestone" which are not currently considered.
  • Investigating the generation of optimal non-deterministic REs for deterministic FAs.
  • Decentralizing BPEL execution, which could potentially eliminate the unstructured loop problem in translation.

Summary updated

Abstract

This paper presents a systematic study of some major problems involved in the transformation of business process modelling languages to executable business process representations. A business process modelling language usually uses the simple concept of 'goto' to describe the operation sequence of a business. If a structured language is chosen as the executable representation, it is difficult to compile the unstructured goto flows into structured statements when the process model is irreducible. This paper discusses a method called Regular Expression Language (REL). REL is a method that can compile a business process model that is irreducible with unstructured loops to statements in structured languages with controlled code complexity. Examples are given for compiling models expressed as UML2 Activity Diagrams into the Business Process Execution Language for Web Services (BPEL4WS).
BibTeX
@article{zhao2006compiling,
  author = {Wei Zhao and Rainer Hauser and Kamal Bhattacharya and Barrett R. Bryant and Fei Cao},
  title = {{Compiling business processes: untangling unstructured loops in irreducible flow graphs}},
  journal = {International Journal of Web and Grid Services},
  year = {2006},
  doi = {10.1504/ijwgs.2006.008880},
}
Figure