Query Unnesting in Object-Oriented Databases.

@inproceedings{DBLP:conf/sigmod/Fegaras98,
  author    = {Leonidas Fegaras},
  editor    = {Laura M. Haas and
               Ashutosh Tiwary},
  title     = {Query Unnesting in Object-Oriented Databases},
  booktitle = {SIGMOD 1998, Proceedings ACM SIGMOD International Conference
               on Management of Data, June 2-4, 1998, Seattle, Washington, USA},
  publisher = {ACM Press},
  year      = {1998},
  isbn      = {0-89791-995-5},
  pages     = {49-60},
  ee        = {http://doi.acm.org/10.1145/276304.276310, db/conf/sigmod/Fegaras98.html},
  crossref  = {DBLP:conf/sigmod/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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 comprehension 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.

Copyright © 1998 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD DiSC

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/Disc99_1 or /cdrom

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM SIGMOD

Extended Version

References

[1]

José A. Blakeley, William J. McKenna, Goetz Graefe: Experiences Building the Open OODB Query Optimizer. SIGMOD Conference 1993: 287-296 BibTeX

[2]

Peter Buneman, Leonid Libkin, Dan Suciu, Val Tannen, Limsoon Wong: Comprehension Syntax. SIGMOD Record 23(1): 87-96(1994) BibTeX

[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. SIGMOD Conference 1994: 383-394 BibTeX

[4]

R. G. G. Cattell: The Object Database Standard: ODMG-93 (Release 1.1). Morgan Kaufmann 1994
BibTeX

[5]

Mitch Cherniack, Stanley B. Zdonik: Changing the Rules: Transformations for Rule-Based Optimizers. SIGMOD Conference 1998: 61-72 BibTeX

[6]

...

[7]

Jens Claußen, Alfons Kemper, Guido Moerkotte, Klaus Peithner: Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases. VLDB 1997: 286-295 BibTeX

[8]

Sophie Cluet, Guido Moerkotte: Efficient Evaluation of Aggregates on Bulk Types. DBPL 1995: 8 BibTeX

[9]

Sophie Cluet, Guido Moerkotte: Nested Queries in Object Bases. DBPL 1993: 226-242 BibTeX

[10]

...

[11]

...

[12]

Leonidas Fegaras, David Maier: An Algebraic Framework for Physical OODB Design. DBPL 1995: 9 BibTeX

[13]

Leonidas Fegaras, David Maier: Towards an Effective Calculus for Object Query Languages. SIGMOD Conference 1995: 47-58 BibTeX

[14]

Leonidas Fegaras, David Maier, Tim Sheard: Specifying Rule-Based Query Optimizers in a Reflective Framework. DOOD 1993: 146-168 BibTeX

[15]

Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 BibTeX

[16]

Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX

[17]

Jie Lin, Z. Meral Özsoyoglu: Processing OODB Queries by O-Algebra. CIKM 1996: 134-142 BibTeX

[18]

M. Muralikrishna: Improved Unnesting Algorithms for Join Aggregate SQL Queries. VLDB 1992: 91-102 BibTeX

[19]

Simon L. Peyton Jones: The Implementation of Functional Programming Languages. Prentice-Hall 1987
BibTeX

[20]

Hennie J. Steenhagen, Peter M. G. Apers, Henk M. Blanken: Optimization of Nested Queries in a Complex Object Model. EDBT 1994: 337-350 BibTeX

[21]

Philip W. Trinder: Comprehensions, a Query Notation for DBPLs. DBPL 1991: 55-68 BibTeX

[22]

...

[23]

...

[24]

Limsoon Wong: Normal Forms and Conservative Properties for Query Languages over Collection Types. PODS 1993: 26-36 BibTeX

[25]

...

Referenced by

1. Leonidas Fegaras, Chandrasekhar Srinivasan, Arvind Rajendran, David Maier: lambda-DB: An ODMG-Based Object-Oriented DBMS. SIGMOD Conference 2000: 583