Reduction in Transaction Conflicts Using

Semantics-Based Concurrency Control ?

Sushil Jajodia
Department of Information Systems and Systems Engineering George Mason University
Fairfax, VA 22030

Ravi Mukkamala
Department of Computer Science
Old Dominion University
Norfolk, VA 23529

In this chapter, we consider algorithms that permit every site in a partitioned database system to perform new updates. Since this may result in independent updates to items in different partitions, conflicts among transactions are bound to occur. Commutative transactions can be used to reduce the number of these conflicts. We develop a probabilistic model to estimate the possible reduction in conflicts if we incorporate this notion of commutativity. The results show that the additional efforts to recognize this commutativity is not beneficial unless the number of transactions that commute with each other is significantly large.

1 INTRODUCTION

A partitioning of a distributed database (DDB) occurs when the sites in the network split into groups of communicating sites due to node or communication link failures. The sites in each group can communicate with each other, but no site in one group is able to communicate with sites in other

?We gratefully acknowledge Elsevier Science Publishing Co., Inc. for permission to use material from `Measuring the effect of commutative transactions on distributed database performance," Information Sciences, Vol. 68, Nos. 1/2, February 1993, pages 91-111.