Schedule (computer science)
From Free net encyclopedia
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 |
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 (has the serializability property).
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.
- <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>
Conflicting actions
Two or more actions are said to be in conflict if:
- The actions belong to different transactions.
- At least one of the actions is a write operation.
- 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 schedules T1 and T2 are said to be conflict-equivalent if the following conditions are satisfied:
- 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)
- 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-serializability 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>
Commitment-ordered
A schedule is said to be commitment-ordered, or commitment-order-serializable, if it obeys the Commitment ordering (commit-order-serializability) schedule property. This means that it is conflict-serializable, and the precedence order of transactions' commitment events is identical to the precedence (partial) order of the respective transactions, as induced by their schedule's acyclic precedence graph/serializability graph.
View equivalence
Two schedules S1 and S2 are said to be view-equivalent when the following conditions are satisfied:
- 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.
- 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.
- 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 view-serializable is NP-complete, view-serializability has little practical interest.
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 (rollbacks)
Also named cascadeless. 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.
Strict
A schedule is strict if for any two transaction T1, T2, if a write operation of T1 precedes a conflicting operation of T2 (either read or write), then the commitment event of T1 also precedes that conflicting operation of T2.
Any strict schedule is cascadeless, but not the converse.
Hierarchical relationship between serializability classes
The following subclass clauses illustrate the hierarachical relationships between serializability classes:
- Serial ⊂ commitment-ordered ⊂ conflict-serializable ⊂ view-serializable ⊂ all schedules
- Serial ⊂ strict ⊂ avoids cascading aborts ⊂ recoverable ⊂ all schedules
The Venn diagram illustrates the above clauses graphically.
Image:Schedule-serializability.png
Practical implementations
In practice, most businesses aim for conflict-serializable and recoverable (primarily strict) schedules.