Serializability and Conflict Types

The Problem with Concurrency

Imagine two people with a shared bank account trying to withdraw money at the exact same time. It's easy to see how things could go wrong, leading to an incorrect final balance. This is the core challenge of concurrency control.

To get a solid grasp of the problems we need to solve, let's start with a video from CMU's Intro to Database Systems course. It uses simple examples to illustrate why simply interleaving operations can lead to chaos.

As the video highlights, we want to maximize parallelism by interleaving operations from different transactions. However, we need a formal way to ensure that this interleaving doesn't lead to an incorrect state. This brings us to the concept of serializability.

Defining Correctness: Schedules and Serializability

To reason about concurrency, we need some precise terminology.

• A Transaction is a sequence of read and write operations that are treated as a single, atomic unit of work. For example, transferring money involves reading the source account, writing the new balance, reading the destination account, and writing its new balance.
• A Schedule is a sequence of operations from one or more transactions as executed by the database. When transactions run concurrently, their operations are interleaved in the schedule.
• A Serial Schedule is a schedule where transactions are executed one after another, with no interleaving. This is simple and guaranteed to be correct, but it offers no parallelism.

The goal of a concurrency control protocol is to create an interleaved schedule that is "as good as" a serial one. This leads to our core definition:

A schedule is Serializable if it is equivalent in its outcome to some serial schedule.

This is the gold standard for isolation. It gives us the best of both worlds: we get the performance of interleaving operations, with the correctness guarantee of a serial execution. The database may run transactions T1 and T2 concurrently, but the final state will be as if either T1 ran before T2, or T2 ran before T1.

For a more formal and visual explanation of these terms, the following short video provides excellent, clear definitions.

The concept of serializability is the 'I'—Isolation—in the well-known ACID (Atomicity, Consistency, Isolation, Durability) properties that guarantee reliable transaction processing. Complete isolation is equivalent to serializability.

When Operations Collide: Conflicts

To understand what makes a schedule non-serializable, we need to identify the specific interactions between operations that can cause problems. These are called conflicts.

Two operations from different transactions conflict if they access the same data object, and at least one of the operations is a write. This gives us three types of conflicts:

1. Read-Write (R-W) Conflict: Transaction T1 reads an object, and then T2 writes to the same object. This can cause an unrepeatable read, where T1 might get a different value if it were to read the same object again.
2. Write-Read (W-R) Conflict: Transaction T1 writes an object, and then T2 reads it. If T1 has not yet committed, this can cause a dirty read, where T2 reads a value that may be rolled back later.
3. Write-Write (W-W) Conflict: Transaction T1 writes an object, and then T2 also writes to it. This can cause a lost update, where T1's change is overwritten by T2 before anyone has had a chance to see it.

Note that a Read-Read (R-R) conflict does not exist, as two transactions reading the same data do not interfere with each other.

The following video segment provides clear, illustrated examples for each of these conflict types and the anomalies they cause.

A Practical Test: Conflict Serializability

We now know what serializability is and what conflicts can break it. But how can we algorithmically determine if a given schedule is serializable? We do this by testing for a slightly stricter, but much more practical, form of serializability called Conflict Serializability.

A schedule is conflict serializable if it can be transformed into a serial schedule by a series of swaps of adjacent, non-conflicting operations.

While this definition is formal, checking it by swapping operations is tedious. A much more elegant and efficient method is to use a Dependency Graph (also called a Precedence Graph).

Here’s the algorithm:

1. Create a node in the graph for each transaction in the schedule (e.g., T1, T2, T3).
2. Draw a directed edge from Ti to Tj if an operation in Ti conflicts with a subsequent operation in Tj. You scan the schedule and for every pair of conflicting operations, you draw an edge from the transaction that came first to the transaction that came second.

The rule is simple: A schedule is conflict serializable if and only if its dependency graph is acyclic (contains no cycles).

A cycle in the graph (e.g., T1 → T2 → T1) means there's a circular dependency, which is impossible to resolve in any serial order. If the graph is acyclic, a valid serial order can be found by performing a topological sort of the graph.

Let's watch the CMU video again for a walkthrough of how to build and interpret these graphs.

Conclusion

In this lesson, we took our first step into the world of database concurrency. We established that while interleaving transactions is crucial for performance, it opens the door to dangerous anomalies.

Key Takeaways:

• Concurrent execution can lead to anomalies like dirty reads, unrepeatable reads, and lost updates if not managed correctly.
• The gold standard for correctness is serializability, which guarantees that a concurrent schedule has the same outcome as some one-at-a-time (serial) execution.
• Operations from different transactions conflict if they touch the same data item and at least one is a write. There are three types: Read-Write, Write-Read, and Write-Write.
• We can efficiently test for conflict serializability by constructing a dependency graph and checking for cycles. An acyclic graph implies the schedule is correct.

Preview of the Next Lesson

We now have a robust theoretical tool to determine if a schedule is correct. But this is an after-the-fact analysis. How does a database enforce a serializable schedule as transactions are running? One of the oldest and most common methods is by using locks.

In our next lesson, we will begin our journey into practical implementation by learning how to implement a lock manager that supports shared (read) and exclusive (write) locks. This will be the foundational component for building our first concurrency control protocol.