Schedule (computer science)

In the field of databases, a schedule is a list of actions, (i.e. reading, writing, aborting, committing), from a set of transactions.

Here is a sample schedule:

<math>D = \begin{bmatrix}

T1 & T2 & T3 \\ R(X) & & \\ W(X) & & \\ Com. & & \\

& R(Y) & \\
& W(Y) & \\
& Com. & \\
&& R(Z) \\
&& W(Z) \\
&& Com. \end{bmatrix}<math>

In this example, Schedule D is the set of 3 transactions T1, T2, T3. The schedule describes the actions of the transactions as seen by the DBMS. T1 Reads and writes to object X, and then T2 Reads and writes to object Y, and finally T3 Reads and writes to object Z. This is an example of a serial schedule, because the actions of the 3 transactions are not interleaved.

Contents

1 Types of Schedule 1.1 Serial 1.2 Serializable 1.3 Recoverable 1.4 Unrecoverable 1.5 Avoids Cascading Aborts (Cascading Rollbacks) 1.6 Conflicting Actions 1.7 Conflict Equivalence 1.8 Conflict Serializable 1.9 View Equivalence 1.10 View Serializable 2 Hierarchical Relationship between Serializability Classes 3 Practical Implementations

Types of Schedule

Serial

The transactions are executed one by one, non-interleaved. (see above)

Serializable

A schedule that is equivalent to a serial schedule.

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

<math>E = \begin{bmatrix}

T1 & T2 & T3 \\ R(X) & & \\

  & R(Y) & \\
&& R(Z) \\

W(X) & & \\

& W(Y) & \\
&& W(Z) \\

Com. & Com. & Com. \end{bmatrix}<math>

Recoverable

Transactions commit only after all transactions whose changes they read commit.

<math>F = \begin{bmatrix}

T1 & T2 \\ R(A) & \\ W(A) & \\

& R(A) \\
& W(A) \\

Com. & \\

& Com.\\
&\end{bmatrix} 

F2 = \begin{bmatrix} T1 & T2 \\ R(A) & \\ W(A) & \\

& R(A) \\
& W(A) \\

Abort & \\ & Abort \\

&\end{bmatrix}<math>

These schedules are recoverable. F is recoverable because T1 commits before T2, that makes the value read by T2 correct. Then T2 can commit itself. In F2, 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.

Unrecoverable

If a transaction T1 aborts, and a transaction T2 commits, but T2 relied on T1, we have an unrecoverable schedule.

<math>G = \begin{bmatrix}

T1 & T2 \\ R(A) & \\ W(A) & \\

& R(A) \\
& W(A) \\
& Com. \\

Abort & \\

&\end{bmatrix}<math>

In this example, G is unrecoverable, because T2 read the value of A written by T1, and committed. T1 later aborted, therefore the value read by T2 is wrong, but since T2 committed, this schedule is unrecoverable.

Avoids Cascading Aborts (Cascading Rollbacks)

If a transaction aborts, it doesn't cause other transactions to abort. Note that all schedules which avoid cascading aborts are also recoverable.

Strategy to prevent cascading aborts is to disallow a transaction from reading uncommitted changes from another transaction in the same schedule.

The following examples are the same as the one from the discussion on recoverable:

<math>F = \begin{bmatrix}

T1 & T2 \\ R(A) & \\ W(A) & \\

& R(A) \\
& W(A) \\

Com. & \\

& Com.\\
&\end{bmatrix} 

F2 = \begin{bmatrix} T1 & T2 \\ R(A) & \\ W(A) & \\

& R(A) \\
& W(A) \\

Abort & \\ & Abort \\

&\end{bmatrix}<math>

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.

<math>F3 = \begin{bmatrix}

T1 & T2 \\

& R(A) \\

R(A) & \\ W(A) & \\

& W(A) \\

Abort & \\ & Commit \\

&\end{bmatrix}<math>

Cascading aborts avoidance is sufficient but not necessary for a schedule to be recoverable.

Conflicting Actions

Two or more actions are said to be conflict if:

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

The following set of actions is conflicting:

• T1:R(X), T2:W(X), T1:W(X)

While the following sets of actions are not:

• T1:R(X), T2:R(X), T3:R(X)
• T1:R(X), T2:W(Y), T3:R(X)

Conflict Equivalence

The schedule T1 and T2 are said to be conflict equivalent of the following conditions are satisfied:

1. Both schedules T1 and T2 involve the same set of actions in the same set of transactions. (informally speaking, both schedules are containing and working on the same thing)
2. The order of each pair of conflicting actions in T1 and T2 are the same.

Conflict Serializable

A schedule is said to be Conflict Serializable when the schedule is Conflict Equivalent to one or more serial schedule.

Another definition for Conflict Serializable is that a schedule is Conflict Serializable if and only if there exist an acyclic precedence graph/serializability graph for the schedule.

<math>G = \begin{bmatrix}

T1 & T2 \\ R(A) & \\

& R(A) \\

W(B) & \\ Com. & \\

& W(A) \\
& Com. \\
&\end{bmatrix}<math>

Which is conflict equivalent to the serial schedule <T1,T2>

View Equivalence

Two schedule S1 and S2 are said to be View Equivalent when the following conditions are satisfied:

1. If the transaction <math>T_i<math> in S1 reads an initial value for object X, so does the transaction <math>T_i<math> in S2.
2. If the transaction <math>T_i<math> in S1 reads the value written by transaction <math>T_j<math> in S1 for object X, so does the transaction <math>T_i<math> in S2.
3. If the transaction <math>T_i<math> in S1 is the final transaction to write the value for an object X, so does the transaction <math>T_i<math> in S2.

View Serializable

A schedule is said to be View Serializable if it is View Equivalent to some Serial Schedule. Note that by definition, all Conflict Serializable schedules are View Serializable.

<math>G = \begin{bmatrix}

T1 & T2 \\ R(A) & \\

& R(A) \\

W(B) & \\ Com. & \\

& W(A) \\
& Com. \\
&\end{bmatrix}<math>

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. However, some View Serializable schedule is not Conflict Serializable, the characteristic for these scedules is that some transaction performs Blind Write.

<math>H = \begin{bmatrix}

T1 & T2 & T3 \\ R(A) & & \\

& W(A) & \\
& Com. & \\

W(A) & & \\ Com. & & \\

& & W(A) \\
& & Com. \\
& & \end{bmatrix}<math>

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 Conflict Serializable is NP-Complete, View Serializability has little practical interest.

Hierarchical Relationship between Serializability Classes

The following subclass clauses illustrate the hierarachical relationships between serializability classes:

• Serial ⊂ Conflict Serializable ⊂ View Serializable ⊂ All Schedules
• Serial ⊂ Strict ⊂ Avoids Cascading Aborts ⊂ Recoverable ⊂ All Schedules

The Venn diagram illustrates the above clauses graphically.

Practical Implementations

In practice, most businesses aim for Conflict Serializable and Recoverable schedules.

See also:

• schedule (project management)