Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases

ABSTRACT

It is possible to significantly reduce the average cost of information retrieval from a large shared database by partitioning data items stored within each record into a primary and a secondary record segment. An analytic model, based upon knowledge of data item lengths, transportation costs, and retrieval patterns, is developed to assist an analyst with this assignment problem. The model is generally applicable to environments in which a database resides in secondary storage, and is useful for both uniprogramming and multiprogramming systems. A computationally tractable record design algorithm has been implemented as a Fortran program and applied to numerous problems. Realistic examples are presented which demonstrate a potential for reducing total system cost by more than 65 percent.

REFERENCES

• 1: BALINSKI, M L On a selection problem Manag Sct 17, 3 (March 1970), 230-231
• 2: BENNER, F H On designing generalized file records for management mformat,on systems Proc AFIPS 1967 FJCC, Vol 31, AFIPS Press, Montvale, N J , 1967, pp 291-303
• 3: CAN~I~G, R G Structures for future systems EDP Analyzer 12, 8 (Aug 1974)
• 4: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 5: EISNER, M j Bicntenon mathematical programs Tech Rep 238, Operations Res , Cornell U , Ithaca, N Y ,July 1974
• 6: FORD, L R , AND FULKERSON, D R Flows m Networks Pnnceton U Press, Pnnceton, N.J., 1962
• 7: GARrlNKEL, R S., AND NEMI~AUSER, G.L. Integer Programmmg Wiley, New York, 1972, Ch. 4.
• 8: GEOFFRION, A M Solving bl-cntenon mathematical programs Oper Res 15, 1 (Jan 1967), 39-54
• 9: Bruce Hahn, A new technique for compression and storage of data, Communications of the ACM, v.17 n.8, p.434-436, Aug. 1974 [doi>10.1145/361082.361086]
• 10: HEAeS, H S Storage analysis of a compression coding for document data bases INFOR 10, 1 (Feb 1972), 47-61
• 11: Jeffrey Alan Hoffer, A clustering approach to the generation of subfiles for the design of a computer data base., 1975
• 12: IBb,l CORP latroduct~on to IBM d~rect-access storage dewces and organlzat~ons GD 20-1649, IBM Corp, White Pitons, N Y , 1974
• 13: KENNEDY, S R The use of access frequencies m data base orgamzat~on Ph D Dlss, Dep Operations Res, Cornell U , Ithaca, N Y , 1973
• 14: KING, W F On the Selection of Indices for a Fde Res Rep RJ1341, IBM Res Lab , San Jose, Cahf, Jan 1974
• 15: Vincent Y. Lum , Huei Ling, An optimization problem on the selection of secondary keys, Proceedings of the 1971 26th annual conference, p.349-356, January 1971 [doi>10.1145/800184.810505]
• 16: MAXWELL, W L, AND SEVERANCE, D G Comparison of alternatwes for the representation of data ~tem values m an mformat~on system Proc. Wharton Conf on Res. on Comptrs m Orgamzauons. U. of Pennsylvanm, Phdadelphm, Pa , Oct 1973, pp 121-136

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

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

General Terms:
Economics, Management, Measurement, Performance, Theory