Database transaction schedule: Difference between revisions

Revision as of 08:18, 27 December 2023

Latest revision as of 12:34, 28 May 2025

(35 intermediate revisions by 8 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)|executionexecutions]] in a set of transactions running in the system. Often it is a ''list'' of operations (actions) ordered by time, performed by a set of [[Database transaction|transactions]] that are executed together in the system. If the order in time between certain operations is not determined by the system, then a ''[[partial order]]'' is used. Examples of such operations are requesting a read operation, reading, writing, aborting, [[Commit (data management)|committing]], requesting a [[Lock (computer science)|lock]], locking, etc. NotOften, all transaction operation types should be included inonly a schedule,subset andof typicallythe only selectedtransaction operation types (e.g., data access operations) are included, asin neededa to reason about and describe certain phenomenaschedule. Schedules and schedule properties are fundamental concepts in database [[concurrency control]] theory.

Schedules are fundamental concepts in database [[concurrency control]] theory. In practice, most general purpose database systems employ conflict-serializable and strict recoverable schedules.

==Formal description==

==Notation==

Grid notation:

* '''Columns:''' The different transactions in the schedule.

* '''Rows:''' The time order of operations (a.k.a., actions).

Operations (a.k.a., actions):

* '''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.

* '''W(X):''' The corresponding transaction "writes" to object X (i.e., it modifies the data stored at X). When the schedule is represented as a list rather than a grid, the action is represented as <math>Wi(X) </math> where <math>i</math> is a number corresponding to a specific transaction.

* '''Com.:''' This represents a "commit" operation in which the corresponding transaction has successfully completed its preceding actions, and has made all its changes permanent in the database.

Alternatively, a schedule can be represented with a ''[[acyclic directed graph|directed acyclic graph]]'' (or DAG) in which there is an arc (i.e., [[directed edge]]) between each ''[[ordered pair]]'' of operations.

=== Example ===

The following is an example of a schedule:

{| class="wikitable"

Line 50 ⟶ 63:

|Com.

|}

In this example, the horizontalcolumns axis representsrepresent the different transactions in the schedule D. The vertical axis represents time order of operations. Schedule D consists of three transactions T1, T2, T3. First TheT1 scheduleReads describesand theWrites actionsto ofobject theX, transactionsand asthen seenCommits. byThen theT2 Reads and Writes to object Y and Commits, and finally, T3 Reads and Writes to object Z and [[DBMS]]Commits.

First T1 Reads and Writes to object X, and then Commits. Then T2 Reads and Writes to object Y and Commits, and finally, T3 Reads and Writes to object Z and Commits. This is an example of a ''serial'' schedule, i.e., sequential with no overlap in time because the actions of all three transactions are sequential, and the transactions are not interleaved in time.

Representing the schedule D above by a table (rather than a list) is just for the convenience of identifying each transaction's operations in a glance. This notation is used throughout the article below. A more common way in the technical literature for representing such schedule is by a list:

:::D = R1(X) W1(X) Com1 R2(Y) W2(Y) Com2 R3(Z) W3(Z) Com3

The schedule D above can be represented as list in the following way:

Usually, for the purpose of reasoning about concurrency control in databases, an operation is modelled as ''[[Atomicity (database systems)|atomic]]'', occurring at a point in time, without duration. When this is not satisfactory, start and end time-points and possibly other point events are specified (rarely). Real executed operations always have some duration and specified respective times of occurrence of events within them (e.g., "exact" times of beginning and completion), but for concurrency control reasoning usually only the precedence in time of the whole operations (without looking into the quite complex details of each operation) matters, i.e., which operation is before, or after another operation. Furthermore, in many cases, the before/after relationships between two specific operations do not matter and should not be specified, while being specified for other pairs of operations.

D = R1(X) W1(X) Com1 R2(Y) W2(Y) Com2 R3(Z) W3(Z) Com3

In general, operations of transactions in a schedule can interleave (i.e., transactions can be executed concurrently), while time orders between operations in each transaction remain unchanged as implied by the transaction's program. Since not always time orders between all operations of all transactions matter and need to be specified, a schedule is, in general, a ''[[partial order]]'' between operations rather than a ''[[total order]]'' (where order for each pair is determined, as in a list of operations). Also in the general case, each transaction may consist of several processes, and itself be properly represented by a partial order of operations, rather than a total order. Thus, in general, a schedule is a partial order of operations, containing ([[embedding]]) the partial orders of all its transactions.

== Duration and order of actions ==

Time-order between two operations can be represented by an ''[[ordered pair]]'' of these operations (e.g., the existence of a pair (OP1, OP2) means that OP1 is always before OP2), and a schedule in the general case is a [[set (mathematics)|set]] of such ordered pairs. Such a set, a schedule, is a [[partial order]] which can be represented by an ''[[acyclic directed graph]]'' (or ''directed acyclic graph'', DAG) with operations as nodes and time-order as a [[directed edge]] (no cycles are allowed since a cycle means that a first (any) operation on a cycle can be both before and after (any) another second operation on the cycle, which contradicts our perception of [[Time]]). In many cases, a graphical representation of such a graph is used to demonstrate a schedule.

Usually, for the purpose of reasoning about concurrency control in databases, an operation is modelled as ''[[Atomicity (database systems)|atomic]]'', occurring at a point in time, without duration. Real executed operations always have some duration.

Operations of transactions in a schedule can interleave (i.e., transactions can be executed [[Concurrency (computer science)|concurrently]]), but time orders between operations in each transaction must remain unchanged. The schedule is in ''[[partial order]]'' when the operations of transactions in a schedule interleave (i.e., when the schedule is conflict-serializable but not serial). The schedule is in ''[[partial order|total order]]'' when the operations of transactions in a schedule do not interleave (i.e., when the schedule is serial).

'''Comment:''' Since a list of operations (and the table notation used in this article) always represents a total order between operations, schedules that are not a total order cannot be represented by a list (but always can be represented by a DAG).

==Types of schedule==

Line 70 ⟶ 79:

===Serial===

TheA transactionsschedule areis '''serial''' if the executed transactions are non-interleaved (i.e., a serial schedule is one in which no transaction starts until a running transaction has ended).

Schedule D is an example of a serial schedule:

Line 118 ⟶ 127:

===Serializable===<!-- This section is linked from [[Concurrency control]] -->

A schedule thatis '''serializable''' if it is equivalent (in its outcome) to a serial schedule. has the [[serializability]] property.

In schedule E, the order in which the actions of the transactions are executed is not the same as in D, but in the end, E gives the same result as D.

Line 156 ⟶ 165:

|Com.

|}

Serializability is used to keep the data in the data item in a consistent state. Serializability is a property of a [[Database transaction schedule|transaction schedule]] (history). 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. This partial order results from the scheduling orders of concurrent transactions' data access operations, which depend on many factors.

====Conflicting actions====

Line 176 ⟶ 185:

* R1(X), W2(Y), R3(X)

Reducing conflicts, such as through commutativity, enhances performance because conflicts are the fundamental cause of delays and aborts.

The conflict is '''materialized''' if the requested conflicting operation is actually executed: in many cases a requested/issued conflicting operation by a transaction is delayed and even never executed, typically by a [[Lock (computer science)|lock]] on the operation's object, held by another transaction, or when writing to a transaction's temporary private workspace and materializing, copying to the database itself, upon commit; as long as a requested/issued conflicting operation is not executed upon the database itself, the conflict is '''non-materialized'''; non-materialized conflicts are not represented by an edge in the precedence graph.

====Conflict equivalence====

Line 185 ⟶ 196:

Equivalently, two schedules are said to be conflict equivalent if and only if one can be transformed to another by swapping pairs of non-conflicting operations (whether adjacent or not) while maintaining the order of actions for each transaction.<ref name=":0" />

Equivalently, two schedules are said to be conflict equivalent if and only if one can be transformed to another by swapping pairs of non-conflicting adjacent operations with different transactions.<ref>{{Cite book |last=Garcia-Molina |first=Hector |title=Database systems: the complete book |last2=Ullman |first2=Jeffrey D. |last3=Widom |first3=Jennifer |date=2009 |publisher=Pearson/Prentice Hall |isbn=978-0-13-187325-4 |edition=2nd |series=Pearson international edition |___location=Upper Saddle River, NJ |pages=891-892891–892}}</ref>

====Conflict-serializable====

A schedule is said to be '''conflict-serializable''' when the schedule is conflict-equivalent to one or more serial schedules.

Equivalently, a schedule is conflict-serializable if and only if its [[precedence graph]] is acyclic when only committed transactions are considered. Note that if the graph is defined to also include uncommitted transactions, then cycles involving uncommitted transactions may occur without conflict serializability violation.

Line 218 ⟶ 229:

|Com.

|}

Conflict serializability can be enforced by restarting any transaction within the cycle in the precedence graph, or by implementing [[two-phase locking]], [[Timestamp-based concurrency control|timestamp ordering]], or [[Snapshot isolation#Workarounds|serializable snapshot isolation]].<ref name="Cahill082">Michael J. Cahill, Uwe Röhm, Alan D. Fekete (2008): [http://portal.acm.org/citation.cfm?id=1376690 "Serializable isolation for snapshot databases"], ''Proceedings of the 2008 ACM SIGMOD international conference on Management of data'', pp. 729-738, Vancouver, Canada, June 2008, {{ISBN|978-1-60558-102-6}} (SIGMOD 2008 best paper award)</ref>

====Commitment-order-serializable====

A schedule is said to be commitment-ordered (commit-ordered), or commitment-order-serializable, if it obeys the [[Commitment ordering]] (CO; also commit-ordering or commit-order-serializability) schedule property. This means that the order in time of transactions' commitment events is compatible with the precedence (partial) order of the respective transactions, as induced by their schedule's acyclic precedence graph (serializability graph, conflict graph). This implies that it is also conflict-serializable. The CO property is especially effective for achieving [[Global serializability]] in distributed systems.

'''Comment:''' [[Commitment ordering]], which was discovered in 1990, is obviously not mentioned in ([[#Bern1987|Bernstein et al. 1987]]). Its correct definition appears in ([[#Weikum2001|Weikum and Vossen 2001]]), however the description thereof its related techniques and theory is partial, inaccurate, and misleading.{{According to whom|date=December 2011}} For an extensive coverage of commitment ordering and its sources see ''[[Commitment ordering]]'' and ''[[The History of Commitment Ordering]]''.

====View equivalence====

Line 228 ⟶ 235:

Two schedules S1 and S2 are said to be view-equivalent when the following conditions are satisfied:

# If the transaction <math>T_i</math> in S1 reads an initial value for object X, so does the same transaction <math>T_i</math> in S2.

# If the transaction <math>T_i</math> in S1 reads thea value (for an object X) written by the transaction <math>T_j</math> in S1, forit objectmust X,do so does the transaction <math>T_i</math> in S2.

# If the transaction <math>T_i</math> in S1 isdoes the final transaction to write the value for an object X, so isdoes the same transaction <math>T_i</math> in S2.

Additionally, two view-equivalent schedules must involve the same set of transactions such that each transaction has the same actions in the same order.

In the example below, the schedules S1 and S2 are view-equivalent, but theyneither areS1 notnor S2 are view-equivalent to the schedule S3.

{| class="wikitable"

! colspan="2" |S1

!S1: T1

! colspan="2" |S2

!S1: T2

! colspan="2" |S3

!S2: T1

|-

!S2: T2

!S3: T1

!S3: T2

!T1

!T2

!T1

!T2

|-

|R(A)

Line 256 ⟶ 267:

|

|-

|R(B)^'''(1)'''

|R(B)

|

|

Line 272 ⟶ 283:

|Com.

|

|R(B)^'''(1)'''

|R(B)

|

|

|R(B)^'''(1)'''

|-

|

Line 288 ⟶ 299:

|Com.

|

|R(B)^'''(2)'''

|

|-

|

|R(B)^'''(2)'''

|R(B)

|

|R(B)^'''(2)'''

|R(B)

|W(B)^'''(3)'''

|

|-

|

|W(B)^'''(3)'''

|W(B)

|

|W(B)^'''(3)'''

|W(B)

|Com.

|

Line 312 ⟶ 323:

|Com.

|}

The conditions for S3 to be view-equivalent to S1 and equivalenceS2 were not satisfied at the corresponding superscripts for the following reasons:

# 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 381 ⟶ 392:

Since determining whether a schedule is view-serializable is [[NP-complete]], view-serializability has little practical interest.{{citation needed|date=April 2015}}

==== Relaxed serializability ====

'''Relaxed serializability''' allows controlled serializability violations in order to achieve higher performance. Higher performance means better transaction execution rate and shorter average transaction response time (transaction duration). Relaxed serializability is used when absolute correctness is not needed from recently modified data (such as when retrieving a list of products). ''[[Snapshot isolation]]'' is a common relaxed serializability method.

Relaxing distributed serializability is often necessary for efficient large-scale data [[Replication (computer science)|replication]] because using a single atomic [[distributed transaction]] for synchronizing multiple replicas is likely to have unavailable [[Computer|computers]] and [[Computer network|networks]] which would cause aborts.<ref name="Gray1996">{{cite conference |author=Gray, J. |author-link=Jim Gray (computer scientist) |author2=Helland, P. |author3=O’Neil, P. |author3-link=Patrick O'Neil |author4=Shasha, D. |author4-link=Dennis Shasha |year=1996 |title=The dangers of replication and a solution |url=ftp://ftp.research.microsoft.com/pub/tr/tr-96-17.pdf |conference=Proceedings of the 1996 [[ACM SIGMOD International Conference on Management of Data]] |pages=173–182 |doi=10.1145/233269.233330}}{{dead link|date=May 2018|bot=InternetArchiveBot|fix-attempted=yes}}</ref> [[Optimistic replication]] is a common distributed serializability relaxation method which compromises [[eventual consistency]].

Classes of schedules defined by ''relaxed serializability'' properties either contain the serializability class, or are incomparable with it.

===Recoverable===<!-- This section is linked from [[Concurrency control]] -->

Line 393 ⟶ 397:

In a '''recoverable schedule''', transactions only commit after all transactions whose changes they read have committed. A schedule becomes '''unrecoverable''' if a transaction <math>T_i</math> reads and relies on changes from another transaction <math>T_j</math>, and then <math>T_i</math> commits and <math>T_j</math> aborts.

{| class="wikitable"

! colspan="2" |F

!F: T1

! colspan="2" |F2

!F: T2

! colspan="2" |J

!F2: T1

|-

!F2: T2

!J: T1

!J: T2

!T1

!T2

!T1

!T2

|-

|R(A)

Line 444 ⟶ 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.

TransactionSchedule GJ is unrecoverable because T2 committed before T1 despite previously reading the value written by T1. Because T1 aborted after T2 committed, the value read by T2 is wrong. Because a transaction cannot be rolled-back after it commits, the schedule is unrecoverable.

====Cascadeless====

'''Cascadeless schedules''' (a.k.a,. "Avoiding Cascading Aborts (ACA) schedules") are schedules which avoid cascading aborts by disallowing [[Write–read conflict|dirty reads]]. '''Cascading aborts''' occur when one transaction's abort causes another transaction to abort because it read and relied on the first transaction's changes to an object. A '''dirty read''' occurs when a transaction reads data from uncommitted write in another transaction.<ref>{{Cite web |date=2019-08-06 |title=Cascadeless in DBMS |url=https://www.geeksforgeeks.org/cascadeless-in-dbms/ |access-date=2023-11-29 |website=GeeksforGeeks |language=en-US}}</ref>

The following examples are the same as the ones in the discussion on recoverable:

{| class="wikitable"

! colspan="2" |F

|+F & F2

! colspan="2" |F2

!F: T1

|-

!F: T2

!F2: T1

!F2: T2

!T1

!T2

|-

|R(A)

Line 525 ⟶ 535:

====Strict====

A schedule is '''strict - has the strictness property -''' if for any two transactions T1, T2, if a write operation of T1 precedes a ''conflicting'' operation of T2 (either read or write), then the commit or abort event of T1 also precedes that conflicting operation of T2. For example, the schedule F3 above is strict.

Any strict schedule is cascade-less, but not the converse. Strictness allows efficient recovery of databases from failure.

== Serializability class relationships ==

==Hierarchical relationship between serializability classes==

The following expressions illustrate the hierarchical (containment) relationships between [[serializability]] and [[Serializability#Correctness - recoverability|recoverability]] classes:

* Serial &sub; commitment-ordered &sub; conflict-serializable &sub; view-serializable &sub; all schedules

* Serial &sub; strict &sub; cascadeless (ACA) &sub; recoverable &sub; all schedules

Line 539 ⟶ 549:

[[File:Schedule-serializability.png|frame|none|Venn diagram for serializability and recoverability classes]]

==Practical implementations==

In practice, most general purpose database systems employ conflict-serializable and recoverable (primarily strict) schedules.

==See also==

* [[scheduleSchedule (project management)]]

* [[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]].

* [[Global serializability]], where the ''Global serializability problem'' and its proposed solutions are described.

* [[Linearizability]], a more general concept in [[concurrent computing]].

==References==

{{Reflist}}

*<cite id=Bern1987>[[Phil Bernstein|Philip A. Bernstein]], Vassos Hadzilacos, Nathan Goodman: [http://research.microsoft.com/en-us/people/philbe/ccontrol.aspx ''Concurrency Control and Recovery in Database Systems''], Addison Wesley Publishing Company, 1987, {{ISBN|0-201-10715-5}}</cite>

*<cite id=Weikum2001>[[Gerhard Weikum]], Gottfried Vossen: [http://www.elsevier.com/wps/find/bookdescription.cws_home/677937/description#description ''Transactional Information Systems''], Elsevier, 2001, {{ISBN|1-55860-508-8}}</cite>

[[Category:Data management]]

[[Category:Databases]]

[[Category:Concurrency control]]

[[Category:Transaction processing]]

[[Category:Distributed computing problems]]

[[Category:NP-complete problems]]