The Difficulty of Optimum Index Selection.

Douglas Comer: The Difficulty of Optimum Index Selection. ACM Trans. Database Syst. 3(4): 440-445(1978)

@article{DBLP:journals/tods/Comer78,
  author    = {Douglas Comer},
  title     = {The Difficulty of Optimum Index Selection},
  journal   = {ACM Trans. Database Syst.},
  volume    = {3},
  number    = {4},
  year      = {1978},
  pages     = {440-445},
  ee        = {http://doi.acm.org/10.1145/320289.320296, db/journals/tods/Comer78.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Given a file on a secondary store in which each record has several attributes, it is usually advantageous to build an index mechanism to decrease the cost of conducting transactions to the file. The problem of selecting attributes over which to index has been studied in the context of various storage structures and access assumptions. One algorithm to make an optimum index selection requires 2k steps in the worst case, where k is the number of attributes in the file. We examine the question of whether a more efficient algorithm might exist and show that even under a simple cost criterion the problem is computationally difficult in a precise sense. Our results extend directly to other related problems where the cost of the index depends on fixed values which are assigned to each attribute. Some practical implications are discussed.

Copyright © 1978 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" 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/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" 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/aDVD2 or /dvd

BibTeX

References

[1]: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX
[2]: ...
[3]: Richard G. Casey: Design of Tree Structures for Efficient Querying. Commun. ACM 16(9): 549-556(1973) BibTeX
[4]: E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[5]: ...
[6]: ...
[7]: Vincent Y. Lum: Multi-Attribute Retrieval with Combined Indexes. Commun. ACM 13(11): 660-665(1970) BibTeX
[8]: ...
[9]: ...
[10]: Mario Schkolnick: The Optimal Selection of Secondary Indices for Files. Inf. Syst. 1(4): 141-146(1975) BibTeX
[11]: ...

Referenced by

Alberto Caprara, Matteo Fischetti, Dario Maio: Exact and Approximate Algorithms for the Index Selection Problem in Physical Database Design. IEEE Trans. Knowl. Data Eng. 7(6): 955-967(1995)
Eric Hughes, Marianne Winslett: The Index Suggestion Problem for Object Database Applications. CIKM 1995: 50-57
Pai-Cheng Chu: Estimating Block Selectivities for Physical Database Design. IEEE Trans. Knowl. Data Eng. 4(1): 89-98(1992)
Timos K. Sellis, Chih-Chen Lin: A Geometric Approach to Indexing Large Rule Bases. EDBT 1992: 405-420
Steve Rozen, Dennis Shasha: A Framework for Automating Physical Database Design. VLDB 1991: 401-411
Elena Barcucci, Alessandra Chiuderi, Renzo Pinzani, M. Cecilia Verri: Index Selection in Relational Databases. MFDBS 1989: 24-36
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents
Sheldon J. Finkelstein, Mario Schkolnick, Paolo Tiberio: Physical Database Design for Relational Databases. ACM Trans. Database Syst. 13(1): 91-128(1988)
Jane Fedorowicz: Database Performance Evaluation in an Indexed File Environment. ACM Trans. Database Syst. 12(1): 85-110(1987)
Kazimierz Subieta, Wiktor Rzeczkowski: Query Optimization by Stored Queries. VLDB 1987: 369-380
Pasquale Rullo, Domenico Saccà, Qinsi Zhong: An Approximation Algorithm for the Physical Access Path Selection in the CODASYL Environment. ICDE 1986: 200-207
M. Al-Suwaiyel, Ellis Horowitz: Algorithms for Trie Compaction. ACM Trans. Database Syst. 9(2): 243-263(1984)
Won Kim: Relational Database Systems. ACM Comput. Surv. 11(3): 187-211(1979)
Mario Schkolnick: A Survey of Physical Database Design Methodology and Techniques. VLDB 1978: 474-487

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]