ACM SIGMOD Anthology VLDB dblp.uni-trier.de

On Index Selection Schemes for Nested Object Hierarchies.

Sudarshan S. Chawathe, Ming-Syan Chen, Philip S. Yu: On Index Selection Schemes for Nested Object Hierarchies. VLDB 1994: 331-341
@inproceedings{DBLP:conf/vldb/ChawatheCY94,
  author    = {Sudarshan S. Chawathe and
               Ming-Syan Chen and
               Philip S. Yu},
  editor    = {Jorge B. Bocca and
               Matthias Jarke and
               Carlo Zaniolo},
  title     = {On Index Selection Schemes for Nested Object Hierarchies},
  booktitle = {VLDB'94, Proceedings of 20th International Conference on Very
               Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile},
  publisher = {Morgan Kaufmann},
  year      = {1994},
  isbn      = {1-55860-153-8},
  pages     = {331-341},
  ee        = {db/conf/vldb/vldb94-331.html},
  crossref  = {DBLP:conf/vldb/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In this paper we address the problem of devising a set of indexes for a nested object hierarchy in an object-oriented database to improve the overall system performance. It is noted that the effects of two indexes could be entangled in that the inclusion of one index might affect the benefit achievable by the other index. Such a phenomenon is termed index interaction. Clearly, the effect of index interaction needs to be taken into consideration when a set of indexes is being built. The index selection problem is first formulated and four index selection algorithms are evaluated via simulation. The effects of different objective functions, which guide the search in the index selection algorithms, are also investigated. It is shown by simulation results that the greedy algorithm which is devised in light of the phenomenon of index interaction performs fairly well in most cases. Sensitivity analysis for various database parameters is conducted.

Copyright © 1994 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 ... BibTeX

Printed Edition

Jorge B. Bocca, Matthias Jarke, Carlo Zaniolo (Eds.): VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile. Morgan Kaufmann 1994, ISBN 1-55860-153-8
Contents BibTeX

References

[1]
Elisa Bertino: Optimization of Queries using Nested Indices. EDBT 1990: 44-59 BibTeX
[2]
Elisa Bertino, C. Guglielmina: Optimization of Object-Oriented Queries Using Path Indices. RIDE-TQP 1992: 140-149 BibTeX
[3]
Elisa Bertino, Won Kim: Indexing Techniques for Queries on Nested Objects. IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989) BibTeX
[4]
Michael J. Carey, David J. DeWitt, Jeffrey F. Naughton: The oo7 Benchmark. SIGMOD Conference 1993: 12-21 BibTeX
[5]
R. G. G. Cattell: Object Data Management: Object-Oriented and Extended Relational Database Systems. Addison-Wesley 1991, ISBN 0-201-53092-9
BibTeX
[6]
Sunil Choenni, Elisa Bertino, Henk M. Blanken, Thiel Chang: On the Selection of Optimal Index Configuration in OO Databases. ICDE 1994: 526-537 BibTeX
[7]
Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984) BibTeX
[8]
...
[9]
Alfons Kemper, Guido Moerkotte: Access Support Relations: An Indexing Method for Object Bases. Inf. Syst. 17(2): 117-145(1992) BibTeX
[10]
Kyung-Chang Kim, Won Kim, Alfred G. Dale: Cyclic Query Processing in Object-Oriented Databases. ICDE 1989: 564-571 BibTeX
[11]
...
[12]
Chee Chin Low, Hongjun Lu, Beng Chin Ooi, Jiawei Han: Efficient Access Methods in Deductive and Object-Oriented Databases. DOOD 1991: 68-84 BibTeX
[13]
David Maier, Jacob Stein: Indexing in an Object-Oriented DBMS. OODBS 1986: 171-182 BibTeX
[14]
David Maier, Jacob Stein, Allen Otis, Alan Purdy: Development of an Object-Oriented DBMS. OOPSLA 1986: 472-482 BibTeX
[15]
...
[16]
Jeffrey D. Ullman: A Comparison between Deductive and Object-Oriented Database Systems. DOOD 1991: 263-277 BibTeX

Referenced by

  1. Elisa Bertino, Paola Foscoli: On Modeling Cost Functions for Object-Oriented Databases. IEEE Trans. Knowl. Data Eng. 9(3): 500-508(1997)
  2. Roy Goldman, Jennifer Widom: DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases. VLDB 1997: 436-445
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:46:00 2009