Serializability: Conflict & View

In a multi-user database environment, transactions often run concurrently. This concurrency improves performance, but if not handled properly, it can lead to inconsistent data. To avoid this, the system must ensure that the outcome of executing transactions concurrently is equivalent to some serial execution—this property is known as serializability.

Serializability ensures the correctness of schedules, and there are two main types: Conflict Serializability and View Serializability.

1. Conflict Serializability

Conflict serializability focuses on whether a concurrent schedule can be transformed into a serial schedule by swapping non-conflicting operations.

Two operations conflict if:

• They belong to different transactions,
• They access the same data item, and
• At least one of them is a write operation.

For example, the following operations would conflict:

If a schedule can be rearranged by swapping non-conflicting operations to form a serial schedule (i.e., one transaction at a time), it is said to be conflict serializable.

Conflict serializability is typically tested using a precedence graph (also called a serializability graph). If this graph has no cycles, the schedule is conflict serializable.

2. View Serializability

View serializability is a more relaxed and broader condition than conflict serializability. A schedule is view serializable if it is view equivalent to some serial schedule.

View equivalence is based on three rules:

• Initial Reads: The first read of any data item should read the same value in both schedules.
• Read-from Relationship: Every read operation should read the value written by the same write operation in both schedules.
• Final Writes: The last write on each data item should be performed by the same transaction in both schedules.

View serializability considers the logical effect of transactions, not just the order of operations. Therefore, all conflict serializable schedules are view serializable, but the converse is not true.

Summary

Conflict Serializability: Based on reordering non-conflicting operations; easier to check using precedence graphs.

View Serializability: Based on comparing the logical outcome of transactions; more general but harder to verify.

Goal: Ensure that concurrent transactions maintain consistency and isolation, just like serial execution would.