loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Scheduling Transactions with Temporal Constraints: Exploiting Data Semantics
September/October 2002 (vol. 14 no. 5)
pp. 1155-1166
ASCII Text
x 
 
Ming Xiong, Krithi Ramamritham, John A. Stankovic, Don Towsley, Rajendran Sivasankaran, "Scheduling Transactions with Temporal Constraints: Exploiting Data Semantics," IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 5, pp. 1155-1166, September/October, 2002.
 
 
BibTex
x
 
@article{ 10.1109/TKDE.2002.1033781,
author = {Ming Xiong and Krithi Ramamritham and John A. Stankovic and Don Towsley and Rajendran Sivasankaran},
title = {Scheduling Transactions with Temporal Constraints: Exploiting Data Semantics},
journal ={IEEE Transactions on Knowledge and Data Engineering},
volume = {14},
number = {5},
issn = {1041-4347},
year = {2002},
pages = {1155-1166},
doi = {http://doi.ieeecomputersociety.org/10.1109/TKDE.2002.1033781},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Knowledge and Data Engineering
TI - Scheduling Transactions with Temporal Constraints: Exploiting Data Semantics
IS - 5
SN - 1041-4347
SP1155
EP1166
EPD - 1155-1166
A1 - Ming Xiong,
A1 - Krithi Ramamritham,
A1 - John A. Stankovic,
A1 - Don Towsley,
A1 - Rajendran Sivasankaran,
PY - 2002
KW - Real-time database systems
KW - temporal consistency
KW - earliest deadline first
KW - least slack first
KW - data-deadline
KW - transaction processing.
VL - 14
JA - IEEE Transactions on Knowledge and Data Engineering
ER -
 

Abstract—In this paper, issues involved in the design of a real-time database which maintains data temporal consistency are discussed. The concept of data-deadline is introduced and time cognizant transaction scheduling policies are proposed. Informally, data-deadline is a deadline assigned to a transaction due to the temporal constraints of the data accessed by the transaction. Further, two time cognizant forced wait policies which improve performance significantly by forcing a transaction to delay further execution until a new version of sensor data becomes available are proposed. A way to exploit temporal data similarity to improve performance is also proposed. Finally, these policies are evaluated through detailed simulation experiments. The simulation results show that taking advantage of temporal data semantics in transaction scheduling can significantly improve the performance of user transactions in real-time database systems. In particular, it is demonstrated that under the forced wait policy, the performance can be improved significantly. Further improvements result by exploiting data similarity.

[1] R.K. Abbott and H. Garcia-Molina, “Scheduling Real-Time Transactions: A Performance Evaluation,” ACM Trans. Database Systems, vol. 17, no. 3, pp. 513–560, Sept. 1992.[2] B. Adelberg, H. Garcia-Molina, and B. Kao, “Applying Update Streams in a Soft Real-Time Database System,” Proc. 1995 ACM SIGMOD, pp. 245-256, 1995.[3] M.J. Carey, R. Jauhari, and M. Livny, “On Transaction Boundaries in Active Databases: A Performance Perspective,” IEEE Trans. Knowledge and Data Eng., vol. 3, no. 3, pp. 320-336, Sept. 1991.[4] D. Chen and A.K. Mok, “SRDE-Application of Data Similarity to Process Control,” Proc. 20th IEEE Real-Time Systems Symp., Dec. 1999.[5] U. Dayal,B. Blaustein,A. Buchmann et al., , "The HiPAC project: Combining active databases and timing constraints," SIGMOD Record, vol. 17, no. 1, pp. 51-70, Mar. 1988.[6] J. Gray and A. Reuter, Transaction Processing: Concepts and Techniques, Morgan Kauffman, 1993.[7] J. Haritsa, M. Livny, and M. Carey, “On Being Optimistic about Real-Time Constraints,” Proc. Ninth ACM Symp. Principles of Database Systems, 1990.[8] J. Haritsa, M. Livny, and M. Carey, “Earliest Deadline Scheduling for Real-Time Database Systems,” Proc. 12th Real-Time Systems Symp., Dec. 1991.[9] M. Turk and A. Pentland, "Face Recognition Using Eigenfaces," Proc. IEEE Conf. on Computer Vision and Pattern Recognition, 1991, pp. 586-591.[10] J. Huang, J. Stankovic, K. Ramamritham, and D. Towsley, “Experimental Evaluation of Real-Time Concurrency Control Schemes,” Proc. 17th Int'l Conf. Very Large Data Bases, 1991.[11] J. Huang,J.A. Stankovic,D. Towsley,, and K. Ramamritham,“Experimental evaluation of real-time transaction processing,” Proc. 10th IEEE Real-Time Systems Symp. (RTSS), Dec. 1989.[12] J. Huang, J.A. Stankovic, K. Ramamritham, D. Towsley, and B. Purimetla, “On Using Priority Inheritance in Real-Time Databases,” Special Issue of Real-Time Systems J., vol. 4. no. 3, Sept. 1992.[13] T.-W. Kuo and A.K. Mok, “SSP: A Semantics-Based Protocol for Real-Time Data Access,” Proc. IEEE 14th Real-Time Systems Symp., Dec. 1993.[14] T. Kuo and A.K. Mok, “Real-Time Data Semantics and Similarity-Based Concurrency Control,” Proc. IEEE Trans. Knowledge and Data Eng., 1995.[15] S. Ho, T. Kuo, and K. Mok, “Similarity- Based Load Adjustment for Static Real-Time Transaction Systems,” Proc. 18th Real-Time Symp., 1997.[16] Y. Lin and S.H. Son, “Concurrency Control in Real-Time Databases by Dynamic Adjustment of Serialization Order,” Proc. IEEE 11th Real-Time Systems Symp., Dec. 1990.[17] M. Livny, DeNet Users Guide. version 1.5, Dept. Computer Science, Univ. of Wisconsin, Madison, WI, 1990.[18] D. Locke, “Real-Time Databases: Real-World Requirements,” Real-Time Database Systems: Issues and Applications, eds., A. Bestavros, K.-J. Lin, and S.H. Son, Kluwer Academic, pp. 83-91, 1997.[19] L.E. McKenzie, Jr. and R.T. Snodgrass, “Evaluation of Relational Algebras Incorporating the Time Dimension in Databases,” ACM Computing Surveys, vol. 23, no. 4, pp. 501–543, 1991.[20] H. Pang, M.J. Carey, and M. Livny, “Multiclass Query Scheduling in Real-Time Database Systems,” IEEE Trans. Knowledge and Data Eng., vol. 7, no. 4, Aug. 1995.[21] B. Purimetla, R.M. Sivasankaran, J. Stankovic, and K. Ramamritham, “Network Services Databases-A Distributed Active Real-Time Database (DARTDB) Applications,” Proc. IEEE Workshop Parallel and Distributed Real-time Systems, Apr. 1993.[22] K. Ramamritham,“Real-time databases,” Distributed and Parallel Databases, vol. 1, no. 2, Apr. 1993.[23] R. Sivasankaran, J. Stankovic, D. Towsley, B. Purimetla, and K. Ramamritham, “Priority Assignment in Real-Time Active Databases,” The VLDB J., vol. 5, 1996.[24] J.A. Stankovic, S. Son, and J. Hansson, “Misconceptions about Real-Time Databases,” IEEE Computer, vol. 32, no. 6, pp. 29-36, June 1999.[25] X. Song and J.W.S. Liu, “Maintaining Temporal Consistency: Pessimistic versus Optimistic Concurrency Control,” Proc. IEEE Trans. Knowledge and Data Eng., vol. 7, no. 5, pp. 786-796, Oct. 1995.[26] M. Xiong, J. Stankovic, K. Ramamritham, D. Towsley, and R.M. Sivasankaran, “Maintaining Temporal Consistency: Issues and Algorithms,” Proc. First Int'l Workshop Real-Time Databases, Mar. 1996.[27] M. Xiong, R.M. Sivasankaran, J. Stankovic, K. Ramamritham, and D. Towsley, “Scheduling Transactions with Temporal Constraints: Exploiting Data Semantics,” Proc. IEEE 17th Real-Time Systems Symp., pp. 240-251, Dec. 1996.[28] H. Zhou and F. Jahanian, “Real-Time Primary-Backup (RTPB) Replication with Temporal Consistency Guarantees,” Proc. Int'l Conf. Distributed Computing Systems, May 1998.

Index Terms:
Real-time database systems, temporal consistency, earliest deadline first, least slack first, data-deadline, transaction processing.
Citation:
Ming Xiong, Krithi Ramamritham, John A. Stankovic, Don Towsley, Rajendran Sivasankaran, "Scheduling Transactions with Temporal Constraints: Exploiting Data Semantics," IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 5, pp. 1155-1166, Sep./Oct. 2002, doi:10.1109/TKDE.2002.1033781
Usage of this product signifies your acceptance of the Terms of Use.