On Herbrand semantics and conflict serializability of read-write transactions (extended abstract)

ABSTRACT

The quest for unified correctness criteria in database concurrency control is addressed from a new perspective. A family of Herbrand semantics is presented, where each semantics provides an interpretation for operations in the read-write model of transactions. Using commutativity arguments, each semantics leads to a notion of conflict, which then gives rise to distinct classes of serializable schedules. Surprisingly, the classical notion of serializability with respect to two of these sematics, update-in-place and deferred-update semantics, already embodies a unified correctness criterion; moreover, prefix-closed variants of it allow for a higher degree of transaction parallelism than, for example, prefix-reducibility. Finally, it is shown that previous criteria may permit undesirable schedules, which are ruled out by a stronger notion of serializability that captures all intuitively correct schedules, but is incomparable to prefix-reducibility and the classes of schedules recognized by optimistic protocols.

REFERENCES

• 1: Gustavo Alonso , Radek Vingralek , Divyakant Agrawal , Yuri Breitbart , Amr El Abbadi , Hans-J. Schek , Gerhard Weikum, Unifying concurrency control and recovery of transactions, Information Systems, v.19 n.1, p.101-115, Jan. 1994 [doi>10.1016/0306-4379(94)90029-9]
• 2: Catriel Beeri , Hans-Jörg Schek , Gerhard Weikum, Multi-Level Transaction Management, Theoretical Art or Practical Need ?, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.134-154, March 14-18, 1988
• 3: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 4: Yuri Breitbart , Dimitrios Georgakopoulos , Marek Rusinkiewicz , Abraham Silberschatz, On rigorous Transaction Scheduling, IEEE Transactions on Software Engineering, v.17 n.9, p.954-960, September 1991 [doi>10.1109/32.92915 ]
• 5: Vassos Hadzilacos, A theory of reliability in database systems, Journal of the ACM (JACM), v.35 n.1, p.121-145, Jan. 1988 [doi>10.1145/42267.42272]
• 6: Theo Härder, Observations on optimistic concurrency control schemes, Information Systems, v.9 n.2, p.111-120, 1984 [doi>10.1016/0306-4379(84)90020-6]
• 7: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• 8: G. Lausen, "Formal Aspects of Optimistic Concurrency Control in a Multiple Version Database System," Information Systems 8, 1983, 291-301.
• 9: J. LechtenbSrger, G. Vossen, "On Herbrand Semantics and Conflict Serializability of Read-Write Transactions," Technical Report, University of Miinster 2000.
• 10: Christos Papadimitriou, The theory of database concurrency control, Computer Science Press, Inc., New York, NY, 1986
• 11: U. Prädel , Gunter Schlageter , Rainer Unland, Redesign of Optimistic Methods: Improving Performance and Applicability, Proceedings of the Second International Conference on Data Engineering, p.466-473, February 05-07, 1986
• 12: Hans-Jörg Schek , Gerhard Weikum , Haiyan Ye, Towards a unified theory of concurrency control and recovery, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.300-311, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153935]
• 13: R. Vingralek , H. Hasse-Ye , Y. Breitbart , H.-J. Schek, Unifying concurrency control and recovery of transactions with semantically rich operations, Theoretical Computer Science, v.190 n.2, p.363-396, Jan. 20, 1998 [doi>10.1016/S0304-3975(97)00095-9 ]
• 14: William E. Weihl, The impact of recovery on concurrency control, Journal of Computer and System Sciences, v.47 n.1, p.157-184, Aug. 1993

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Management, Theory