Information AboutSerializability |
| CATEGORIES ABOUT SERIALIZABILITY | |
| data management | |
| databases | |
| concurrency control | |
| transaction processing | |
|
''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 System s. The rationale behind it is the following: If each transaction is correct, than a serial execution of these transaction is correct. As a result, any execution that is equivalent (in its outcome) to such serial execution, is correct. Schedules that are not serializable are likely to generate erronous 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 being generated from nowhere. This is caused by one transaction writing, and "stepping on" and erasing what have been writen by another transaction. This does not happen if serializability is maintained. 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). In many applications, unlike with finances, absolute correctness is not needed. For example, when retrieving a list of products according to specification it is not a disaster if a product, that its data was updated a short time ago, will not appear in the list, even if it meets the specification. It probably will appear in such a list when tried a short time later. Commercial databases provide a whole range of concurrency control with (controlled) serializability violations in order to achieve higher concurrency of transactions when possible. Higher concurrency means better performance, shorter transaction response time (transaction duration), and higher availability of the data in the database to users. Two major types of serializability exist: ''Conflict serializability'', and ''View serializability''. The class of schedules with the latter property contains the class of the first, however, conflict serializability is easier to achieve, and is widely utilized. 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. '' (Strong) Strict Two Phase Locking '' (SS2PL) is a common mechanism (and schedule property) utilized to enforce serializability in database systems. The related schedule property is also referred to as ''rigorousness''. Practically it means that all locked resources on behalf of a transaction are released only after the transaction has ended (either committed or aborted). 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 CO algorithm can run beside any concurrency control mechanism (serializability enforcing mechanism) without interfering with its resource access scheduling strategy. With the CO 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. SS2PL implies Commitment ordering, and SS2PL compliant databases can participate in multidatabase systems that utilize CO. |
|
|