A Formal Characterization of Epsilon Serializability.
AbstractEpsilon serializability (ESR) is a generalization of classic serializability (SR). In this paper, we provide a precise characterization of ESR when queries that may view inconsistent data run concurrently with consistent update transactions.Our first goal is to understand the behavior of queries in the presence of conflicts and to show how ESR in fact is a generalization of SR. So, using the ACTA framework, we formally express the intertransaction conflicts that are recognized by ESR and through that define ESR, analogous to the manner in which conflict-based serializability is defined. Secondly, expressions are derived for the amount of inconsistency (in a data item) viewed by a query and its effects on the results of a query. These inconsistencies arise from concurrent updates allowed by ESR. Thirdly, in order to maintain the inconsistencies within bounds associated with each query, the expressions are used to determine the preconditions that operations have to satisfy. The results of a query, and the errors in it, depend on what a query does with the, possibly inconsistent, data viewed by it. One of the important byproducts of this work is the identification of different types of queries which lend themselves to an analysis of the effects of data inconsistency on the results of the query.
Introduction
Epsilon Serializability (ESR) [21, 29], a generalization of classic serializability (SR), explicitly
allows some limited amount of inconsistency in transaction processing (TP). ESR enhances
concurrency since some non-SR execution schedules are permitted. For example, epsilon-
transactions (ETs) that just perform queries may execute in spite of ongoing concurrent
updates to the database. Thus, the query ETs may view uncommitted, i.e., possibly in-
consistent, data. Concretely, an update transaction may export some inconsistency when it
updates a data item while query ETs are in progress. Conversely, a query ET may import
some inconsistency when it reads a data item while uncommitted updates on that data item
exist. The correctness notion in ESR is based on bounding the amount of imported and
exported inconsistency for each ET. The benefits of ESR have been discussed in the papers
cited above. For instance, ESR may increase system availability and autonomy [22] in distributed
TP systems, since asynchronous execution is allowed. But in this paper we restrict
our attention to ESR in a centralized TP system.
In its full generality, update ETs may view inconsistent data the same way query ETs
may. However, in this paper we focus on the situation where query-only ETs run concurrently
with consistent update transactions. That is, the update transactions are not allowed to view
uncommitted data and hence will produce consistent database states.
Our first goal is to understand the behavior of queries in the presence of conflicts and to
show how ESR in fact is a generalization of SR. So, in section 2, using the
[5, 6, 4] we formally express the inter-transaction conflicts that are recognized by ESR and,
through that, define ESR, analogous to the manner in which conflict-based serializability is
defined.
Our second goal is to quantify the amount of inconsistency experienced by queries. To
this end, in section 3, expressions are derived for the amount of inconsistency (in a data
item) viewed by a query. These inconsistencies arise from concurrent updates allowed by
ESR. This section also considers how transaction aborts affect the inconsistency of data.
ESR imposes limits on the amount of inconsistency that can be viewed by a query. So,
our third goal is to find ways by which these bounds are maintained. Using the expressions
quantifying the inconsistency, we derive preconditions that operations have to satisfy. Derivation
of these preconditions is the subject of Section 4. These preconditions point to possible
mechanisms that can be used to realize ESR and show that more flexible implementations
than those presented in [21, 29] are possible.
The effects of the inconsistent view on the results of a query depend on what a query does
with the viewed data. In general, a small data inconsistency can translate into an arbitrarily
large result inconsistency. So our fourth goal is to derive the effect of the inconsistency of
the data read by a query on the results produced by the query. This derivation is done in
Section 5 which also shows some of the restrictions that need to be imposed on the queries
and updates so as to be able to bound the inconsistency in the result of the query to lie
within reasonable limits. This helps characterize the situations in which ESR is applicable.
Thus, one of the important byproducts of this work is the identification of different types
of queries which lend themselves to an analysis of the effects of data inconsistency on the
results of the query.
Related work is discussed in Section 6 while section 7 concludes the paper and offers
suggestions for further work.
In the rest of this introduction, we provide an informal introduction to ESR and define
the terms used.
1.1 ESR and ETs
A database is a set of data items. Each data item contains a value. A database state is the
set of all data values. A database state space is the set of all possible database states. A
database state space SDB is a metric space if it has the following properties:
ffl A distance function distance(u; v) is defined over every pair of states u; v 2 SDB on
real numbers.
The distance function can be defined as the absolute value of the difference between
two states of an account data item. For instance, the distance between $50 and $120
is $70. Thus, if the current account balance is $50 and $70 is credited, the distance
between the new state and the old state is $70.
ffl Symmetry. For every
Continuing with the example, suppose, the current account balance is $120 and $70 is
debited. The distance between the new state and the old state is still $70.
ffl Triangle inequality. For every u; v; w 2 SDB , distance(u; v)+distance(v; w) - distance(u; w).
The account data clearly satisfies triangle inequality. For example, suppose the current
account balance is $50 and $70 is credited. The distance between the new state and
the old state, as we saw before is $70. Suppose $40 is now debited. The distance
between the state after the credit and the state after the debit is $40. The distance
between the initial state of the account ($50) and the one after both updates ($80) is
inequality is satisfied.
Many database state spaces have such a regular geometry. As we just saw, in banking
databases, dollar amounts possess these properties. Similarly, airplane seats in airline reservation
systems also form a metric space.
Usually the term "database state space" refers to the state on disk (implicitly, only the
committed values). We are not restricted to the database state on disk, however, since we
also consider the intermediate states of the database, including the contents in the main
memory. We will use the shorter term "data state" to include the intermediate states. Note
that the magnitude of an update can be measured by the distance between the old data item
state and the new data item state.
ESR defines correctness for both consistent states and inconsistent states. In the case
of consistent states, ESR reduces to classic serializability. In addition, ESR associates an
amount of inconsistency with each inconsistent state, defined by its distance from a consistent
state. Informally, inconsistency in a data item x with respect to a query q is defined as the
difference between the current value of x and the value of x if no updates on x were allowed
to execute concurrently with q. A query imports inconsistency when it views, i.e., reads,
an inconsistent data item. Conversely, an update transaction exports inconsistency when it
updates, i.e., writes to, a data item while query ETs that read the data item are in progress.
ESR has meaning for any state space that possesses a distance function. In general, serializable
executions produce answers that have zero inconsistency, but if a (non-serializable)
query returns an answer that differs from a serializable result by at most $10,000 we say
that the amount of inconsistency produced by the query is $10,000. In addition, the triangle
inequality and symmetry properties help us design efficient algorithms. In this paper, we
will confine our attention to state spaces that are metric spaces.
To an application designer and transaction programmer, an ET is a classic transaction
with the addition of inconsistency limits. A query ET has an import-limit , which specifies
the maximum amount of inconsistency that can be imported by it. Similarly, an update
ET has an export-limit that specifies the maximum amount of inconsistency that can be
exported by it. Since our focus is on queries, and for simplicity of presentation, we examine
in detail ETs when import-limits are placed on individual data items (a single attribute in
the relational model). The algorithms can be extended to handle an import-limit that spans
several attributes (e.g., checking accounts and savings accounts).
An application designer specifies the limit for each ET and the TP system ensures that
these limits are not exceeded during the execution of the ET. For example, a bank may wish
to know how many millions of dollars there are in the checking accounts. If this query were
executed directly on the checking accounts during the banking hours, serious interference
would arise because of updates. Most of the interference is irrelevant, however, since typical
updates refer to small amounts compared to the query output unit, which is in millions of
dollars. Hence we must be able to execute the query during banking hours. Specifically,
under ESR, if we specify an import-limit for the query ET, for example, of $100,000, for
this query, the result also would be guaranteed to be within $100,000 of a consistent value
(produced by a serial execution of the same transactions). For example, if the ET returns the
value $357,215,000 (before round-off) then at least one of the serial transaction executions
would have yielded a serializable query result in the $325,215,000\Sigma$100,000 interval.
The inconsistency accumulated by a query that reads multiple data items, such as in the
example above, depends on how the values read are used within the query. The percolation
of inconsistency from the data items read by the query to the results of the query is an
interesting issue and is discussed in Section 5.
Sections 3 and 4 focus on individual data items. Let us assume that limits are imposed
on the amount of inconsistency an ET can import or export with respect to a particular
data item. Let import limit t;x stand for the import-limit that has been set for ET t with
respect to data x. Let import inconsistency t;x stand for the amount of inconsistency that
has already been imported by ET t on data item x. The system that supports queries reading
inconsistent data must ensure the following for every ET t (that accesses data item x):
import inconsistency t;x - import limit t;x (1)
export inconsistency t;x - export limit t;x : (2)
We call the invariants (1) and (2) Safe(t; x) for brevity. For query ET q reading x, Safe(q; x)
reduces to:
import inconsistency q;x - import limit q;x (3)
export inconsistency
states that a query q cannot exceed its import-limit and that q cannot export
inconsistency.
Thus, during the execution of each ET, the system needs to maintain the amount of
inconsistency the ET has imported so far. Note that the amount of inconsistency is given
by the distance function and the incremental accumulation of inconsistency depends on the
triangle inequality property of metric spaces. Without triangle inequality, we would have to
recompute the distance function for the entire history each time a change occurs. In Section
3 we derive the algorithms necessary to maintain the specified limit on the inconsistency
imported from individual data items.
Before we end this section we would like to point out that throughout the paper, it is
assumed that the read set of a query, i.e., the set of data items read by a query is not affected
by the inconsistency in the data read by a query.
2 A Formal Definition of ESR
We use the 4, 6] to introduce the notion of conflicts between operations
and discuss the dependencies induced between transactions when they invoke conflicting
transactions.
For a given state s of a data item, we use return(s; a) to denote the output produced by
operation a, and state(s; a) to denote the state produced after the execution of a. value(s; P )
denotes the value of predicate P in state s.
Given a history H, H (x) is the projection of the history containing the operation invocations
on a data item x. H both the order of execution of the
operations, (a i precedes a i+1 ), as well as the functional composition of operations. Thus, a
state s of a data item produced by a sequence of operations equals the state produced by
applying the history H (x) corresponding to the sequence of operations on the data item's
initial state s 0 For brevity, we will use H (x) to denote the state of a
data item produced by H (x) , implicitly assuming initial state s 0 . Note that H (x) may depend
on values read in H from data items other than x.
operations a and b conflict in a state produced by H (x) , denoted by
Thus, two operations conflict if their effects on the state of a data item or their return values
are not independent of their execution order.
Let a t i
[x] denote operation a invoked by t i on data item x. (a t i
[x]) implies that
a t i
[x] appears before b t j
[x] in H.
Let us first define the classic serializability correctness criterion.
Given a history H of events relating to
transactions in T , C SR , a binary relation on T , is defined as follows:
[x])).
Let C
SR be the transitive-closure of C SR ; i.e.,
H is (conflict preserving) serializable iff
SR t).
To illustrate the practical implications of this definition, let us consider the case where
all operations perform in-place updates. In this case, if transactions t i and t j have a C SR
has invoked an operations which conflicts with a previous operation by t i ,
as long as t i is serlialized before t j , the conflict can be tolerated. Consider the (serialization)
graph corresponding to the C SR relation induced by a history. The above definition states
that for the history to be serializable, there should be no cycles in the graph. That is, the
serialization order must be acyclic.
The following three definitions constitute the definition of ESR.
whose events are recorded in history H.
CESR , a binary relation on transactions in T , is defined as follows:
In other words, t i and t j are related by cesr if and only if they are related by C SR and they
violate one of the invariants that constitute the predicate Safe. Note that the last term in
the definition of cesr makes cesr strictly weaker than C
Just as C SR denotes ordering requirements due to conflicts under serializability, cesr denotes
the ordering requirements imposed by conflicts under epsilon serializability. Since cesr is a
subset of the C SR relationship, a smaller number of orderings are imposed under ESR than
under classic serializability.
Consider the graph corresponding to the C SR and cesr relations induced by a history.
Definition 4 A cycle formed by transactions t 0 , has a cesr edge iff
As the next definition shows, (unlike SR) ESR can tolerate cycles formed by the C SR
relation. However, if the graph has a cycle consisting of a cesr edge, then the history is not
ESR.
Definition 5 A history H is (conflict-preserving) epsilon serializable iff, in the graph which
corresponds to the C SR and cesr relations induced by the history, there is no cycle that has
a cesr edge.
Before we examine the practical meaning of the above definitions, let us summarize the
properties of ESR compared to serializability:
ffl When all import-limit and export-limit are zero, cesr reduces to C SR . cesr is then
just C SR and ESR reduces to serializability.
ffl A set of transactions may not satisfy serializability because of cycles in the C SR relation,
but may satisfy ESR.
ffl When some import-limits and export-limits are greater than zero, cesr ' C SR (given
the additional term in definition 3). That is, ESR may allow more operations to execute
concurrently than serializability.
To understand the practical meaning of the definitions, let us focus on a query q executing
concurrently with an update transaction t. Suppose q reads x and this is followed by t's write
to x. Assume that t's write does not violate safe(t,x). Thus (q C SR t) but (q cesr t) is not
true. Assume that now q does another read of x. Let us consider two scenarios:
1. Assume that q's second read does not violate safe(q,x) and so (t C SR q) but not (t cesr
q). So we have a cyclic C SR relationship and yet the read is permitted by ESR. The
reason for this is that, under ESR, the values of x read by q are considered acceptable,
i.e., within the limits of inconsistency specified. More precisely, the value of x read by q
when concurrently executed with t is within the inconsistency limits considering either
of the serialization orderings: (q, t) or (t, q). That is why no orderings are imposed by
ESR, since according to ESR, both orderings are acceptable.
2. Assume that q's second read violates safe(q,x). So (t cesr q). This imposes an
ordering requirement such that it is as though q read x serially after t. Thus (t, q)
is the only serialization order acceptable - in order to conform to the inconsistency
limits. This implies that we cannot have (q C SR
t) since that corresponds to the
opposite serialization ordering. Hence it is required that there be no cycles consisting
of C SR and cesr edges.
Given the above characterization of ESR, one of the first tasks is to quantify the inconsistency
experienced by a query so that we can check if the safe predicates hold. This is
done in Section 3. Then in Section 4 we examine how to ensure that only epsilon serializable
histories are produced. One way is to allow no cesr to form, i.,e., to disallow an operation if
it violates safe. The question of how the inconsistency in the data read by a query percolates
to the the results of the query is studied in Section 5. Different types of queries are identified
with a view to determining the amount of data inconsistency they can tolerate in order to
maintain specified limits on result inconsistency.
Inconsistency Imported by a Query ET
We focus on the inconsistency of a single data item x read by a query q. Informally, inconsistency
in x with respect to a query q is defined as the difference between the current value
of x and the value of x if no updates on x were allowed to execute concurrently with q.
Consider update transactions where each of the t i 's updates x. We allow a query
q to read x multiple times and each of the updating t i 's to write x multiple times. Let us
define a transaction t i 's write interval with respect to x to be the interval of time between
its first write and the last write. A read interval is defined similarly.
Every query q has a set of Concurrent Update Transactions (denoted by CUT(q)). Update
its write interval intersects with q's read interval. Note that lock-based
realizations of serializability ensure that
The question we are attempting to answer here is the following: What can one say about
the value of x read by q given the CUT(q)? Our main objective is to bound the inconsistency
in the value of x read by q. But first we establish that the write intervals of transactions
in CUT(q) are totally ordered, since consistent update ETs are serializable.
Theorem 1 The serialization order of the transactions t i 2 CUT(q), w.r.t. x, is the same
as the order in which each t i enters its write interval which in turn is the same as the order
in which they commit.
Now we name the values of x at different points in time:
ffl x current is the current value of x.
final is the value of x committed by transaction t i .
initial is the value of x when transaction t i in CUT(q) begins, i.e., x t i
final .
initial is defined to be the value of x before any of the transactions in CUT(q) begin
execution. That is, if CUT(q) 6= ;; x q
From these values of x we can derive:
current change t i
initial
during t i
fcurrent change t i ;x g
final change t i
initial
final
Clearly, final change t i ;x - max change t i ;x and current change t i ;x -
We are in a position to define inconsistency formally.
initial inconsistency q;x )
That is, inconsistency q;x denotes the distance between x q
initial and x current . So, inconsistency
in the value of x for a query q while t i is in progress and update ETs
committed is given by
inconsistency
initial
initial
initial
initial
initial
initial
final
initial
current change t
final change t
Let committed CUT(q) denote the subset of CUT(q) containing the ETs that have commit-
ted. Let t current 2 CUT(q) denote the update transaction whose write interval has begun but
has not ended yet. If no such t current exists, it has a "null" value and current change null;x is
defined to be 0.
From these discussions we can state the following theorem which expresses (bounds on)
the inconsistency of a data item read by a query q when its read interval intersects with the
write intervals of ETs in CUT(q).
Theorem 2
inconsistency
initial
2committed CUT(q)
final change t current change t current;x
2committed CUT(q)
final change t
2committed CUT(q)
Whereas expression (5) is an exact expression of the inconsistency, expressions (6) through
(8) can be viewed as different bounds on inconsistency q;x .
We are now in a position to relate the inconsistency bound with the conflict-based definition
of ESR given in Section 2. Recall the definitions of C SR and cesr :
A pair of transactions have a C SR relationship but not a cesr relationship
iff one of them is a query and the other is an update and the import limits are not
violated. Let us focus on C SR relationships induced by operations on x. Given
(8), each of the update transactions t i that appears in the pairs that belongs to
C SR but not to cesr contributes an inconsistency of at most max change t i ;x
to the value of x read by q.
So far we have considered the case when all transactions commit. As stated by the following
theorem, abortion of update transactions has the effect of increasing the inconsistency
imported by a query without changing the value of x.
Theorem 3 The maximum increase in imported inconsistency caused by aborted transactions
is given by
aborted
Proof: Suppose transactions t 1 to t i\Gamma1 have committed and then t i begins but subsequently
aborts. In addition to the inconsistency due to t 1 to t i\Gamma1 , derived earlier, if q
reads x any time during t i 's execution, it will experience an additional inconsistency of
aborts whereby changes made by t i are obliterated and thus
subsequent updates will increase the value of x only with respect to that resulting from t 1
to t i\Gamma1 .
Suppose all the transactions in CUT(q) that follow t i commit. Then max change t i ;x is the
only increase to the inconsistency due to aborted transactions and hence the theorem holds.
Suppose instead that t i+1 to aborts. When q reads x after t j begins,
x will only reflect the changes done by (1) transactions t 1 to t
to . (3) is bounded by max change t j ;x . If this is larger than
is the increase in inconsistency due to the aborted
transactions t i and t j and hence the theorem follows for two transaction aborts. If this is
smaller, remains the upper bound on the increase. That is, the maximum of
the two is the effective increase in inconsistency due to two transaction aborts. This proof
extends easily if further transactions abort.
Ensuring Epsilon Serializability: Pre-Conditions for
Operations
To make sure that all histories are ESR (as per Definition 4) we should ensure that no cycles
are formed with cesr edges in them. But what if we do not even allow cesr relations to
Just like SR can be realized by preventing the formation of serialization orderings (i.e.,
C SR relations), ESR can be realized by preventing the formation of cesr relations). Thus, if
we ensure that a query is always safe, i.e, (import inconsistency q;x - import limit q;x ) is an
invariant, then ESR is guaranteed. Specifically, the inequality must hold (before and) after
every read and write operation as well as every transaction transaction management event.
We derive the preconditions for performing the operations. These are sufficient to ensure
that import limits of transactions are not exceeded. The preconditions will in turn be used
to show how the transaction executions should be managed.
Let begin write t;x denote the attempt by ET t to begin its write interval with respect to x.
begin read t;x is invoked by t to begin its read interval with respect to x. Let end write t;x denote
that t has completed its writes on x. We will now consider the semantics of begin write,
begin read, end write, end read, read and write. There are two situations to consider. The
first is if a query ET q is already in progress (initially with committed
an update transaction's write interval begins. This may be followed by other update ETs
before q commits. The second is if an update ET is in progress when the query begins.
Recall that our attention is confined to a centralized database with a single transaction manager

Let q be a query and t be an update ET. / stands for assignment.
If query q is in progress,
begin write t;x j (t current /
current / null) - (committed CUT(q) / committed CUT(q) [ t)
Otherwise, begin write t;x j () and end write t;x j ():
If an update transaction t is in progress, begin read q;x j (t current /t) - (CUT(q) / t).
Otherwise, begin read q;x
Here are the semantics of the other operations.
read t;x j ()
read q;x j (import inconsistency q;x / inconsistency q;x )
current / x current
\Delta is a parameter to the write operation that denotes the amount by which x is modified
when the write occurs.
It is important to note from the above semantics that a query imports inconsistency only
if it performs a read operation. That is, the inconsistency in the value of x due to updates
translates to imported inconsistency only when read operations occur.
We will now establish the preconditions necessary to maintain (3), i.e.,
(import inconsistency q;x - import limit q;x )
Case 1: Preconditions only on read q;x Operations.
Given that inconsistency is imported by q only when it performs a read, the following
precondition is all we need to maintain (9):
inconsistency q;x - import limit q;x :
From (5), this implies the precondition
current ; x q
initial
Every read operations must be intercepted by the transaction management mechanism to ensure
that the above precondition holds. If the predicate does not hold, the read by the query
will have to be aborted or delayed. If q is a long query, this has performance implications.
This is the motivation for examining other possible ways to maintain (9).
Case 2: Preconditions on write t;x Operations and begin read q;x Operations
Suppose we satisfy the following invariant:
inconsistency q;x - import limit q;x ;
i.e.,
current ; x q
initial
Note that this is a stronger invariant than (9), i.e, if this is maintained, then (9) will be
maintained. (This has a negative side-effect: If the query does not read x at all, then the
allowable inconsistency on x has been restricted unnecessarily.) Given the semantics of the
various operations, and the expression (5) for inconsistency, the following precondition on
results.
current
initial
and given that x is in metric space, this implies the precondition
initial
where j\Deltaj denotes the absolute value of \Delta. (We also use j S j to denote the cardinality of
set S. The meaning should be obvious from the context.) This says that a write should
be allowed only if the increase in inconsistency caused by the intended increment will not
violate the limit imposed on the inconsistency imported by q.
Even though no precondition is necessary for a read, the following precondition is required
for begin read q;x when it is invoked while an update transaction t is already in progress:
current
initial
Note that x q
initial when q begins its read interval while t's writes are in progress.
This says that if the changes that have already been done by the update transaction exceed
the import limit imposed on q then the query must not be allowed to begin its read on x.
The above preconditions imply that for each query q, we should maintain x q
initial . This
can be avoided by maintaining an even stronger invariant, corresponding to the inconsistency
bound (6), i.e., by maintaining
2committed CUT(q)
final change t current change t current ;x - import limit q;x :
This imposes the following precondition on write t;x :
2committed CUT(q)
final change t current change t current;x
import limit q;x
and the following precondition on begin read q;x :
current change t current ;x - import limit q;x :
This implies that write operations by update ETs and requests by query ETs to begin
their reading have to be monitored to ensure that they are allowed only when the above
preconditions hold.
Both these invariants require maintenance of the most recent committed state of x. This
is available anyway. However, the need to check every write by an update ET implies
increased overheads and may also result in aborts or delays of update ETs in progress. Both
can be avoided as shown below if an even stronger invariant is maintained.
Case 3: Preconditions on begin read q;x and begin write t;x Operations
Consider the following invariant corresponding to inconsistency bound (7):
2committed CUT(q)
final change t current ;x - import limit q;x :
This inequality turns out to be the precondition for begin write t;x . begin read q;x has the
following precondition:
This implies that unlike the previous case, no preconditions are associated with individual
writes by update transactions. While this reduces transaction management overheads, it
does introduce some pessimism into the decision making since worst case changes to x by t
are assumed.
The precondition for begin write t;x requires knowledge about final change of transac-
tions. This can be avoided if the following invariant, corresponding to inconsistency bound
(8), is maintained:
2committed CUT(q)
current ;x - import limit q;x (11)
(11) is also the precondition for begin write t;x . (10) stays as the precondition for begin read q;x .
Suppose is the same for all update ETs t i . Then, a given import limit q;x
for a query q translates into a limit on the cardinality of CUT(q).
In terms of the impact of the above derivation on an implementation of ESR, note that
we progressed from preconditions on individual read and write operations to preconditions
for read and write intervals to begin. The latter introduce more pessimism, because of the
the assumptions that have to be made about the amount of changes done by a given update
transaction.
Modeling query and transaction executions in terms of their read and write intervals
allows us to capture different types of concurrency control techniques. For instance, if the
begin events correspond to the acquisition of locks and the end events correspond to the
release of locks, we get lock based protocols. Assume we use the preconditions on these
events to ensure bounds. This is the basis for the lock-based implementation in [29] wherein
precondition (11) for begin write corresponds to LOK-2 and precondition (10) for begin read
corresponds to LOK-1.
However, the above derivation is not restricted to lock-based implementations. In optimistic
concurrency control, writes are done after the validation phase. In this case, precondition
checking for writes will be part of the validation phase of an update transaction.
5 Inconsistency in the Results of a Query
Since a query, by definition, does not update data, it does not affect the permanent state of
the database. Furthermore, we have assumed that updates do not import inconsistency, i.e.,
they operate on consistent database states. Thus, assuming that each update ET maintains
database consistency, updates also do not affect the consistency of the database. The only
effect of the updates is on the inconsistency of the data read by queries. In Section 3
we derived expressions for the amount of inconsistency imported by a query. Given this
inconsistency, the only observable effect of a query ET is on the results produced by a query.
In other words, the inconsistency imported by a query can percolate to the results of a query,
in ways that are obviously dependent on the manner in which the query utilizes the values
read.
This section is devoted to determining the effect of the inconsistency of data read by a
query on its results. In general, a small input inconsistency can translate into an arbitrarily
large result inconsistency. Therefore, we study the properties of a query that make the result
inconsistency more predictable.
First we establish some terminology. Consider the situation where a query q reads data
items produces a result based on the values read. In general, the results
of such a query can be stated as a function of the form:
where g denotes a query ET and f i 's are functions such that f
the range of f i . We assume that R f is also a metric space. In practice, typically R f is a
subset of SDB . For example, aggregate functions and queries on the database usually return
a value in SDB .
Focusing on monotonic queries, in Section 5.1 we derive the inconsistency in the result
of a query and show that even though the inconsistency can be bound, the bound may
not be tight. Suppose, similar to import limit and export limit, a limit is placed on the
inconsistency in the result of a query. In Section 5.2, we derive the preconditions on ET
operations imposed by such a limit. In Section 5.3 a class of queries called bounded queries
is considered. Section 5.4 examines steady queries and discusses how queries can be designed
to have tighter inconsistency bounds thereby requiring less restrictive preconditions.
5.1 Monotonic Queries
The first important class of queries consists of monotonic functions. A function f is monotonically
increasing if x - y function g is monotonically decreasing if
function is called monotonic if it is either monotonically increasing
or decreasing. Without loss of generality in the rest of this section we describe only
monotonically increasing functions.
The result returned by a monotonic ET q assuming that the value of x i read by q is given
by x i;read is
where, if max inconsistency x i
is the maximum inconsistency in the value of x i read by
q (given by Theorem 2 of Section 3), x i;initial is the value of x i when the first update
ET in CUT(q) begins, and x
and x
inconsistency x i
, then
Thus, since g and the f i 's are monotonic, the result of the query can lie between
min result
and
Note that if f i is not monotonic, the smallest (largest) value of f i need not correspond to
the smallest (largest) value of x i .
Thus, by our definition of inconsistency,
result inconsistency
Let us look at some examples:
Example 1: n=1; the identity function. This corresponds to the single data
element case and hence the inconsistency in the result of q can be seen to be given by (13).
Example 2: n=20;
the identity function. In this case, as one would
expect, the result of the query, according to (14) and (15), will lie between
inconsistency x i
Example 3: n=20;
predicate has a value 1 if it is
true, otherwise 0.) In this case, the result of the query, according to (14) and (15), will lie
Example 4: This is a concrete case of Example 3. Consider a bank database with
accounts, numbered 1-20. Each account with an odd number happens to have $5,001
and even-numbered accounts have $4,999. The only update transaction in the system is:
transfers $2 from Acc i into Acc j . The query ET sums up all
the deposits that are greater than $5,000. Suppose that the first set of transactions executed
by the system are: Transfer(Acc these finish, the
following are executed: Transfer(Acc 2i ; Acc
These update transactions maintain the total of money in the database, and it is easy to
see that a serializable execution of the query ET should return $50,010, since at any given
exactly 10 accounts have more than $5,000.
This query will produce a result between $0 and $100,080 since it is exactly Example 3,
where,
The range of the result does include the serializable result of $50,010. However, given that
the range is not very "tight", it is too pessimistic. This occurs because the inconsistency
caused by the updates percolate, in a rather drastic manner, to the results of the query. In
Section 5.4, we identify a class of queries for which tight bounds on the results of a query
exist.
One other point to note here is that even this bound requires knowledge of x i;initial , the
value of x i when the first ET in CUT(q) begins. This has practical implications. Specifically,
before an update is begun, the data values may have to be logged in order to derive the
inconsistency for the queries that may subsequently begin. This is the case of systems that
require UNDO capability (using the STEAL buffering policy [12]).
Given that the lower bound on the result of the above query is 0, one may be tempted
to take the following solution: Assume that x i;initial is the smallest value x i can take, i.e., 0.
It is not too difficult to see why this will not produce the correct range for the above query's
result.
5.2 Pre-Conditions for Monotonic Queries
Suppose result inconsistency limit q denotes the maximum inconsistency that an application
can withstand in the result of a query q. Then
result inconsistency q - result inconsistency limit q
is an invariant. Just as we derived preconditions to maintain import limit q;x and export limit q;x ,
we can derive preconditions to maintain the above invariant.
For instance, consider the expression (8) for max inconsistency x . From this, given (16)
and the semantics of ET operations (see Section 3), we have the following precondition for
begin write t;x i
2committed CUT(q)
2committed CUT(q)
result inconsistency limit q
and the following precondition for begin read q;x i
result inconsistency limit q
In a similar manner, preconditions can be derived in case the other expressions for inconsistency
are used.
5.3 Bounded Queries
We say that a function f is bounded if there is a maximum bound in the result of f . It is easy
to see that we can calculate bounds on the inconsistency in the results of a query composed
from bounded functions.
Example 5: Consider the following variation of Example 4. The query ET sums up
all the deposits that are not greater than $5,000. For this query, n=20;
's are not monotonic because when x i increases from $4999 to
decreases from $4999 to $0. So the expressions derived for result inconsistency in
Section 5.2 do not apply.
It is easy to see that a serializable execution of the query ET should return $49,990, since
at any given time, exactly 10 accounts have balance - $5,000. It is also not difficult to see
that for the above ET query, the smallest possible result is $0 and the largest possible result
is $99,980.
Even though the the f i 's are not monotonic, we now show that it is possible to obtain
bounds on the query results. Let min f i denote the smallest value of f i for any value of
denote the largest value of f i for any value of x i in
as long as g is monotonic, the result of the query can lie between
Let us return to Example 5. In this case,
hence, the result of the query can lie between $0
and $100,000. Since the actual result of the query lies between $0 and $99,980, using the
maximum and minimum possible f i values leads to an overestimate of the inconsistency in
the query results.
A generalization of bounded functions and monotonic functions is the class of functions
of bounded variation. To avoid confusion for readers familiar with mathematical analysis,
we follow closely the usual definition of these functions in compact metric spaces.
Definition 6 If [a; b] is a finite interval in a metric space, then a set of points
satisfying the inequalities a is called a partition of [a; b].
The interval [x is called the k th subinterval of P and we write \Deltax
that
Definition 7 Let f be defined on [a; b]. If is a partition of [a; b], write
n. If there exists a positive number M such that
for all partitions of [a; b], then f is said to be of bounded variation on [a; b].
It is clear that all bounded functions are of bounded variation. In Example 5,
Furthermore, all monotonic functions are also of bounded variation. This happens because
for a monotonically increasing function f we have \Deltaf k - 0 and therefore:
In general, for a function of bounded variation, the M bound can be used as an (over)estimate
of result inconsistency given the interval [a; b] caused by input inconsistency. However, the
examples above show that what we need is to restrict the forms of ET queries such that
tighter bounds on result inconsistency can be found without overly restricting the type of
queries allowed.
5.4 Steady Queries
Let DS denote the set of distances defined by SDB and DR the set of distances defined by
R f . We say that f is steady if for every ffl 2
such that Steady functions on discrete metric spaces are analogous
to continuous functions on compact sets. The definition is similar, except that we exclude a
fixed number of small ffl due to the discrete nature of SDB . Informally, if ffl
to be zero.
The importance of steady functions is that the application designer may specify a limit
on the result inconsistency, result inconsistency limit (ffl), and the TP system can calculate
the limit on the imported inconsistency, max inconsistency (ffi), that guarantees the specified
limit on the result inconsistency. Section 5.2 shows how this calculation can be done for
monotonic functions. Note that every monotonic function can be steady with a convenient
choice of ffl 0 . However, the smaller is the ffl 0 the tighter is the bound on ffi. In the following
example, the bound is tight because ffl
Example Consider a query ET that returns the balance of a bank account. If an
update is executing, say transferring some money into the account, then the query result
inconsistency is equal to imported inconsistency and
For an example where ffl 0 is large, consider Example 4. When an account balance is
actually 5000, an input inconsistency of 1 may change the result by 5000. Therefore we have
since a smaller ffl requires
One way to handle such a situation is to reduce or eliminate the imported inconsistency
in the data item that causes a large ffl 0 . For instance, suppose that
that a large ffl 0 is due to x 1 . We should tighten the import limit for x 1 and allow inconsistency
only for x 2 . Consider the following example which is a simple variation of Example 4.
Example 7: The query ET returns the checking account balance of customers that have
savings accounts with balance greater than $5,000. Note that in this example, x 1 refers to the
savings account and x 2 to the checking account. In this case, we may specify import limit =
0 for the savings account balance and import limit = $100 for the checking account balance.
This way, we avoid the large ffl 0 with respect to x 1 but maintain the tight control over
result inconsistency since the function that returns the checking account balance is a steady
function with ffl (from Example 6).
Being able to calculate ffl from ffi and vice-versa are properties of ET queries that allow
the system to maintain tight bounds on result inconsistency. Functions of bounded variation
and steady functions are abstract classes of functions that have these properties. Clearly,
more elaborate characterization of these functions defined on discrete metric spaces will be
useful.
6 Related Work
6.1 General Weak Consistency Criteria
Several notions of correctness weaker than SR have been proposed previously. A taxonomy
of these correctness criteria is given in [23]. Here we contrast those that are closely related
to ESR with ESR.
Gray's different degrees of consistency [11] is an example of a coarse spectrum of consis-
tency. Of specific interest to us is degree 2 consistency which trades off reduced consistency
for higher concurrency for queries. Since degree 2 allows unbounded inconsistency, degree 2
queries become less accurate as a system grows larger and faster. In general, ESR offers a
much finer granularity control than the degrees of consistency.
Garcia-Molina and Wiederhold [10] have introduced the weak consistency class of read-only
transactions. In contrast to their WLCA algorithm, ESR is supported by many divergence
control methods [29]. Similarly, Du and Elmagarmid [7] proposed quasi-serializability
(QSR). QSR has limited applicability because of the local SR requirements despite unbounded
inconsistency. Korth and Speegle [16] introduced a formal model that include
transaction pre-conditions and post-conditions. In contrast, ESR refers specifically to the
amount of inconsistency in state space.
Sheth and Rusinkiewicz [26] have proposed eventual consistency, similar to identity
connections introduced by Wiederhold and Qian [28], and lagging consistency, similar to
asynchronously updated copies like quasi-copies [1]. They discuss implementation issues
in [24, 25]. In comparison, ESR achieves similar goals but has a general approach based on
state space properties and functional properties. Barbara and Garcia-Molina [2] proposed
controlled inconsistency, which extends their work on quasi-copies [1]. Their demarcation
protocol [3] can be used for implementing ESR in distributed TP systems. ESR is applicable
to arithmetic and other kinds of consistency constraints.
6.2 Asynchronous Transaction Processing
Garcia-Molina et al. [9] proposed sagas that use semantic atomicity [8] defined on transaction
semantics. Sagas differ from ESR because an unlimited amount of inconsistency (revealed
before a compensation) may propagate and persist in the database. Levy et al [19] defined
relaxed atomicity and its implementation by the Polarized Protocol. ESR is defined over
state space properties and less dependent on application semantics.
An important problem in asynchronous TP is to guarantee uniform outcome of distributed
transactions in the absence of a commit protocol. Unilateral Commit [13] is a
protocol that uses reliable message transmission to ensure that a uniform decision is carried
out asynchronously. Optimistic Commit [18] is a protocol that uses Compensating Transactions
[15] to compensate for the effects of inconsistent partial results, ensuring a uniform
decision. Unilateral Commit and Optimistic Commit can be seen as implementation techniques
for ESR-based systems.
Another way to increase TP concurrency is Escrow Method [20]. Like the escrow method,
ESR also uses properties of data state space, but ESR does not rely on operation semantics to
preserve consistency. Similarly, data-value partitioning [27] increases distributed TP system
availability and autonomy. ESR can be used in the modeling and management of escrow
and partitioned data-values.
Conclusions
Previous ESR papers discussed ESR in informal terms by motivating it via specific applications
[21, 22] and by presenting implementation-oriented considerations [29]. An evaluation
of the performance improvement due to ESR is reported in [14].
In this paper, we have examined epsilon serializability (ESR) from first principles. We
showed precisely how ESR is related to SR, for example, which conflicts considered by SR
are ignored by ESR. A conflict based specification of ESR using the ACTA formalism was
employed to bring out the differences between SR and ESR.
We began our formalization of query behavior by deriving the formulae that express
the inconsistency in the data values read by a query. From these expressions we derived
the preconditions, that depend on the data values and the import limits, for the read and
operations invoked by transactions and for transaction management events. In other
words, from a precise definition of ETs and ESR, we have been able to derive the behavioral
specifications for the necessary transaction management mechanisms. These form the second
contribution of this paper. Results showed that more flexible transaction management
techniques, than the ones discussed previously, are possible.
Another important aspect of this paper is the derivation of expressions for the inconsistency
of the results of queries. We showed that since arbitrary queries may produce results
with large inconsistency, it is important to restrict ET queries to have certain properties
that permit tight inconsistency bounds. Towards this end, we came up with different types
of queries that allow us to bound the result inconsistency, and in some cases, to find tight
bounds as well. Clearly, more work is needed in this area since generality of the queries has
to be traded off against the tightness of the result inconsistency.
Among the other active topics of research is the formal treatment of general ETs that
both import and export inconsistency. Also, the effect of relaxing some of the assumptions,
for instance, that read set of a query is unaffected by the inconsistency, needs to be studied.

Acknowledgements

The authors thank P. Chrysanthis, H.V. Jagadish, V. Wolfe, and the referees for their comments
on previous versions of this paper.



--R

Data caching issues in an information retrieval systems.
The case for controlled inconsistency in replicated data.
The Demarcation Protocol: A Technique for Maintaining Arithmetic Constraints in Distributed Database Systems
A formalism for extended transaction models.
ACTA: A framework for specifying and reasoning about transaction structure and behavior.
ACTA: The Saga continues.
Quasi serializability: a correctness criterion for global concurrency control in InterBase.
Using semantic knowledge for transactions processing in a distributed database.


Granularity of locks and degrees of consistency in a shared data base.
Principles of transaction-oriented database recovery
Unilateral commit: A new paradigm for reliable distributed transaction processing.
"Performance Characteristics of Epsilon Serializability with Hierarchical Inconsistency Bounds"
A formal approach to recovery by compensating transactions.
Formal model of correctness without serializability.
Bounded Ignorance in Replicated Systems.
An optimistic commit protocol for distributed trans-action management
A theory of relaxed atomicity.
The escrow transactional method.
Replica control in distributed systems: An asynchronous approach.
Autonomous transaction execution with epsilon-serializability
"In Search of Acceptability Criteria: Database Consistency Requirements and Transaction Correctness Properties"
Redundant data management in Bellcore and BCC databases.
Maintaining consistency of interdependent data in multidatabase systems.
Management of interdependent data: Specifying dependency and consistency requirements.

Modeling asynchrony in distributed databases.
Divergence control for epsilon-serializability
--TR

--CTR
Lyman Do , Prabhu Ram , Pamela Drew, The need for distributed asynchronous transactions, ACM SIGMOD Record, v.28 n.2, p.534-535, June 1999
Kun-Lung Wu , Philip S. Yu , Calton Pu, Divergence Control Algorithms for Epsilon Serializability, IEEE Transactions on Knowledge and Data Engineering, v.9 n.2, p.262-274, March 1997
Dang Depeng , Liu Yunsheng, Concurrency control in real-time broadcast environments, Journal of Systems and Software, v.68 n.2, p.137-144, 15 November
Lisa Cingiser DiPippo , Victor Fay Wolfe, Object-Based Semantic Real-Time Concurrency Control with Bounded Imprecision, IEEE Transactions on Knowledge and Data Engineering, v.9 n.1, p.135-147, January 1997
Nir Shavit , Dan Touitou, Elimination trees and the construction of pools and stacks: preliminary version, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.54-63, June 24-26, 1995, Santa Barbara, California, United States
Tei-Wei Kuo , Shao-Juen Ho, Similarity-Based Load Adjustment for Static Real-Time Transaction Systems, IEEE Transactions on Computers, v.49 n.2, p.112-126, February 2000
Alexander Totok , Vijay Karamcheti, Modeling of concurrent web sessions with bounded inconsistency in shared data, Journal of Parallel and Distributed Computing, v.67 n.7, p.830-847, July, 2007
Philip A. Bernstein , Alan Fekete , Hongfei Guo , Raghu Ramakrishnan , Pradeep Tamma, Relaxed-currency serializability for middle-tier caching and replication, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
Man Hon Wong , Divyakant Agrawal , Hang Kwong Mak, Bounded Inconsistency for Type-Specific Concurrency Control, Distributed and Parallel Databases, v.5 n.1, p.31-75, Jan. 1997
Yuan-Ting Kao , Chin-Fu Kuo, Two-Version Based Concurrency Control and Recovery in Real-Time Client/Server Databases, IEEE Transactions on Computers, v.52 n.4, p.506-524, April
Evaggelia Pitoura , Bharat Bhargava, Data Consistency in Intermittently Connected Distributed Systems, IEEE Transactions on Knowledge and Data Engineering, v.11 n.6, p.896-915, November 1999
Aloysius K. Mok, Real-Time Data Semantics and Similarity-Based Concurrency Control, IEEE Transactions on Computers, v.49 n.11, p.1241-1254, November 2000
Tei-Wei Kuo , Chih-Hung Wei , Kam-Yiu Lam, Real-Time Access Control and Reservation on B-Tree IndexedData, Real-Time Systems, v.19 n.3, p.245-281, Nov. 2000
Krithi Ramamritham , Panos K. Chrysanthis, A taxonomy of correctness criteria in database applications, The VLDB Journal  The International Journal on Very Large Data Bases, v.5 n.1, p.085-097, January 1996
Yasushi Saito , Marc Shapiro, Optimistic replication, ACM Computing Surveys (CSUR), v.37 n.1, p.42-81, March 2005
concurrency control;epsilon serializability;formal techniques;ACTA;transaction processing