A structural/temporal query language for Business Processes

AbstractA 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,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=NP the efficiency of our algorithm is asymptotically optimal