A record and file partitioning model

ABSTRACT

One of the main objectives in the design of a file system is the reduction of storage and data transfer costs. This paper presents a model in which several requests access the file system, and each request requires information from one or more variable length data-items. The probabilities of access and the distribution of each data-item's length are assumed to be known, and to be mutually independent. The file system uses one or more storage devices, and each record may be partitioned into subrecords that are stored on different devices. One of the subrecords is designated as the primary record; when a request for a record is made, the primary record is first accessed, and other sub-records are accessed only if the pertinent information is not stored in the primary record. The model that is presented in this paper, both as a nonlinear programming model and a mixed integer programming model, is a very general one; several types of file systems may be derived from it by an appropriate selection of its parameters. This model has already been used in the optimization of library routines' storage at a large scale operating system.

REFERENCES

• 1: Babad, J.M. A record and file partitioning model. Rep. No. 7358, Center for Mathematical Research in Business and Econonomics, U. of Chicago, Chicago, I11., Dec. 1973.
• 2: Babad, J.M., Balachandran, V., and Stohr, E.A. Management of program storage in computers. Management Sei. (to appear).
• 3: Benner, F.J. On designing generalized file records for management information systems. Proc. AFIPS 1967 FJCC, AFIPS Press, Montvale, N.J., pp. 291-303.
• 4: Day, R.H. On optimal extracting from a multiple file data storage system: an application of integer programming. Operations Res. 13 (1965), 482-494.
• 5: Hoffer, J.A. An integer programming formulation of computer data base design problems. Tech. Rep. No. 1-74, Dep. Managerial Studies, School of Management, Case Western Reserve U., Cleveland, Ohio, Oct. 1974.
• 6: Jeffrey Alan Hoffer, A clustering approach to the generation of subfiles for the design of a computer data base., 1975
• 7: Kennedy, S.R. A file partition model. Information Sci. Tech. Rep. No. 2, Cal. Tech., Pasadena, Calif., 1972.
• 8: Maxwell, W.L., and Severance, D.G. Comparison of alternatives for the representation of data item values in an information system. Tech. Rep. No. 199, Dep. Operations Res., Cornell U., Ithaca, N.Y., Sept. 1973.
• 9: OLle, T.W. Data structures and storage structures for generalized file processing. Proc. FILE 68, Int. Seminar on File Organization, Copenhagen, 1968, pp. 285-294.
• 10: Seppala, Y. Definition of extraction files and their optimization by zero-one programming. BIT 7, 3 (1967), 206-215.
• 11: Dennis Gordon Severance, Some generalized modeling structures for use in design of file organizations., 1972
• 12: H. E. Thiess, System optimization: Mathematical programming techniques for optimal computer use, Proceedings of the 1965 20th national conference, p.501-512, August 24-26, 1965, Cleveland, Ohio, United States [doi>10.1145/800197.806071]

INDEX TERMS

Keywords:
file design, file partitioning, file system, record partitioning