Serializability
Encyclopedia : S : SE : SER : Serializability
In databases and transaction processing, serializability is the property of a schedule (history) being serializable. It means equivalence (in its outcome, the resulting database state) to a serial schedule (serial schedule: No overlap in two transactions' execution time intervals; consecutive transaction execution). It relates to the isolation property of a transaction, and plays an essential role in concurrency control.
Correctness - Serializability
Serializability is the major criterion for the correctness of concurrent transactions' executions (i.e., transactions that have overlapping execution time intervals, and possibly access same shared resources), and a major goal for concurrency control. As such it is supported in all general purpose database systems. The rationale behind it is the following: If each transaction is correct by itself, then any serial execution of these transactions is correct. As a result, any execution that is equivalent (in its outcome) to a serial execution, is correct.
Schedules that are not serializable are likely to generate erroneous outcomes. Well known examples are with transactions that debit and credit accounts with money. If the related schedules are not serializable, then the total sum of money may not be preserved. Money could disappear, or be generated from nowhere. This is caused by one transaction writing, and "stepping on" and erasing what has been written by another transaction. This does not happen if serializability is maintained.
Correctness - Recoverability
In systems where transactions can abort (virtually all real systems), serializability by itself is not sufficient for correctness. Schedules also need to possess the Recoverability property. Recoverability means that committed transactions do not read data written by aborted transactions (whose effects do not exist in the resulting database states). While serializability can be compromised in many applications, compromising recoverability always violates the database's integrity.
Relaxing serializability
In many applications, unlike with finances, absolute correctness is not needed. For example, when retrieving a list of products according to specification, in most cases it does not matter much if a product, whose data was updated a short time ago, does not appear in the list, even if it meets the specification. It will probably appear in such a list when tried again a short time later. Commercial databases provide concurrency control with a whole range of (controlled) serializability violations (see isolation levels) in order to achieve higher concurrency of transactions, when the application can tolerate this. Higher concurrency means better performance, shorter transaction response time (transaction duration), and higher availability of the data in the database to users.
View serializability and Conflict serializability
Two major types of serializability exist: View serializability, and Conflict serializability. Any schedule with the latter property also has the first property. However, conflict serializability is easier to achieve, and is widely utilized.
View serializability of a schedule is define by equivalence to a serial schedule with the same transactions, such that respective transactions in the two schedules read and write the same data values ("view" the same data values).
Conflict serializability is defined by equivalence to a serial schedule with the same transactions, such that both schedules have the same sets of respective ordered (by time) pairs of conflicting operations (same precedence relations of respective conflicting operations). Two operations (read or write) are conflicting if they are of different transactions, upon the same data item, and at least one of them is write. A more general definition of conflicting operations (also for complex operations, which may consist each of several "simple" read/write operations) requires that they are noncommutative (changing their order also changes their combined result).
Testing conflict serializability
Schedule compliance with Conflict serializability can be tested as follows: The Conflict graph (Serializability graph) of the schedule, the directed graph representing precedence of transactions in the schedule, as reflected by precedence of conflicting operations in the transactions (transactions are nodes, precedence relations are directed edges), needs to be acyclic.
Common mechanism - (Strong) Strict Two Phase Locking
(Strong) Strict Two Phase Locking (SS2PL) is a common mechanism (and schedule property) utilized to enforce both conflict serializability and Strictness, a special case of recoverability, in database systems. The related schedule property is also referred to as Rigorousness. In this mechanism each data item is locked by a transaction before accessing it (any read or modify operation): The item is marked by a lock type, depending on operation. Access by another transaction may be blocked, typically upon conflict, depending on lock type and the other transaction's access operation type. All locked data on behalf of a transaction are released only after the transaction has ended (either committed or aborted).
Global serializability - Commitment ordering
Enforcing global serializability in a multidatabase system (typically distributed), where transactions span multiple databases, is problematic, since even if each database enforces serializability, the global schedule of all the databases is not necessarily serializable. An effective way to enforce conflict serializability globally in such a system is to enforce the Commitment ordering (CO, or Commit-order-serializability) property in each database. CO is a special case of conflict serializability, and if enforced locally in each database, also the global schedule possesses this property (CO). An effective local (to any single database) CO algorithm can run beside any local concurrency control mechanism (serializability enforcing mechanism) without interfering with its resource access scheduling strategy. As such CO is also a solution to a heterogeneous environment with different database system types that may employ different serializability mechanisms.
SS2PL implies Commitment ordering, and any SS2PL compliant database can participate in multidatabase systems that utilize CO without any modification or addition of a CO algorithm component.
With the Commitment ordering property the precedence order of transactions' commitment events is identical to the precedence (partial) order of the respective transactions, as determined by their schedule's (acyclic) conflict graph. The commitment events are generated by an atomic commitment protocol. Any conflict serializable schedule can be made a CO compliant one, without aborting any transaction in the schedule, by delaying commitment events to comply with the needed partial order.
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.