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

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]

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 (Bernstein et al. 1987). Its correct definition appears in (Weikum and Vossen 2001), however the description thereof its related techniques and theory is partial, inaccurate, and misleading. For an extensive coverage of commitment ordering and its sources see Commitment ordering and The History of Commitment Ordering.

View equivalence

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

1. If the transaction ${\displaystyle T_{i}}$ in S1 reads an initial value for object X, so does the transaction ${\displaystyle T_{i}}$ in S2.
2. If the transaction ${\displaystyle T_{i}}$ in S1 reads the value written by transaction ${\displaystyle T_{j}}$ in S1 for object X, so does the transaction ${\displaystyle T_{i}}$ in S2.
3. If the transaction ${\displaystyle T_{i}}$ in S1 is the final transaction to write the value for an object X, so is the transaction ${\displaystyle T_{i}}$ 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 they are not view-equivalent to S3.

The conditions for view equivalence 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, 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, 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, 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.

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:

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.

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 because using a single atomic distributed transaction for synchronizing multiple replicas is likely to have unavailable computers and networks which would cause aborts.^[9] 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 system (e.g., a distributed database system). Such a system is characterized by distributed transactions (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) 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, 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., smartphones,) 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.^[10][11] 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. 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.

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

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

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).

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

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