One of the most common frameworks for specifying workflows is control flow graph [3,11,13,22]. Although a control flow graph can depict local execution dependencies of the tasks in a workflow, it is not capable of expressing global dependencies and is not helpful in reasoning about workflow properties. Recently, a path constraint theory has been developed for semistructured data [2,7,8,9,10]. It has proven useful for semantic specification and query optimization in the database context. To overcome the limitations of flow control graphs, this paper generalizes the path constraint theory to specify and analyze workflows. More specifically, it proposes a path constraint language and shows that both local and global dependencies, as well as sub-workflows, can be naturally expressed in the language. This allows one to reason about workflows in the traditional logic framework. The paper also establishes the decidability of several verification problems associated with workflows.
|Title of host publication||Internet Applications|
|Subtitle of host publication||5th International Computer Science Conference, ICSC'99, Hong Kong, China, December 13-15, 1999, Proceedings|
|Publisher||Springer Berlin Heidelberg|
|Number of pages||10|
|Publication status||Published - 1999|