Database transaction schedule: Difference between revisions

Revision as of 21:43, 15 March 2024

Latest revision as of 12:34, 28 May 2025

(7 intermediate revisions by 5 users not shown)

Line 5:

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)|executions]] 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. Often, only a subset of the transaction operation types are included in a schedule.

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

==Notation==

Line 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:

Line 535:

====Strict====

A schedule is '''strict''' 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 Classclass Relationshipsrelationships ==

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

Line 565:

[[Category:Transaction processing]]

[[Category:Distributed computing problems]]

[[Category:NP-complete problems]]