Implementing semantic-based decomposition of transactions

In some database applications, performance requirements are not satisfied by the traditional approach of serializability, in which transactions appear to execute atomically and in isolation on a consistent database state. Although many researchers have investigated the process of decomposing transactions into steps to increase concurrency, the focus of the research is typically on implementing a decomposition supplied by the database application developer, with relatively little attention to what constitutes a desirable decomposition and how the developer should obtain such a decomposition. In our research, we focus on the decomposition process itself. In [2], we introduced the notion of semantic histories and identified a number of properties which must be satisfied by a decomposition if the decomposition correctly models the original collection of transactions. We also formulated the notion of successor sets to describe efficiently the correct interleavings of steps. In this paper, we develop the successor set constraints more fully, and show how they can be used to take full advantage of conflict serializability at the level of steps. We give a graph-based characterization of correctness of successor set histories, and show how a verified decomposition can be implemented in a two-phase locking environment. We also discuss how the problems related to starvation, deadlocks, and recovery could be addressed.