Digital Symposium Collection 2000

Workflow, Transactions, and Datalog Anthony J. Bonner   View Paper (PDF)   Return to Transactions Abstract Transaction Datalog (abbreviated TD) is a concurrent programming language that provides process modeling, database access, and advanced transactions. This paper illustrates the use of TD for specifying and simulating workflows, with examples based on the needs of a high- throughpnt genome laboratory. In addition to traditional database support, these needs include synchronization of work, cooperation between concurrent workflows, and non- serializable access to shared resources. After illustrating workflows, we use TD to explore their computational complexity in data-intensive applications. We show, for in- stance, that workflows can be vastly more complex than traditional database transactions, largely because concurrent processes can interact and communicate via the database (i.e., one process can read what another process writes). We then investigate the s,ources of this complexity, focusing on features for data modeling and process modeling. We show that by carefully controlling these features, the complexity of workflows can be reduced substantially. Finally, we develop a sub-language called fully bounded TD that provides a practical blend of modeling features while minimizing complexity. References Note: References link to DBLP on the Web. [1] Serge Abiteboul , Richard Hull , Victor Vianu : Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0 Contents [2] ... [3] Serge Abiteboul , Victor Vianu : Procedural Languages for Database Queries and Updates. JCSS 41(2) : 181-229(1990) [4] Serge Abiteboul , Victor Vianu : Datalog Extensions for Database Queries and Updates. JCSS 43(1) : 62-124(1991) [5] Serge Abiteboul , Victor Vianu , Bradley S. Fordham , Yelena Yesha : Relational Transducers for Electronic Commerce. PODS 1998 : 179-187 [6] ... [7] Philip A. Bernstein , Vassos Hadzilacos , Nathan Goodman : Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5 Contents [8] Anthony J. Bonner : Modular Composition of Transaction Programs with Deductive Databases. DBPL 1997 : 373-395 [9] ... [10] Anthony J. Bonner , Michael Kifer : Concurrency and Communication in Transaction Logic. JICSLP 1996 : 142-156 [11] Anthony J. Bonner , Michael Kifer : A Logic for Programming Database Transactions. Logics for Databases and Information Systems 1998 : 117-166 [12] Anthony J. Bonner , Michael Kifer : The State of Change: A Survey. Transactions and Change in Logic Databases 1998 : 1-36 [13] ... [14] ... [15] Anthony J. Bonner , Adel Shrufi , Steve Rozen : LabFlow-1: A Database Benchmark for High-Throughput Workflow Management. EDBT 1996 : 463-478 [16] Ashok K. Chandra , David Harel : Computable Queries for Relational Data Bases. JCSS 21(2) : 156-178(1980) [17] Ashok K. Chandra , David Harel : Structure and Complexity of Relational Queries. JCSS 25(1) : 99-128(1982) [18] Ashok K. Chandra , Dexter Kozen , Larry J. Stockmeyer : Alternation. JACM 28(1) : 114-133(1981) [19] Søren Christensen , Yoram Hirshfeld , Faron Moller : Decidable Subsets of CCS. The Computer Journal 37(4) : 233-242(1994) [20] ... [21] Hasan Davulcu , Michael Kifer , C. R. Ramakrishnan , I. V. Ramakrishnan : Logic Based Modeling and Analysis of Workflows. PODS 1998 : 25-33 [22] Umeshwar Dayal , Qiming Chen : From Database Programming to Business Process Programming. DBPL 1995 : 1 [23] Doron Drusinsky , David Harel : On the Power of Bounded Concurrency I: Finite Automata. JACM 41(3) : 517-539(1994) [24] Ahmed K. Elmagarmid (Ed.): Database Transaction Models for Advanced Applications. Morgan Kaufmann 1992, ISBN 1-55860-214-3 Contents [25] ... [26] 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) [27] David Harel : Statecharts: A Visual Formulation for Complex Systems. Science of Computer Programming 8(3) : 231-274(1987) [28] David Harel : A Thesis for Bounded Concurrency. MFCS 1989 : 35-48 [29] ... [30] John E. Hopcroft , Jeffrey D. Ullman : Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02888-X [31] ... [32] ... [33] Neil Immerman : Relational Queries Computable in Polynomial Time (Extended Abstract). STOC 1982 : 147-152 [34] Neil D. Jones , Lawrence H. Landweber , Y. Edmund Lien : Complexity of Some Problems in Petri Nets. TCS 4(3) : 277-299(1977) [35] ... [36] ... [37] ... [38] ... [39] ... [40] Dirk Taubner : Finite Representations of CCS and TCSP Programs by Automata and Petri Nets. Lecture Notes in Computer Science Vol. 369 Springer 1989, ISBN 3-540-51525-9 [41] Moshe Y. Vardi : The Complexity of Relational Query Languages (Extended Abstract). STOC 1982 : 137-146 [42] Dirk Wodtke , Gerhard Weikum : A Formal Foundation for Distributed Workflow Execution Based on State Charts. ICDT 1997 : 230-246 BIBTEX @inproceedings{DBLP:conf/pods/Bonner99,   author    = {Anthony J. Bonner},    title     = {Workflow, Transactions, and Datalog},    booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium                 on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,                 Pennsylvania},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-062-7},    pages     = {294-305},    crossref  = {DBLP:conf/pods/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM