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. 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. 2.D. Beech. Collections of Objects in SQL3. In VLDB'93, pp 244-255.
3. 3.C. Beeri and Y. K ornatzky. Algebraic Optimization of Object-Oriented Query Languages. In International Conference on Database Theory, Paris, France, pp 72- 88. Springer-Verlag, December 1990. LNCS 470.
4. 4.V. Breazu-Tannen, P. Buneman, and S. Naqvi. Structural Recursion as a Query Language. In Proceedings of the Third International Workshop on Database Programming Languages, pp 9-19. August 1991.
5. 5.V. Breazu-Tannen, P. Buneman, and L. Wong. Naturally Embedded Query Languages. In 4th International Conference on Database Theory, Berlin, Germany, pp 140-154. Springer-Verlag, October 1992. LNCS 646.
6. 6.V. Breazu-Tannen and R. Subrahmanyam. Logical and Computational Aspects of Programming with Sets/Bags/Lists. In 18th International Colloquium on Automata, Languages and Programming, Madmd, Spain, pp 60-75, July 1991. LNCS 510.
7. 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. 8.P. Buneman, L. Libkin, D. Suciu, V. Tannen, and L. Wong. Comprehension Syntax. SIGMOD Record, 23(1):87-96, March 1994.
9. 9.R. Cattell. The Object Database Standard: ODMG-93. Morgan Kaufmann, 1994.
10. 10.D. Chan and P. Trinder. Object Comprehensions: A Query Notation for Object-Orlented Databases. In Twelfth Brihsh Conference on Databases, pp 55-72, July 1994. LNCS 826.
11. 11.S. Cluet and C. Delobel. A General Framework for the Optimization of Object-Oriented Queries. In SIGMOD'9~, pp 383-292.
12. 12.P. Dadam, et al. A DBMS Prototype to Support Extended NF2 Relations: An Integrated View on Flat Tables and Hierarchies. In SIGMOD'86, pp 356-367.
13. 13.S. Danforth and P. Valduriez. A FAD for Data Intensive Applications. Transactions on Knowledge and Data Engineering, 4(1):34-51, February 1992.
14. 14.U. Dayal, N. Goodman, and R. H. Katz. An Extended Relational Algebra with Control Over Duplicate Elimination. In PODS'82, pp 117-123.
15. 15.O. Deux, et al. The Story of 02. Transactions on Knowledge and Data Engineering, 2(1):91-108, March 1990.
16. 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. 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. 18.S. K. Gadia. A Homogeneous Relational Model and Query Languages for Temporal Databases. Transactions on Database Systems, 13(4):418-448, December 1988.
19. 19.N. Immerman, S. Patnaik, and D. Stemple. The Expressiveness of a Family of Finite Set Languages. In PODS'91, pp 37-52.
20. 20.A. Kemper and G. Moerkotte. Advanced Query Processing in Object Bases Using Access Support Relations. In VLDB'90, pp 290-301.
21. 21.T. Leung, G. Mitchell, B. Subramanian, B. Vance, S. Vandenberg, and S. Zdonik. The AQUA Data Model and Algebra. In Fourth International Workshop on Database Programm,ng Languages, Manhattan, New York City, pp 157-175, August 1993.
22. 22.D. Maier and B. Vance. A Call to Order. In PODS'93, pp 1-16.
23. 23.A. Ohori. Representing Object Identity in a Pure Functional Language. in International Conference on Database Theory, Paris~ France, pp 41-55. Springer- Verlag, December 1990. LNCS 470.
24. 24.G. Ozsoyo~lu, Z. Ozsoyo~lu, and V. Matos. Extending Relational Algebra and Relational Calculus with Set-VMued Attributes and Aggregate Functions. A CM Transactions on Database Systems, 12(4):566-592, December 1987.
25. 25.P. Pistor and R. Traunmueller. A Database Language for Sets, Lists, and Tables. Information Systems, 11(4):323-336, 1986.
26. 26.P. Trinder. Comprehensions: A Query Notation for DBPLs. In Proceedings of the Third International Workshop on Database Programming Languages, pp 55-68, August 1991.
27. 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. 28.S. Vandenberg and D. DeWitt. Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance. In SIGMOD'91, pp 158-167.
29. 29.P. Wadler. Comprehending Monads. In Proceedings o/ the A CM Symposium on Lisp and Functional Programming, Nice, France, pp 61-78, June 1990.
30. 30.L. Wong. Normal Forms and Conservative Properties for Query Languages over Collection Types. In PODS'93, pp 26-36.

Index Terms

• Computing methodologies

  • Symbolic and algebraic manipulation

• Information systems

  • Data management systems

    • Database design and models

    • Query languages

• Theory of computation

  • Formal languages and automata theory

    • Formalisms

      • Rewrite systems

    • Grammars and context-free languages