ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases.

Georges Gardarin, Jean-Robert Gruser, Zhao-Hui Tang: Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases. VLDB 1996: 390-401
@inproceedings{DBLP:conf/vldb/GardarinGT96,
  author    = {Georges Gardarin and
               Jean-Robert Gruser and
               Zhao-Hui Tang},
  editor    = {T. M. Vijayaraman and
               Alejandro P. Buchmann and
               C. Mohan and
               Nandlal L. Sarda},
  title     = {Cost-based Selection of Path Expression Processing Algorithms
               in Object-Oriented Databases},
  booktitle = {VLDB'96, Proceedings of 22th International Conference on Very
               Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India},
  publisher = {Morgan Kaufmann},
  year      = {1996},
  isbn      = {1-55860-382-4},
  pages     = {390-401},
  ee        = {db/conf/vldb/GardarinGT96.html},
  crossref  = {DBLP:conf/vldb/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

An object query can include a path expression to traverse a number of related collections. The order of collection traversals given by the path expression may not be the most efficient to process the query. This generates a critical problem for object query optimizer to select the best execution plan. This paper studies the different algorithms to process path expressions with predicates, including depth first navigation, forward and reverse joins. Using a cost model, it then compares their performances in different cases, according to memory size, selectivity of predicates, fan out between collections, etc.. It also presents a heuristic-based algorithm to find profitable n-ary operators for traversing collections, thus reducing the search space of query plans to process a query with a qualified path expression. An implementation based on the O2 system demonstrates the validity of the results.

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

T. M. Vijayaraman, Alejandro P. Buchmann, C. Mohan, Nandlal L. Sarda (Eds.): VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India. Morgan Kaufmann 1996, ISBN 1-55860-382-4
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Electronic Edition

References

[Ber91]
Elisa Bertino: An Indexing Technique for Object-Oriented Databases. ICDE 1991: 160-170 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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
[Cat93]
R. G. G. Cattell: The Object Database Standard: ODMG-93. Morgan Kaufmann 1993, ISBN 1-55860-302-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FG94]
Béatrice Finance, Georges Gardarin: A Rule-Based Query Optimizer with Multiple Search Strategies. Data Knowl. Eng. 13(1): 1-29(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FV94]
...
[GGT95]
Georges Gardarin, Jean-Robert Gruser, Zhao-Hui Tang: A Cost Model for Clustered Object-Oriented Databases. VLDB 1995: 323-334 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GV92]
Georges Gardarin, Patrick Valduriez: ESQL2: An Object-Oriented SQL with F-Logic Semantics. ICDE 1992: 320-327 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KBZ86]
Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KKS92]
Michael Kifer, Won Kim, Yehoshua Sagiv: Querying Object-Oriented Databases. SIGMOD Conference 1992: 393-402 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KKD89]
Won Kim, Kyung-Chang Kim, Alfred G. Dale: Indexing Techniques for Object-Oriented Databases. Object-Oriented Concepts, Databases, and Applications 1989: 371-394 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KM90]
Alfons Kemper, Guido Moerkotte: Access Support in Object Bases. SIGMOD Conference 1990: 364-374 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KGM91]
Thomas Keller, Goetz Graefe, David Maier: Efficient Assembly of Complex Objects. SIGMOD Conference 1991: 148-157 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mel93]
...
[SC89]
Eugene J. Shekita, Michael J. Carey: Performance Enhancement Through Replication in an Object-Oriented DBMS. SIGMOD Conference 1989: 325-336 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
[TL91]
Kian-Lee Tan, Hongjun Lu: A Note on the Strategy Space of Multiway Join Query Optimization Problem in Parallel Systems. SIGMOD Record 20(4): 81-82(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Yao77]
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Mon Mar 15 03:55:57 2010 by Michael Ley (ley@uni-trier.de)