Multi-Attribute Retrieval with Combined Indexes.

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

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

• 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/An4-1 or /cdrom

• 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

Online Edition

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)