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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

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

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/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

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

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

Electronic Edition

From CS Dept., University Trier (Germany)

References

[Ber91]: Elisa Bertino: An Indexing Technique for Object-Oriented Databases. ICDE 1991: 160-170
[BMG93]: José A. Blakeley, William J. McKenna, Goetz Graefe: Experiences Building the Open OODB Query Optimizer. SIGMOD Conference 1993: 287-296
[Cat93]: R. G. G. Cattell: The Object Database Standard: ODMG-93. Morgan Kaufmann 1993, ISBN 1-55860-302-6
[FG94]: Béatrice Finance, Georges Gardarin: A Rule-Based Query Optimizer with Multiple Search Strategies. Data Knowl. Eng. 13(1): 1-29(1994)
[FV94]: ...
[GGT95]: Georges Gardarin, Jean-Robert Gruser, Zhao-Hui Tang: A Cost Model for Clustered Object-Oriented Databases. VLDB 1995: 323-334
[GV92]: Georges Gardarin, Patrick Valduriez: ESQL2: An Object-Oriented SQL with F-Logic Semantics. ICDE 1992: 320-327
[KBZ86]: Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137
[KKS92]: Michael Kifer, Won Kim, Yehoshua Sagiv: Querying Object-Oriented Databases. SIGMOD Conference 1992: 393-402
[KKD89]: Won Kim, Kyung-Chang Kim, Alfred G. Dale: Indexing Techniques for Object-Oriented Databases. Object-Oriented Concepts, Databases, and Applications 1989: 371-394
[KM90]: Alfons Kemper, Guido Moerkotte: Access Support in Object Bases. SIGMOD Conference 1990: 364-374
[KGM91]: Thomas Keller, Goetz Graefe, David Maier: Efficient Assembly of Complex Objects. SIGMOD Conference 1991: 148-157
[Mel93]: ...
[SC89]: Eugene J. Shekita, Michael J. Carey: Performance Enhancement Through Replication in an Object-Oriented DBMS. SIGMOD Conference 1989: 325-336
[Sha86]: Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986)
[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)
[Yao77]: S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977)