Database transaction schedule

Last updated

In the fields of databases and transaction processing (transaction management), a schedule (or history) of a system is an abstract model to describe the order of 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 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, committing, requesting a lock, locking, etc. Often, only a subset of the transaction operation types are included in a schedule.

Contents

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

Notation

Grid notation:

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

Alternatively, a schedule can be represented with a 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:

D
T1T2T3
R(X)
W(X)
Com.
R(Y)
W(Y)
Com.
R(Z)
W(Z)
Com.

In this example, the columns represent the different transactions in the schedule D. Schedule D consists of three transactions T1, T2, T3. 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.

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

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

Duration and order of actions

Usually, for the purpose of reasoning about concurrency control in databases, an operation is modelled as 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 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 total order when the operations of transactions in a schedule do not interleave (i.e., when the schedule is serial).

Types of schedule

A complete schedule is one that contains either an abort (a.k.a. rollback) or commit action for each of its transactions. A transaction's last action is either to commit or abort. To maintain atomicity, a transaction must undo all its actions if it is aborted.

Serial

A schedule is 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:

D
T1T2T3
R(X)
W(X)
Com.
R(Y)
W(Y)
Com.
R(Z)
W(Z)
Com.

Serializable

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.

E
T1T2T3
R(X)
R(Y)
R(Z)
W(X)
W(Y)
W(Z)
Com.Com.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). [1] [2] [3]

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

Two actions are said to be in conflict (conflicting pair) if and only if all of the 3 following conditions are satisfied:

  1. The actions belong to different transactions.
  2. At least one of the actions is a write operation.
  3. The actions access the same object (read or write). [4] [5]

Equivalently, two actions are considered conflicting if and only if they are noncommutative. Equivalently, two actions are considered conflicting if and only if they are a read-write, write-read, or write-write conflict.

The following set of actions is conflicting:

  • R1(X), W2(X), W3(X) (3 conflicting pairs)

While the following sets of actions are not conflicting:

  • R1(X), R2(X), R3(X)
  • 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 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

The schedules S1 and S2 are said to be conflict-equivalent if and only if both of the following two conditions are satisfied:

  1. Both schedules S1 and S2 involve the same set of transactions such that each transaction has the same actions in the same order.
  2. Both schedules have the same set of conflicting pairs (such that the actions in each conflicting pair are in the same order). [6] This is equivalent to requiring that all conflicting operations (i.e., operations in any conflicting pair) are in the same order in both schedules.

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

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

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.

The schedule K is conflict-equivalent to the serial schedule <T1,T2>, but not <T2,T1>.

K
T1T2
R(A)
R(A)
W(B)
Com.
W(A)
Com.

Conflict serializability can be enforced by restarting any transaction within the cycle in the precedence graph, or by implementing two-phase locking, timestamp ordering, or serializable snapshot isolation. [8]

View equivalence

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

  1. If the transaction in S1 reads an initial value for object X, so does the same transaction in S2.
  2. If the transaction reads a value (for an object X) written by the transaction in S1, it must do so S2.
  3. If the transaction in S1 does the final write for object X, so does the same transaction 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 neither S1 nor S2 are view-equivalent to the schedule S3.

S1S2S3
T1T2T1T2T1T2
R(A)R(A)R(A)
W(A)W(A)W(A)
R(B)(1)R(A)R(A)
W(B)W(A)W(A)
Com.R(B)(1)R(B)(1)
R(A)W(B)W(B)
W(A)Com.R(B)(2)
R(B)(2)R(B)(2)W(B)(3)
W(B)(3)W(B)(3)Com.
Com.Com.Com.

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

  1. 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.
  2. 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.
  3. 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:

  • S1: R1(A)initial read, W1(A), R1(B)initial read, W1(B), Com1, R2(A)written by T1, W2(A)final write, R2(B)written by T1, W2(B)final write, Com2
  • S2: R1(A)initial read, W1(A), R2(A)written by T1, W2(A)final write, R1(B)initial read, W1(B), Com1, R2(B)written by T1, W2(B)final write, Com2
  • S3: R1(A)initial read, W1(A), R2(A)written by T1, W2(A)final write, R2(B)initial read, W2(B), R1(B)written by T2, W1(B)final write, Com1, Com2

View-serializable

A schedule is view-serializable if it is view-equivalent to some serial schedule. Note that by definition, all conflict-serializable schedules are view-serializable.

G
T1T2
R(A)
R(A)
W(B)

