ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases.

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
@inproceedings{DBLP:conf/vldb/ClaussenKMP97,
  author    = {Jens Clau{\ss}en and
               Alfons Kemper and
               Guido Moerkotte and
               Klaus Peithner},
  editor    = {Matthias Jarke and
               Michael J. Carey and
               Klaus R. Dittrich and
               Frederick H. Lochovsky and
               Pericles Loucopoulos and
               Manfred A. Jeusfeld},
  title     = {Optimizing Queries with Universal Quantification in Object-Oriented
               and Object-Relational Databases},
  booktitle = {VLDB'97, Proceedings of 23rd International Conference on Very
               Large Data Bases, August 25-29, 1997, Athens, Greece},
  publisher = {Morgan Kaufmann},
  year      = {1997},
  isbn      = {1-55860-470-7},
  pages     = {286-295},
  ee        = {db/conf/vldb/ClaussenKMP97.html},
  crossref  = {DBLP:conf/vldb/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We investigate the optimization and evaluation of queries with universal quantification in the context of the object-oriented and object-relational data models. The queries are classified into 16 categories depending on the variables referenced in the so-called range and quantifier predicates. For the three most important classes we enumerate the known query evaluation plans and devise some new ones. These alternative plans are primarily based on anti-semijoin, division, generalized grouping with count aggregation, and set difference. In order to evaluate the quality of the many different evaluation plans a thorough performance analysis on some sample database configurations was carried out. The quantitative analysis reveals that--if applicable--the anti-semijoin-based plans are superior to all the other alternatives, even if we employ the most sophisticated division algorithms. Furthermore, exploiting object-oriented features, anti-semijoin plans can be derived even when this is not possible in the relational context.

Copyright © 1997 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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Matthias Jarke, Michael J. Carey, Klaus R. Dittrich, Frederick H. Lochovsky, Pericles Loucopoulos, Manfred A. Jeusfeld (Eds.): VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece. Morgan Kaufmann 1997, ISBN 1-55860-470-7
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Electronic Edition

From CS Dept., University Trier (Germany)

References

[BMG93]
José A. Blakeley, William J. McKenna, Goetz Graefe: Experiences Building the Open OODB Query Optimizer. SIGMOD Conference 1993: 287-296 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bry89a]
François Bry: Logical Rewritings for Improving the Evaluation of Quantified Queries. MFDBS 1989: 100-116 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bry89b]
François Bry: Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited. SIGMOD Conference 1989: 193-204 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Car86]
John V. Carlis: HAS, a Relational Algebra Operator or Divide is not Enough to Conquer. ICDE 1986: 254-261 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cat96]
R. G. G. Cattell: The Object Database Standard: ODMG-93 (Release 1.2). Morgan Kaufmann 1996
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CKMP97]
...
[CM95a]
...
[CM95b]
Sophie Cluet, Guido Moerkotte: Efficient Evaluation of Aggregates on Bulk Types. DBPL 1995: 8 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cod72]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Dat97]
C. J. Date, Hugh Darwen: A Guide to SQL Standard, 4th Edition. Addison-Wesley 1997, ISBN 0-201-96426-0
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Day87]
Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Day83]
Umeshwar Dayal: Processing Queries with Quantifiers: A Horticultural Approach. PODS 1983: 125-136 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GC95]
Goetz Graefe, Richard L. Cole: Fast Algorithms for Universal Quantification in Large Databases. ACM Trans. Database Syst. 20(2): 187-236(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ger96]
Carsten Andreas Gerlhof: Optimierung von Speicherzugriffskosten in Objektbanken: Clustering und Prefetching. DISDBIS Vol. 18 Infix Verlag, St. Augustin, Germany 1996, ISBN 3-89601-418-8
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GL87]
Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gra93]
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HM97]
Sven Helmer, Guido Moerkotte: Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates. VLDB 1997: 386-395 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HP95]
Ping-Yu Hsu, Douglas Stott Parker Jr.: Improving SQL with Generalized Quantifiers. ICDE 1995: 298-305 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[JK83]
Matthias Jarke, Jürgen Koch: Range Nesting: A Fast Method to Evaluate Quantified Queries. SIGMOD Conference 1983: 196-206 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KM90]
Alfons Kemper, Guido Moerkotte: Advanced Query Processing in Object Bases Using Access Support Relations. VLDB 1990: 290-301 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mai83]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MS93]
Jim Melton, Alan R. Simon: Understanding the New SQL: A Complete Guide. Morgan Kaufmann 1993, ISBN 1-55860-245-3
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mur88]
...
[Nak90]
Ryohei Nakano: Translation with Optimization from Relational Calculus to Relational Algebra Having Aggregate Functions. ACM Trans. Database Syst. 15(4): 518-557(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RBG96]
Sudhir Rao, Antonio Badia, Dirk Van Gucht: Providing Better Support for a Class of Decision Support Queries. SIGMOD Conference 1996: 217-227 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RGL90]
Arnon Rosenthal, César A. Galindo-Legaria: Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins. SIGMOD Conference 1990: 291-299 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RRS91]
Christian Rich, Arnon Rosenthal, Marc H. Scholl: Reducing Duplicate Work in Relational Join(s): A Unified Approach. CISMOD 1993: 87-102 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sha86]
Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SPMK95]
Michael Steinbrunn, Klaus Peithner, Guido Moerkotte, Alfons Kemper: Bypassing Joins in Disjunctive Queries. VLDB 1995: 228-238 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ste95]
Hennie J. Steenhagen: Optimization of Object Query Languages. Ph.D. thesis, University of Twente 1995
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sto96]
Michael Stonebraker, Dorothy Moore: Object-Relational DBMSs: The Next Great Wave. Morgan Kaufmann 1996, ISBN 1-55860-397-2
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[vB91]
...
[WMSB90]
Kyu-Young Whang, Ashok Malhotra, Gary H. Sockut, Luanne M. Burns: Supporting Universal Quantification in a Two-Dimensional Database Query Language. ICDE 1990: 68-75 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:06 2010 by Michael Ley (ley@uni-trier.de)