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}
}

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

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

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

References

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