ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Logic Based Modeling and Analysis of Workflows.

Hasan Davulcu, Michael Kifer, C. R. Ramakrishnan, I. V. Ramakrishnan: Logic Based Modeling and Analysis of Workflows. PODS 1998: 25-33
@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-996-3},
  pages     = {25-33},
  ee        = {http://doi.acm.org/10.1145/275487.275491, db/conf/pods/DavulcuKRR98.html},
  crossref  = {DBLP:conf/pods/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

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.

Copyright © 1998 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington. ACM Press 1998, ISBN 0-89791-996-3
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1199 KB]

References

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

Referenced by

  1. Anthony J. Bonner: Workflow, Transactions, and Datalog. PODS 1999: 294-305
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:18 2009