Tolerating bounded inconsistency for increasing concurrency in database systems

ABSTRACT

Recently, the scope of databases has been extended to many non-standard applications, and serializability is found to be too restrictive for such applications. In general, two approaches are adopted to address this problem. The first approach considers placing more structure on data objects to exploit type specific properties while keeping serializability as the correctness criterion. The other approach uses explicit semantics of transactions and databases to permit interleaved executions of transactions that are non-serializable. In this paper, we attempt to bridge the gap between the two approaches by using the notion of serializability with bounded inconsistency. Users are free to specifiy the maximum level of inconsistency that can be allowed in the executions of operations dynamically. In particular, if no inconsistency is allowed in the execution of any operation, the protocol will be reduced to a standard strict two phase locking protocol based on type-specific semantics of data objects. Bounded inconsistency can be applied to many areas which do not require exact values of the data such as for gathering information for statistical purpose, for making high level decisions and reasoning in expert systems which can tolerate uncertainty in input data.

REFERENCES

• 1: Divyakant Agrawal , Amr El Abbadi , Ambuj K. Singh, Consistency and orderability: semantics-based correctness criteria for databases, ACM Transactions on Database Systems (TODS), v.18 n.3, p.460-486, Sept. 1993 [doi>10.1145/155271.155276]
• 2: B. R. Badrinath , Krithi Ramamritham, Semantics-based concurrency control: beyond commutativity, ACM Transactions on Database Systems (TODS), v.17 n.1, p.163-199, March 1992 [doi>10.1145/128765.128771]
• 3: Naser S. Barghouti , Gail E. Kaiser, Concurrency control in advanced database applications, ACM Computing Surveys (CSUR), v.23 n.3, p.269-317, Sept. 1991 [doi>10.1145/116873.116875]
• 4: P.A. Bernstein, D. W. Shipman, and W. S. Wong. Formal aspects of serializability in datable concurrency control. IEEE Transactions on Software Engineering, 5(5):203-216, May 1979.
• 5: Panos K. Chrysanthis , S. Raghuram , Krithi Ramamritham, Extracting concurrency from objects: a methodology, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.108-117, May 29-31, 1991, Denver, Colorado, United States
• 6: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 7: Abdel Aziz Farrag , M. Tamer Özsu, Using semantic knowledge of transactions to increase concurrency, ACM Transactions on Database Systems (TODS), v.14 n.4, p.503-525, Dec. 1989 [doi>10.1145/76902.76905]
• 8: Hector Garcia-Molina, Using semantic knowledge for transaction processing in a distributed database, ACM Transactions on Database Systems (TODS), v.8 n.2, p.186-213, June 1983 [doi>10.1145/319983.319985]
• 9: Hector Garcia-Molina , Kenneth Salem, Non-deterministic queue operations, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.53-62, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113418]
• 10: Thanasis Hadzilacos , Vassos Hadzilacos, Transaction synchronisation in object bases, Journal of Computer and System Sciences, v.43 n.1, p.2-24, Aug. 1991 [doi>10.1016/0022-0000(91)90030-9]
• 11: Maurice Herlihy, A quorum-consensus replication method for abstract data types, ACM Transactions on Computer Systems (TOCS), v.4 n.1, p.32-53, Feb. 1986 [doi>10.1145/6306.6308]
• 12: Maurice P. Herlihy , William E. Weihl, Hybrid concurrency control for abstract data types, Journal of Computer and System Sciences, v.43 n.1, p.25-61, Aug. 1991 [doi>10.1016/0022-0000(91)90031-Y]
• 13: Henry F. Korth, Locking Primitives in a Database System, Journal of the ACM (JACM), v.30 n.1, p.55-79, Jan. 1983 [doi>10.1145/322358.322363]
• 14: Nancy A. Lynch, Multilevel atomicity—a new correctness criterion for database concurrency control, ACM Transactions on Database Systems (TODS), v.8 n.4, p.484-502, Dec. 1983 [doi>10.1145/319996.319999]
• 15: Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]
• 16: Calton Pu , Avraham Leff, Replica control in distributed systems: as asynchronous approach, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.377-386, May 29-31, 1991, Denver, Colorado, United States
• 17: Peter M. Schwarz , Alfred Z. Spector, Synchronizing shared abstract types, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.223-250, Aug. 1984 [doi>10.1145/989.1188]
• 18: W. E. Weihl. Specification and implementalzou of A tomzc Data Types. PhD thesis, Massachusetts Institute of Technology, 1984.
• 19: W. E. Weihl, Local atomicity properties: modular concurrency control for abstract data types, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.2, p.249-282, April 1989 [doi>10.1145/63264.63518]
• 20: W. E. Weihl, The impact of recovery on concurrency control, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.259-269, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73748]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Algorithms, Design