Formal CharacteristicsEpsilon serializability (ESR) is a weaker form of correctness designed to provide more concurrency than classic serializability (SR) by allowing, for example, query transactions to view inconsistent data in a controlled fashion i.e. limiting the inconsistency within the specified bounds.
Additional information about ESR can be obtained from the Epsilon Serializability home page at OGI, Oregon.
Formal CharacteristicsIn ACTA, an SR history is defined as a sequence of operations with an empty transitive closure of transaction dependencies. This is equivalent to the Serializability Theorem that uses acyclic transaction dependency graphs. The formal definition of ESR in ACTA is simply an extension of this definition. An epsilon-serializable history is a sequence of operations with an empty transitive closure of epsilon-transaction dependencies, which are the normal dependencies excluding the conflicts allowed under the transaction epsilon specification. In the work we also discuss the accumulation and transformation of inconsistency within epsilon-transactions.
Performance AspectsPreviously ESR inconsistency bounds have been specified with respect to transactions or with respect to objects. In this work, we introduce the notion of hierarchical inconsistency bounds that allows inconsistency to be specified at different granularities. The motivation for this comes from the way data is usually organized, in hierarchical groups, based on some common features and interrelationships. Bounds on transactions are specified at the top of the hierarchy, while bounds on the objects are specified at the bottom and on groups in between. We also discuss mechanisms needed to control the inconsistency so that it lies within the specified bounds. While executing a transaction, the system checks for possible violation of inconsistency bounds bottom up, starting with the object level and ending with the transaction level.
We report on an evaluation of the performance improvement due to ESR incorporating hierarchical inconsistency bounds. The tests were performed on a prototype transaction processing system that uses timestamp based concurrency control. For simplicity, our implementation uses a two level hierarchy for inconsistency specification - the transaction level and the object level. We make two important observations from the tests. First, the thrashing point shifts to a higher multiprogramming level when transaction inconsistency bounds are increased. Further, for a particular multiprogramming level and a particular transaction inconsistency bound, the throughput does not increase with increasing object inconsistency bounds but peaks at some intermediate value.
Publications 
Back to the Database Systems Home Page