Formal Characteristics & Performance Aspects of Epsilon Serializability


Epsilon 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 Characteristics

In 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 Aspects

Previously 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.


Krithi Ramamritham and Calton Pu, "A Formal Characterization of Epsilon Serializability", IEEE Transactions on Knowledge and Data Engineering, (to appear) 1995.

Mohan U. Kamath and Krithi Ramamritham, "Performance Characteristics of Epsilon Serializability with Hierarchical Inconsistency Bounds", Proceedings of 9th International Conference on Data Engineering, Vienna, 1993, IEEE Computer Society Press.

Back to the Database Systems Home Page

If you have any comments on this page or need further information, please send your mail to
Last Update: 23 June 95