Browse Prior Art Database

Multigranularity Locking Divergence Control for Epsilon Serializability

IP.com Disclosure Number: IPCOM000105197D
Original Publication Date: 1993-Jun-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 6 page(s) / 250K

Publishing Venue

IBM

Related People

Wu, K: AUTHOR [+2]

Abstract

In this disclosure, three multigranularity-locking divergence control designs for epsilon serializability (ESR) are presented. More concurrency is allowed by permitting controlled inconsistency for read-only transactions.

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

Multigranularity Locking Divergence Control for Epsilon Serializability

      In this disclosure, three multigranularity-locking divergence
control designs for epsilon serializability (ESR) are presented.
More concurrency is allowed by permitting controlled inconsistency
for read-only transactions.

      Serializability is the standard notion of correctness in
transaction processing.  Serializability (SR) maintains database
consistency.  However, for read-only transactions that can tolerate
some amount of inconsistency, the strictness of serializability may
impose unnecessary limitations on the system throughput.

      To alleviate the limitations of SR, the notion of epsilon
serializability has been proposed [1, 2].  Instead of weakening
database consistency, ESR stretches it.  ESR allows for limited
inconsistency in read-only transaction processing while maintaining
database consistency.  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.

      To introduce controlled inconsistency, a new grouping of
database operations is presented.  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.  The number
of non-SR R/W conflicts is used as a concrete measure for
inconsistency specification.  Each ET has two parameters, ImpLimit
which denotes the maximum number of non-SR conflicts the ET can
import from other ETs and ExpLimit which denotes the maximum number
of non-SR conflicts the ET can export to other ETs.  In this
disclosure, an update ET is not allowed to import any inconsistency.
Therefore, an Import_Accumu is maintained for each query ET and an
Export_Accumu for each update ET.  A marker can be added to query ETs
so that they can be distinguished from update ETs.

      Two-Phase-Locking Divergence Control:  Before proceeding to
multigranularity-locking divergence control algorithms, the standard
two-phase-locking divergence control is...