A structural/temporal query language for Business Processes

A Business Process consists of multiple business activities, which, when combined in a flow, achieve some particular goal. These processes usually operate in a distributed environment and the software implementing them is fairly complex. Thus, effective tools for analysis of the possible executions of such processes are extremely important for companies (Beeri et al., 2006, 2007 [4] and [5]); (Deutch and Milo, 2008 [13]); these tools can allow to debug and optimize the processes, and to make an optimal use of them. The goal of the present paper is to consider a formal model underlying Business Processes and study query languages over such processes. We study in details the relationship of the proposed model with previously suggested formalisms for processes modeling and querying. In particular we propose a query evaluation algorithm of polynomial data complexity that can be applied uniformly to two kind of common queries over processes, namely queries on the structure of the process specification as well as temporal queries on the potential behavior of the defined process. We show that unless P=NPP=NP the efficiency of our algorithm is asymptotically optimal.

► We study a formal model for Business Processes and compare it to other formalisms. ► We consider two different semantics for a query language on the process executions. ► One semantics focuses on executions structure and the second on their temporal behavior. ► We present a query evaluation algorithm that can be applied uniformly to both semantics. ► We provide lower and upper bonds on the complexity of query evaluation.