PROBABILISTIC ANALYSIS OF TRANSACTION BLOCKING UNDER ARBITRARY DATA ACCESS DISTRIBUTION IN DATABASE-SYSTEMS

Past analytic studies of concurrency control algorithms for database s ystems have assumed that data access distributions of transactions are uniformly distributed across the entire database. This assumption is largely forced by the fact that computation of the probability of tran saction blocking due to conflicts in case of an arbitrary access distr ibution is impractical (due to combinatorial explosion), even for a da tabase of small size. However, this assumption is unrealistic because in real-life databases, transactions exhibit locality of data referenc e [16, 21, 25]. Since the probability of conflicts among transactions is sensitive to the data access distribution of transactions, and sinc e the performance of concurrency control algorithms is sensitive to th e probability of conflicts, it is important that performance studies o f concurrency control algorithms be carried out for arbitrary data acc ess distribution. To assist the performance analysis of concurrency co ntrol algorithms under arbitrary data access distributions, in this pa per we present an analysis of transaction blocking under arbitrary dat a access distribution. We present a polynomial time algorithm for comp utation of probability of conflicts among a set of transactions of giv en size for databases where data access distribution is arbitrary. Dir ect computation of this probability from the expression has exponentia l complexity, and complexity of computation of this probability under uniform data access case is constant. We illustrate the proposed techn ique by taking a numerical example, and show that the assumption of un iform data access distribution can introduce significant error.