|
|
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: -
T1 & T2 & T3 \\ R(X) & & \\ W(X) & & \\ Com. & & \\ & R(Y) & \\ & W(Y) & \\ & Com. & \\ && R(Z) \\ && W(Z) \\ && Com. \end{bmatrix} 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. 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 of D has been changed, but in the end, E gives the same result as D. -
T1 & T2 & T3 \\ R(X) & & \\ & R(Y) & \\ && R(Z) \\ W(X) & & \\ & W(Y) & \\ && W(Z) \\ Com. & Com. & Com. \end{bmatrix} Recoverable Transactions commit only after all transactions whose changes they read commit. -
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} 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. -
T1 & T2 \\ R(A) & \\ W(A) & \\ & R(A) \\ & W(A) \\ & Com. \\ Abort & \\ &\end{bmatrix} 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. Note that all schedules which avoids 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: -
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} 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: -
T1 & T2 \\ & R(A) \\ R(A) & \\ W(A) & \\ & W(A) \\ Abort & \\ & Commit \\ &\end{bmatrix} Cascading aborts avoidance is sufficient but not necessary for recoverable. Conflicting Actions Two or more actions are said to be conflict if: - At least one of the action is a WRITE operation.
- The actions are operating (READ/WRITE) on the same object.
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: - 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 Serializable is that a schedule is Conflict Serializable if and only if there exist an acyclic precedence graph/serializability graph for the schedule. -
T1 & T2 \\ R(A) & \\ & R(A) \\ W(B) & \\ Com. & \\ & W(A) \\ & Com. \\ &\end{bmatrix} Which is conflict equivalent to the serial schedule View Equivalence Two schedule S1 and S2 are said to be View Equivalent when the following conditions are satisfied: - If the transaction in S1 reads an initial value for object X, so does the transaction in S2.
- If the transaction in S1 reads the value written by transaction in S1 for object X, so does the transaction in S2.
- If the transaction in S1 is the final transaction to write the value for an object X, so does the transaction 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. -
T1 & T2 \\ R(A) & \\ & R(A) \\ W(B) & \\ Com. & \\ & W(A) \\ & Com. \\ &\end{bmatrix} 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. -
T1 & T2 & T3 \\ R(A) & & \\ & W(A) & \\ & Com. & \\ W(A) & & \\ Com. & & \\ & & W(A) \\ & & Com. \\ & & \end{bmatrix} The above example is not Conflict Serializable, but it is View Serializable since it has a view equivalent serial schedule . 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:
|
 |