Investigations in tree locking for compiled database applications
Authors: 
Heng Yu, Grant E. WeddellAuthors Info & Claims
Pages 217 - 231
Abstract
We report on initial research in tree locking (TL) schemes for compiled database applications. Such applications have a repository style of architecture in which a collection of software modules operate on a common database in terms of a set of predefined transaction types, an architectural view that is also useful for embedded control programs. Since TL schemes are deadlock free, it becomes possible to entirely decouple concurrency control from any functionality relating to recovery. This property can help in the deployment of database technology to this new application area. Moreover, with knowledge of transaction workload, efficacious lock trees for runtime concurrency control can be determined at the time of system generation. Our experimental results show that TL produces better throughput than traditional two-phase locking (2PL) when transactions are write-only; and for main-memory data, TL performs comparably to 2PL even in workloads with many reads.
References
[1]
{1} Transaction Processing Performance Council. URL http://www.tpc.org.
[2]
{2} Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley, 1987.
[3]
{3} Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms . McGraw Hill, 2001.
[4]
{4} K. P. Eswaran, J. Gray, R.A. Lorie, and I.L. Traiger. The Notions of Consistency and Predicate Locks in Database System. Communications of the ACM, 19(16):624-633, 1976.
[5]
{5} Pasal Felber and Michael K. Reiter. Advanced Concurrency Control in Java. Concurrency and Computation: Practice and Experience, 14(4):261-285, 2002.
[6]
{6} Hector Garcia-Molina and Kenneth Salem. Sagas. In Proceedings of the ACM SIGMOD Annual Conference on Management of Data, pages 249-259, New York, NY, USA, 1987. ACM Press.
[7]
{7} Jim Gray and Andreas Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, 1993.
[8]
{8} Raj Jain. The Art of Computer Systems Performance Analysis. John Wiley & Sons, 1991.
[9]
{9} Zvi Kedem and Abraham Silberschatz. Controlling Concurrency Using Locking Protocols (Preliminary Report). In Proceedings of 20th Symposium on Foundations of Computer Science, pages 274-285, October 1979.
[10]
{10} Zvi M. Kedem and Abraham Silberschatz. Locking Protocols: From Exclusive to Shared Locks. Journal of ACM, 30(4), October 1983.
[11]
{11} Dennis Shasha and Nathan Goodman. Concurrent search structure algorithms. ACM Transactions on Database Systems (TODS), 13(1):53-90, March 1988.
[12]
{12} Abraham Silberschatz and Zvi Kedem. Consistency in Hierarchical Database Systems. Journal of ACM, 27(1), January 1980.
[13]
{13} Abraham Silberschatz and Zvi M. Kedem. A Family of Locking Protocols for Data-base Systems that Are Modeled by Directed Graphs. IEEE Transactions on Software Engineering, 8(6):558-562, November 1982.
[14]
{14} Lubomir Stanchev and Grant Weddell. Index Selection for Compiled Database Applications in Embedded Control Programs. In Proceedings of CASCON 2002, pages 156-170, Toronto, Canada, September - October 2002.
[15]
{15} David Toman and Grant E. Weddell. Query Processing in Embedded Control Programs. In Proceedings of the Second International Workshop on Databases in Telecommunications, number 2209 in Lecture Notes in Computer Science, pages 68-87. Springer-Verlag, 2001.
[16]
{16} Gerhard Weikum. Principles and Realization Strategies of Multi-level Transaction Management. ACM Transactions on Database Systems, 16(1):132-180, March 1991.
[17]
{17} Gerhard Weikum and Gottfried Vossen. Transactional Information Systems: Theory, Algorithms, and the practice of concurrency control and recovery. Morgan Kaufmann, 2001.
[18]
{18} Mihalis Yannakakis. A Theory of Safe Locking Policies in Database Systems. Journal of ACM, 29(3):718-740, July 1982.
Index Terms
- Investigations in tree locking for compiled database applications
Recommendations
Pre-analysis locking: a safe and deadlock free locking policy
VLDB '85: Proceedings of the 11th international conference on Very Large Data Bases - Volume 11A safe and deadlock free lock policy is introduced, called pre-analysis locking. Pre-analysis locking is based on an efficient geometric algorithm which inserts lock and unlock operations into the transactions. Pre-analysis locking is the first safe and ...
Locking Timestamps versus Locking Objects
PODC '18: Proceedings of the 2018 ACM Symposium on Principles of Distributed ComputingWe present multiversion timestamp locking (MVTL), a new genre of multiversion concurrency control algorithms for serializable transactions. The key idea behind MVTL is simple: lock individual timestamps instead of locking objects. After presenting a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2004
317 pages
- Conference Chairs:
- Martin Wildberger,
- Michael Halasz,
- Editors:
- Hanan Lutfiyya,
- Janice Singer,
- Darlene A. Stewart,
- Program Chairs:
- Hanan L. Lufiyya,
- Janice Singer
Sponsors
- IBM Centre for Advanced Studies (CAS)
- IBM Toronto Laboratory
- NRC: National Research Council - Canada
Publisher
IBM Press
Publication History
Published: 04 October 2004
Qualifiers
- Article
Acceptance Rates
Overall Acceptance Rate 24 of 90 submissions, 27%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 145Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in