An urn model with applications to database performance evaluation

The authors consider two problems in distributed databases that have identical probabilistic structure, both of which have received significant attention in the literature. One is the problem of characterizing the number of distinct sites accessed by transactions in a distributed database and the other is the problem of determining the number of block accesses in a relation. They focus in particular on obtaining the distribution of this number when accesses are generated randomly. Previously published research has derived the mean number of sites or blocks accessed under some assumptions about the system parameters. The results presented in this article generalize this work in several ways. First, the authors weaken the standard uniformity assumption to allow for a transaction accessing a random number of distinct sites or blocks and also consider a non-uniform access pattern in which one site or block (a ‘hotspot’) is accessed more frequently than others. Second, they compute not only the mean and variance but also the entire distribution of the number of sites (blocks) accessed, a measure found useful in the performance analysis of distributed databases. Additional generalizations are discussed in the article.