Context-based synchronization: an approach beyond semantics for concurrency control

ABSTRACT

The expressiveness of various object-oriented languages is investigated with respect to their ability to create new objects. We focus on database method schemas (dms), a model capturing the data manipulation capabilities of a large class of deterministic methods in object-oriented databases. The results clarify the impact of various language constructs on object creation. Several new constructs based on expanded notions of deep equality are introduced. In particular, we provide a tractable construct which yields a language complete with respect to object creation. The new construct is also relevant to query complexity. For example, it allows expressing in polynomial time some queries, like counting, requiring exponential space in dms alone.

REFERENCES

• 1: 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]
• 2: Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981 [doi>10.1145/356842.356846]
• 3: P. A. Bernstein, D. W. Shipman, and W. S. Wong. Formal Aspects of Serializability in Database Concurrency Control. IEEE Transactions an Software Engineering, 5(5):203-216, May 1979.
• 4: 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
• 5: 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]
• 6: 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]
• 7: 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]
• 8: Christos H. Papadimitriou , Paris C. Kanellakis, On Concurrency Control by Multiple Versions, ACM Transactions on Database Systems (TODS), v.9 n.1, p.89-99, March 1984 [doi>10.1145/348.318588]
• 9: 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]
• 10: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 11: 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]
• 12: D. P. Reed, NAMING AND SYNCHRONIZATION IN A DECENTRALIZED COMPUTER SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 13: 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]
• 14: W. E. Weihl. Specification and Implementation of Atomic Data Types. PhD thesis, Massachusetts Institute of Technology, 1984.
• 15: 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]
• 16: 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]
• 17: Gerhard Weikum, Principles and realization strategies of multilevel transaction management, ACM Transactions on Database Systems (TODS), v.16 n.1, p.132-180, March 1991 [doi>10.1145/103140.103145]
• 18: M. It. Wong and D. Agrawal. Context-Based Synchronization: An Approach beyond Semantics for Concurrency Control. Technical report, Department of Computer Science, University of California, Santa Barbara, CA93106, 1992.
• 19: Man Hon Wong , Divyakant Agrawal, Context-specific synchronization for atomic data types in object-based databases, Selected papers of the fourth international conference on Database theory, p.179-199, September 1995, Berlin, Germany

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.4 Systems
          Subjects: Transaction processing

General Terms:
Algorithms, Theory