Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers.
Umeshwar Dayal:
Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers.
VLDB 1987: 197-208@inproceedings{DBLP:conf/vldb/Dayal87,
author = {Umeshwar Dayal},
editor = {Peter M. Stocker and
William Kent and
Peter Hammersley},
title = {Of Nests and Trees: A Unified Approach to Processing Queries
That Contain Nested Subqueries, Aggregates, and Quantifiers},
booktitle = {VLDB'87, Proceedings of 13th International Conference on Very
Large Data Bases, September 1-4, 1987, Brighton, England},
publisher = {Morgan Kaufmann},
year = {1987},
isbn = {0-934613-46-X},
pages = {197-208},
ee = {db/conf/vldb/Dayal87.html},
crossref = {DBLP:conf/vldb/87},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
Existing query optimizers focus on Restrict-Project-Join
queries. In practice, however, query languages such as SQL and
DAPLEX have many powerful features (eg., control over duplicates,
nested subqueries, grouping, aggregates, and quantifiers)
that are not expressible as sequences of Restrict, Project, and
Join operations. Existing optimizers are severely limited in their
strategies for processing such queries; typically they use only
tuple substitution, and process nested subquery blocks top down.
Tuple substitution, however, is generally inefficient and
especially so when the database is distributed. Hence, it is
imperative to develop alternative strategies.
This paper introduces new operations for these difficult features,
and describes implementation methods for them.
From the algebraic properties of these operations, new query
processing tactics are derived.
It is shown how these new tactics can be deployed to
greatly increase the space of interesting strategies for optimization,
without seriously altering the architecture of existing optimizers.
The contribution of the paper is in demonstrating the feasibility
and desirability of developing an integrated framework for
optimizing all of SQL or other query languages that have similiar features.
Copyright © 1987 by the VLDB Endowment.
Permission to copy without fee all or part of this material is granted provided that the copies are not made or
distributed for direct commercial advantage, the VLDB
copyright notice and the title of the publication and
its date appear, and notice is given that copying
is by the permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires
a fee and/or special permission from the Endowment.
Online Paper
CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
Peter M. Stocker, William Kent, Peter Hammersley (Eds.):
VLDB'87, Proceedings of 13th International Conference on Very Large Data Bases, September 1-4, 1987, Brighton, England.
Morgan Kaufmann 1987, ISBN 0-934613-46-X
Contents
References
- [BERN81]
- Philip A. Bernstein, Dah-Ming W. Chiu:
Using Semi-Joins to Solve Relational Queries.
J. ACM 28(1): 25-40(1981)
![bibliographical record in XML](../../xml.gif)
- [BLAS77]
- ...
- [CERI85]
- Stefano Ceri, Georg Gottlob:
Translating SQL Into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries.
IEEE Trans. Software Eng. 11(4): 324-345(1985)
![bibliographical record in XML](../../xml.gif)
- [CHAM76]
- ...
- [CODD70]
- E. F. Codd:
A Relational Model of Data for Large Shared Data Banks.
Commun. ACM 13(6): 377-387(1970)
![bibliographical record in XML](../../xml.gif)
- [CODD72]
- E. F. Codd:
Relational Completeness of Data Base Sublanguages.
In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972)
![bibliographical record in XML](../../xml.gif)
- [CODD79]
- E. F. Codd:
Extending the Database Relational Model to Capture More Meaning.
ACM Trans. Database Syst. 4(4): 397-434(1979)
![bibliographical record in XML](../../xml.gif)
- [DATE85]
- ...
- [DAYA82]
- Umeshwar Dayal, Nathan Goodman, Randy H. Katz:
An Extended Relational Algebra with Control over Duplicate Elimination.
PODS 1982: 117-123
![bibliographical record in XML](../../xml.gif)
- [DAYA83]
- Umeshwar Dayal:
Processing Queries with Quantifiers: A Horticultural Approach.
PODS 1983: 125-136
![bibliographical record in XML](../../xml.gif)
- [DAYA85]
- Umeshwar Dayal:
Query Processing in a Multidatabase System.
Query Processing in Database Systems 1985: 81-108
![bibliographical record in XML](../../xml.gif)
- [DEWI87]
- Goetz Graefe, David J. DeWitt:
The EXODUS Optimizer Generator.
SIGMOD Conference 1987: 160-172
![bibliographical record in XML](../../xml.gif)
- [FREY87]
- Johann Christoph Freytag:
A Rule-Based View of Query Optimization.
SIGMOD Conference 1987: 173-180
![bibliographical record in XML](../../xml.gif)
- [GANS87]
- Richard A. Ganski, Harry K. T. Wong:
Optimization of Nested SQL Queries Revisited.
SIGMOD Conference 1987: 23-33
![bibliographical record in XML](../../xml.gif)
- [JARK82]
- Matthias Jarke, Joachim W. Schmidt:
Query Processing Strategies in the PASCAL/R Relational Database Management System.
SIGMOD Conference 1982: 256-264
![bibliographical record in XML](../../xml.gif)
- [KIM82]
- Won Kim:
On Optimizing an SQL-like Nested Query.
ACM Trans. Database Syst. 7(3): 443-469(1982)
![bibliographical record in XML](../../xml.gif)
- [KLUG82]
- Anthony C. Klug:
Access Paths in the 'ABE' Statistical Query Facility.
SIGMOD Conference 1982: 161-173
![bibliographical record in XML](../../xml.gif)
- [LACR76]
- ...
- [LOHM84]
- Guy M. Lohman, Dean Daniels, Laura M. Haas, Ruth Kistler, Patricia G. Selinger:
Optimization of Nested Queries in a Distributed Relational Database.
VLDB 1984: 403-415
![bibliographical record in XML](../../xml.gif)
- [MACK86a]
- Lothar F. Mackert, Guy M. Lohman:
R* Optimizer Validation and Performance Evaluation for Local Queries.
SIGMOD Conference 1986: 84-95
![bibliographical record in XML](../../xml.gif)
- [MACK86b]
- Lothar F. Mackert, Guy M. Lohman:
R* Optimizer Validation and Performance Evaluation for Distributed Queries.
VLDB 1986: 149-159
![bibliographical record in XML](../../xml.gif)
- [PALE72]
- ...
- [ROSE84]
- Arnon Rosenthal, David S. Reiner:
Extending the Algebraic Framework of Query Processing to Handle Outerjoins.
VLDB 1984: 334-343
![bibliographical record in XML](../../xml.gif)
- [SELI79]
- Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price:
Access Path Selection in a Relational Database Management System.
SIGMOD Conference 1979: 23-34
![bibliographical record in XML](../../xml.gif)
- [SHIP81]
- David W. Shipman:
The Functional Data Model and the Data Language DAPLEX.
ACM Trans. Database Syst. 6(1): 140-173(1981)
![bibliographical record in XML](../../xml.gif)
- [SMIT83]
- ...
- [WONG76]
- Eugene Wong, Karel Youssefi:
Decomposition - A Strategy for Query Processing.
ACM Trans. Database Syst. 1(3): 223-241(1976)
![bibliographical record in XML](../../xml.gif)
Copyright © Mon Mar 15 03:55:50 2010
by Michael Ley (ley@uni-trier.de)