Analysis and performance of inverted data base structures

ABSTRACT

The need to envision and architecture data base systems in a hierarchical level by level framework is stressed. The inverted data base (file) organization is then analyzed, considering implementation oriented aspects. The inverted directory is viewed realistically as another large data base which itself is subjected to inversion. Formulations are derived to estimate average access time (read only) and storage requirements, formalizing the interaction of data base content characteristics, logical complexity of queries, and machine timing and blocking specifications identified as having a first-order effect on performance. The formulations presented are necessary to be used in conjunction with any index selection criteria to determine the optimum set of index keys.

REFERENCES

• 1: Senko, M.E., Altman, E.B., Astrahan, M.M., and Fehder, P.L. Data structures and accessing in data base systems. IBM Sys. J. 12, 1 (1973), 30-93.
• 2: 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]
• 3: Private communications with E.B. Altman, J. Fry, D. Smith and R. Taylor, CODASYL, Storage Definition and Data Translation Task Group, 1973.
• 4: Michael Stonebraker, Retrieval efficiency using combined indices, Proceedings of 1972 ACM-SIGFIDET workshop on Data description, access and control, p.243-256, January 1972 [doi>10.1145/800295.811493]
• 5: King, W.F. On the selection of indices for a file. Proc. IFIP Cong. 74, Stockholm, Sweden, 1974.
• 6: 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]
• 7: Senko, M. E., Lum, B.Y., and Owens, P.J. A File Organization Evaluation Model (FOREM), Proc. IFIP Cong., Edinburgh, 1968.
• 8: 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]
• 9: L. E. Stanfel, Tree Structures for Optimal Searching, Journal of the ACM (JACM), v.17 n.3, p.508-517, July 1970 [doi>10.1145/321592.321601]
• 10: Alfonso F. Cardenas, Evaluation and selection of file organization—a model and system, Communications of the ACM, v.16 n.9, p.540-548, Sept. 1973 [doi>10.1145/362342.362352]
• 11: Cardenas, A.F., and Sagamang, J.P. Doubly-chained tree data base organization--Analysis and design strategies. IBM Res. Lab. Tech. Rep. RJ 1374, San Jose, Calif. Apr. 4, 1974, 56 pages.
• 12: R. G. Casey, Design of tree structures for efficient querying, Communications of the ACM, v.16 n.9, p.549-556, Sept. 1973 [doi>10.1145/362342.362353]
• 13: Robert E. Bleier, Treating hierarchical data structures in the SDC Time-Shared Data Management System (TDMS), Proceedings of the 1967 22nd national conference, p.41-49, January 1967, Washington, D.C., United States [doi>10.1145/800196.805973]
• 14: 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]
• 15: Lefkovitz, D. File Structures for On-line Systems. Spartan Books, New York, 1969.
• 16: Nahouraii, E. Direct-access storage-device simulation. Proc. 1973 Summer Computer Simulation Conf., Montreal, July 17-19. 1973, pp. 172-176.
• 17: Computer System Simulator CSS/II. Program Description and Operations Manual, IBM Pub. SH20-0875-1, Mar. 1971.
• 18: lhrer, F.C. A Technical Description ofSCERT. Comress Inc. Pub., Rockville, Md.
• 19: Davies, C.T. A logical concept for the control and management of data. IBM Rep. AR-0803-00, Syst. Develop. Div., Poughkeepsie, N.Y., 1967.
• 20: Robert Bosak , Richard F. Clippinger , Carey Dobbs , Roy Goldfinger , Renee B. Jasper , William Keating , George Kendrick , Jean E. Sammet, An information algebra: phase 1 report—language structure group of the CODASYL development committee, Communications of the ACM, v.5 n.4, p.190-204, April 1962 [doi>10.1145/366920.366935]
• 21: Wang, C.P., and Wedekind, H.H. An approach for segment synthesis in logical data base design. IBM Res. Lab. Tech. Rep. RJ 1397, San Jose, Calif., Sept. 1974.
• 22: Siler, K.F. A model for the evaluation of large scale data retrieval systems. Proc. 42nd Nat. ORSA Meeting, Atlantic City, N.J., Nov. 1972.
• 23: 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]
• 24: System 2000 Reference Manual, MRI Systems Corp., Austin, Tex., 1973.

INDEX TERMS

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

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

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

Keywords:
data base architecture, data base performance and measurement, information storage and retrieval, inverted file organization, query answering, secondary index organization