ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Multi-Attribute Retrieval with Combined Indexes.

Vincent Y. Lum: Multi-Attribute Retrieval with Combined Indexes. Commun. ACM 13(11): 660-665(1970)
@article{DBLP:journals/cacm/Lum70,
  author    = {Vincent Y. Lum},
  title     = {Multi-Attribute Retrieval with Combined Indexes},
  journal   = {Commun. ACM},
  volume    = {13},
  number    = {11},
  year      = {1970},
  pages     = {660-665},
  ee        = {db/journals/cacm/Lum70.html, http://doi.acm.org/10.1145/362790.362794},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In this paper a file organization scheme designed to replace the use of the popular secondary index filing scheme (or inverted files on secondary key fields) is described. Through the use of redundancy and storing keys (or access numbers of the records) that satisfy different combinations of secondary index values in "buckets", it is possible to retrieve all keys satisfying any input query derived from a subset of fields by a single access to an index file, although each bucket may be used for many combinations of values and a combination of buckets may be required for a given query.

The method which, in its degenerate case, becomes the conventional secondary index filing scheme works similarly but has the following advantages: (1) the elimination of multiple accesses in many cases; (2) the elimination of false drops; (3) the elimination of computer time to perform intersection of key sets each qualified for one secondary index field only; and (4) the avoidance of long strings of keys when an index field appearing in a query has very few possible values. Redundancy, in some cases, is the same as the secondary indexing method. In the general case, trade-off between the number of accesses for query and redundancy exists.

Copyright © 1970 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.


ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition

Citation Page BibTeX

References

[1]
...
[2]
...
[3]
Chacko T. Abraham, Sakti P. Ghosh, Dwijendra K. Ray-Chaudhuri: File Organization Schemes Based on Finite Geometries. Information and Control 12(2): 143-163(1968) BibTeX
[4]
...
[5]
...
[6]
...
[7]
...
[8]
...

Referenced by

  1. Guido Moerkotte: Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing. VLDB 1998: 476-487
  2. Theodore Johnson, Dennis Shasha: Some Approaches to Index Design for Cube Forest. IEEE Data Eng. Bull. 20(1): 27-35(1997)
  3. Chris Clifton, Hector Garcia-Molina, David Bloom: HyperFile: A Data and Query Model for Documents. VLDB J. 4(1): 45-86(1995)
  4. Alfons Kemper, Christoph Kilger, Guido Moerkotte: Function Materialization in Object Bases: Design, Realization, and Evaluation. IEEE Trans. Knowl. Data Eng. 6(4): 587-608(1994)
  5. Guido Moerkotte, Peter C. Lockemann: Reactive Consistency Control In Deductive Databases. ACM Trans. Database Syst. 16(4): 670-702(1991)
  6. Chris Clifton, Hector Garcia-Molina: Indexing in a Hypertext Database. VLDB 1990: 36-49
  7. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  8. Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984)
  9. Douglas Comer: The Difficulty of Optimum Index Selection. ACM Trans. Database Syst. 3(4): 440-445(1978)
  10. Mario Schkolnick: A Survey of Physical Database Design Methodology and Techniques. VLDB 1978: 474-487
  11. Henry D. Anderson, P. Bruce Berra: Minimum Cost Selection of Secondary Indexes for Formatted Files. ACM Trans. Database Syst. 2(1): 68-90(1977)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
CACM, 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:51:45 2009