The distribution of granule accesses made by database transactions

ABSTRACT

The problem of characterizing the number of granules (or blocks) accessed by a transaction is important in modeling the performance of database management systems and other applications. Different expressions for this quantity have appeared in the literature under different probabilistic assumptions. These expressions along with one new result are presented with a uniform notation and a clear statement of the assumptions underlying each. The partial order relating the predictions of the expected number of granules accessed is presented.

REFERENCES

• 1: 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]
• 2: Merett, T.H., and Otoo, E. Distribution models of relations. Proc. 5th Conf. Very Large Data Bases, Rio de Janeiro, 1979.
• 3: Ries, D. The effect of concurrency control on database management system performance. Ph.D Dissertation, Computer Science Department, University of California, Berkeley, Apr. 1979.
• 4: Piordan, J. An Introduction to Combinatorial Analysis. Wiley, New York, 1958.
• 5: D. Potier , Ph. Leblanc, Analysis of locking policies in database management systems, Communications of the ACM, v.23 n.10, p.584-593, Oct. 1980 [doi>10.1145/359015.359021]
• 6: 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]
• 7: 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]

INDEX TERMS

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

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

General Terms:
Design, Performance

Keywords:
database, database locking granularity, database performance and measurement, database transaction behavior