On computing serial dependency relations

摘要

In a database system where the data is a collection of shared objects there can be concurrent access to the data by several transactions. Traditional concurrency-controls use a notion of conflict between pairs of operations (of which the transactions are composed) to ensure correctness. Herlihy has proposed the notion of a serial dependency relation over the set of operations to capture this idea of conflict. Since the smaller the conflict relation the more the concurrency, it is of interest to construct minimal serial dependency relations. In this paper, we give necessary and sufficient conditions for a pair of operations to be related by a minimal serial dependency relation. However, we go on to show that, in general, the problem of constructing a minimal relation is undecidable. We also show that some approaches advocated for constructing serial dependency relations are not feasible in general. We then provide a sufficiency condition for cases where the minimal relations are computable.