Database method schemas and object creation

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

• AH87: Serge Abiteboul , Richard Hull, IFO: a formal semantic database model, ACM Transactions on Database Systems (TODS), v.12 n.4, p.525-565, Dec. 1987 [doi>10.1145/32204.32205]
• AK89: 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
• AKW90: 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]
• AV91a: Serge Abiteboul , Victor Vianu, Datalog extensions for database queries and updates, Journal of Computer and System Sciences, v.43 n.1, p.62-124, Aug. 1991 [doi>10.1016/0022-0000(91)90032-Z]
• AV91b: Serge Abiteboul , Victor Vianu, Generic Computation and its complexity, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.209-219, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103444]
• AP92: Marc Andries , Jan Paredaens, A Language for Generic Graph-Transformations, Proceedings of the 17th International Workshop, p.63-74, June 17-19, 1991
• B78: F. Bancilhon. On t}he Completeness of Query Languages for Relational Data Bases. In Proc. 7th Symp. on Ma#!hematical Foundations of Computer Science, Lecture Notes in Computer Science 64, 112-123, Springer-Verlag, 1978.
• BG2: Jan Van den Bussche , Dirk Van Gucht, Semi-determinism (extended abstract), Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.191-201, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137866]
• BGAG92: J. Van den Bussche, D. Van Gucht, M. Andries and M. Gyssens. On the Completeness of Object-Creating Query Languages. In Proc. 33rd Symp. on Foundations of Computer Science, 372-379, 1992.
• BP91: Jan Van den Bussche , Jan Paredaens, The expressive power structured values in pure OODB's (extended abstract), Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.291-299, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113440]
• Ch81: Ashok K. Chandra, Programming primitives for database languages, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.50-62, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567537]
• CH80: A. Chandra and D. {-Iarel. Computable Queries for Relational Data Bases. Journal of Computer and System Sciences,, 21(2):156-178, Oct. 1980.
• DV91: Karl Denninghoff , Victor Vianu, The Power of Methods With Parallel Semantics, Proceedings of the 17th International Conference on Very Large Data Bases, p.221-232, September 03-06, 1991
• D93: K. Denninghoff. Database Method Schemas. PhD Thesis, in preparation.
• GPVG90a: Marc Gyssens , Jan Paredaens , Dirk van Gucht, A graph-oriented object database model, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.417-424, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298593]
• GPVG90b: Marc Gyssens , Jan Paredaens , Dirk Van Gucht, A graph-oriented object model for database end-user interfaces, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.24-33, May 23-26, 1990, Atlantic City, New Jersey, United States
• HS88: Richard Hull , Jianwen Su, On the expressive power of database queries with intermediate types, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.39-51, March 1988, Austin, Texas, United States [doi>10.1145/308386.308409]
• KC90: S. Khoshafian , G. P. Copeland, Object identity, Readings in object-oriented database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• KV88: G. M. Kuper , M. Y. Vardi, On the complexity of queries in the logical data model, Lecture notes in computer science on ICDT '88, p.267-280, October 1988, Bruges, Belgium

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.3 Languages
          Subjects: Data manipulation languages (DML)

General Terms:
Languages, Theory