On estimating block accesses in database organizations
Wo-Shun Luk · Communications of the ACM · 1983
In designing a physical database organization, one almost inevitably encounters the following estimating problem: Given k records to be retrieved oat of a file of n records organized into m blocks, how many of the m blocks have to be accessed?A correct solution to this problem was given by B. Yao.The solution as a function of Y(n, m, k) depends on the assumptions that n, m, and k are nonstochastic, as well as uniform block size.This paper examines the validity of this function when some of the assumptions are not true.