Logic Based Modeling and Analysis of Workflows
Hasan Davulcu, Michael Kifer, C. R. Ramakrishnan, I. V. Ramakrishnan
Full Paper (PDF)

Slides (PDF)

Abstract
We propose Concurrent Transaction Logic (CTR) as the language for specifying, analyzing, and scheduling of workflows. We show that both local and global properties of workflows can be naturally represented as CTR formulas and reasoning can be done with the use of the proof theory and the semantics of this logic. We describe a transformation that leads to an efficient algorithm for scheduling workflows in the presence of global temporal constraints, which leads to decision procedures for dealing with several safety related properties such as whether every valid execution of the workflow satisfies a particular property or whether a workflow execution is consistent with some given global constraints on the ordering of events in a workflow. We also provide tight complexity results on the running times of these algorithms.

References

References, where available, link to the DBLP on the World Wide Web.

[1]
Gustavo Alonso, Divyakant Agrawal, Amr El Abbadi, Mohan Kamath, Roger Günthör, C. Mohan: Advanced Transaction Models in Workflow Contexts. ICDE 1996: 574-581
[2]
Gustavo Alonso, Divyakant Agrawal, Amr El Abbadi, C. Mohan: Functionality and Limitations of Current Workflow Management Systems. IEEE Expert 12(5): 0-(1997)
[3]
Paul C. Attie, Munindar P. Singh, Amit P. Sheth, Marek Rusinkiewicz: Specifying and Enforcing Intertask Dependencies. VLDB 1993: 134-145
[4]
Anthony J. Bonner, Michael Kifer: An Overview of Transaction Logic. TCS 133(2): 205-265(1994)
[5]
...
[6]
Anthony J. Bonner, Michael Kifer: Concurrency and Communication in Transaction Logic. JICSLP 1996: 142-156
[7]
Anthony J. Bonner, Michael Kifer, Mariano P. Consens: Database Programming in Transaction Logic. DBPL 1993: 309-337
[8]
...
[9]
Edmund M. Clarke, E. Allen Emerson, A. Prasad Sistla: Automatic Verification of Finite-State Concurrent Systems Using Temporal Logic Specifications. TOPLAS 8(2): 244-263(1986)
[10]
...
[11]
Umeshwar Dayal, Meichun Hsu, Rivka Ladin: Organizing Long-Running Activities with Triggers and Transactions. SIGMOD Conference 1990: 204-214
[12]
Ahmed K. Elmagarmid, Yungho Leu, Witold Litwin, Marek Rusinkiewicz: A Multidatabase Transaction Model for InterBase. VLDB 1990: 507-518
[13]
Ahmed K. Elmagarmid (Ed.): Database Transaction Models for Advanced Applications. Morgan Kaufmann 1992, ISBN 1-55860-214-3
Contents
[14]
...
[15]
Hector Garcia-Molina, Kenneth Salem: Sagas. SIGMOD Conference 1987: 249-259
[16]
M. R. Garey, David S. Johnson: Computer and Intractability: A Guide to NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
[17]
Dimitrios Georgakopoulos, Mark F. Hornick, Piotr Krychniak, Frank Manola: Specification and Management of Extended Transactions in a Programmable Transaction Environment. ICDE 1994: 462-473
[18]
Dimitrios Georgakopoulos, Mark F. Hornick, Amit P. Sheth: An Overview of Workflow Management: From Process Modeling to Workflow Automation Infrastructure. Distributed and Parallel Databases 3(2): 119-153(1995)
[19]
Roger Günthör: Extended Transaction Processing Based on Dependency Rules. RIDE-IMS 1993: 207-214
[20]
...
[21]
...
[22]
...
[23]
...
[24]
A. H. M. ter Hofstede, Maria E. Orlowska, Jayantha Rajapakse: Verification Problems in Conceptual Workflow Specifications. ER 1996: 73-88
[25]
...
[26]
Munindar P. Singh: Semantical Considerations on Workflows: An Algebra for Intertask Dependencies. DBPL 1995: 5
[27]
Munindar P. Singh: Synthesizing Distributed Constrained Events from Transactional Workflow. ICDE 1996: 616-623
[28]
...
[29]
Dirk Wodtke, Gerhard Weikum: A Formal Foundation for Distributed Workflow Execution Based on State Charts. ICDT 1997: 230-246
BIBTEX

@inproceedings{DBLP:conf/pods/DavulcuKRR98,
author = {Hasan Davulcu and
Michael Kifer and
C. R. Ramakrishnan and
I. V. Ramakrishnan},
title = {Logic Based Modeling and Analysis of Workflows},
booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-966-3},
pages = {25-33},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}


DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).