A New Approach for Recoverable Timestamp Ordering Schedule

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.

Authors:

• Hassan M. Najadat

Keywords:

• Concurrency control
• schedule
• timestamp
• transaction.

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.