Index Concurrency Control in Firm Real-Time Database Systems.

Brajesh Goyal, Jayant R. Haritsa, S. Seshadri, V. Srinivasan: Index Concurrency Control in Firm Real-Time Database Systems. VLDB 1995: 146-157

@inproceedings{DBLP:conf/vldb/GoyalHSS95,
  author    = {Brajesh Goyal and
               Jayant R. Haritsa and
               S. Seshadri and
               V. Srinivasan},
  editor    = {Umeshwar Dayal and
               Peter M. D. Gray and
               Shojiro Nishio},
  title     = {Index Concurrency Control in Firm Real-Time Database Systems},
  booktitle = {VLDB'95, Proceedings of 21th International Conference on Very
               Large Data Bases, September 11-15, 1995, Zurich, Switzerland},
  publisher = {Morgan Kaufmann},
  year      = {1995},
  isbn      = {1-55860-379-4},
  pages     = {146-157},
  ee        = {db/conf/vldb/GoyalHSS95.html},
  crossref  = {DBLP:conf/vldb/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Although real-time transaction concurrency control has been extensively studied, the design and evaluation of real-time index concurrency control algorithms has not yet been considered. In this paper, we develop real-time variants of several classical B-tree concurrency control algorithms and compare their performance using a detailed simulation model of a firm-deadline real-time database system. The experimental results show that the performance characteristics of the real-time version of an index concurrency control algorithm could be significantly different from the performance of the same algorithm in a conventional (non-real-time) database system. In particular, B-link algorithms, which are reputed to provide the best overallperformance in conventional database systems, perform poorly under heavy real-time loads. We present and evaluate a simple load-adaptive variant of the B-link algorithm called LAB-link, which provides the best performance over the entire loading range for a variety of real- time transaction workloads.

Copyright © 1995 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.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Umeshwar Dayal, Peter M. D. Gray, Shojiro Nishio (Eds.): VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. Morgan Kaufmann 1995, ISBN 1-55860-379-4
Contents

References

[AEJ92]: Divyakant Agrawal, Amr El Abbadi, Richard Jeffers: Using Delayed Commitment in Locking Protocols for Real-Time Databases. SIGMOD Conference 1992: 104-113
[AG92]: Robert K. Abbott, Hector Garcia-Molina: Scheduling Real-Time Transactions: A Performance Evaluation. ACM Trans. Database Syst. 17(3): 513-560(1992)
[Bil86]: ...
[BS77]: Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977)
[Com79]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)
[Gra79]: Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481
[HCL91]: ...
[HCL92]: ...
[HJC93]: D. Hong, Theodore Johnson, Sharma Chakravarthy: Real-Time Transaction Scheduling: A Cost Conscious Approach. SIGMOD Conference 1993: 197-206
[JS90]: Theodore Johnson, Dennis Shasha: A Framework for the Performance Analysis of Concurrent B-tree Algorithms. PODS 1990: 273-287
[KW82]: Yat-Sang Kwong, Derick Wood: A New Method for Concurrency in B-Trees. IEEE Trans. Software Eng. 8(3): 211-222(1982)
[LS86]: Vladimir Lanin, Dennis Shasha: A Symmetric Concurrent B-Tree Algorithm. FJCC 1986: 380-389
[LS92]: David B. Lomet, Betty Salzberg: Access Method Concurrency with Recovery. SIGMOD Conference 1992: 351-360
[LY81]: Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981)
[Moh90]: C. Mohan: ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. VLDB 1990: 392-405
[MR85]: Yehudit Mond, Yoav Raz: Concurrency Control in B+-Trees Databases Using Preparatory Operations. VLDB 1985: 331-334
[ML92]: C. Mohan, Frank E. Levine: ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. SIGMOD Conference 1992: 371-380
[PCL94]: HweeHwa Pang, Michael J. Carey, Miron Livny: Managing Memory for Real-Time Queries. SIGMOD Conference 1994: 221-232
[Sag85]: Yehoshua Sagiv: Concurrent Operations on B*-Trees with Overtaking. J. Comput. Syst. Sci. 33(2): 275-296(1986)
[SC91]: V. Srinivasan, Michael J. Carey: Performance of B-Tree Concurrency Algorithms. SIGMOD Conference 1991: 416-425
[SG88]: Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988)
[SRL87]: Lui Sha, Ragunathan Rajkumar, John P. Lehoczky: Priority Inheritance Protocols: An Approach to Real-Time Synchronization. IEEE Trans. Computers 39(9): 1175-1185(1990)
[Str86]: Bjarne Stroustrup: The C++ Programming Language, First Edition. Addison-Wesley 1986, ISBN 0-201-12078-X