Notice that the above example (which is the same as the example in the discussion of conflict-serializable) is both view-serializable and conflict-serializable at the same time. There are however view-serializable schedules that are not conflict-serializable: those schedules with a transaction performing a blind write:

H
T1T2T3
R(A)
W(A)
Com.
W(A)
Com.
W(A)
Com.

The above example is not conflict-serializable, but it is view-serializable since it has a view-equivalent serial schedule <T1,| T2,| T3>.

Since determining whether a schedule is view-serializable is NP-complete, view-serializability has little practical interest.[ citation needed ]

Recoverable

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

FF2J
T1T2T1T2T1T2
R(A)R(A)R(A)
W(A)W(A)W(A)
R(A)R(A)R(A)
W(A)W(A)W(A)
Com.AbortCom.
Com.AbortAbort

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.

Schedule 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 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. [9]

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

FF2
T1T2T1T2
R(A)R(A)
W(A)W(A)
R(A)R(A)
W(A)W(A)
Com.Abort
Com.Abort

In this example, although F2 is recoverable, it does not avoid cascading aborts. It can be seen that if T1 aborts, T2 will have to be aborted too in order to maintain the correctness of the schedule as T2 has already read the uncommitted value written by T1.

The following is a recoverable schedule which avoids cascading abort. Note, however, that the update of A by T1 is always lost (since T1 is aborted).

F3
T1T2
R(A)
R(A)
W(A)
W(A)
Abort
Commit

Note that this Schedule would not be serializable if T1 would be committed. Cascading aborts avoidance is sufficient but not necessary for a schedule to be recoverable.

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 Class Relationships

The following expressions illustrate the hierarchical (containment) relationships between serializability and recoverability classes:

The Venn diagram (below) illustrates the above clauses graphically.

Venn diagram for serializability and recoverability classes Schedule-serializability.png
Venn diagram for serializability and recoverability classes

See also

Related Research Articles

In computer science, ACID is a set of properties of database transactions intended to guarantee data validity despite errors, power failures, and other mishaps. In the context of databases, a sequence of database operations that satisfies the ACID properties is called a transaction. For example, a transfer of funds from one bank account to another, even involving multiple changes such as debiting one account and crediting another, is a single transaction.

In computer science, particularly the field of databases, the Thomas write rule is a rule in timestamp-based concurrency control. It can be summarized as ignore outdated writes.

In computer science, a timestamp-based concurrency control algorithm is a optimistic concurrency control method. It is used in some databases to safely handle transactions using timestamps.

In information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while getting those results as quickly as possible.

In computer science, in the field of databases, write–read conflict, is a computational anomaly associated with interleaved execution of transactions. Specifically, a write–read conflict occurs when "a transaction requests to write an entity, for which an unclosed transaction has already made a read request."

In computer science, in the field of databases, write–write conflict, also known as overwriting uncommitted data is a computational anomaly associated with interleaved execution of transactions. Specifically, a write–write conflict occurs when "transaction requests to write an entity for which an unclosed transaction has already made a write request."

In computer science, in the field of databases, read–write conflict, also known as unrepeatable reads, is a computational anomaly associated with interleaved execution of transactions. Specifically, a read–write conflict occurs when a "transaction requests to read an entity for which an unclosed transaction has already made a write request."

Multiversion concurrency control, is a non-locking concurrency control method commonly used by database management systems to provide concurrent access to the database and in programming languages to implement transactional memory.

A database transaction symbolizes a unit of work, performed within a database management system against a database, that is treated in a coherent and reliable way independent of other transactions. A transaction generally represents any change in a database. Transactions in a database environment have two main purposes:

  1. To provide reliable units of work that allow correct recovery from failures and keep a database consistent even in cases of system failure. For example: when execution prematurely and unexpectedly stops in which case many operations upon a database remain uncompleted, with unclear status.
  2. To provide isolation between programs accessing a database concurrently. If this isolation is not provided, the programs' outcomes are possibly erroneous.

In databases and transaction processing, two-phase locking (2PL) is a pessimistic concurrency control method that guarantees conflict-serializability. It is also the name of the resulting set of database transaction schedules (histories). The protocol uses locks, applied by a transaction to data, which may block other transactions from accessing the same data during the transaction's life.

In database systems, isolation is one of the ACID transaction properties. It determines how transaction integrity is visible to other users and systems. A lower isolation level increases the ability of many users to access the same data at the same time, but also increases the number of concurrency effects users might encounter. Conversely, a higher isolation level reduces the types of concurrency effects that users may encounter, but requires more system resources and increases the chances that one transaction will block another.

<span class="mw-page-title-main">Linearizability</span> Property of some operation(s) in concurrent programming

