Edinburgh Research Explorer

Specifying and Reasoning about Workflows with Path Constraints

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Original languageEnglish
Title of host publicationInternet Applications
Subtitle of host publication5th International Computer Science Conference, ICSC'99, Hong Kong, China, December 13-15, 1999, Proceedings
PublisherSpringer Berlin Heidelberg
Pages226-235
Number of pages10
Volume1749
ISBN (Electronic)978-3-540-46652-9
ISBN (Print)978-3-540-66903-6
DOIs
Publication statusPublished - 1999

Abstract

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.

ID: 19850415