loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Correct Execution of Transactions at Different Isolation Levels
September 2004 (vol. 16 no. 9)
pp. 1070-1081
Many transaction processing applications execute at isolation levels lower than SERIALIZABLE in order to increase throughput and reduce response time. However, the resulting schedules might not be serializable and, hence, not necessarily correct. The semantics of a particular application determines whether that application will run correctly at a lower level and, in practice, it appears that many applications do. The decision to choose an isolation level at which to run an application and the analysis of the correctness of the resulting execution is usually done informally. In this paper, we develop a formal technique to analyze and reason about the correctness of the execution of an application at isolation levels other than SERIALIZABLE. We use a new notion of correctness, semantic correctness, a criterion weaker than serializability, to investigate correctness. In particular, for each isolation level, we prove a condition under which the execution of transactions at that level will be semantically correct. In addition to the ANSI/ISO isolation levels of READ UNCOMMITTED, READ COMMITTED, and REPEATABLE READ, we also prove a condition for correct execution at the READ-COMMITTED with first-committer-wins and at SNAPSHOT isolation. We assume that different transactions in the same application can be executing at different levels, but that each transaction is executing at least at READ UNCOMMITTED.

[1] 1070 ANSI X3. 135-1992, Am. Nat'l Standard for Information Systems-Database Languages-sql, Nov. 1992.[2] K. Apt, Ten Years of Hoare's Logic: A Survey Part I ACM Trans. Programming Language Systems, vol. 3, no. 4, pp. 431-483, 1981.[3] H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O'Neil, and P. O'Neil, A Critique of ANSI SQL Isolation Levels Proc. 1995 ACM SIGMOD Int'l Conf. Management of Data, pp. 1-10, May 1995.[4] J. Bergstra and J. Tucker, Expressiveness and Completeness of Hoare's Logic J. Computer and System Sciences, vol. 25, no. 3, pp. 267-284, Dec. 1982.[5] A. Bernstein, D. Gerstl, W.H. Leung, and P. Lewis, Design and Performance of an Assertional Concurrency Control System Proc. 14th IEEE Int'l Conf. Data Eng., pp. 436-445, Feb. 1998.[6] A. Bernstein, D. Gerstl, and P. Lewis, A Concurrency Control for Step-Decomposed Transactions Information Systems, vol. 24, no. 8, pp. 673-698, 1999.[7] A. Bernstein, D. Gerstl, P. Lewis, and S. Lu, Using Transaction Semantics to Increase Performance Proc. Eighth Int'l Workshop High Performance Trans. Systems, Sept. 1999.[8] Concurrency in Programming and Database Systems. A. Bernstein and P. Lewis, eds., Jones and Bartlett Publishers, 1993.[9] A. Bernstein and P. Lewis, High Performance Transaction Systems Using Transaction Semantics Distributed and Parallel Databases, vol. 4, no. 1, Jan. 1996.[10] A. Bernstein, P. Lewis, and S. Lu, Semantic Conditions for Correctness at Different Isolation Levels Proc. 16th IEEE Int'l Conf. Data Eng., pp. 57-66, Mar. 2000.[11] S. Cook, Soundness and Completeness of an Axiom System for Program Verification SIAM J. Computing, vol. 7, no. 1, pp. 70-90, Feb. 1978.[12] K. Eswaran, J. Gray, R. Lorie, and I. Traiger, The Notions of Consistency and Predicate Locks in a Database System Comm. ACM, vol. 19, no. 11, pp. 624-633, Nov. 1976.[13] J. Gray, R. Lorie, G. Putzolu, and I. Traiger, Granularity of Locks and Degrees of Consistency in a Shared Database Modeling in Data Base Management Systems, Amsterdam: Elsevier North-Holland, 1976.[14] The Science Of Programming, D. Gries, ed., New York: Springer-Verlag, 1981.[15] Logic in Computer Science: Modelling and Reasoning about Systems, M. Huth and M. Ryan, eds., Cambridge Univ. Press, 2000.[16] T. Nipkow, Hoare Logics in Isabelle/HOL Proof and System-Reliability, H. Schwichtenberg and R. Steinbrüggen, eds., pp. 341-367, Kluwer, 2002.[17] S. Owicki and D. Gries, An Axiomatic Proof Technique for Parallel Programs I Acta Informatica, vol. 6, pp. 319-340, 1976.

Index Terms:
Isolation levels, correctness, serializability, transactions.
Citation:
Shiyong Lu, Arthur Bernstein, Philip Lewis, "Correct Execution of Transactions at Different Isolation Levels," IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 9, pp. 1070-1081, Sept. 2004, doi:10.1109/TKDE.2004.34
Usage of this product signifies your acceptance of the Terms of Use.