Database transaction schedule: Difference between revisions

Revision as of 07:16, 5 March 2024

Latest revision as of 12:34, 28 May 2025

(18 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)|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. AIn schedulepractice, describesmost thegeneral orderpurpose ofdatabase actionssystems ofemploy theconflict-serializable transactionsand asstrict seenrecoverable by the [[DBMS]]schedules.

==Notation==

Line 10 ⟶ 12:

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

Line 125 ⟶ 127:

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

A schedule is '''serializable''' if it is equivalent (in its outcome) to a serial schedule.

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 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. This partial order results from the scheduling orders of concurrent transactions' data access operations, which depend on many factors.

Serializability is used in concurrency control of databases,<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> transaction processing (transaction management), and various [[Database transaction|transactional]] applications (e.g., [[transactional memory]]<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> and [[software transactional memory]]). Serializability is considered the highest level of [[Isolation (database systems)|isolation]] between [[Database transaction|transactions]], and plays an essential role in [[concurrency control]].

'''Serializability theory''' provides the formal framework to reason about and analyze serializability and its techniques.

====Conflicting actions====

Line 237 ⟶ 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

!S1: T1

!S1: T2

!S2: T1

!S2: T2

|-

|R(A)

Line 265 ⟶ 267:

|

|-

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

|R(B)

|

|

Line 281 ⟶ 283:

|Com.

|

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

|R(B)

|

|

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

|-

|

Line 297 ⟶ 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 321 ⟶ 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 390 ⟶ 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]]s 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.

==== Distributed serializability ====

'''Distributed serializability''' is the serializability of a schedule of a transactional [[Distributed computing|distributed system]] (e.g., a [[distributed database]] system). Such a system is characterized by ''[[distributed transaction]]s'' (also called ''global transactions''), i.e., transactions that span computer processes (a process abstraction in a general sense, depending on computing environment; e.g., [[operating system]]'s [[Thread (computer science)|thread]]) and possibly network nodes. A distributed transaction comprises more than one of several ''local sub-transactions'' that each has states as described above for a [[database transaction]]. A local sub-transaction comprises a single process, or more processes that typically fail together (e.g., in a single [[processor core]]). Distributed transactions imply a need for an [[atomic commit]] protocol to reach consensus among its local sub-transactions on whether to commit or abort. Such protocols can vary from a simple (one-phase) handshake among processes that fail together to more sophisticated protocols, like [[Two-phase commit protocol|two-phase commit]], to handle more complicated cases of failure (e.g., process, node, communication, etc. failure). Distributed serializability is a major goal of [[distributed concurrency control]] for correctness. With the proliferation of the [[Internet]], [[cloud computing]], [[grid computing]], and small, portable, powerful computing devices (e.g., [[smartphone]]s,) the need for effective distributed serializability techniques to ensure correctness in and among distributed applications seems to increase.

Distributed serializability is achieved by implementing distributed versions of the known centralized techniques.<ref name="Bernstein872"/><ref name="Weikum012"/> Typically, all such distributed versions require utilizing conflict information (of either materialized or non-materialized conflicts, or, equivalently, transaction precedence or blocking information; conflict serializability is usually utilized) that is not generated locally, but rather in different processes, and remote locations. Thus information distribution is needed (e.g., precedence relations, lock information, timestamps, or tickets). When the distributed system is of a relatively small scale and message delays across the system are small, the centralized concurrency control methods can be used unchanged while certain processes or nodes in the system manage the related algorithms. However, in a large-scale system (e.g., ''grid'' and ''cloud''), due to the distribution of such information, a substantial performance penalty is typically incurred, even when distributed versions of the methods (vs. the centralized ones) are used, primarily due to computer and communication [[Latency (engineering)|latency]]. Also, when such information is distributed, related techniques typically do not scale well. A well-known example with respect to scalability problems is a [[distributed lock manager]], which distributes lock (non-materialized conflict) information across the distributed system to implement locking techniques.

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

Line 407 ⟶ 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

!F: T1

!F: T2

!F2: T1

!F2: T2

|-

|R(A)

Line 458 ⟶ 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 J 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

!F: T1

!F: T2

|-

|R(A)

Line 539 ⟶ 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 553 ⟶ 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]].

Line 567 ⟶ 559:

==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]]

Line 576 ⟶ 565:

[[Category:Transaction processing]]

[[Category:Distributed computing problems]]

[[Category:NP-complete problems]]