Retrieval efficiency using combined indices

ABSTRACT

The problem considered here involves choosing the best set of indices for indexing a file on a secondary storage device where space may be limited. For a general class of queries and a specific index organization, approximations to the expected retrieval time for any choice of indices are developed. Subject to the simplifying assumptions the best selection of indices is obtained for several cases, both where the number of possible lists is constrained and where it is not. The examples indicate that retrieval time is quite sensitive to the choice made.

REFERENCES

• 1: Thomas C. Lowe, The Influence of Data Base Characteristics and Usage on Direct Access File Organization, Journal of the ACM (JACM), v.15 n.4, p.535-548, Oct. 1968 [doi>10.1145/321479.321482]
• 2: V. Y. Lum, Multi-attribute retrieval with combined indexes, Communications of the ACM, v.13 n.11, p.660-665, Nov 1970 [doi>10.1145/362790.362794]
• 3: James K. Mullin, Retrieval—Update speed tradeoffs using combined indices, Communications of the ACM, v.14 n.12, p.775-776, Dec. 1971 [doi>10.1145/362919.362933]
• 4: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 5: Codd, E.F., "A Data Base Sublanguage Founded on the Relational Calculus", Proc. 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control, San Diego.
• 6: Senko, M.E., "Semi-Operational Evaluation of File Modeling Techniques", Information Sciences Department, IBM Research Laboratory, San Jose, February, 1971.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

General Terms:
Theory