In concurrent programming, an operation is linearizable if it consists of an ordered list of invocation and response events, that may be extended by adding response events such that:

  1. The extended list can be re-expressed as a sequential history.
  2. That sequential history is a subset of the original unextended list.

In computer science, software transactional memory (STM) is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. It is an alternative to lock-based synchronization. STM is a strategy implemented in software, rather than as a hardware component. A transaction in this context occurs when a piece of code executes a series of reads and writes to shared memory. These reads and writes logically occur at a single instant in time; intermediate states are not visible to other (successful) transactions. The idea of providing hardware support for transactions originated in a 1986 paper by Tom Knight. The idea was popularized by Maurice Herlihy and J. Eliot B. Moss. In 1995, Nir Shavit and Dan Touitou extended this idea to software-only transactional memory (STM). Since 2005, STM has been the focus of intense research and support for practical implementations is growing.

Nonimaging optics is a branch of optics that is concerned with the optimal transfer of light radiation between a source and a target. Unlike traditional imaging optics, the techniques involved do not attempt to form an image of the source; instead an optimized optical system for optimal radiative transfer from a source to a target is desired.

Commitment ordering (CO) is a class of interoperable serializability techniques in concurrency control of databases, transaction processing, and related applications. It allows optimistic (non-blocking) implementations. With the proliferation of multi-core processors, CO has also been increasingly utilized in concurrent programming, transactional memory, and software transactional memory (STM) to achieve serializability optimistically. CO is also the name of the resulting transaction schedule (history) property, defined in 1988 with the name dynamic atomicity. In a CO compliant schedule, the chronological order of commitment events of transactions is compatible with the precedence order of the respective transactions. CO is a broad special case of conflict serializability and effective means to achieve global serializability across any collection of database systems that possibly use different concurrency control mechanisms.

In databases, and transaction processing, snapshot isolation is a guarantee that all reads made in a transaction will see a consistent snapshot of the database, and the transaction itself will successfully commit only if no updates it has made conflict with any concurrent updates made since that snapshot.

A precedence graph, also named conflict graph and serializability graph, is used in the context of concurrency control in databases. It is the directed graph representing precedence of transactions in the schedule, as reflected by precedence of conflicting operations in the transactions. A schedule is conflict-serializable if and only if its precedence graph of committed transactions is acyclic.

<span class="mw-page-title-main">Wait-for graph</span>

A wait-for graph in computer science is a directed graph used for deadlock detection in operating systems and relational database systems.

A quorum is the minimum number of votes that a distributed transaction has to obtain in order to be allowed to perform an operation in a distributed system. A quorum-based technique is implemented to enforce consistent operation in a distributed system.

<span class="mw-page-title-main">Six-rays model</span> Mathematical model

The six-rays model is applied in an urban or indoor environment where a radio signal transmitted will encounter some objects that produce reflected, refracted or scattered copies of the transmitted signal. These are called multipath signal components, they are attenuated, delayed and shifted from the original signal (LOS) due to a finite number of reflectors with known location and dielectric properties, LOS and multipath signal are summed at the receiver.

References

  1. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman (1987): Concurrency Control and Recovery in Database Systems (free PDF download), Addison Wesley Publishing Company, ISBN   0-201-10715-5
  2. Gerhard Weikum, Gottfried Vossen (2001): Transactional Information Systems, Elsevier, ISBN   1-55860-508-8
  3. 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.
  4. 1 2 "Conflict Serializability in DBMS". GeeksforGeeks. 2015-12-29. Retrieved 2023-11-27.
  5. Silberschatz, Abraham; Korth, Henry F.; Sudarshan, S. (2020). Database system concepts (Seventh ed.). New York, NY: McGraw-Hill Education. p. 814. ISBN   978-1-260-08450-4.
  6. Ramakrishnan, Raghu; Gehrke, Johannes (2000). Database management systems. Computer science series (2nd ed.). Boston: McGraw-Hill. p. 540. ISBN   978-0-07-232206-4.
  7. Garcia-Molina, Hector; Ullman, Jeffrey D.; Widom, Jennifer (2009). Database systems: the complete book. Pearson international edition (2nd ed.). Upper Saddle River, NJ: Pearson/Prentice Hall. pp. 891–892. ISBN   978-0-13-187325-4.
  8. 1 2 Michael J. Cahill, Uwe Röhm, Alan D. Fekete (2008): "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)
  9. "Cascadeless in DBMS". GeeksforGeeks. 2019-08-06. Retrieved 2023-11-29.