On Herbrand Semantics and Conflict Serializability of Read-Write Transactions Jens Lechtenbörger and Gottfried Vossen   View Paper (PDF)   Return to Indexing / Transactions 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 Note: References link to DBLP on the Web. [1] Gustavo Alonso , Radek Vingralek , Divyakant Agrawal , Yuri Breitbart , Amr El Abbadi , Hans-Jörg Schek , Gerhard Weikum : Unifying concurrency control and recovery of transactions. IS 19(1) : 101-115(1994) [2] Catriel Beeri , Hans-Jörg Schek , Gerhard Weikum : Multi-Level Transaction Management, Theoretical Art or Practical Need ? EDBT 1988 : 134-154 [3] Philip A. Bernstein , Vassos Hadzilacos , Nathan Goodman : Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5 Contents [4] Yuri Breitbart , Dimitrios Georgakopoulos , Marek Rusinkiewicz , Abraham Silberschatz : On Rigorous Transaction Scheduling. TSE 17(9) : 954-960(1991) [5] Vassos Hadzilacos : A Theory of Reliability in Database Systems. JACM 35(1) : 121-145(1988) [6] Theo Härder : Observations on optimistic concurrency control schemes. IS 9(2) : 111-120(1984) [7] H. T. Kung , John T. Robinson : On Optimistic Methods for Concurrency Control. TODS 6(2) : 213-226(1981) [8] Georg Lausen : Formal aspects of optimistic concurrency control in a multiple version database system. IS 8(4) : 291-301(1983) [9] ... [10] Christos H. Papadimitriou : The Theory of Database Concurrency Control. Computer Science Press 1986, ISBN 0-88175-027-1 [11] U. Prädel , Gunter Schlageter , Rainer Unland : Redesign of Optimistic Methods: Improving Performance and Applicability. ICDE 1986 : 466-473 [12] Hans-Jörg Schek , Gerhard Weikum , Haiyan Ye : Towards a Unified Theory of Concurrency Control and Recovery. PODS 1993 : 300-311 [13] Radek Vingralek , Haiyan Hasse-Ye , Yuri Breitbart , Hans-Jörg Schek : Unifying Concurrency Control and Recovery of Transactions with Semantically Rich Operations. TCS 190(2) : 363-396(1998) [14] William E. Weihl : The Impact of Recovery on Concurrency Control. JCSS 47(1) : 157-184(1993) BIBTEX @inproceedings{DBLP:conf/pods/LechtenborgerV00,   author    = {Jens Lechtenb{\"o}rger and                 Gottfried Vossen},    title     = {On Herbrand Semantics and Conflict Serializability of Read-Write                 Transactions},    booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium                 on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,                 USA},    publisher = {ACM},    year      = {2000},    isbn      = {1-58113-214-X},    pages     = {187-194},    crossref  = {DBLP:conf/pods/00},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.