Encyclopedia > Schedule

  Article Content

Schedule

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

Type of Schedules

  • Serial: The transactions are executed one by one, no interleaved. (see above)
  • Serializable: A schedule that is equivalent to a serial schedule.

Given E, the order of D has been changed, 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: If a transaction aborts, it doesn't cause other transactions to abort.

-- Example Here ---

  • Conflict Equivalent
  • Conflict Serializable

  • View Serializable

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



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Radio station

... radio waves, and occurs on commercial US airwaves in the frequency range of 530 to 1600 kiloHertz (thousand cycles per second). FM refers to frequency modulation, and ...