Content deleted Content added
→Hierarchical relationship between serializability classes: Fixed heading title |
m →Cascadeless: Typo fixing, replaced: a.k.a, → a.k.a. |
||
| (12 intermediate revisions by 5 users not shown) | |||
Line 3:
{{more citations needed|date=November 2012}}
In the fields of [[database]]s and [[transaction processing]] (transaction management), a '''schedule''' (or '''history''') of a system is an abstract model to describe the order of [[Execution (computing)|
Schedules ==Notation==
Line 10 ⟶ 12:
* '''Columns:''' The different transactions in the schedule.
* '''Rows:''' The time order of operations (a.k.a., actions).
Operations
* '''R(X):''' The corresponding transaction "reads" object X (i.e., it retrieves the data stored at X). This is done so that it can modify the data (e.g., X=X+4) during a "write" operation rather than merely overwrite it. When the schedule is represented as a list rather than a grid, the action is represented as <math>Ri(X)</math> where <math>i</math> is a number corresponding to a specific transaction.
Line 163 ⟶ 165:
|Com.
|}
Serializability is used to keep the data in the data item in a consistent state. It is the major criterion for the correctness of concurrent transactions' schedule, and thus supported in all general purpose database systems. Schedules that are not serializable are likely to generate erroneous outcomes; which can be extremely harmful (e.g., when dealing with money within banks).<ref name="Bernstein872">[[Phil Bernstein|Philip A. Bernstein]], Vassos Hadzilacos, Nathan Goodman (1987): [http://research.microsoft.com/en-us/people/philbe/ccontrol.aspx ''Concurrency Control and Recovery in Database Systems''] (free PDF download), Addison Wesley Publishing Company, {{ISBN|0-201-10715-5}}</ref><ref name="Weikum012">[[Gerhard Weikum]], Gottfried Vossen (2001): [http://www.elsevier.com/wps/find/bookdescription.cws_home/677937/description#description ''Transactional Information Systems''], Elsevier, {{ISBN|1-55860-508-8}}</ref><ref name="Herlihy1993">[[Maurice Herlihy]] and J. Eliot B. Moss. ''Transactional memory: architectural support for lock-free data structures.'' Proceedings of the 20th annual international symposium on Computer architecture (ISCA '93). Volume 21, Issue 2, May 1993.</ref>
If any specific order between some transactions is requested by an application, then it is enforced independently of the underlying serializability mechanisms. These mechanisms are typically indifferent to any specific order, and generate some unpredictable [[partial order]] that is typically compatible with multiple serial orders of these transactions
====Conflicting actions====
Line 325 ⟶ 323:
|Com.
|}
The conditions for S3 to be view-equivalent to S1 and
# Failed the first condition of view equivalence because T1 read the initial value for B in S1 and S2, but T2 read the initial value for B in S3.
# Failed the second condition of view equivalence because T2 read the value written by T1 for B in S1 and S2, but T1 read the value written by T2 for B in S3.
# Failed the third condition of view equivalence because T2 did the final write for B in S1 and S2, but T1 did the final write for B in S3.
To quickly analyze whether two schedules are view-equivalent, write both schedules as a list with each action's subscript representing which view-equivalence condition they match. The schedules are view equivalent if and only if all the actions have the same subscript (or lack thereof) in both schedules:
Line 454 ⟶ 452:
These schedules are recoverable. The schedule F is recoverable because T1 commits before T2, that makes the value read by T2 correct. Then T2 can commit itself. In the F2 schedule, if T1 aborted, T2 has to abort because the value of A it read is incorrect. In both cases, the database is left in a consistent state.
====Cascadeless====
'''Cascadeless schedules''' (a.k.a
The following examples are the same as the ones in the discussion on recoverable:
Line 537 ⟶ 535:
====Strict====
A schedule is '''strict
Any strict schedule is cascade-less, but not the converse. Strictness allows efficient recovery of databases from failure.
== Serializability
The following expressions illustrate the hierarchical (containment) relationships between [[serializability]] and [[Serializability#Correctness - recoverability|recoverability]] classes:
Line 553 ⟶ 551:
==See also==
* [[
* [[Two-phase locking|Strong strict two-phase locking]] (SS2PL or Rigorousness).
* [[Snapshot isolation#Making Snapshot Isolation Serializable|Making snapshot isolation serializable]]<ref name="Cahill082"/> in [[Snapshot isolation]].
Line 561 ⟶ 559:
==References==
{{Reflist}}
[[Category:Data management]]
Line 570 ⟶ 565:
[[Category:Transaction processing]]
[[Category:Distributed computing problems]]
[[Category:NP-complete problems]]
| |||