Performance analysis of three related assignment problems

ABSTRACT

The relative placement of records in a database has a significant impact on the overall system performance. In this paper we study three related assignment problems. They are (1) the assignment of records to devices so as to minimize the expected completion time and to maximize the expected utilization of the devices, (2) the assignment of records to pages or blocks in secondary memory so as to minimize the number of blocks to be accessed, and (3) the analysis of the performance of a hashing scheme under the assumption that the record-to-bucket probability varies from one bucket to another. The solutions to these problems are obtained by studying an occupancy problem. In each case, an optimal solution is obtained.

REFERENCES

• 1: Feller, W., An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed., John Wiley and Sons, New York, 1968.
• 2: Moran, P.A.P., An Introduction to Probability Theory, Clarendon Press, Oxford, 1968, (pp. 31--36).
• 3: Pfeiffer, P.E. and Shum, D.A., Introduction to Applied Probability Theory, Academic Press, New York, 1973, (pp. 25--28).
• 4: Harris, B., Theory of Probability, Addison-Wesley, Mass., 1968, (pp. 35--36).
• 5: James Martin, Computer Database Organization, 2nd Ed, Prentice Hall PTR, Upper Saddle River, NJ, 1977
• 6: Robert Epstein , Michael Stonebraker , Eugene Wong, Distributed query processing in a relational data base system, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509292]
• 7: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 8: Feller, W., An Introduction to Probability Theory and Its Applications, Vol. 2, 2nd ed., John Wiley and Sons, New York, 1971, (pp. 155).
• 9: James B. Rothnie, Jr. , Tomas Lozano, Attribute based file organization in a paged memory environment, Communications of the ACM, v.17 n.2, p.63-69, Feb. 1974 [doi>10.1145/360827.360831]
• 10: Yue, P.C. and Wong, C.K., "Storage Cost Considerations in Secondary Index Selection," Int. J. Cptr. Inform. Sci. 4, 4 (1975), pp. 307--327.
• 11: Alfonso F. Cárdenas, Analysis and performance of inverted data base structures, Communications of the ACM, v.18 n.5, p.253-263, May 1975 [doi>10.1145/360762.360766]
• 12: Chan, A., "Index Selection in a Self Adaptive Relationsl Data Base Management System," M.Sc. Thesis, M.I.T., Mass. Sept. 1976.
• 13: Kenneth F. Siler, A stochastic evaluation model for database organizations in data retrieval systems, Communications of the ACM, v.19 n.2, p.84-95, Feb. 1976 [doi>10.1145/359997.360010]
• 14: S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977 [doi>10.1145/359461.359475]
• 15: Dennis Gordon Severance, Some generalized modeling structures for use in design of file organizations., 1972
• 16: S. B. Yao, An attribute based model for database access cost analysis, ACM Transactions on Database Systems (TODS), v.2 n.1, p.45-67, March 1977 [doi>10.1145/320521.320535]
• 17: Handley, G., Nonlinear and Linear Programming, Addison-Wesley, Mass., 1964 (pp. 87--91).
• 18: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 19: Ronald Rivest, On self-organizing sequential search heuristics, Communications of the ACM, v.19 n.2, p.63-67, Feb. 1976 [doi>10.1145/359997.360000]
• 20: Peterson, W.W., "Addressing for Random Access Storage," IBM.J. Res. Devel., 1, 2 (Apr. 1957), pp. 130--146.
• 21: Robert Morris, Scatter storage techniques, Communications of the ACM, v.11 n.1, p.38-44, Jan. 1968 [doi>10.1145/362851.362882]
• 22: J. D. Ullman, A Note on the Efficiency of Hashing Functions, Journal of the ACM (JACM), v.19 n.3, p.569-575, July 1972 [doi>10.1145/321707.321722]
• 23: Dennis G. Severance, Identifier Search Mechanisms: A Survey and Generalized Model, ACM Computing Surveys (CSUR), v.6 n.3, p.175-194, Sept. 1974 [doi>10.1145/356631.356633]
• 24: V. Y. Lum , P. S. T. Yuen , M. Dodd, Key-to-address transform techniques: a fundamental performance study on large existing formatted files, Communications of the ACM, v.14 n.4, p.228-239, April 1971 [doi>10.1145/362575.362578]
• 25: L. R. Johnson, An indirect chaining method for addressing on secondary keys, Communications of the ACM, v.4 n.5, p.218-222, May 1961 [doi>10.1145/366532.366540]
• 26: Owen, D.B. and Steck, G.P., "Moments of Order Statistics From the Equivorrelated Multivariate Normal Distribution," Annals of Math. Statistics, Vol. 33, 1962, pp. 1286--1291.
• 27: Paul J. Sadowski , S. A. Schuster, Exploiting parallelism in a Relational Associative Processor, Proceedings of the fourth workshop on Computer architecture for non-numeric processing, p.99-109, August 01-04, 1978, Blue Mountain Lake, New York, United States [doi>10.1145/800128.804174]
• 28: E. A. Ozkarahan , S. A. Schuster , K. C. Sevcik, Performance evaluation of a relational associative processor, ACM Transactions on Database Systems (TODS), v.2 n.2, p.175-195, June 1977 [doi>10.1145/320544.320553]
• 29: P. C. Yue , C. K. Wong, On the Optimality of the Probability Ranking Scheme in Storage Applications, Journal of the ACM (JACM), v.20 n.4, p.624-633, Oct. 1973 [doi>10.1145/321784.321790]
• 30: Fagin, R., "Asymptotic Miss Ratio Over Independent References," J.CSS., 14, 1977, pp. 222--250.
• 31: Ronald Fagin , Malcolm C. Easton, The independence of miss ratio on page size, Journal of the ACM (JACM), v.23 n.1, p.128-146, Jan. 1976 [doi>10.1145/321921.321935]