Schedules (Histories) of Transactions – Detailed Explanation

When multiple transactions run concurrently in a database system, their operations may execute interleaved (mixed together).

The order in which these operations execute is called a schedule or history.

Schedules are important because they help the DBMS handle:

Concurrency control
Recovery after failures
Transaction correctness

1. What is a Schedule?

A schedule (S) is the sequence or ordering of operations from multiple transactions.

If there are n transactions:


T1, T2, T3, ... , Tn

A schedule S arranges their operations in a specific order.

Key Rule

Even though operations from different transactions may be interleaved, the order of operations within each individual transaction must remain unchanged.

Example

Transaction T1


read(X)
write(X)
read(Y)
write(Y)

Transaction T2


read(X)
write(X)

Possible schedule:


r1(X)
r2(X)
w1(X)
r1(Y)
w2(X)
w1(Y)

Here:

Operations of T1 and T2 are interleaved
But the internal order of T1 and T2 operations remains unchanged

2. Total Ordering of Operations

In schedules, operations follow total ordering.

This means:

For any two operations in the schedule, one operation must occur before the other.

Example:


r1(X) → occurs before → w2(X)

Even if operations run concurrently in reality, the schedule represents them as a specific sequence.

Partial Order (Theoretical Concept)

Sometimes operations may not require strict ordering if they do not conflict.

This leads to a partial order.

However, for simplicity, database theory usually assumes total ordering of operations.

3. Important Operations in a Schedule

For recovery and concurrency control, the important operations are:

Operation	Meaning
read_item(X)	Read data item X
write_item(X)	Write data item X
commit	Transaction successfully completed
abort	Transaction failed and rolled back

4. Shorthand Notation for Schedules

Schedules are often written using short symbols.

Symbol	Operation
b	begin transaction
r	read
w	write
e	end transaction
c	commit
a	abort

A subscript indicates the transaction number.

Example


r1(X)

Meaning:


Transaction T1 reads item X

Another example:


w2(Y)

Meaning:


Transaction T2 writes item Y

5. Example Schedules

Schedule Sa


Sa: r1(X); r2(X); w1(X); r1(Y); w2(X); w1(Y)

Explanation:

Operation	Meaning
r1(X)	T1 reads X
r2(X)	T2 reads X
w1(X)	T1 writes X
r1(Y)	T1 reads Y
w2(X)	T2 writes X
w1(Y)	T1 writes Y

Operations of T1 and T2 are interleaved.

Schedule Sb


Sb: r1(X); w1(X); r2(X); w2(X); r1(Y); a1

Explanation:

Operation	Meaning
r1(X)	T1 reads X
w1(X)	T1 writes X
r2(X)	T2 reads X
w2(X)	T2 writes X
r1(Y)	T1 reads Y
a1	T1 aborts

Here T1 fails (aborts).

6. Conflicting Operations in a Schedule

Two operations are said to conflict if three conditions are satisfied.

Conditions for Conflict

They belong to different transactions
They access the same data item
At least one operation is a write

Example Conflicts

In schedule Sa:


r1(X) and w2(X)

These conflict because:

Different transactions
Same data item X
One operation is write

Other Conflicts


r2(X) and w1(X)


w1(X) and w2(X)

7. Non-Conflicting Operations

Some operations do not conflict.

Example 1


r1(X) and r2(X)

Both are read operations, so changing their order does not change the result.

Example 2


w2(X) and w1(Y)

They access different data items.

Example 3


r1(X) and w1(X)

They belong to the same transaction, so they do not conflict.

8. Why Conflicts Matter

Conflicting operations matter because changing their order may change the result of the schedule.

Example: Read-Write Conflict

Original order:


r1(X)
w2(X)

T1 reads old value of X.

If order changes:


w2(X)
r1(X)

Now T1 reads the new value written by T2.

Result is different, so this is a read-write conflict.

Example: Write-Write Conflict

Original:


w1(X)
w2(X)

Final value written by T2.

If order changes:


w2(X)
w1(X)

Final value written by T1.

Thus final result changes.

9. Complete Schedule

A schedule S is called a complete schedule if it satisfies three conditions.

Condition 1

All operations of all transactions must appear in the schedule, including:


commit or abort

Condition 2

The order of operations within each transaction must remain unchanged.

Example:

If T1 originally executes:


r(X)
w(X)

The schedule cannot change it to:


w(X)
r(X)

Condition 3

For conflicting operations, the schedule must specify which operation occurs first.

This ensures that the database knows how conflicts are resolved.

10. Partial vs Total Order

The schedule may leave nonconflicting operations unordered, creating a partial order.

But:

Conflicting operations must always have a defined order
Operations of the same transaction must also have a defined order

11. Active Transactions in a Schedule

In a complete schedule:

Every transaction must either commit or abort
No transaction remains active at the end

12. Committed Projection of a Schedule

In real systems, schedules often contain transactions that have not finished yet.

Therefore, we use Committed Projection C(S).

Definition

Committed Projection C(S) includes only the operations of committed transactions.

Transactions that abort or remain active are ignored.

Example

Schedule:


r1(X)
w1(X)
r2(X)
w2(X)
c2
a1

Committed projection C(S) will include only T2 operations because:

T2 committed
T1 aborted

Key Summary

A schedule is the ordered sequence of operations from multiple concurrent transactions.

Important concepts:

Concept	Meaning
Schedule	Order of operations from concurrent transactions
Interleaving	Mixing operations of different transactions
Conflicting operations	Operations accessing same item with at least one write
Complete schedule	Includes all operations with commit/abort
Committed projection	Schedule containing only committed transactions

✅ Main Idea

Schedules describe how concurrent transactions execute in a database system, ensuring correct concurrency control and recovery after failures.