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}
}
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
CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ...
DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...
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)
- [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 - [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)
- [Breitbart & Silberschatz 1988]
- Yuri Breitbart, Abraham Silberschatz:
Multidatabase Update Issues.
SIGMOD Conference 1988: 135-142
- [Dayal et al. 1990]
- Umeshwar Dayal, Meichun Hsu, Rivka Ladin:
Organizing Long-Running Activities with Triggers and Transactions.
SIGMOD Conference 1990: 204-214
- [Du & Elmagarmid 1989]
- Weimin Du, Ahmed K. Elmagarmid:
Quasi Serializability: a Correctness Criterion for Global Concurrency Control in InterBase.
VLDB 1989: 347-355
- [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)
- [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)
- [Garcia-Molina 1983]
- Hector Garcia-Molina:
Using Semantic Knowledge for Transaction Processing in Distributed Database.
ACM Trans. Database Syst. 8(2): 186-213(1983)
- [Garcia-Molina & Salem 1987]
- Hector Garcia-Molina, Kenneth Salem:
Sagas.
SIGMOD Conference 1987: 249-259
- [Georgakopoulos et al. 1991]
- Dimitrios Georgakopoulos, Marek Rusinkiewicz, Amit P. Sheth:
On Serializability of Multidatabase Transactions Through Forced Local Conflicts.
ICDE 1991: 314-323
- [Gray 1978]
- Jim Gray:
Notes on Data Base Operating Systems.
Advanced Course: Operating Systems 1978: 393-481
- [Gray 1981]
- Jim Gray:
The Transaction Concept: Virtues and Limitations (Invited Paper).
VLDB 1981: 144-154
- [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
- [Herlihy 1990]
- Maurice Herlihy:
Apologizing Versus Asking Permission: Optimistic Concurrency Control for Abstract Data Types.
ACM Trans. Database Syst. 15(1): 96-124(1990)
- [Jefferson 1985a]
- ...
- [Jefferson 1985b]
- David R. Jefferson:
Virtual Time.
ACM Trans. Program. Lang. Syst. 7(3): 404-425(1985)
- [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
- [Jefferson & Motro 1986]
- David R. Jefferson, Amihai Motro:
The Time Warp Mechanism for Database Concurrency Control.
ICDE 1986: 474-481
- [Korth & Speegle 1988]
- Henry F. Korth, Gregory D. Speegle:
Formal Model of Correctness Without Serializability.
SIGMOD Conference 1988: 379-386
- [Kumar & Stonebraker 1988]
- Akhil Kumar, Michael Stonebraker:
Semantics Based Transaction Management Techniques for Replicated Data.
SIGMOD Conference 1988: 117-125
- [Kung & Robinson 1981]
- H. T. Kung, John T. Robinson:
On Optimistic Methods for Concurrency Control.
ACM Trans. Database Syst. 6(2): 213-226(1981)
- [Lamport 1978]
- Leslie Lamport:
Time, Clocks, and the Ordering of Events in a Distributed System.
Commun. ACM 21(7): 558-565(1978)
- [Leu et al. 1990]
- Ahmed K. Elmagarmid, Yungho Leu, Witold Litwin, Marek Rusinkiewicz:
A Multidatabase Transaction Model for InterBase.
VLDB 1990: 507-518
- [Litwin 1988]
- Witold Litwin:
From Database Systems to Multidatabase Systems: Why and How.
BNCOD 1988: 161-188
- [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)
- [Ngu 1990]
- Anne H. H. Ngu:
Specification and verification of temporal relationships in transaction modelling.
Inf. Syst. 15(2): 257-267(1990)
- [Papadimitriou 1986]
- ...
- [Reed 1983]
- David P. Reed:
Implementing Atomic Actions on Decentralized Data.
ACM Trans. Comput. Syst. 1(1): 3-23(1983)
- [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)
- [Schwarz 1984]
- ...
- [Skeen 1982a]
- Dale Skeen:
Nonblocking Commit Protocols.
SIGMOD Conference 1981: 133-142
- [Skeen 1982b]
- Dale Skeen:
A Quorum-Based Commit Protocol.
Berkeley Workshop 1982: 69-80
- [Weihl 1988]
- William E. Weihl:
Commutativity-Based Concurrency Control for Abstract Data Types.
IEEE Trans. Computers 37(12): 1488-1505(1988)
- [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)
Copyright © Wed Nov 11 05:42:57 2009
by Michael Ley (ley@uni-trier.de)
