Evaluation and selection of file organization—a model and system

ABSTRACT

This work first discusses the factors that affect file (data base) organization performance, an elusive subject, and then presents a methodology, a model and a programmed system to estimate primarily total storage costs and average access time of several file organizations, given a specific data base, query characterization and device-related specifications. Based on these estimates, an appropriate file structure may be selected for the specific situation. The system is a convenient tool to study file structures and to facilitate as much as possible the process of data base structure design and evaluation.

REFERENCES

• 1: Codasyl Data Base Task Group. Codasyl data base task group report. Oct. 1969.
• 2: Codasyl Systems Committee. A survey of generalized data base management systems. May 1969.
• 3: Codasyl Systems Committee. Feature analysis of generalized data basic management systems. Apr. 1971.
• 4: CORPORATE Codasyl Systems Committee, Introduction to “feature analysis of generalized data base management systems”, Communications of the ACM, v.14 n.5, p.308-318, May 1971 [doi>10.1145/362588.362590]
• 5: Lefkovitz, D., File Structures for On-Line Systems, Spartan Press, New York, 1969.
• 6: Senko, M.E., et al. File Design Handbook. Information Sciences Dept. IBM Res. Lab., San Jose, Calif., Nov. 1969.
• 7: Minker, J., and Sable, J. File organization and data management. In Annual Review of Information Science and Technology, Carlos Cradra (Ed.), Wiley, New York, 1967, pp. 123-160.
• 8: Senko, M.E., et al. A file organization evaluation model. In Proc. IFIP Congress 68, Edinburgh, Scotland, 1968.
• 9: Senko, M.E., et al. Semi-operational evaluation of file modeling techniques. Information Sciences Dept. IBM Res. Lab., San Jose, Calif., Feb. 1971.
• 10: Lum, V.Y., and P.J. Owens. File organization and evaluation modeling systems. Users guides, Information Sciences Dept. IBM Res. Lab., San Jose, Calif., Feb. 1971.
• 11: Lure, V.Y., et al. Analysis of a complex data management access method by simulation modeling. Proc. AFIPS 1970 FJCC, Vol. 37, AFIPS Press, Montvale, N.J., pp. 211-222.
• 12: 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]
• 13: Ghosh, S.P., and Ganguly, A.K. Comparison of techniques for adding and organizing records in the independent overflow area of ISAM. IBM Report RJ602, IBM Res. Lab., San Jose, Calif., Aug. 1969.
• 14: Kenneth Francis Siler, A stochastic model for the evaluation of large scale data retrieval systems: an analysis of data base inversion and key truncation, 1971
• 15: Head, R.V. Automated systems analysis. Datamation (Aug. 15, 1971), 22-24.
• 16: Computer System Simulator II (CSS/II). Program Description and Operations Manual, IBM Pub. SH20-0875-1, Mar. 1971.
• 17: Data processing planning via simulation. EDP Analyzer6, 4 (1968), 1-13.
• 18: Teichroew, D., and Sayani, H. Automation of system building. Datamation (Aug. 15, 1971), 22-24.
• 19: George G. Dodd, Elements of Data Management Systems, ACM Computing Surveys (CSUR), v.1 n.2, p.117-133, June 1969 [doi>10.1145/356546.356550]
• 20: Edward H. Sussenguth, Jr., Use of tree structures for processing files, Communications of the ACM, v.6 n.5, p.272-279, May 1963 [doi>10.1145/366552.366600]
• 21: Donald Ervin Knuth, The Art of Computer Programming, 2nd Ed. (Addison-Wesley Series in Computer Science and Information, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 22: Yale N. Patt, Variable length tree structures having minimum average search time, Communications of the ACM, v.12 n.2, p.72-76, Feb. 1969 [doi>10.1145/362848.362853]
• 23: IBM System 360 Operating System, PL/I Programmer's Guide. Managing data. Form C28-6594--4, pp. 51-77.
• 24: IBM System 360, PL/1 Reference Manual. Input and output. Form C28-820-1, pp. 89-105; 117-124.
• 25: Weinberg, G.M. PL/1 Programming: A Manual of Style. McGraw-Hill, New York, 1970.
• 26: Sagamang, J.P. Automatic selection of storage structure in a generalized data management system. M.S. Thesis, Computer Science Dept., U. California, Los Angeles, Calif., June 1971.
• 27: Workshop session with Senko, M., Wang, C.P., Lum, V., Ghosh, S., et al., and Siler, K., and Kohn, L., Information Sciences Dept., IBM Res. Lab., San Jose, Calif., Feb. 25, 1972.
• 28: 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]

INDEX TERMS

Keywords:
access time, data base, data base analysis, data management, file management, file organization, file organization model, file organization performance, file structure design, file structures, secondary index organization, simulation, storage requirement