Browse Prior Art Database

Timestamp Ordering Divergence Control for Epsilon Serializability

IP.com Disclosure Number: IPCOM000122201D
Original Publication Date: 1991-Nov-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 4 page(s) / 199K

Publishing Venue

IBM

Related People

Pu, C: AUTHOR [+3]

Abstract

An efficient timestamp ordering divergence-control method is disclosed for epsilon-serializability. Compared with timestamp ordering concurrency control for serializability, timestamp ordering divergence control allows for more concurrency by permitting controlled, limited inconsistency in transaction processing.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 31% of the total text.

Timestamp Ordering Divergence Control for Epsilon Serializability

      An efficient timestamp ordering divergence-control method
is disclosed for epsilon-serializability.  Compared with timestamp
ordering concurrency control for serializability, timestamp ordering
divergence control allows for more concurrency by permitting
controlled, limited inconsistency in transaction processing.

      Serializability is the standard notion of correctness in
transaction processing.  Serializability (SR) maintains database
consistency: when a database only runs serializable transactions,
then (if the database starts out in a consistent state) the database
is guaranteed to remain in a consistent state.  However,
serializability has its limitations.  For read-only transactions that
can tolerate some amount of inconsistency, the strictness of
serializability may impose unnecessary limitations on the system
throughout.

      To alleviate the limitations of SR, the notion of
epsilon-serializability (ESR) has been proposed.  Instead of
weakening database consistency, ESR stretches it.  ESR allows for
limited inconsistency in transaction processing. Such ESR properties
are automatically preserved by divergence control (DC) methods in a
way similar to SR by concurrency control (CC) mechanisms.  Users can
benefit from ESR through a high-level and simple specification of
inconsistency tolerances.  Although DC allows for bounded
inconsistency, it prevents update transactions from causing
inconsistency in the database.  Namely, read-only transactions need
not be serializable with other transactions, but update transactions
must be serializable among themselves.  As a result, DC allows more
concurrency than CC does.  DC methods are designed by first analyzing
CC algorithms to identify the places where the CC algorithms detect
conflicts of database operations that would cause
non-serializability, and then modifying the CC algorithms to accept
non-serializable (non-SR), conflicting operations in such a way that
the inconsistency tolerance is bounded.

      Described in this article is a timestamp ordering divergence
control method for ESR.  Divergence control methods based on
optimistic concurrency control algorithms can be similarly designed.
To introduce controlled inconsistency, we first present a new
grouping of database operations.  An epsilon-transaction, denoted by
ET, is a sequence of operations that maintain database consistency
when executed atomically.  However, an ET extends standard
transaction, denoted by T, in the sense that an ET includes a
specification of the amount of permitted inconsistency. We use the
number of non-SR R/W conflicts as a concrete measure for
inconsistency specification.  Each ET has two parameters, ImpLimit
that denotes the maximum number of non-SR conflicts the ET can import
from other ETs and ExpLimit that denotes the maximum number of non-SR
conflicts the ET can export to other ETs.  In this art...