A logical semantics for object-oriented databases

ABSTRACT

Although the mathematical foundations of relational databases are very well established, the state of affairs for object-oriented databases is much less satisfactory. We propose a semantic foundation for object-oriented databases based on a simple logic of change called rewriting logic, and a language called MaudeLog that is based on that logic. Some key advantages of our approach include its logical nature, its simplicity without any need for higher-order features, the fact that dynamic aspects are directly addressed, the rigorous integration of user-definable algebraic data types within the framework, the existence of initial models, and the integration of query, update, and programming aspects within a single declarative language.

REFERENCES

• 1: Serge Abiteboul , Anthony Bonner, Objects and views, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.238-247, May 29-31, 1991, Denver, Colorado, United States
• 2: Serge Abiteboul , Paris C. Kanellakis, Object identity as a query language primitive, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.159-173, June 1989, Portland, Oregon, United States
• 3: Serge Abiteboul , Paris C. Kanellakis, The two facets of object-oriented data models, Data Engineering, v.14 n.2, p.3-7, June 1991
• 4: Serge Abiteboul , Paris C. Kanellakis , Emmanuel Waller, Method schemas, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.16-27, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298538]
• 5: G. Agha. Actors. MIT Press, 1986.
• 6: Gul Agha , Carl Hewitt, Concurrent programming using actors, Object-oriented concurrent programming, MIT Press, Cambridge, MA, 1987
• 7: M. Atkinson, P. Richard, and P. Trinder. Bulk types for large scale programming, in Proc. Next Generation In. .formation System Technology, pages 228-250, Springer LNCS 504, 1991.
• 8: Catriel Beeri, Theoretical foundations for OODB's—a personal perspective, Data Engineering, v.14 n.2, p.8-12, June 1991
• 9: Catriel Beeri, New data models and languages—the challenge, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-15, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137101]
• 10: Catriel Beeri , Tova Milo, Functional and predictive programming in OODB's, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.176-190, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137863]
• 11: Elisa Bertino, A View Mechanism for Object-Oriented Databases, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.136-151, March 23-27, 1992
• 12: Val Breazu-Tannen , Ramesh Subrahmanyam, Logical and computational aspects of programming with sets/bags/lists, Proceedings of the 18th international colloquium on Automata, languages and programming, p.60-75, June 1991, Madrid, Spain
• 13: Bob Carpenter, The logic of typed feature structures, Cambridge University Press, New York, NY, 1992
• 14: Weidong Chen , Michael Kifer , David S. Warren, HiLog as a platform for database languages, Proceedings of the second international workshop on Database programming languages, p.315-329, December 1989, Salishan Lodge, Gleneden Beach, Oregon, United States
• 15: Nachum Dershowitz , Jean-Pierre Jouannaud, Rewrite systems, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 16: 3. Gogucn. Merged views, closed worlds, and ordered sorts: Some novel database features in OBJ. in A. Borgida and P. Buneman (editors), Proc. 19892 Workshop on Database Interfaces, pages 38-47, University of Pennsylvania, Computer Science Department, 1985.
• 17: Joseph A. Goguen , José Meseguer, Unifying functional, object-oriented and relational programming with logical semantics, Research directions in object-oriented programming, MIT Press, Cambridge, MA, 1987
• 18: Joseph A. Goguen , José Meseguer, Order-sorted algebra I: equational deduction for multiple inheritance, overloading, exceptions and partial operations, Theoretical Computer Science, v.105 n.2, p.217-273, Nov. 1992 [doi>10.1016/0304-3975(92)90302-V]
• 19: J. Goguen, J. Thatcher, and E. Wagner. An initial algebra approach to the specification, correctness and implementation of abstract data types. In Current Trends in Programming Methodology, IV, R. Yeh (editor), Prentice-Hall, 1978, pages 80-149.
• 20: J. Goguen, T. Wlnkler, J. Meseguer, K. Futatsugi, and J.-P. Jou#mnaud. Introducing OBJ. To appear in J. Goguen (editor), Applications of Algebraic Specification Using OBJ, Cambridge University Press.
• 21: J. Goguen and D. Wolfram. On types and FOOPS. In Proc. IFIP Working Group 2.6 Working Conference on Database Semantics: Object-Oriented Databases: Analysis, Design and Construction, 1990.
• 22: Gérard Huet, Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems: Abstract Properties and Applications to Term Rewriting Systems, Journal of the ACM (JACM), v.27 n.4, p.797-821, Oct. 1980 [doi>10.1145/322217.322230]
• 23: Michael Kifer , Georg Lausen, F-logic: a higher-order language for reasoning about objects, inheritance, and scheme, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.134-146, June 1989, Portland, Oregon, United States
• 24: Claude Kirchner , Hélène Kirchner , José Meseguer, Operational Semantics of OBJ-3 (Extended Abstract), Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.287-301, July 11-15, 1988
• 25: S. MacLane. Categories}or the working mathematician. Springer-Verlag, 1971.
• 26: D. Maier. A logic for objects. In Proc. Workshop on Foundations of Deductive Databases and Logic Programming, Washington, D.C., pages 6-26, 1986.
• 27: José Meseguer, Conditional rewriting logic as a unified model of concurrency, Theoretical Computer Science, v.96 n.1, p.73-155, 6 April 1992
• 28: José Meseguer, Multiparadigm Logic Programming, Proceedings of the Third International Conference on Algebraic and Logic Programming, p.158-200, September 02-04, 1992
• 29: José Meseguer, A logical theory of concurrent objects and its realization in the Maude language, Research directions in concurrent object-oriented programming, MIT Press, Cambridge, MA, 1993
• 30: J. Meseguer , J. A. Goguen , G. Smolka, Order-sorted unification, Journal of Symbolic Computation, v.8 n.4, p.383-413, Oct. 1989 [doi>10.1016/S0747-7171(89)80036-7]
• 31: José Meseguer , Timothy C. Winkler, Parallel Programmming in Maude, Research Directions in High-Level Parallel Programming Languages, p.253-293, June 17-19, 1991
• 32: Gert Smolka , Hassan Ait-Kac, Inheritance hierarchies: semantics and unification, Journal of Symbolic Computation, v.7 n.3-4, p.343-370, March/April 1989 [doi>10.1016/S0747-7171(89)80016-1]
• 33: Gio Wiederhold, Mediators in the Architecture of Future Information Systems, Computer, v.25 n.3, p.38-49, March 1992 [doi>10.1109/2.121508]
• 34: Gio Wiederhold , Peter Wegner , Stefano Ceri, Toward megaprogramming, Communications of the ACM, v.35 n.11, p.89-99, Nov. 1992 [doi>10.1145/138844.138853]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parallel rewriting systems (e.g., developmental systems, L-systems)

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Design, Languages