Towards an effective calculus for object query languages

ABSTRACT

We define a standard of effectiveness for a database calculus relative to a query language. Effectiveness judges suitability to serve as a processing framework for the query language, and comprises aspects of coverage, manipulability and efficient evaluation. We present the monoid calculus, and argue its effectiveness for object-oriented query languages, exemplified by OQL of ODMG-93. The monoid calculus readily captures such features as multiple collection types, aggregations, arbitrary composition of type constructors and nested query expressions. We also show how to extend the monoid calculus to deal with vectors and arrays in more expressive ways than current query languages do, and illustrate how it can handle identity and updates.

REFERENCES

• 1: S. Abiteboul and C. Beeri. On the Power of Languages for the Manipulation of Complex Objects. In International Workshop on Theory and Applicatzons of Nested Relations and Complex Objects, Darmstadt, 1987.
• 2: David Beech, Collections of Objects in SQL3, Proceedings of the 19th International Conference on Very Large Data Bases, p.244-255, August 24-27, 1993
• 3: Catriel Beeri , Yoram Kornatzky, Algebraic optimization of object-oriented query languages, Proceedings of the third international conference on database theory on Database theory, p.72-88, November 1990, Paris, France
• 4: Val Breazu-Tannen , Peter Buneman , Shamim Naqvi, Structural recursion as a query language, Proceedings of the third international workshop on Database programming languages : bulk types & persistent data: bulk types & persistent data, p.9-19, April 1992, Nafplion, Greece
• 5: Val Tannen , Peter Buneman , Limsoon Wong, Naturally Embedded Query Languages, Proceedings of the 4th International Conference on Database Theory, p.140-154, October 14-16, 1992
• 6: 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
• 7: P. Buneman. The Fast Fourier Transform as a Database Query. Technical report, University of Pennsylvania, March 1993. MS-CIS-93-37/L&C 60.
• 8: Peter Buneman , Leonid Libkin , Dan Suciu , Val Tannen , Limsoon Wong, Comprehension syntax, ACM SIGMOD Record, v.23 n.1, p.87-96, March 1994 [doi>10.1145/181550.181564]
• 9: Roderick G. Cattell , Tom Atwood, Object Database Standard: ODMG-93, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 10: Daniel K. C. Chan , Philip W. Trinder, Object Comprehensions: A Query Notation for Object-Oriented Databases, Proceedings of the 12th British National Conference on Databases: Directions in Databases, p.55-72, July 06-08, 1994
• 11: Sophie Cluet , Claude Delobel, A general framework for the optimization of object-oriented queries, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.383-392, June 02-05, 1992, San Diego, California, United States
• 12: P. Dadam , K. Kuespert , F. Andersen , H. Blanken , R. Erbe, A DBMS prototype to support extended NF2 relations: an integrated view on flat tables and hierarchies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.356-367, May 28-30, 1986, Washington, D.C., United States
• 13: S. Danforth , P. Valduriez, A FAD for Data Intensive Applications, IEEE Transactions on Knowledge and Data Engineering, v.4 n.1, p.34-51, February 1992 [doi>10.1109/69.124896]
• 14: Umeshwar Dayal , Nathan Goodman , Randy H. Katz, An extended relational algebra with control over duplicate elimination, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588132]
• 15: O. Deux et al., The Story of O2, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.91-108, March 1990 [doi>10.1109/69.50908]
• 16: L. Fegaras. A Uniform Calculus for Collection Types. Oregon Graduate Institute Technical Report 94-030. Available by anonymous ftp from cse. ogi. edu:/pub/crml/tapos, ps. Z.
• 17: L. Fegaras and D. Maier. An Algebraic Framework for Physical OODB Design. Available by anonymous ftp from cse. ogi. edu:/pub/crml/oodb-design.ps. Z.
• 18: Shashi K. Gadia, A homogeneous relational model and query languages for temporal databases, ACM Transactions on Database Systems (TODS), v.13 n.4, p.418-448, Dec. 1988 [doi>10.1145/49346.50065]
• 19: Neil Immerman , Sushant Patnaik , David Stemple, The expressiveness of a family of finite set languages, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.37-52, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113417]
• 20: Alfons Kemper , Guido Moerkotte, Advanced query processing in object bases using access support relations, Proceedings of the sixteenth international conference on Very large databases, p.290-301, September 1990, Brisbane, Australia
• 21: Theodore W. Leung , Gail Mitchell , Bharathi Subramanian , Bennet Vance , Scott L. Vandenberg , Stanley B. Zdonik, The AQUA Data Model and Algebra, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.157-175, August 30-September 01, 1993
• 22: David Maier , Bennet Vance, A call to order, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-16, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153851]
• 23: Atushi Ohori, Representing object identity in a pure functional language, Proceedings of the third international conference on database theory on Database theory, p.41-55, November 1990, Paris, France
• 24: G. Özsoyoğlu , Z. M. Özsoyoğlu , V. Matos, Extending relational algebra and relational calculus with set-valued attributes and aggregate functions, ACM Transactions on Database Systems (TODS), v.12 n.4, p.566-592, Dec. 1987 [doi>10.1145/32204.32219]
• 25: P Pistor , R Traunmueller, A database language for sets, lists and tables, Information Systems, v.11 n.4, p.323-336, Oct. 1986 [doi>10.1016/0306-4379(86)90012-8]
• 26: Phil Trinder, Comprehensions, a query notation for DBPLs, Proceedings of the third international workshop on Database programming languages : bulk types & persistent data: bulk types & persistent data, p.55-68, April 1992, Nafplion, Greece
• 27: P. Trinder and P. Wadler. improving List Comprehension Database Queries. In in Proceedings of TEN- CON'89, Bombay, india, pp 186-192, November 1989.
• 28: Scott L. Vandenberg , David J. DeWitt, Algebraic support for complex objects with arrays, identity, and inheritance, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.158-167, May 29-31, 1991, Denver, Colorado, United States
• 29: Philip Wadler, Comprehending monads, Proceedings of the 1990 ACM conference on LISP and functional programming, p.61-78, June 27-29, 1990, Nice, France [doi>10.1145/91556.91592]
• 30: Limsoon Wong, Normal forms and conservative properties for query languages over collection types, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.26-36, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153853]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems

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

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.0 General

General Terms:
Algorithms, Languages, Theory