ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Value-Based Scheduling in Real-Time Database Systems.

Jayant R. Haritsa, Michael J. Carey, Miron Livny: Value-Based Scheduling in Real-Time Database Systems. VLDB J. 2(2): 117-152(1993)
@article{DBLP:journals/vldb/HaritsaCL93,
  author    = {Jayant R. Haritsa and
               Michael J. Carey and
               Miron Livny},
  title     = {Value-Based Scheduling in Real-Time Database Systems},
  journal   = {VLDB J.},
  volume    = {2},
  number    = {2},
  year      = {1993},
  pages     = {117-152},
  ee        = {db/journals/vldb/HaritsaCL93.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In a real-time database system, an application may assign a value to a transaction to reflect the return it expects to receive if the transaction commits before its deadline. Most research on real-time database systems has focused on systems where all transactions are assigned the same value, the performance goal being to minimize the number of missed deadlines. When transactions are assigned differend values, the goal of the system shifts to maximizing the sum of the values of those transactions that commit by their deadlines. Minimizing the number of missed deadlines becomes a secondary concern. In this article, we address the problem of establishing a priority ordering among transactions characterized by both values and deadlines that results in maximizing the realized value. Of particular interest is the tradeoff established between these values and deadlines in constructing the priority ordering. Using a detailed simulation model, we evaluate the performance of several priority mappings that make this tradeoff different, but fixed, ways. In addition, a "bucket" priority mechanism that allows the relative importance of values and deadlines to be controlled is introduced and studied. The notion of associating a penalty with transactions whose deadlines are not met is also briefly considered.

Copyright © 1993 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 values and deadlines, priority mapping, resource and data contention, priority and concurrency algorithms.

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 1988]
Robert K. Abbott, Hector Garcia-Molina: Scheduling Real-time Transactions: a Performance Evaluation. VLDB 1988: 1-12 BibTeX
[Abbott & Garcia-Molina 1989]
Robert K. Abbott, Hector Garcia-Molina: Scheduling Real-Time Transactions with Disk Resident Data. VLDB 1989: 385-396 BibTeX
[Abbott & Garcia-Molina 1990]
...
[Agrawal et al. 1987]
Rakesh Agrawal, Michael J. Carey, Miron Livny: Concurrency Control Performance Modeling: Alternatives and Implications. ACM Trans. Database Syst. 12(4): 609-654(1987) BibTeX
[Baruah & Rosier 1991]
...
[Biyabani et al. 1988]
...
[Buchmann et al. 1989]
Alejandro P. Buchmann, Dennis R. McCarthy, Meichun Hsu, Umeshwar Dayal: Time-Critical Database Scheduling: A Framework For Integrating Real-Time Scheduling and Concurrency Control. ICDE 1989: 470-480 BibTeX
[Dertouzos 1974]
Michael L. Dertouzos: Control Robotics: The Procedural Control of Physical Processes. IFIP Congress 1974: 807-813 BibTeX
[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
[Franaszek & Robinson 1985]
Peter A. Franaszek, John T. Robinson: Limitations of Concurrency in Transaction Processing. ACM Trans. Database Syst. 10(1): 1-28(1985) BibTeX
[Gray 1979]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[Haritsa et al. 1990a]
Jayant R. Haritsa, Michael J. Carey, Miron Livny: On Being Optimistic about Real-Time Constraints. PODS 1990: 331-343 BibTeX
[Haritsa et al. 1990b]
...
[Haritsa et al. 1991]
...
[Haritsa et al. 1992]
...
[Huang et al. 1989]
...
[Huang & Stankovic 1990a]
...
[Huang & Stankovic 1990b]
...
[Jensen et al. 1985]
...
[Koren & Shasha 1992]
...
[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
[Livny 1988]
...
[Locke 1986]
...
[Menasce & Nakanishi 1982]
Daniel A. Menascé, Tatuo Nakanishi: Optimistic versus pessimistic concurrency control mechanisms in database management systems. Inf. Syst. 7(1): 13-27(1982) BibTeX
[Reed 1978]
...
[Robinson 1982]
...
[Sha et al. 1987]
Lui Sha, Ragunathan Rajkumar, John P. Lehoczky: Priority Inheritance Protocols: An Approach to Real-Time Synchronization. IEEE Trans. Computers 39(9): 1175-1185(1990) BibTeX
[Stankovic & Zhao 1988]
John A. Stankovic, Wei Zhao: On Real-Time Transactions. SIGMOD Record 17(1): 4-18(1988) BibTeX

Referenced by

  1. Gultekin Özsoyoglu, Richard T. Snodgrass: Temporal and Real-Time Databases: A Survey. IEEE Trans. Knowl. Data Eng. 7(4): 513-532(1995)
  2. Seok-Hee Hong, Yoon-Joon Lee, Myoung-Ho Kim: Real-Time Multiversion Concurrency Control Using Precedence Relationship. DASFAA 1995: 222-229
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:18 2009