Optimizing object queries using an effective calculus

ABSTRACT

Object-oriented databases (OODBs) provide powerful data abstractions and modeling facilities, but they generally lack a suitable framework for query processing and optimization. The development of an effective query optimizer is one of the key factors for OODB systems to successfully compete with relational systems, as well as to meet the performance requirements of many nontraditional applications. We propose an effective framework with a solid theoretical basis for optimizing OODB query languages. Our calculus, called the monoid comprehension calculus, captures most features of ODMG OQL, and is a good basis for expressing various optimization algorithms concisely. This article concentrates on query unnesting (also known as query decorrelation), an optimization that, even though it improves performance considerably, is not treated properly (if at all) by most OODB systems. Our framework generalizes many unnesting techniques proposed recently in the literature, and is capable of removing any form of query nesting using a very simple and efficient algorithm. The simplicity of our method is due to the use of the monoid comprehension calculus as an intermediate form for OODB queries. The monoid comprehension calculus treats operations over multiple collection types, aggregates, and quantifiers in a similar way, resulting in a uniform method of unnesting queries, regardless of their type of nesting.

REFERENCES

• 1: 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
• 2: 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
• 3: Stephen Bellantoni , Stephen Cook, A new recursion-theoretic characterization of the polytime functions (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.283-293, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129740]
• 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: 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]
• 8: Peter Buneman , Shamim Naqvi , Val Tannen , Limsoon Wong, Principles of programming with complex objects and collection types, Theoretical Computer Science, v.149 n.1, p.3-48, Sept. 18, 1995
• 9: Michael J. Carey , David J. DeWitt, Of Objects and Databases: A Decade of Turmoil, Proceedings of the 22th International Conference on Very Large Data Bases, p.3-14, September 03-06, 1996
• 10: 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, ACM SIGMOD Record, v.23 n.2, p.383-394, June 1994
• 11: R. G. G. Cattell , Douglas K. Barry , Mark Berler , Jeff Eastman , David Jordan , Craig Russell , Olaf Schadow , Torsten Stanienda , Fernando Velez, The object data standard: ODMG 3.0, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 12: 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
• 13: Mitch Cherniack , Stan Zdonik, Changing the rules: transformations for rule-based optimizers, ACM SIGMOD Record, v.27 n.2, p.61-72, June 1998
• 14: Mitch Cherniack , Stanley B. Zdonik, Inferring Function Semantics to Optimize Queries, Proceedings of the 24rd International Conference on Very Large Data Bases, p.239-250, August 24-27, 1998
• 15: 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
• 16: Sophie Cluet , Claude Delobel, A general framework for the optimization of object-oriented queries, ACM SIGMOD Record, v.21 n.2, p.383-392, June 1, 1992
• 17: CLUET,S.AND MOERKOTTE, G. 1995a. Efficient evaluation of aggregates on bulk types. Tech. Rep. 95-05. Aachen University of Technology, Aachen, Germany.
• 18: CLUET,S.AND MOERKOTTE, G. 1995b. Nested queries in object bases. In Proceedings of the Fifth International Workshop on Database Programming Languages (Gubbio, Italy, Sept.).
• 19: Latha S. Colby, A recursive algebra and query optimization for nested relations, ACM SIGMOD Record, v.18 n.2, p.273-283, June 1989
• 20: 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]
• 21: Scott Daniels , Goetz Graefe , Thomas Keller , David Maier , Duri Schmidt , Bennet Vance, Query optimization in revelation, an overview, Data Engineering, v.14 n.2, p.58-62, June 1991
• 22: 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]
• 23: Andrew Eisenberg , Jim Melton, SQL: 1999, formerly known as SQL3, ACM SIGMOD Record, v.28 n.1, p.131-138, March 1999 [doi>10.1145/309844.310075]
• 24: Leonidas Fegaras, Efficient Optimization of Iterative Queries, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.200-225, August 30-September 01, 1993
• 25: Leonidas Fegaras, A New Heuristic for Optimizing Large Queries, Proceedings of the 9th International Conference on Database and Expert Systems Applications, p.726-735, August 24-28, 1998
• 26: Leonidas Fegaras, Query unnesting in object-oriented databases, ACM SIGMOD Record, v.27 n.2, p.49-60, June 1998
• 27: Leonidas Fegaras, Optimizing Queries with Object Updates, Journal of Intelligent Information Systems, v.12 n.2-3, p.219-242, March 1999 [doi>10.1023/A:1008757010516]
• 28: Leonidas Fegaras, VOODOO: A Visual Object-Oriented Database Language For ODMG OQL, Proceedings of the Workshop on Object-Oriented Technology, p.61-72, June 14-18, 1999
• 29: 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
• 30: FEGARAS, L., MAIER, D., AND SHEARD, T. 1993. Specifying rule-based query optimizers in a reflective framework. In Proceedings of the Conference on Deductive and Object-Oriented Databases (Phoenix, AZ, Dec.). Springer-Verlag, Vienna, Austria, 146-168.
• 31: Leonidas Fegaras , Chandrasekhar Srinivasan , Arvind Rajendran , David Maier, &lgr;-DB: an ODMG-based object-oriented DBMS, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.583, May 15-18, 2000, Dallas, Texas, United States
• 32: Richard A. Ganski , Harry K. T. Wong, Optimization of nested SQL queries revisited, ACM SIGMOD Record, v.16 n.3, p.23-33, Dec. 1987
• 33: 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
• 34: 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]
• 35: Daniel Leivant, Stratified functional programs and computational complexity, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.325-333, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158659]
• 36: 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
• 37: Alon Y. Levy , Inderpal Singh Mumick , Yehoshua Sagiv, Query Optimization by Predicate Move-Around, Proceedings of the 20th International Conference on Very Large Data Bases, p.96-107, September 12-15, 1994
• 38: Leonid Libkin , Rona Machlin , Limsoon Wong, A query language for multidimensional arrays: design, implementation, and optimization techniques, ACM SIGMOD Record, v.25 n.2, p.228-239, June 1996
• 39: 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]
• 40: 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]
• 41: Erik Meijer , Maarten Fokkinga , Ross Paterson, Functional programming with bananas, lenses, envelopes and barbed wire, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.124-144, June 1991, Cambridge, Massachusetts, United States
• 42: I. S. Mumick , S. J. Finkelstein , Hamid Pirahesh , Raghu Ramakrishnan, Magic is relevant, ACM SIGMOD Record, v.19 n.2, p.247-258, Jun. 1990
• 43: 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
• 44: Z. Meral Özsoyoglu , Jian Wang, A Keying Method for a Nested Relational Database Management System, Proceedings of the Eighth International Conference on Data Engineering, p.438-446, February 03-07, 1992
• 45: 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
• 46: Benjamin C. Pierce, Basic category theory for computer scientists, MIT Press, Cambridge, MA, 1991
• 47: 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]
• 48: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 49: 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
• 50: Simon Thompson, Haskell: the craft of functional programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 51: 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
• 52: TRINDER,P.AND WADLER, P. 1989. Improving list comprehension database queries. In Proceedings of on TENCON'89 (Bombay, Nov.). 186-192.
• 53: 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]
• 54: 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]
• 55: Limsoon Wong , Peter Buneman, Querying nested collections, 1994

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design

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

General Terms:
Design, Experimentation, Performance

Keywords:
nested relations, object-oriented databases, query decorrelation, query optimization