Schedule (computer science)

From Wikipedia, the free 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:

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.2.1 Conflicting actions 1.2.2 Conflict equivalence 1.2.3 Conflict-serializable 1.2.4 Commitment-ordered 1.2.5 View equivalence 1.2.6 View-serializable 1.3 Recoverable 1.3.1 Unrecoverable 1.3.2 Avoids cascading aborts (rollbacks) 1.3.3 Strict 2 Hierarchical relationship between serializability classes 3 Practical implementations 4 See also

[edit] Types of schedule

[edit] Serial

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

[edit] 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.

[edit] Conflicting actions

Two or more actions are said to be in 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), T3: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)

[edit] Conflict equivalence

The schedules S1 and S2 are said to be conflict-equivalent if the following conditions are satisfied:

1. Both schedules S1 and S2 involve the same set of transactions (including ordering of actions within each transaction).
2. The order of each pair of conflicting actions in S1 and S2 are the same.

[edit] Conflict-serializable

A schedule is said to be conflict-serializable when the schedule is conflict-equivalent to one or more serial schedules.

Another definition for conflict-serializability is that a schedule is conflict-serializable if and only if there exists an acyclic precedence graph/serializability graph for the schedule.

Which is conflict-equivalent to the serial schedule <T1,T2>, but not <T2,T1>.

[edit] 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.

[edit] View equivalence

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

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

[edit] 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.

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.

[edit] Recoverable

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

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.

[edit] Unrecoverable

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

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.

[edit] Avoids cascading aborts (rollbacks)

Also named cascadeless. A single transaction abort leads to a series of transaction rollback. 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:

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.

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

[edit] Strict

A schedule is strict 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 event of T1 also precedes that conflicting operation of T2.

Any strict schedule is cascadeless, but not the converse.

[edit] 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.

[edit] Practical implementations

In practice, most businesses aim for conflict-serializable and recoverable (primarily strict) schedules.

[edit] See also

• schedule (project management)