 |
|
|
Query Unnesting in Object-Oriented Databases |
Full Paper (PDF)
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. |
References, where available, link to the DBLP on the World Wide Web.
[1]José A. Blakeley, William J. McKenna, Goetz Graefe:
Experiences Building the Open OODB Query Optimizer.
SIGMOD Conference 1993: 287-296[2]Peter Buneman, Leonid Libkin, Dan Suciu, Val Tannen, Limsoon Wong:
Comprehension Syntax.
SIGMOD Record 23(1): 87-96(1994)[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[4]R. G. G. Cattell:
The Object Database Standard: ODMG-93 (Release 1.1).
Morgan Kaufmann 1994
[5]Mitch Cherniack, Stanley B. Zdonik:
Changing the Rules: Transformations for Rule-Based Optimizers.
SIGMOD Conference 1998: 61-72[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[8]Sophie Cluet, Guido Moerkotte:
Efficient Evaluation of Aggregates on Bulk Types.
DBPL 1995: 8[9]Sophie Cluet, Guido Moerkotte:
Nested Queries in Object Bases.
DBPL 1993: 226-242[10]...
[11]...
[12]Leonidas Fegaras, David Maier:
An Algebraic Framework for Physical OODB Design.
DBPL 1995: 9[13]Leonidas Fegaras, David Maier:
Towards an Effective Calculus for Object Query Languages.
SIGMOD Conference 1995: 47-58[14]Leonidas Fegaras, David Maier, Tim Sheard:
Specifying Rule-Based Query Optimizers in a Reflective Framework.
DOOD 1993: 146-168[15]Richard A. Ganski, Harry K. T. Wong:
Optimization of Nested SQL Queries Revisited.
SIGMOD Conference 1987: 23-33[16]Won Kim:
On Optimizing an SQL-like Nested Query.
TODS 7(3): 443-469(1982)[17]Jie Lin, Z. Meral Özsoyoglu:
Processing OODB Queries by O-Algebra.
CIKM 1996: 134-142[18]M. Muralikrishna:
Improved Unnesting Algorithms for Join Aggregate SQL Queries.
VLDB 1992: 91-102[19]Simon L. Peyton Jones:
The Implementation of Functional Programming Languages.
Prentice-Hall 1987
[20]Hennie J. Steenhagen, Peter M. G. Apers, Henk M. Blanken:
Optimization of Nested Queries in a Complex Object Model.
EDBT 1994: 337-350[21]Philip W. Trinder:
Comprehensions, a Query Notation for DBPLs.
DBPL 1991: 55-68[22]...
[23]...
[24]Limsoon Wong:
Normal Forms and Conservative Properties for Query Languages over Collection Types.
PODS 1993: 26-36[25]...
|
@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-955-5},
pages = {49-60},
crossref = {DBLP:conf/sigmod/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
