Technical reports:
A Formal Characterization of Epsilon Serializability
Krithi Ramamritham; Calton Pu
Downloads:
- Title:
- A Formal Characterization of Epsilon Serializability
- Author(s):
-
Ramamritham, Krithi
Pu, Calton - Date:
- 1991
- Type:
- Technical reports
- Department:
- Computer Science
- Permanent URL:
- http://hdl.handle.net/10022/AC:P:12841
- Series:
- Columbia University Computer Science Technical Reports
- Part Number:
- CUCS-044-91
- Publisher:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- Abstract:
- Epsilon Serializability (ESR) is a generalization of classic serializability (SR). ESR allows some limited amount of inconsistency in transaction processing (TP), through an interface called epsilon-transactions (ETs). For example, some query ETs may view inconsistent data due to non-SR interleaving with concurrent updates. In this paper, we restrict our attention to the situation where query-only ETs run concurrently with consistent update transactions that are SR without the ETs. This paper presents a formal characterization of ESR and ETs. Using the ACTA framework, the first part of this characterization formally expresses the inter-transaction conflicts that are recognized by ESR and, through that, defines ESR, analogous to the manner in which conflict-based serializability is defined. The second part of the paper is devoted to deriving expressions for: (1) the inconsistency in the values of data -- arising from ongoing updates, (2) the inconsistency of the results of a query – arising from the inconsistency of the data read in order to process the query, and (3) the inconsistency exported by an update ET - arising from ongoing queries reading uncommitted data produced by the update ET. These expressions are used to determine the preconditions that ET operations have to satisfy in order to maintain the limits on the inconsistency in the data read by query ETs, the inconsistency exported by update ETs, and the inconsistency in the results of queries. This determination suggests possible mechanisms that can be used to realize ESR.
- Subject(s):
- Computer science
- Item views:
- 29