A New Approach for Recoverable Timestamp Ordering Schedule

Authors: Hassan M. Najadat

Abstract:

A new approach for timestamp ordering problem in serializable schedules is presented. Since the number of users using databases is increasing rapidly, the accuracy and needing high throughput are main topics in database area. Strict 2PL does not allow all possible serializable schedules and so does not result high throughput. The main advantages of the approach are the ability to enforce the execution of transaction to be recoverable and the high achievable performance of concurrent execution in central databases. Comparing to Strict 2PL, the general structure of the algorithm is simple, free deadlock, and allows executing all possible serializable schedules which results high throughput. Various examples which include different orders of database operations are discussed.

Keywords: Concurrency control, schedule, timestamp, transaction.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330769

References:

[1] P. A. Bernstein, V. Hadzilacos, N. Good-Man, "Concurrency control and recovery in database systems", Addison Wesley, 1987.
[2] T. Kristian, S. J. Christian, T. S. Richard, "Effective time stamping in databases, a time center", Technical report, 1998.
[3] Elmasri, Navathe, "Fundamentals of database systems", Addison Wesley, 2nd edition 1994.
[4] Ramon Lawrence, "Advanced database seminar-concurrency control", Lecture notes, 2001
[5] D. Jeffrey, Ullman, "Principles of database and knowledge-base systems", W.H. Freeman & Company, 1988.
[6] A. James, A. Fekete, N. Lynch, M. Merrittt, W. Weihl, "A theory of timestamp-based concurrency control for nested transactions", Proceedings of the 14th VLDB Conference, 1988.
[7] J. T. Young, J. C. Peck, "A mathematical theory of correct executions in temporal databases supporting concurrent simulations", ACM ,1998
[8] W. Smith, D. B. Johnson, "Minimizing timestamp size for completely asynchronous optimistic recovery with minimal rollback", 15th IEEE Symposium on Reliable Distributed Systems, 1996.
[9] T. Connolly, C. Begg, A. Strachan, "Database systems, A practical approach to design, implementation, and management", Addison Wesley, 4nd edition, 2004.
[10] A. Adya, B. Liskov, and P. O'Neil, "Generalized isolation level definitions", proceedings of the IEEE International Conference on Data Engineering, san Diego, CA, March 2000.
[11] M. Lonescu, B. Dorohonceanu, I. Marsic," A novel concurrency control algorithm in distributed groupware", Proceedings of the international conference on parallel and distributed processing techniques and applications (PDPTA '2000), p. 1551-1557, Las Vegas, NV, June, 2000.