Characterizing Schedules Based on Serializability

In a database system, many transactions may run concurrently. Their operations may be interleaved in different orders.

Some of these orders produce correct results, while others may lead to incorrect database states.

To determine whether a schedule is correct, the concept of serializability is used.

Serializability helps identify which concurrent schedules behave the same as a serial schedule.

---

1. Serial Schedules

A serial schedule is a schedule where transactions execute one after another without interleaving.

Only one transaction runs at a time.

Example

Two transactions: T1 and T2

Possible serial schedules:

Serial Schedule A

T1 executes completely
then
T2 executes completely

Serial Schedule B

T2 executes completely
then
T1 executes completely

These schedules are always correct, because:

• Each transaction runs in isolation

• No interference occurs between transactions

This assumption is valid because every transaction is assumed to maintain database consistency when executed alone.

2. Nonserial Schedules

A nonserial schedule occurs when operations from different transactions are interleaved.

Example:

T1: read(X)
T2: read(X)
T1: write(X)
T2: write(X)

Here both transactions execute simultaneously, mixing their operations.

Nonserial schedules allow concurrency, but they may produce incorrect results.

3. Why Serial Schedules Are Not Practical

Although serial schedules guarantee correctness, they have major disadvantages:

1. Poor CPU Utilization

If a transaction waits for I/O operations, the CPU remains idle.

Example:

Transaction waiting for disk → CPU unused

---

2. Long Waiting Time

If one transaction is very long, other transactions must wait.

Example:

T1 (long transaction)
T2 waits until T1 completes

This reduces system performance.

---

Solution

Allow interleaving of transactions while ensuring correctness.

This leads to the concept of serializability.

---

4. Serializability

A schedule is serializable if:

Its result is equivalent to the result of some serial schedule.

In other words:

Even though operations are interleaved, the final result is the same as if transactions executed one after another.

Serializable schedules are considered correct schedules.

---

5. Example with Transactions

Suppose the database initially has:

X = 90
Y = 90
N = 3
M = 2

Transactions:

Transaction T1

read(X)
X = X - N
write(X)

read(Y)
Y = Y + N
write(Y)

Transaction T2

read(X)
X = X + M
write(X)

---

Expected Result

After both transactions:

X = 89
Y = 93

---

6. Serial Execution

Serial Schedule A

T1 executes completely
T2 executes completely

Result:

X = 89
Y = 93

Correct.

---

Serial Schedule B

T2 executes completely
T1 executes completely

Result:

X = 89
Y = 93

Also correct.

---

7. Nonserial Schedules

When operations are interleaved, results may differ.

Schedule C

Produces:

X = 92
Y = 93

This result is incorrect.

The reason is the Lost Update Problem.

---

Lost Update Problem

Transaction T2 reads X before T1 updates it, so T1’s update gets overwritten.

Thus:

Effect of T1 is lost

---

Schedule D

Produces:

X = 89
Y = 93

This result is correct.

Even though operations are interleaved, the result matches a serial schedule.

Therefore:

Schedule D is serializable

8. Schedule Equivalence

To determine serializability, we check whether two schedules are equivalent.

Two schedules are equivalent if they produce the same logical effect on the database.

There are two main types:

1. Result equivalence

2. Conflict equivalence

---

9. Result Equivalence

Two schedules are result equivalent if they produce the same final database state.

However, this method is not reliable.

Example:

Two schedules might produce the same result only for a specific initial value, but not for other values.

Therefore, result equivalence is not sufficient.

---

10. Conflict Equivalence

A better approach is conflict equivalence.

Two schedules are conflict equivalent if:

The order of every pair of conflicting operations is the same in both schedules.

---

11. Conflicting Operations

Two operations conflict if:

1. They belong to different transactions

2. They access the same data item

3. At least one operation is a write

---

Types of Conflicts

Type	Example
Read–Write conflict	r1(X) , w2(X)
Write–Read conflict	w1(X) , r2(X)
Write–Write conflict	w1(X) , w2(X)

---

Non-conflicting Operations

Example	Reason
r1(X) , r2(X)	Both reads
w1(X) , w2(Y)	Different items

---

12. Conflict Serializable Schedules

A schedule is conflict serializable if:

It is conflict equivalent to some serial schedule.

This means:

We can reorder non-conflicting operations to obtain a serial schedule.

---

13. Example

Schedule D is conflict equivalent to Serial Schedule A.

Reason:

• Order of conflicting operations is the same

• Non-conflicting operations can be rearranged

Therefore:

Schedule D is serializable

---

14. Non-Serializable Schedule

Schedule C cannot be rearranged to match any serial schedule.

Conflicts prevent the operations from being reordered.

Therefore:

Schedule C is NOT serializable

Such schedules may produce incorrect database results.

---

15. Types of Serializable Schedules

There are two main types:

1. Conflict Serializable

Most commonly used method.

Based on conflicting operations.

---

2. View Serializable

A more general but complex concept.

Based on read-from relationships.

Less commonly used in practice.

---

16. Importance of Serializability

Serializability ensures:

• Correct execution of concurrent transactions

• Database consistency

• Maximum concurrency without errors

Without serializability:

• Lost updates may occur

• Inconsistent data may appear

• Transactions may interfere with each other

---

Final Summary

Concept	Meaning
Serial Schedule	Transactions execute one after another
Nonserial Schedule	Operations are interleaved
Serializable Schedule	Equivalent to some serial schedule
Conflict Equivalence	Same order of conflicting operations
Conflict Serializable	Can be rearranged into a serial schedule

---

✅ Key Idea

Serializability ensures that concurrent execution of transactions produces the same result as serial execution, maintaining correctness and database consistenc