ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Chronological Scheduling of Transactions with Temporal Dependencies.

Dimitrios Georgakopoulos, Marek Rusinkiewicz, Witold Litwin: Chronological Scheduling of Transactions with Temporal Dependencies. VLDB J. 3(1): 1-28(1994)
@article{DBLP:journals/vldb/GeorgakopoulosRL94,
  author    = {Dimitrios Georgakopoulos and
               Marek Rusinkiewicz and
               Witold Litwin},
  title     = {Chronological Scheduling of Transactions with Temporal Dependencies},
  journal   = {VLDB J.},
  volume    = {3},
  number    = {1},
  year      = {1994},
  pages     = {1-28},
  ee        = {db/journals/vldb/GeorgakopoulosRL94.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Database applications often impose temporal dependencies between transactions that must be satisfied to preserve data consistency. The extant correctness criteria used to schedule the execution of concurrent transactions are either time independent or use strict, difficult to satisfy real-time constraints. On one end of the spectrum, serializability completely ignores time. On the other end, deadline scheduling approaches consider the outcome of each transaction execution correct only if the transaction meets its real-time deadline. In this article, we explore new correctness citeria and scheduling methods that capture temporal transaction dependencies and belong to the broad area between these two extreme approaches. We introduce the concept of succession dependency and chronological dependency and define correctness criteria under which temporal dependencies between transactions are preserved even if the dependent transactions execute concurrently. We also propose a chronological scheduler that can guarantee that transaction executions satisfy their chronological constraints. The advantages of chronological scheduling over traditional scheduling methods, as well as the main issues in the implementation and performance of the proposed scheduler, are discussed.

Copyright © 1994 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Key Words

Transaction ordering, synchronization, execution correctness, concurrent succession, partial rollbacks.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[Abbott & Garcia-Molina 1992]
Robert K. Abbott, Hector Garcia-Molina: Scheduling Real-Time Transactions: A Performance Evaluation. ACM Trans. Database Syst. 17(3): 513-560(1992) BibTeX
[Bernstein et al. 1987]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
[Berry 1986]
...
[Breitbart et al. 1991]
Yuri Breitbart, Dimitrios Georgakopoulos, Marek Rusinkiewicz, Abraham Silberschatz: On Rigorous Transaction Scheduling. IEEE Trans. Software Eng. 17(9): 954-960(1991) BibTeX
[Breitbart & Silberschatz 1988]
Yuri Breitbart, Abraham Silberschatz: Multidatabase Update Issues. SIGMOD Conference 1988: 135-142 BibTeX
[Dayal et al. 1990]
Umeshwar Dayal, Meichun Hsu, Rivka Ladin: Organizing Long-Running Activities with Triggers and Transactions. SIGMOD Conference 1990: 204-214 BibTeX
[Du & Elmagarmid 1989]
Weimin Du, Ahmed K. Elmagarmid: Quasi Serializability: a Correctness Criterion for Global Concurrency Control in InterBase. VLDB 1989: 347-355 BibTeX
[Elmagarmid et al. 1991]
...
[Eswaran et al. 1976]
Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX
[Farrag & Ozsu 1989]
Abdel Aziz Farrag, M. Tamer Özsu: Using Semantic Knowledge of Transactions to Increase Concurrency. ACM Trans. Database Syst. 14(4): 503-525(1989) BibTeX
[Garcia-Molina 1983]
Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983) BibTeX
[Garcia-Molina & Salem 1987]
Hector Garcia-Molina, Kenneth Salem: Sagas. SIGMOD Conference 1987: 249-259 BibTeX
[Georgakopoulos et al. 1991]
Dimitrios Georgakopoulos, Marek Rusinkiewicz, Amit P. Sheth: On Serializability of Multidatabase Transactions Through Forced Local Conflicts. ICDE 1991: 314-323 BibTeX
[Gray 1978]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[Gray 1981]
Jim Gray: The Transaction Concept: Virtues and Limitations (Invited Paper). VLDB 1981: 144-154 BibTeX
[Gray et al. 1981]
Jim Gray, Pete Homan, Henry F. Korth, Ron Obermarck: A Straw Man Analysis of the Probability of Waiting and Deadlock in a Database System. Berkeley Workshop 1981: 125 BibTeX
[Herlihy 1990]
Maurice Herlihy: Apologizing Versus Asking Permission: Optimistic Concurrency Control for Abstract Data Types. ACM Trans. Database Syst. 15(1): 96-124(1990) BibTeX
[Jefferson 1985a]
...
[Jefferson 1985b]
David R. Jefferson: Virtual Time. ACM Trans. Program. Lang. Syst. 7(3): 404-425(1985) BibTeX
[Jefferson et al. 1987]
David R. Jefferson, Brian Beckman, Frederick Wieland, Leo Blume, Mike Di Loreto, Phil Hontalas, Pierre Laroche, Kathy Sturdevant, Jack Tupman, L. Van Warren, John J. Wedel, Herb Younger, Steve Bellenot: Distributed Simulation and the Time Wrap Operating System. SOSP 1987: 77-93 BibTeX
[Jefferson & Motro 1986]
David R. Jefferson, Amihai Motro: The Time Warp Mechanism for Database Concurrency Control. ICDE 1986: 474-481 BibTeX
[Korth & Speegle 1988]
Henry F. Korth, Gregory D. Speegle: Formal Model of Correctness Without Serializability. SIGMOD Conference 1988: 379-386 BibTeX
[Kumar & Stonebraker 1988]
Akhil Kumar, Michael Stonebraker: Semantics Based Transaction Management Techniques for Replicated Data. SIGMOD Conference 1988: 117-125 BibTeX
[Kung & Robinson 1981]
H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226(1981) BibTeX
[Lamport 1978]
Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) BibTeX
[Leu et al. 1990]
Ahmed K. Elmagarmid, Yungho Leu, Witold Litwin, Marek Rusinkiewicz: A Multidatabase Transaction Model for InterBase. VLDB 1990: 507-518 BibTeX
[Litwin 1988]
Witold Litwin: From Database Systems to Multidatabase Systems: Why and How. BNCOD 1988: 161-188 BibTeX
[Litwin & Shan 1991]
...
[Litwin & Tirri 1988]
...
[Manola & Tirri 1989]
...
[Manola et al. 1992]
Frank Manola, Sandra Heiler, Dimitrios Georgakopoulos, Mark F. Hornick, Michael L. Brodie: Distributed Object Management. Int. J. Cooperative Inf. Syst. 1(1): 5-42(1992) BibTeX
[Ngu 1990]
Anne H. H. Ngu: Specification and verification of temporal relationships in transaction modelling. Inf. Syst. 15(2): 257-267(1990) BibTeX
[Papadimitriou 1986]
...
[Reed 1983]
David P. Reed: Implementing Atomic Actions on Decentralized Data. ACM Trans. Comput. Syst. 1(1): 3-23(1983) BibTeX
[Rusinkiewicz et al. 1990]
Marek Rusinkiewicz, Ahmed K. Elmagarmid, Yungho Leu, Witold Litwin: Extending the Transaction Model to Capture more Meaning. SIGMOD Record 19(1): 3-7(1990) BibTeX
[Schwarz 1984]
...
[Skeen 1982a]
Dale Skeen: Nonblocking Commit Protocols. SIGMOD Conference 1981: 133-142 BibTeX
[Skeen 1982b]
Dale Skeen: A Quorum-Based Commit Protocol. Berkeley Workshop 1982: 69-80 BibTeX
[Weihl 1988]
William E. Weihl: Commutativity-Based Concurrency Control for Abstract Data Types. IEEE Trans. Computers 37(12): 1488-1505(1988) BibTeX
[Weihl 1989]
William E. Weihl: Local Atomicity Properties: Modular Concurrency Control for Abstract Data Types. ACM Trans. Program. Lang. Syst. 11(2): 249-283(1989) BibTeX

Referenced by

  1. Dimitrios Georgakopoulos, Mark F. Hornick, Frank Manola: Customizing Transaction Models and Mechanisms in a Programmable Environment Supporting Reliable Workflow Automation. IEEE Trans. Knowl. Data Eng. 8(4): 630-649(1996)
  2. 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
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:31:20 2009