ACM SIGMOD Anthology TODS dblp.uni-trier.de

Minimum Cost Selection of Secondary Indexes for Formatted Files.

Henry D. Anderson, P. Bruce Berra: Minimum Cost Selection of Secondary Indexes for Formatted Files. ACM Trans. Database Syst. 2(1): 68-90(1977)
@article{DBLP:journals/tods/AndersonB77,
  author    = {Henry D. Anderson and
               P. Bruce Berra},
  title     = {Minimum Cost Selection of Secondary Indexes for Formatted Files},
  journal   = {ACM Trans. Database Syst.},
  volume    = {2},
  number    = {1},
  year      = {1977},
  pages     = {68-90},
  ee        = {http://doi.acm.org/10.1145/320521.320537, db/journals/tods/AndersonB77.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Secondary indexes are often used in database management systems for secondary key retrieval. Although their use can improve retrieval time significantly, the cost of index maintenance and storage increases the overhead of the file processing application. The optimal set of indexed secondary keys for a particular application depends on a number of application dependent factors. In this paper a cost function is developed for the evaluation of candidate indexing choices and applied to the optimization of index selection. Factors accounted for include file size, the relative rates of retrieval and maintenance and the distribution of retrieval and maintenance over the candidate keys, index structure, and system charging rates. Among the results demonstrated are the increased effectiveness of secondary indexes for large files, the effect of the relative rates of retrieval and maintenance, the greater cost of allowing for arbitrarily formulated queries, and the impact on cost of the use of different index structures.

Copyright © 1977 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 ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
...
[2]
...
[3]
Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975) BibTeX
[4]
...
[5]
...
[6]
...
[7]
...
[8]
...
[9]
...
[10]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[11]
Thomas C. Lowe: The Influence of Data Base Characteristics and Usage on Direct Access File Organization. J. ACM 15(4): 535-548(1968) BibTeX
[12]
...
[13]
Vincent Y. Lum: Multi-Attribute Retrieval with Combined Indexes. Commun. ACM 13(11): 660-665(1970) BibTeX
[14]
Michael Stonebraker: Retrieval Efficiency Using Combined Indexes. SIGFIDET Workshop 1972: 243-256 BibTeX
[15]
...

Referenced by

  1. 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)
  2. Eric Hughes, Marianne Winslett: The Index Suggestion Problem for Object Database Applications. CIKM 1995: 50-57
  3. Pai-Cheng Chu: Estimating Block Selectivities for Physical Database Design. IEEE Trans. Knowl. Data Eng. 4(1): 89-98(1992)
  4. Henk M. Blanken, Alle IJbema, Paul Meek, Bert van den Akker: The Generalized Grid File: Description and Performance Aspects. ICDE 1990: 380-388
  5. Yannis Manolopoulos, John G. Kollias: Performance of a Two-Headed Disk System when Serving Database Queries Under the Scan Policy. ACM Trans. Database Syst. 14(3): 425-442(1989)
  6. Elena Barcucci, Alessandra Chiuderi, Renzo Pinzani, M. Cecilia Verri: Index Selection in Relational Databases. MFDBS 1989: 24-36
  7. Sheldon J. Finkelstein, Mario Schkolnick, Paolo Tiberio: Physical Database Design for Relational Databases. ACM Trans. Database Syst. 13(1): 91-128(1988)
  8. Mario Schkolnick, Paolo Tiberio: Estimating the Cost of Updates in a Relational Database. ACM Trans. Database Syst. 10(2): 163-179(1985)
  9. Salvatore T. March, Gary D. Scudder: On the Selection of Efficient Record Segmentations and Backup Strategies for Large Shared Databases. ACM Trans. Database Syst. 9(3): 409-438(1984)
  10. Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984)
  11. Stanley Y. W. Su, Shamkant B. Navathe, Don S. Batory: Logical and Physical Modeling of Statistical Scientific Databases. SSDBM 1983: 251-263
  12. Nick Roussopoulos: View Indexing in Relational Databases. ACM Trans. Database Syst. 7(2): 258-290(1982)
  13. Don S. Batory, C. C. Gotlieb: A Unifying Model of Physical Databases. ACM Trans. Database Syst. 7(4): 509-539(1982)
  14. Kenneth C. Sevcik: Data Base System Performance Prediction Using an Analytical Model (Invited Paper). VLDB 1981: 182-198
  15. Kjell Karlsson: Reduced Cover-Trees and their Application in the Sabre Access Path Model. VLDB 1981: 345-353
  16. Mario Schkolnick: A Survey of Physical Database Design Methodology and Techniques. VLDB 1978: 474-487
  17. Salvatore T. March, Dennis G. Severance: A Mathematical Modeling Approach to the Automatic Selection of Database Designs. SIGMOD Conference 1978: 52-65
  18. Peter P. Chen, S. Bing Yao: Design and Performance Tools for Data Base Systems. VLDB 1977: 3-15
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:36 2008