A stochastic evaluation model for database organizations in data retrieval systems

ABSTRACT

Experimental work in the valuation of large scale data retrieval systems has been scarce due to its difficulty and prohibitive cost. This paper discusses a simulation model of a data retrieval system which has the effect of significantly reducing the cost of experimentation and enabling research never attempted before. The model is designed to estimate the retrieval workload of alternative data retrieval systems. These data retrieval systems can be organized under several database organizations, including inverted list, threaded list, and cellular list organizations and hybrid combinations of these systems. Effectiveness of the methodology is demonstrated by using the model to study the effect of database organizations in data retrieval systems. In particular, the impact of query complexity is analyzed.

REFERENCES

• 1: ADABAS, distributed by Software AG, Reston, Va.
• 2: Aiyer, A.K. The CIMARON System: Modular Programs for the Organization and Search of Large Files. Institute of Library Research, U. of California, Berkeley, 1971.
• 3: Bleier, R.E., and Vorhaus, A.H. File organization in the SDC time-shared data management system (TDMS). TDMS Project, Systems Development Corp. (now known as CDMS), SP-2750, Aug. 1967.
• 4: 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]
• 5: Codasyl Systems Committee. A survey of generalized data base management systems. May 1969.
• 6: 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]
• 7: 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]
• 8: 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]
• 9: IBM Corp. Introduction to IBM System/360 Direct Access Storage Devices and Organization Methods, IBM Corp, White Plains, C20-1649-2, Oct., 1967.
• 10: Lefkovitz, D. File StrueturesJor On-Line Systems. Spartan Books, New York 1969.
• 11: Lowe, T.C. Design principles for an on-line information retrieval system. Ph.D. Diss., U. of Pennsylvania, Philadelphia, Penn., 1966.
• 12: 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]
• 13: Elliott Mendelson, Introduction to mathematical logic (3rd ed.), Wadsworth Publ. Co., Belmont, CA, 1987
• 14: Minker, J., and Sable, J. File organization and data management. In Annual Review of Information Science and Technology, C. Cradra (Ed.), Wiley, New York, 1967, pp. 123-160.
• 15: A. J. Perlis , Charles Thornton, Symbol manipulation by threaded lists, Communications of the ACM, v.3 n.4, p.195-204, April 1960 [doi>10.1145/367177.367202]
• 16: Prywes, N.S., and Gray, H.J. The Multi-list for real-time storage and retrieval. Proc. IFIP Congress 62, North-Holland Pub. Co., Amsterdam, 1962, pp. 273-278.
• 17: Prywes, N.S., et al. The multi-list type associative memory. In Proc. Symp. on Gigacycle Computing Systems, AIEE Publications No. S-136, Jan. 1962, pp.87-107.
• 18: Raven, N. In Proc. 3rd Annual National Colloquium on Information Retrieval, Philadelphia, Penn., May 1966.
• 19: Senko, M.E., et al. A file organization evaluation model. In Proc. IFIP Congress 68, North-Holland Pub. Co., Amsterdam, 1968.
• 20: Senko, M.E., et al. File Design Handbook. Information Sci. Dep., IBM Research Lab., San Jose, Calif., Nov. 1969.
• 21: Senko, M.E., et al. Semi-operational evaluation of file modeling techniques. Information Sci. Dep. IBM Research Lab., San Jose, Calif., Feb. 1971.
• 22: Kenneth F. Siler, A model for the evaluation of large scale data retrieval systems, Proceedings of the 7th conference on Winter simulation, p.259-274, January 14-16, 1974, Washington, DC [doi>10.1145/800287.811187]
• 23: System 2000, distributed by MRI Systems, Inc., Austin, Texas.
• 24: J. Weizenbaum, Knotted list structures, Communications of the ACM, v.5 n.3, p.161-165, March 1962 [doi>10.1145/366862.366897]
• 25: Zipf, G.K. Humall Behavior and the Principle of Least Effort. Addison-Wesley, Cambridge, Mass., 1949.

INDEX TERMS

Keywords:
Monte Carlo simulation, cellular list, database architecture, database organizations, database performance and evaluation, information retrieval, invented list, query complexity, stochastic model, threaded list