Serializability is a concept of database theory for handling
concurrent transactions. You don't have to understand
it to use locks well, but in case you want to know a little
more background: A schedule of concurrent
transactions is called serializeable if there exists an
equivalent, serial schedule of the same transactions. In other
words: the schedules are serializable if the operations
of all transactions can be reordered in such a way that
afterwards the transactions can be executed completely one after
another. If a schedule is serializable, it is correct (i.e.
maintains the ACID principles) and all transactions of the schedule
can commit. If a schedule is not serializable, the schedule might
be incorrect and at least one transaction has to be aborted.
There exist various definitions for the above mentioned
equivalence of two schedules. Depending on
which definition is chosen, different kinds of serializability arise:
- State serializability
-
Based on state equivalence; Two schedules are state-equivalent if
for all possible start states both schedules reach a common
end state.
-
View serializability
-
Based on view equivalence; Two schedules are view-equivalent if
they are state-equivalent and all read operations in
both schedules read the value written by the same write operation
(i.e. they see the same view of the data). Please note that if
both schedules write all used data at their beginning and read all
changed data at the end, state equivalence is enforced implicitly
and then doesn't have to be demanded in the view equivalence
definition.
-
Conflict serializability
-
Based on conflict equivalence; Two schedules are
conflict-equivalent if the order of all conflicting operations of
concurrent transactions is the same in both. Normally a read and a
write operations on the same data conflict with each other as well
as two write operations.
It can be shown that a subset relationship exists between the
sets of schedules which fulfill these three serializability criteria:
The conflict-serializable schedules are a subset of the
view-serializable schedules, which are a subset of the
state-serializable schedules, which in turn are a subset of all
correct schedules. So it would be best to test for state
serializability since that would allow the most concurrency. Alas
it can also be shown that checking for state serializability and view
serializability is NP-complete. For this reason all commercial
RDBMSs use AFAIK conflict serializability which can be
enforced by two-phase locking with read and write locks.