How Databases Achieve Concurrency Through Conflict-Free Scheduling

In my previous blog, I explored how serializability ensures isolation across transactions while linearizability guarantees real-time consistency of single objects.

This post builds on that discussion by diving deeper into serializability, essentially exploring how valid serial transaction orders are nothing but a means to achieve concurrency through conflict-free scheduling.

We already understand that concurrency control is fundamentally about ensuring that transactions running in parallel behave as though they were executed one after another. This property is called Serializability, and it’s the gold standard for correctness. The keyword here, however, that demands sincere attention is "behave" because if transactions were executed serially, it would be highly inefficient. Upon closer inspection, we see that overlapping transaction operations can indeed be safely ordered, as long as they don’t conflict. This may seem like a narrow window for concurrency, allowing transactions to reorder themselves while running independently, except when they conflict but it apparently has a huge impact on performance.

Of course, when conflicts do occur, they must be detected and handled carefully, a topic I’ll explore in my next blog. But before that, it’s worth understanding that databases first create room for concurrency by avoiding conflicts altogether.

The scope of this conflict avoidance takes the form of what we know as conflict-serializable and view-serializable schedules. These are underpinned by different concurrency control mechanisms such as dependency graph analysis and timestamp ordering, respectively, which I’ll discuss in an upcoming post.

Let’s see what these schedules look like in practice.

Conflict Serializability

A schedule is conflict serializable if it can be transformed into a serial schedule (i.e., transactions executed one after another, no overlap) by swapping only non-conflicting operations.

Two operations conflict if they:
1. Belong to different transactions,
2. Access the same data item,
3. At least one of them is a write.

So, R1(X)W2(X), W1(X)R2(X), and W1(X)W2(X) pairs are in conflict.

Non-conflicting, operations would be R1(X)R2(X) and ones that involve different data items. For instance, R1(X)W2(Y), W1(X)R2(Y) and W1(X)W2(Y).

Because reordering non-conflicting operations preserves the outcome, conflict serializability ensures the schedule is equivalent to some serial execution guaranteeing correctness.

Looking at the examples from my previous blog post,

Given following transaction operations:
(T1) X = X - 10
(T1') Y = Y + 10
(T2) Y = Y - 5
(T2') Z = Z + 5

Valid serial orders would be:
1. T1 T1' T2 T2' (T1 -> T2)
2. T2 T2' T1 T1' (T2 -> T1)

And conflict serializable schedules would be:

T1 T2 T1' T2' (Equivalent to serial order T2 -> T1), and
T2 T1 T2' T1' (Equivalent to serial order T2 -> T1)

Notice, in both of these conflict serializable orders T1' and T2 are engaged in a RW conflict. In other words, they can't be reordered. T'1 must always follows T2 if we are leaning for serial order T2 -> T1.

We can also see that (T1, T2) and (T1', T2') can flip order without violating the serial order T2 -> T1 only because they are not in conflict with each other.

View Serializability

While conflict serializability enforces strict ordering on all RW, WR, and WW conflicts, view serializability is more relaxed. It is a superset of conflict-serializable schedules, because in certain cases a conflict can be safely ignored without affecting the correctness of the outcome.

The classic case is with write–write conflicts W1(X)W2(X). If transaction T1 writes X = 5 but then T2 overwrites it with X = 7 and the value from T1 is never observed by anyone. In this case, the system does not need to abort T1. It can simply ignore T1’s write. The final state is still X = 7, which is the same as if T1’s write never happened.

If W1(X) arrived before W2(X), then it would just be part of normal schedule, and we would keep it. But if W1(X) arrives late, after W2(X) has already committed, the database can treat it as obsolete and skip persisting it altogether.

However, there is one important caveat: if any operation did read the value written by W1(X), we can't safely ignore it anymore. This write now matters to the schedule because it influenced another transaction. Thomas' Write Rule doesn't apply to it anymore. Ignoring it would break view serializability. The system must either abort T1 or reject the conflicting read.

Conclusion

Conflict serializability is stricter than view serializability. Every conflict-serializable schedule is also view-serializable, but not vice versa.

View serializability allows the system to safely accept more schedules, by recognising that some operations are obsolete and can be discarded without affecting correctness.

Together, these forms of serializability reveal how databases achieve concurrency through conflict-free scheduling: by reordering or skipping operations that don’t interfere, systems preserve correctness while unlocking parallelism.

In the next post, we’ll look at what happens when conflicts can’t be avoided and how databases handle them through concurrency control.