Database Reference
In-Depth Information
different schedules. In fact, the number of possible schedules for a set of
n
transac-
tions is much larger than
n
(
n
-
1
)(
n
-
2
)
……3.2.1
. With just five transactions, you
can come up with more than 120 different schedules. Some of these possible sched-
ules preserve data integrity—many do not.
Obviously, all the possible serial schedules preserve data integrity. In a serial
schedule, the operations of one transaction are all executed before the next trans-
action starts. However, serial schedules are unacceptable, because they do not
promote concurrency. Concurrent processing of transactions is highly desirable. So,
what types of nonserial schedules are safe to preserve data integrity? In what types
of schedules is there no interference among the participating transactions? This
leads us to the discussion of serializability and recoverability.
Serializability
A serial schedule, although leaving the database in a consistent state, is inefficient.
However, a nonserial schedule, although improving efficiency, increasing through-
put, and reducing response times, still has the potential of leaving the database in
an inconsistent state. So the question is whether you can find an equivalent sched-
ule that will produce the same result as a serial schedule. This new schedule must
still be nonserial, to allow for concurrency of transaction execution, but behave like
a serial schedule. Such a schedule is known as a serializable schedule.
Serializability finds nonserial schedules that allow transactions to execute con-
currently without interference and leave the database in a consistent state as though
the transactions executed serially.
Serializable Schedule
Consider a schedule S of
n
transactions with interleaving
operations. Schedule S is defined to be serializable if it is equivalent to some serial
schedule of the same
n
transactions. Two schedules are equivalent if they produce
the same final state of the database. A serializable, complete schedule leaves the
database in a consistent state.
Figure 15-13 illustrates the equivalence between a given serializable schedule and
a serial schedule.
Ordering of Operations
In serializability, ordering of read and write operations
is important. Consider the following cases for two concurrent transactions, T1 and
T2:
•
If both T1 and T2 only read a specific data item, there is no conflict; therefore,
order of the operations is not important.
•
If T1 and T2 read or write completely different data items, there is no conflict;
therefore, order of the operations is not important.
•
If T1 writes a specific data item and T2 reads or writes the same data item,
conflict arises; therefore, order of the operations becomes important.
Forms of Equivalence
When two consecutive operations in a schedule belong-
ing to different transactions both operate on the same data item, and if at least one
of the two operations is a write, then the two operations are in conflict. Therefore,
Search WWH ::
Custom Search