An urn model with applications to database performance evaluation

doi:10.1016/S0305-0548(96)00063-9

1997-04-01

PRE

Rahul Simha *

A. Majumdar

DOI：10.1016/S0305-0548(96)00063-9

原文链接

原文求助

摘要

En 中文

We 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. We 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, we 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, we 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. (C) 1997 Elsevier Science Ltd.

Keyword:

ESTIMATING BLOCK ACCESSES

ORGANIZATIONS

NUMBER