Query unnesting in object-oriented databases

ABSTRACT

There is already a sizable body of proposals on OODB query optimization. One of the most challenging problems in this area is query unnesting, where the embedded query can take any form, including aggregation and universal quantification. Although there is already a number of proposed techniques for query unnesting, most of these techniques are applicable to only few cases. We believe that the lack of a general and simple solution to the query unnesting problem is due to the lack of a uniform algebra that treats all operations (including aggregation and quantification) in the same way. This paper presents a new query unnesting algorithm that generalizes many unnesting techniques proposed recently in the literature. Our system is capable of removing any form of query nesting using a very simple and efficient algorithm. The simplicity of the system is due to the use of the monoid comprehension calculus as an intermediate form for OODB queries. The monoid comphrehension calculus treats operations over multiple collection types, aggregates, and quantifiers in a similar way, resulting in a uniform way of unnesting queries, regardless of their type of nesting.

REFERENCES

• 1: José A. Blakeley , William J. McKenna , Goetz Graefe, Experiences building the open OODB query optimizer, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.287-296, May 25-28, 1993, Washington, D.C., United States
• 2: 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]
• 3: Michael J. Carey , David J. DeWitt , Michael J. Franklin , Nancy E. Hall , Mark L. McAuliffe , Jeffrey F. Naughton , Daniel T. Schuh , Marvin H. Solomon , C. K. Tan , Odysseas G. Tsatalos , Seth J. White , Michael J. Zwilling, Shoring up persistent applications, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.383-394, May 24-27, 1994, Minneapolis, Minnesota, United States
• 4: Roderick G. Cattell , Tom Atwood, Object Database Standard: ODMG-93, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 5: Mitch Cherniack , Stan Zdonik, Changing the rules: transformations for rule-based optimizers, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.61-72, June 01-04, 1998, Seattle, Washington, United States
• 6: M. Cherniack, S. Zdonik, J. Lee, and K. Kim. Composing Rules the COKO-KOLA Way. Brown University, March 1997.
• 7: Jens Claußen , Alfons Kemper , Guido Moerkotte , Klaus Peithner, Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.286-295, August 25-29, 1997
• 8: S. Cluet and G. Moerkotte. Efficient Evaluation of Aggregates on Bulk Types. Technical report, Aachen University of Technology, October 1995. Technical Report 95-05.
• 9: S. Cluet and G. Moerkotte. Nested Queries in Object Bases. In Fifth International Workshop on Database Programming Languages, Gubbio, Italy, September 1995.
• 10: L. Fegaras. An Experimental Optimizer for OQL. University of Texas at Arlington Technical Report TR- CSE-97-007. Available at http://www-cse.uta.edu/ ~fegaras/oqlopt.ps.gz, May 1997.
• 11: L. Fegaras. Query Unnesting in Object-Oriented Databases (extended version). Available at http ://www-cse. uta. edu/~f egaras/s igmod98, ps, January }998.
• 12: Leonidas Fegaras , David Maier, An Algebraic Framework for Physical OODB Design, Proceedings of the Fifth International Workshop on Database Programming Languages, p.9, September 06-08, 1995
• 13: Leonidas Fegaras , David Maier, Towards an effective calculus for object query languages, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.47-58, May 22-25, 1995, San Jose, California, United States
• 14: L. Fegaras, D. Maier, and T. Sheard. Specifying Rulebased Query Optimizers in a Reflective Framework. Deductive and Object-Oriented Databases, Phoenix, Arizona, pp 146-168, December 1993. Springer-Verlag, LNCS 461.
• 15: Richard A. Ganski , Harry K. T. Wong, Optimization of nested SQL queries revisited, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.23-33, May 27-29, 1987, San Francisco, California, United States
• 16: Won Kim, On optimizing an SQL-like nested query, ACM Transactions on Database Systems (TODS), v.7 n.3, p.443-469, Sept. 1982 [doi>10.1145/319732.319745]
• 17: Jie Lin , Z. Meral Ozsoyoglu, Processing OODB queries by O-Algebra, Proceedings of the fifth international conference on Information and knowledge management, p.134-142, November 12-16, 1996, Rockville, Maryland, United States [doi>10.1145/238355.238470]
• 18: M. Muralikrishna, Improved Unnesting Algorithms for Join Aggregate SQL Queries, Proceedings of the 18th International Conference on Very Large Data Bases, p.91-102, August 23-27, 1992
• 19: Simon L. Peyton Jones, The Implementation of Functional Programming Languages (Prentice-Hall International Series in Computer Science), Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 20: Hennie J. Steenhagen , Peter M. G. Apers , Henk M. Blanken, Optimization of nested queries in a complex object model, Proceedings of the 4th international conference on extending database technology on Advances in database technology, p.337-350, May 1994, Cambridge, United Kingdom
• 21: 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
• 22: P. Trinder and P. Wadler. Improving List Comprehension Database Queries. In in Proceedings of TEN- CON'89, Bombay, India, pp 186-192, November 1989.
• 23: 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]
• 24: 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]
• 25: Limsoon Wong , Peter Buneman, Querying nested collections, 1994

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Object-oriented databases

General Terms:
Algorithms, Verification