—

Database Design and Applications

Transactions: Schedules, Serializability, and Recovery

Published: 2026-08-06

Level: postgraduate

Audience: Postgraduate students in Database Design and Applications

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Transactions and the ACID properties — covered in Lecture 1 and Lecture 12
Transaction states, commit, and the log — covered in Lecture 12
Schedules and conflict serializability — covered in Lecture 12
Indexes, B-trees, and B+ trees — covered in Lecture 10 and Lecture 13

A database is rarely used by one person alone. The moment a second user connects, two questions appear: what happens when their operations interleave, and what happens when something fails mid-operation? This lecture answers both. It defines the transaction — the unit of work that must run as a chunk — explains the ACID properties every transaction promises, builds the theory of schedules and serializability that decides which interleavings are safe, and then shows what can go wrong when failures strike and how the two classic mechanisms, lock-based and timestamp-based protocols, enforce the rules. Along the way, the professor grounds every abstract idea in the everyday world: bank transfers, cloud databases, Git, restaurants and hospitals handing out token numbers, and the token system at the Mata Vaishno Devi temple near Katra.

15.1 The Story So Far: From Requirements to Transactions

15.1.1 The Path We Have Walked

Hook: You have spent the semester turning a customer's vague idea into a fast, clean database. The professor opens this session with a one-line question that frames everything: we have built the database well — now how do we let many people use it at the same time without breaking it?

The session opens by placing transactions inside the story of the whole course. A customer or client gives us certain requirements for an application. We start by making an ER diagram — an entity-relationship picture of the data — so that our concepts are clear and visible to both parties; once both sides agree, we make a basic relational schema, which is good enough for a proof-of-concept. When the proof of concept moves into a production phase, we want the database to be as clean, as simple, as efficient, and as scalable as possible. That is where we write down the functional dependencies and ensure that within each relation we have the least redundancy — the topic of normalization, where we take the schema to whatever level suits it best: 1NF, 2NF, 3NF, BCNF, whatever we can.

Then we looked at making queries faster. The better we serve customers, the more customers we can serve at any point of time — that is the whole advantage of an application. So we studied how to write various indexes, and we understood the physical reason behind them: the database lives in secondary storage, and because of limitations in performance and cost we have a hierarchical storage setup, with the processor working as closely as possible with main memory. Whatever is in secondary storage has to be brought back into main memory, worked upon there, and written back to secondary storage, where the database is persistent. Along the way we discussed how to optimize searching, updating, and inserting for the user: multi-level indexes, B-trees, B+ trees, a bit of bitmap indexing, and hashing or hash-based indexes. We also noted that most commercial databases create B+ tree indexes, which is exactly what allows faster range queries. That whole discussion matters when you have administrative access, or when you want to create your own database software.

Recap: the design story of the course, in one chain — requirements → ER diagram → relational schema → normalization (1NF, 2NF, 3NF, BCNF) → indexes (B-trees, B+ trees, bitmap, hashing) → transactions. Each step prepared the database for more users and more work; the transaction concept is the next and final layer of that preparation.

15.1.2 The Next Problem: Many People, One Database

We have converted user requirements into a relational schema, we have practiced SQL — the programmable way to insert, retrieve, access, and update the data we want — and we have seen how to create an index for faster access. Now comes the next step: multiple people must be able to access the database simultaneously. Depending on the application requirement, whatever is expected to be executed as a chunk must really be executed as a chunk, and the properties of such a chunk — which we call a transaction — must be satisfied.

Concurrent access is wanted for two reasons:

Performance: while one transaction waits for input/output (reading a block from disk), the processor can execute another transaction instead of sitting idle. Multiprogramming is what makes this possible — the operating system switches the CPU from one process to another during I/O waits, and this keeps the processor busy.
User experience: hundreds of users submit work at the same time — travel agents booking flights, bank tellers processing transfers, shoppers placing orders — and none of them should feel like they are queued behind everyone else.

A serial execution (one transaction fully completing, then the next) is simple and correct, but it wastes the processor's time and makes every user wait for every other user. The entire theory of this session exists to answer one question: which interleavings of transactions can we allow without sacrificing correctness?

This session covers the transaction concept, and it sets up how we will later handle transaction control. Today's discussion also previews the mechanisms of concurrency control — the lock-based and timestamp-based protocols — which are covered in detail next.

15.2 Transactions and the ACID Properties

15.2.1 What a Transaction Is

Hook: You hand your card to a cashier. The machine reads your balance, deducts the price, and records the sale — or it does nothing at all. It can never deduct the price and forget to record the sale. What makes that "all or nothing" behaviour possible is a transaction.

A transaction is a unit of program that we want to execute as it is — a group of instructions that must be accessed and executed as a whole. Transactions are everywhere in real applications: a transaction can be a banking operation, a sales or purchase operation, or anything else of that shape.

In the standard textbook model, a transaction is made up of simple database access operations on named data items:

$r e a d_i t e m (X)$ — read the value of data item $X$ into a program variable. Physically, this means finding the disk block containing $X$ , copying that block into a main-memory buffer, and copying item $X$ into the program variable.
$w r i t e_i t e m (X)$ — write the value of program variable $X$ into the database item $X$ . Physically, this means copying the new value into the buffer and, at some point, storing the updated block back to disk.

A read-only transaction only retrieves data; a read-write transaction also updates the database. Notice what the two operations share: both involve moving blocks between secondary storage and main memory — the same seek and transfer costs we studied in the indexing lectures.

The professor's opening remark captures the attitude: the properties of a transaction are absolutely uncompromisable. They are not nice-to-have features; they are a contract. Together the four properties are known by their acronym — ACID.

15.2.2 Atomicity: Everything or Nothing

The first property is atomicity: transactions must be executed in an atomic manner — either everything happens, or nothing happens. There is no acceptable middle ground where part of a transaction's effects land and the rest vanish.

Atomicity (from Greek atomos, "indivisible"): the transaction must be performed in its entirety or not performed at all. If a transaction fails halfway — say the system crashes in the middle — the recovery subsystem must undo any effects the transaction already applied to the database. The user never sees "half a transfer": either the whole transfer happened, or none of it did.

This is why a transaction cannot be allowed to commit step by step: committing halfway would be a public declaration that it is acceptable for half the work to land — the exact opposite of atomicity. The commit operation belongs at the end of the transaction, and nowhere else.

15.2.3 Consistency: Constraints Before and After

The second property is consistency. Before the customer executes a transaction and after the customer executes a transaction, the basic constraints and the important constraints of the database must be satisfied.

Consistency preservation: a transaction should take the database from one consistent state to another. A consistent state is one that satisfies all the constraints of the schema and application — primary-key constraints, foreign-key constraints, check constraints, and application-level rules such as "total money in the system is conserved".

The professor's concrete test: if the total amount of money before and after must remain the same — one of the requirements of a transaction — then it must remain the same. A transfer of ₹500 from account A to account B is consistent if and only if A loses exactly 500 and B gains exactly 500; the money is neither created nor destroyed. Consistency is about the database never violating its own rules across the execution.

Two responsibilities are worth separating. The concurrency-control and recovery machinery ensures that interleavings and failures do not themselves corrupt the state; but the transaction program itself must also be written so that, when it runs alone from a consistent state, it ends in a consistent state. If the program itself has a bug — deducting money and never crediting it — no amount of concurrency control can save the consistency of the database.

15.2.4 Isolation: The Feeling of Being Alone

The third property is isolation: users should feel as if they are working in isolation — as if nobody else exists in the system.

Isolation: even though many transactions execute concurrently, each transaction should appear to execute as if it were the only one running. The execution of one transaction should not be interfered with by any other transaction.

Isolation has various layers; the layer we discuss is that executing a transaction should be as good as executing it in a serial manner. The result should not change whether I am executing alone or somebody else is executing simultaneously. If the outcome of "everyone working at once" equals the outcome of "everyone working one after another", then nobody's work has been disturbed — each user got the feeling of being alone.

Why is isolation hard? Because without control, interleaved transactions can step on each other. A classic example: two transactions both read the same account balance, both add their own amount, and both write back — the first write is lost because the second transaction never saw it. Isolation is the property that forbids such interference.

15.2.5 Durability: The Promise of Persistence

The fourth property is durability: once a transaction has committed — and we will see precisely what commit means — the changes made are persistent. A committed transaction's effects survive in the database no matter what happens afterwards.

Durability (or permanency): the changes applied to the database by a committed transaction must persist. They must not be lost because of any failure — not a power cut, not a system crash, not a hardware fault. Once the database has said "this transfer is done", it can never take it back.

The professor's image for durability is a promise: after commit, the transaction must never "come back from its promise". Rolling back a committed transaction would mean exactly that — breaking the promise — and it is forbidden.

Scope — what ACID guarantees, and what it does not:

Atomicity, isolation, and durability are enforced by the DBMS itself — by the recovery subsystem and the concurrency-control subsystem.
Consistency is co-responsibility: the DBMS enforces schema-level constraints, but the transaction program must be written to preserve application-level constraints (like the total-money test). A badly written transaction can still leave the database inconsistent.
Durability assumes the DBMS has arranged its storage properly (log records written to disk before commit); durability is not a guarantee that disk hardware itself can never fail — that is what archival backups are for.

Pitfalls:

Confusing consistency with atomicity. Atomicity says "all operations or none"; consistency says "constraints hold before and after". They are different: a transaction can be perfectly atomic (all operations executed) and still break a constraint (operations that add up wrong).
Thinking isolation means "at most one user at a time". No — isolation is about the appearance of being alone while many users are actually running concurrently. Serial execution does satisfy isolation, because nobody ever interleaves — but it destroys performance.
Believing a committed transaction can be rolled back later. A rollback after commit violates durability — the database promised persistence and broke the promise.
Committing in the middle of a transaction. This violates atomicity (half the work is accepted) and creates a performance bottleneck through cascading commits.

Recap + Bridge: ACID is the contract every transaction promises — Atomicity (all or nothing), Consistency (constraints before and after), Isolation (each user feels alone), Durability (committed work persists forever). The professor's single sentence to remember: the properties of a transaction are absolutely uncompromisable. Next we see how the life of a transaction is tracked — the states it passes through between active and committed or aborted.

Real-world: transactions are the unit of banking operations, sales and purchase operations, and anything else of that shape — airline reservations, credit-card processing, stock trading, and online retail all run on transaction systems with hundreds of concurrent users. The ACID properties are the contract every such application relies on.

15.3 Transaction States: From Active to Committed or Aborted

15.3.1 The State Diagram

Hook: A transaction is a living thing — it starts, works, and then either succeeds or fails. The database must know exactly where each transaction is, because what the recovery system does depends entirely on that knowledge. How do we track a transaction's life?

How a transaction executes is captured in a state diagram, and we agree to model a transaction by these states. There are five states, and the transitions between them tell the whole story of a transaction's life:

The five transaction states:

Active — the transaction has started execution and is performing its read and write operations. This is the state the transaction enters as soon as it begins.
Partially committed — all the instructions have been executed; the transaction has finished its work and wants to commit. The changes are not yet guaranteed permanent.
Committed — the changes have been successfully recorded in the database; the transaction's effects are permanent and will survive any failure.
Failed — the transaction could not complete, or a check failed after execution; it can no longer continue normally.
Aborted — the transaction has been rolled back: all effects of its operations on the database have been undone, and the database has been restored to the state before the transaction started.

The state diagram, in words:

As soon as the transaction starts, we say the transaction is active.
From active, one of two things happens. The transaction can move to a partially committed stage: all the instructions have been executed, and we now want to commit — to write the changes back to secondary storage so that the database becomes persistent. Once the commit is done, the transaction is committed.
The other branch: if the transaction fails, we roll back whatever changes have happened and abort it.

So the states are: active, partially committed, committed, failed, and aborted. (Textbooks often add a final terminated state — the transaction leaving the system, its information removed from system tables — and note that a failed or aborted transaction may later be restarted as a brand new transaction.)

Visual intuition: picture a flow diagram with five circles and three arrows. Active sits at the left. From active, one arrow goes down to failed (marked "abort") and one arrow goes right to partially committed (marked "end transaction"). From partially committed, an arrow labeled "commit" goes to committed; from failed, an arrow labeled "abort" goes to aborted. The committed and aborted states are terminal — no arrow leaves them. The takeaway: a transaction never leaves the committed or aborted state; everything before that is still reversible.

What triggers the failed state? A transaction can fail during execution — a read operation that was expected did not happen, an auxiliary operation hit an error, the transaction was aborted by the concurrency-control method because it violated serializability, or a deadlock forced one transaction to be aborted so the others could proceed. It can also fail at the commit checkpoint: after all instructions have executed, the system performs checks (recording the changes in the log so they can survive a system failure) and, if those checks fail, the transaction moves to failed instead of committed.

15.3.2 What Commit Really Means

Commit — the physical act of persistence. Commit means that not only are all the operations of the transaction complete, but all the changes have been written to the secondary storage. After that point, whatever happens — even a catastrophic failure, even a hardware failure — the database remains durable.

The key physical idea, repeated throughout the session: commit means that not only are all the operations of the transaction complete, but all the changes have been written to the secondary storage. After that point, whatever happens — even a catastrophic failure, even a hardware failure — the database remains durable. This is the bridge between the abstract ACID property of durability and the physical act of writing blocks to persistent storage.

The professor adds an honest refinement that anticipates the recovery lecture: in practice, the database does not necessarily write the actual data pages to disk at commit time. What it does guarantee is that the log records describing the changes have been written to disk before commit is declared — this is the standard write-ahead logging discipline. The log is an append-only file on disk recording, for each write, the transaction id, the item, the old value (before image) and the new value (after image). Because the log records are on disk, a committed transaction's changes can always be replayed (redone) even if the data pages themselves are still sitting in main-memory buffers when a crash happens. So "written to secondary storage" is precise: the log is forced to disk at commit; the data pages follow when convenient.

Pitfalls:

Thinking commit and "transaction finished" are the same thing. "Finished" (partially committed) is not enough — until the changes are durable, the transaction can still be rolled back. Commit is the persistence step, not the completion step.
Believing the data pages themselves must be on disk at commit. Standard engines commit with the log forced to disk, while data pages are written back lazily — this is why the log exists.
Confusing aborted with failed. Failed is the state where the transaction has been found unable to proceed; aborted is the state after its effects have been undone. Rollback is the action that moves a failed transaction to the aborted state.

Recap + Bridge: a transaction's life is active → partially committed → committed on the happy path, or active → failed → aborted when something goes wrong — and commit is the physical act of making changes durable in secondary storage. The state diagram gives us the vocabulary for the rest of the lecture: everything after commit is permanent, everything before it can be undone. Next we move from the life of one transaction to the lives of many — schedules of concurrently executing transactions and the operations that determine whether an interleaving is safe.

Real-world: every time you see "transaction successful" in a banking app, the database has pushed that transaction through this exact state machine — the app's confirmation is only shown after the committed state is reached, precisely so that the bank can never silently undo what the screen just promised.

15.4 Schedules and Conflicting Operations

15.4.1 Schedules and Serial Schedules

When multiple people — or multiple transactions, or multiple sets of programs — are executing simultaneously on the database, we call that a schedule.

Schedule (or history): given $n$ transactions $T_{1}, T_{2}, \dots, T_{n}$ , a schedule is an ordering of all their operations. Operations from different transactions may be interleaved, but the operations of each single transaction must appear in the schedule in the same order in which they appear inside that transaction — a transaction's own program order is never reordered.

A serial schedule is the special case where one set of instructions executes completely and commits, and only then does the next set of instructions execute and commit. With two transactions there are exactly two serial schedules: $T_{1}$ then $T_{2}$ , or $T_{2}$ then $T_{1}$ . With $n$ transactions there are $n!$ serial schedules. In a serial schedule, no interleaving at all occurs — at any instant exactly one transaction is running.

The professor's grounding fact: any serial schedule always follows the ACID properties. That is what we know for sure, and it becomes the yardstick for everything else. If every transaction is correct when run alone (its consistency property), then running whole transactions one after another is correct no matter which order we pick. The problem is that serial schedules are also slow: while a transaction waits for disk I/O, the processor cannot switch to another transaction, and a long transaction makes everyone else wait. So the practical question is: which interleaved schedules behave as if they were serial?

15.4.2 Schedule Notation

We write general schedules in a compact format that records, for every instruction, which transaction it belongs to, what operation it performs, and on which data item it operates:

$S = ⟨ r_{1} (A), w_{1} (A), r_{2} (B), w_{2} (B), \dots ⟩$

Here $T_{i}$ is the transaction, $r_{i} (X)$ means transaction $T_{i}$ reads data item $X$ , and $w_{i} (X)$ means transaction $T_{i}$ writes data item $X$ . The subscript records the transaction, the letter records the operation (read or write), and the parenthesized item records the data item — exactly the three pieces of information the professor described in words: what is the transaction, what is the operation, and what is the data item. The notation is the standard one used throughout the transaction-processing literature, and some authors also write $c_{i}$ and $a_{i}$ for commit and abort operations.

For example, the schedule

$S = r_{1} (A), w_{1} (A), r_{2} (A), w_{2} (B)$

reads as: $T_{1}$ reads A and writes A; then $T_{2}$ reads A and writes B. We will use this notation for every schedule in this lecture.

15.4.3 The Definition of a Conflicting Operation

The central idea that decides whether a schedule can be reorganized is the conflicting operation. The professor's definition, stated and restated: two operations are conflicting when they belong to two different transactions, operate on the same data item, and at least one of them is a write.

$o_{i} (X) and o_{j} (X) conflict ⟺ i \neq = j, same data item X, and at least one of o_{i}, o_{j} is a write$

where $o$ ranges over read $r$ and write $w$ . Everything else is a non-conflicting operation. Notice the two escapes: if the operations are in the same transaction, they are not conflicting; and if they are on different data items, they are not conflicting — even if one of them is a write.

Why these three conditions? Two operations conflict when swapping their order could change the outcome:

Different transactions — operations of the same transaction are tied to that transaction's program order; they are never swapped, so they can never conflict.
Same data item — operations on different items cannot see each other's effects; swapping them changes nothing.
At least one write — if both are reads, swapping them changes nothing (both read the same value). But $r_{i} (X)$ before $w_{j} (X)$ versus $w_{j} (X)$ before $r_{i} (X)$ changes what $T_{i}$ reads (read–write conflict), and $w_{i} (X)$ before $w_{j} (X)$ versus $w_{j} (X)$ before $w_{i} (X)$ changes the final value of X (write–write conflict).

This is how we will swap operations later to test whether a schedule is equivalent to a serial schedule.

Scope — what "conflict" covers and what it does not:

The definition assumes a total order of operations: in the schedule, one operation happens before the other, one instruction at a time, on a single processor.
Commit and abort operations are tracked for recovery, but the conflict definition itself is about read and write operations on data items.
The definition says nothing about why the operations conflict — it is purely structural: transactions, item, and write. That structural simplicity is exactly what lets us test serializability by graph instead of by reasoning about semantics.

15.4.4 The T1/T2 Pair Example

To fix the definition, consider a small schedule with two transactions. Transaction $T_{1}$ writes item A; transaction $T_{2}$ reads item A and writes item B.

$T_{1} : w_{1} (A) T_{2} : r_{2} (A), w_{2} (B)$

Walking through the pairs:

$w_{1} (A)$ and $r_{2} (A)$ : two different transactions, same data item A, and one of them is a write — this is a conflicting operation.
$w_{1} (A)$ and $w_{2} (B)$ : two different transactions, at least one is a write, but they are on different data items — not a conflicting operation.
A pair of operations on the same data item within the same transaction (for example a read and a write inside $T_{2}$ ): not a conflicting operation, because they are not from two different transactions.

Worked example — the full pair table. With the schedule above, list every cross-transaction pair and apply the three conditions:

Pair	Different transactions?	Same item?	One write?	Conflict?
$w_{1} (A)$ , $r_{2} (A)$	yes	A	yes	conflict
$w_{1} (A)$ , $w_{2} (B)$	yes	no (A vs B)	yes	no conflict
$r_{2} (A)$ , $w_{2} (B)$ (both in $T_{2}$ )	no	no	yes	no conflict

The only conflicting pair is the one on item A with a writer on one side. The pair $r_{2} (A)$ , $w_{2} (B)$ inside $T_{2}$ is not conflicting even though one is a write, because the same-transaction escape applies. Sense-check: if we swapped $w_{1} (A)$ with $r_{2} (A)$ , then $T_{2}$ would read the value before $T_{1}$ 's write instead of after — different outcome, so these two genuinely conflict; no other swap changes anything.

The class was asked to find the conflicting operations in this schedule, and the professor underlined the rule of the room: do not worry whether your answer is right or wrong right now — the idea is to participate more and more, because the group is here to learn and help each other grow.

15.4.5 Student Questions and Answers

Q: Suppose my database (an RDS instance) is residing in North Virginia and the application is running in North Virginia and in Singapore. A read operation comes from both places, and there will be a time difference between the two locations. How can we maintain the properties of the transaction?

A: Now you are taking into consideration the network delay that will be incurred. So far, when we talked about database access, we assumed the database is in secondary storage and we bring the data from secondary storage into main memory for the processor. We considered the seek time and the read (transfer) time. Now we add a third component: the network delay. The total time for an access becomes:

$t_{access} = t_{seek} + t_{read} + t_{network}$

But here is the deeper point: if the access is just a read, it is not a conflicting operation, even though the time zones differ. Locally, one person may feel it is day while the other feels it is night — the sun may be at one coordinate for one place and the moon at that coordinate for the other — but the network speed is so high (available at well above a gigabyte per second, if not thousands of terabytes per second) that both the person in North Virginia and the person in Singapore face a similar network-side delay to reach the database, whether the database sits in North Virginia or even in Australia or Japan. The time-zone difference does not create a correctness problem by itself. The problem you must worry about arises for consistency: both of them accessing, and worse, both of them trying to write to the database simultaneously. That is exactly the discussion we are having. So take transaction one as coming from the person in North Virginia and transaction two from the person in Singapore, and add the network delay to the seek time and transfer time — that is the broader, more practical version of the same picture. Thank you for this very practical question; it widens the horizon for the whole session.

Q: There should be a commit after T1 writes, so that only T2 should read. (And: a read operation does not cause an issue, right?)

A: Yes, you are right. If both of them are reads, there is no problem — primarily because we are talking about swapping operations. If both are reads, we can swap them easily. And about the comment that an integrity constraint holds even after commit: yes, we will discuss commit ordering when we talk about recoverability, because that is what gives us better recoverability. I am happy that most of you have got an idea of this — right or wrong, the participation is what matters.

Pitfalls:

Treating network delay as a correctness problem. The network delay is a cost — it adds $t_{network}$ to the access time — but a read across time zones is still just a read: not a conflicting operation, and swappable with any other read.
Thinking "simultaneous access" means simultaneous execution of two instructions. A single processor executes one instruction at a time, so "concurrent" transactions are actually interleaved; the schedule notation captures exactly that interleaving.
Forgetting the item in the conflict test. Same transaction, different items, or two reads — each alone is enough to make a pair non-conflicting; students often stop at "one of them is a write" and miss the other two conditions.

Recap + Bridge: a schedule records who reads/writes what, a serial schedule runs whole transactions one after another (and always follows ACID), and two operations conflict exactly when they belong to different transactions, touch the same item, and at least one is a write. The conflict definition is the key we will now use to test schedules: we may swap non-conflicting operations freely and see whether the schedule can be rearranged into a serial one.

Real-world: the question grounds the whole discussion in cloud database deployment — a single RDS instance in North Virginia served from Singapore — and shows that geographically distributed applications still reduce to the same single-database concurrency problem, with an extra term in the access cost. This is exactly the pattern behind modern cloud architecture: one authoritative database, many application servers around the world, and the concurrency of the single database as the bottleneck to manage.

15.5 Conflict Serializability: Swapping to a Serial Schedule

15.5.1 The Brute-Force Idea

We know that serial schedules always follow ACID. So we take any given schedule and try to make it equivalent to a serial schedule.

Conflict equivalence: two schedules are conflict equivalent if the order of every pair of conflicting operations is the same in both schedules. Since swapping non-conflicting operations never changes the outcome, two schedules that differ only in the order of non-conflicting operations are equivalent.

The brute-force method: apart from the conflicting operations, we try to swap the other operations — the non-conflicting ones — and see whether we can reach a serial schedule. If we can, the schedule is a conflict serializable schedule: even after swapping the non-conflicting operations, the schedule is equivalent to a serial schedule.

Why is the swap allowed? Because if I execute these operations first or execute that operation first, there is no change in the database and no change in any of the ACID properties. The result is the same one. So we can swap and declare the schedule equivalent to a serial schedule.

The intuition behind the definition: if the order of two conflicting operations changed, the outcome would change — a read might read a value written by a different transaction, or the final value of an item would be written by a different transaction. So conflict equivalence pins down every pair that matters and leaves free only the pairs that cannot matter.

15.5.2 The T1/T2 Swap Walkthrough

The professor walks through a two-transaction schedule operation by operation. Some instructions cannot be swapped — the conflicting ones — but other instructions can be swapped freely: "I can easily swap this with this one; all these instructions can be swapped with this." So an instruction from here may come there, and an instruction from there may come here. After the swaps, the schedule reads as a serial schedule: transaction one first, transaction two second (or the reverse), with all conflicting pairs still in their original relative order.

Worked example — a concrete swap. Take the schedule

$S = r_{1} (A), w_{1} (A), r_{2} (A), w_{2} (B)$

with transactions $T_{1}$ and $T_{2}$ . First, mark every conflicting pair: $w_{1} (A)$ and $r_{2} (A)$ conflict (different transactions, item A, one write). The pair $w_{1} (A), w_{2} (B)$ is non-conflicting (different items), and the pair $r_{2} (A), w_{2} (B)$ is non-conflicting (same transaction, $T_{2}$ 's own order is preserved anyway).

Now swap non-conflicting operations freely. Can we reach a serial schedule? The operations of $T_{2}$ are $r_{2} (A)$ then $w_{2} (B)$ ; the operations of $T_{1}$ are $r_{1} (A)$ then $w_{1} (A)$ . Because $r_{2} (A)$ must stay after $w_{1} (A)$ (they conflict), we cannot bring all of $T_{2}$ 's operations before $T_{1}$ 's. But look at $w_{2} (B)$ : it conflicts with nothing in $T_{1}$ (item B appears nowhere in $T_{1}$ ), so it can be moved anywhere. Move it to the very end:

$S = r_{1} (A), w_{1} (A), r_{2} (A), w_{2} (B) swap w_{2} (B) with nothing needed S^{'} = r_{1} (A), w_{1} (A), r_{2} (A), w_{2} (B)$

The schedule is already $T_{1}$ 's operations followed by $T_{2}$ 's operations — it is a serial schedule as written: $T_{1}$ then $T_{2}$ . The conflict-serializability test passes without any swap: the schedule is a serial schedule. Sense-check: the final database state after $S$ is: A was written by $T_{1}$ , B was written by $T_{2}$ , and $T_{2}$ read A's value after $T_{1}$ 's write — identical to the serial order $T_{1}, T_{2}$ . Same result, same ACID properties, so the schedule is allowed to run.

That is the point of conflict serializability: even though the transaction will run, in reality, along its own timeline as the scheduler executes it, we are allowed to think of it as equivalent to a serial schedule, and so we know it will always follow the ACID properties. Our basic agenda throughout the session stays fixed: we want to ensure that atomicity, consistency, isolation, and durability are followed, and the way we check that is to ask whether the schedule is equivalent to a serial schedule.

Why we never swap conflicting operations: swapping a conflicting pair changes the read-from relationship — this data item would be read as written by somebody else, which is not correct. The whole point of the conflicting-operation definition is to identify exactly the pairs that must keep their order.

15.5.3 When Swapping Is Impossible

The reverse case: a schedule that is not equivalent to any serial schedule, because there are conflicting operations that cannot be swapped. "I cannot swap this because this is a conflicting operation. So I cannot swap either of them, and neither can these operations be swapped." Since the schedule is not equal to any serial schedule even after swapping all non-conflicting operations, we cannot guarantee that it follows the ACID properties — and so we should not allow it to execute as it is. That is the whole reason serializability testing exists.

Worked example — the impossible swap. Now suppose the schedule interleaves the same two transactions as

$S = r_{2} (A), w_{1} (A), w_{2} (A)$

with $T_{1}$ : $w_{1} (A)$ and $T_{2}$ : $r_{2} (A), w_{2} (A)$ . Conflicting pairs: $r_{2} (A)$ and $w_{1} (A)$ (different transactions, item A, one write); $w_{1} (A)$ and $w_{2} (A)$ (different transactions, item A, both writes). To reach a serial schedule we would need all of $T_{2}$ 's operations together or all of $T_{1}$ 's together. But $r_{2} (A)$ cannot move after $w_{1} (A)$ (they conflict), and $w_{2} (A)$ cannot move before $w_{1} (A)$ (they conflict) — the two conflicts lock the operations into an interleaved order forever. There is no serial schedule equivalent to $S$ . Sense-check: in any serial schedule, the final writer of A is the transaction that runs second; here $T_{2}$ reads A and then both write — the interleaving means $T_{2}$ 's read sees $T_{1}$ 's write, an ordering that exists in no serial schedule. Not conflict serializable → the system must reject this schedule.

15.5.4 The Guarantee You Get

Recap + Bridge: conflict serializability is the admission test — a conflict serializable schedule is allowed to run, and however it runs along the timeline, we treat it as equivalent to a serial schedule, so it will always follow the ACID properties. A schedule that cannot be made equivalent gives us no such guarantee and must not execute as it is. The decision "allow it to run, or reject it" is exactly the decision that concurrency-control mechanisms will automate later — which is why the next concept, the precedence graph, is such a valuable shortcut.

The professor's framing of the payoff: a conflict serializable schedule is allowed to run, and however it runs along the timeline, we treat it as equivalent to a serial schedule, so it will always follow the ACID properties. A schedule that cannot be made equivalent gives us no such guarantee. The decision "allow it to run, or reject it" is exactly the decision that concurrency-control mechanisms will automate later.

Real-world: real database engines never test schedules after the fact — that would mean cancelling work that already happened. Instead they enforce protocols (like two-phase locking, later in this session) that guarantee only conflict serializable schedules arise. The swap test in this section is the conceptual basis of those protocols.

15.6 The Precedence Graph: Visualizing Conflicts

15.6.1 Drawing the Graph

Instead of swapping operations by hand every time, we form a graph.

Precedence graph (also called the serialization graph or conflict graph): one node per transaction — $T_{1}, T_{2}, T_{3}, \dots$ — and, for every pair of conflicting operations, a directed arrow from the transaction that must come first to the transaction that must come after. The arrow says: there is a conflict, and the information conveyed by the edge is which transaction's operation must precede the other's.

The drawing rule is mechanical — three cases produce an edge:

If $T_{i}$ has written X and later $T_{j}$ reads X, draw $T_{i} \to T_{j}$ (the reader must come after the writer it reads from).
If $T_{i}$ reads X and $T_{j}$ later performs a write on X, draw $T_{i} \to T_{j}$ .
If both $T_{i}$ and $T_{j}$ write X, the later writer is $T_{j}$ , so draw $T_{i} \to T_{j}$ .

The test: the schedule is conflict serializable if and only if the precedence graph has no cycle.

Visual intuition: picture the graph for a two-transaction schedule as two circles labeled $T_{1}$ and $T_{2}$ . Each conflicting pair draws one arrow. If the arrows form a loop that returns to its start — $T_{1} \to T_{2}$ and also $T_{2} \to T_{1}$ — the two transactions demand to be ordered in contradictory ways, and no serial order can satisfy both. The one-sentence takeaway: an arrow says who must go first; a cycle says nobody can.

Why does the graph test work? An edge $T_{i} \to T_{j}$ records a requirement that $T_{i}$ precede $T_{j}$ in any equivalent serial schedule. A schedule is conflict serializable exactly when some serial order satisfies all requirements at once — which is possible if and only if the requirements contain no cycle. (The textbook name for extracting the serial order from an acyclic graph is topological sorting.)

15.6.2 The T1/T2 Graph: No Cycle

For the earlier $T_{1}, T_{2}$ schedule, the conflicts produce edges only from $T_{1}$ to $T_{2}$ : read A of one transaction conflicts with the write of the other, so we draw an arrow $T_{1} \to T_{2}$ , and the remaining pairs are not conflicting. Since there is no cycle in the graph, we conclude that the schedule is a conflict serializable schedule. This matches the manual swap test: this schedule is equivalent to that serial schedule after swapping non-conflicting operations.

Worked example — $T_{1} \to T_{2}$ , no cycle. Take the schedule from 15.5.2:

$S = r_{1} (A), w_{1} (A), r_{2} (A), w_{2} (B)$

Nodes: $T_{1}$ and $T_{2}$ . Conflicting pairs: $w_{1} (A)$ before $r_{2} (A)$ → case (1) gives edge $T_{1} \to T_{2}$ . No other conflicts (the other pairs are non-conflicting). Graph: two nodes, one arrow $T_{1} \to T_{2}$ , no cycle. Verdict: conflict serializable — the equivalent serial schedule is $T_{1}, T_{2}$ , which matches the swap walkthrough. Sense-check: the graph demanded exactly one order, $T_{1}$ before $T_{2}$ , and that order exists, so the schedule is admitted.

15.6.3 The T3/T4 Graph: A Cycle

Now consider $T_{3}$ and $T_{4}$ on the same data item Q, where the schedule has a read and a write of Q in different transactions:

$T_{3} : r_{3} (Q) T_{4} : w_{4} (Q) T_{3} : w_{3} (Q)$

The professor invites the class to draw this graph themselves and then completes it for completeness: there is a conflicting operation — two different transactions, same data item Q, and one of them is a write — so we draw an arrow from $T_{3}$ to $T_{4}$ . And there is a second conflicting operation: two different transactions on the same data item, and both of them are writes — so we also draw an arrow from $T_{4}$ to $T_{3}$ . Now there is a cycle in the graph, and a cycle means the schedule is not a conflict serializable schedule. That is how we distinguish conflict serializable from non-conflict serializable schedules: find the conflicting operations, note which transaction must precede which, draw the directed edges, and check for a cycle.

Worked example — the cycle. The schedule, in order:

$S = r_{3} (Q), w_{4} (Q), w_{3} (Q)$

Conflicting pairs on item Q:

$r_{3} (Q)$ before $w_{4} (Q)$ : case (2), $T_{3}$ read before $T_{4}$ wrote → edge $T_{3} \to T_{4}$ .
$w_{4} (Q)$ before $w_{3} (Q)$ : case (3), both writes → edge $T_{4} \to T_{3}$ .

Graph: two nodes with arrows in both directions — $T_{3} \to T_{4}$ and $T_{4} \to T_{3}$ . That is a cycle of length two. Verdict: NOT conflict serializable. Why does the cycle capture the real problem? $T_{3}$ reads Q, then $T_{4}$ overwrites Q without having read it, and then $T_{3}$ writes Q again. In any serial schedule, either $T_{3}$ runs entirely before $T_{4}$ (then $T_{3}$ 's read sees the old Q, but here $T_{4}$ 's write sits between $T_{3}$ 's read and write) or $T_{4}$ runs entirely before $T_{3}$ (then $T_{4}$ 's write cannot sit between $T_{3}$ 's read and write). Neither serial order reproduces this interleaving. Sense-check: the two arrows demand $T_{3}$ before $T_{4}$ and $T_{4}$ before $T_{3}$ — contradictory demands, exactly what a cycle means — so the schedule cannot run.

15.6.4 Student Questions and Answers

Q: When we say T3 and T4 — on the left-hand side we are saying read Q, on the right-hand side we are saying write Q — do we mean that both read Q and write Q happen at the same point of time? Or does T4 write after T3's read, and then T3 writes? How do we read this?

A: Beautiful question — let us be precise about what a read operation and a write operation mean, and about the timeline. When I say read Q, the first thing that happens is a seek towards the area of secondary storage where the data item Q actually resides; the entire block is read and brought into main memory. That is the operation of read Q. When I say write Q, we already have something in main memory with changes made to it, and I am writing it back to the block in secondary storage. So read means reading from secondary storage and write means writing back to secondary storage; both places involve a seek time and a read (transfer) time, and in our case the network delay may also be included. After reading, I may do certain changes — plus, minus, up, down, whatever — and when I say write Q, I write back to secondary storage. One honest caveat: when we discuss recoverability, the definition may be refined for optimization — I will generally use log-based storage, so that whenever I am writing, I write the log entries to secondary storage before commit, and the actual data pages may be written back at a more appropriate time. So attend that discussion too; this definition is not complete by itself. Second point: the clock is increasing in this manner. There is a single processor — I am assuming a single processor — and even if there are multiple cores, for simplicity we assume one processor executing one instruction at a time. There are clock cycles; you cannot execute the same thing simultaneously. One processor can execute one instruction at a time. Everything happening — different people making different changes — flows through that same processor, and the database is the single one being read and written. The requests may come from Japan, Russia, Europe, Australia, America, Canada, India — wherever — but our server resides at one place, and near to that place is where the database is accessed. First this operation happens in the database via the processor, then the next operation, one at a time. So when we write the schedule, we mean: operation by operation, in that left-to-right order — not at the same point of time.

Q: Can we compare this to a Git repository, where users commit, and if any other user commits before taking a pull, then that code will override the other person's code?

A: Absolutely, absolutely. What has happened here is that T3 reads first — first it pulls — and then it tries to commit something. T4 does not read anything; it just directly, almost bombardingly, goes to the same URL and tries to write to it. That is the difference I want to share: T4 has not read anything — it has not pulled anything. T3 has pulled, maybe done something, and then it is trying to commit. You have really visualized, in a very field-wise way, how any application will look. Thank you for that.

Q: Locks can be used to control all write transactions, right?

A: You will come to locks, and how transactions in a concurrent manner can be handled with lock-based access or timestamp-based access. We will cover it — let us move further.

Pitfalls:

Reading the schedule as simultaneous operations. Read Q and write Q are separate instructions executed one after another by a single processor; the left-to-right order in the schedule is the real timeline.
Forgetting that the write is a write-back. Write Q means "write the modified block back to secondary storage" — not "create Q in memory". If you miss the storage semantics, the whole recovery discussion later makes no sense.
Thinking one arrow is enough. A single arrow is fine; the killer is the cycle. Two transactions conflicting in both directions is the canonical non-serializable case.
Skipping the graph and guessing from the swap test. The graph exists precisely because hand-swapping is error-prone with three or more transactions — the cycle test is mechanical and complete.

Recap + Bridge: the precedence graph turns the swap test into a drawing: one node per transaction, one directed arrow per conflicting pair, and the rule acyclic ⇒ conflict serializable, cycle ⇒ reject. The T1/T2 graph passed with a single edge; the T3/T4 graph failed with a two-arrow cycle — the Git scenario (commit without pulling) is exactly that cycle in daily life. Next, the lecture asks a sharper question: is conflict serializability too strict? Some schedules fail the conflict test yet behave perfectly — that is the blind-write case, and it leads to view serializability.

Real-world: the Git scenario is a faithful picture of the same problem — a writer that never pulled the latest state overwrites the work of a writer that did pull. Version-control users have felt this exact conflict in daily work; the database schedule $T_{3}, T_{4}$ is the same story in a different setting.

15.8 Recoverability: What Happens When Failure Strikes

15.8.1 Failures Can Happen Anywhere

Serializability — conflict and view — focuses on the consistency part of ACID: before and after the transaction, constraints are followed. But we also need durability: the database must be recoverable if a failure happens in between. And failures come in many shapes. There can be a power failure; the hard disk or secondary storage can fail; a memory outage or power outage can hit the processor; a catastrophic change can happen.

Intuition: the professor makes the point physical — even the processor is made of hardware: diodes, gates, transistors, MOSFETs, proper circuits, combinations of circuits into a microprocessor. All of it involves materials with their own lifetime, and more current flowing through them for long enough can push them past their limits. Failures can happen at this point in time, at that point in time, at any place. A failure can even happen inside a transaction itself: you submitted a transaction, a read operation that was expected did not happen, or some auxiliary operation needed by the transaction hit an error — depending on something else, or on a failure in the database, in the memory, in the processor, or some other catastrophic or power failure. So the honest position is: failure may happen at any point of time, and the schedule must still be recoverable.

The failure taxonomy: failures are classified as transaction failures (a logical error, an error condition like insufficient balance, an abort by the concurrency-control method, a user interrupt), system failures (a crash of the processor — memory contents lost), and media failures (disk failure or catastrophe). The recovery subsystem must restore a consistent database state after any of them.

15.8.2 The Commit Promise

Recoverability rests on what commit promises. Commit says: not only are all the operations done, but I have made all the changes in secondary storage. After this point, whatever happens — even a catastrophic failure, even a hardware failure, whatever happens in the entire world — the database will remain durable.

The professor's image: I may have to "come back from my commit, come back from my promise" — and that is exactly what must never happen. A committed transaction must not roll back; the changes must be persistent throughout.

Scope — what commit does and does not promise:

Commit promises durability of the transaction's own changes: they will never be rolled back, and they will be redoable from the log even if the data pages were still in memory at crash time.
Commit does not promise that later transactions cannot overwrite the same items — that is normal database operation, controlled by serializability.
The price of the promise is discipline: the log records (old and new values of every write) must be written to disk before the commit is announced — the write-ahead logging rule. Only the log at commit is guaranteed to survive; everything still in main memory is lost at a system crash.

15.8.3 The Money Transfer Example

Real-world: the canonical illustration is a money transfer from my account to another account — in the example, the recipient account is called the Vegas account. The amount of the transaction has happened; money has been reflected in my account and in the Vegas account. After this point, money should not change hands without our intervention — that must not happen because of some failure.

Now walk through the failure case, with the account balance $B$ :

$B = 100 transfer out 10 B = 90$

If the transaction now aborts — say a failure happens before commit — the transaction will roll back and all its changes will be undone: the balance that was made 90 must be made 100 again.

$B = 90 rollback B = 100$

So far so good: the aborted transaction restored the value it changed. But now suppose another transaction had read $B$ while it was 90 — read the uncommitted value — and executed its own operations after that. This second transaction reads 90, adds 50, and writes back:

$90 + 50 = 140 written back to secondary storage$

Then the first transaction aborts, and $B$ is restored to 100 — but the second transaction already committed its 140, or at least performed its operations on the basis of 90. Now we have a real problem: either we are inconsistent (140 stands while the underlying balance is 100), or we violate durability (we must undo the second transaction's committed work, going back on the promise that anything that commits will not roll back). The professor's summary: "Either I am having a problem in consistency or I am having a problem in durability — I may have to come back from my commit." Failures on both sides.

Worked example — the full timeline. Let $B = 100$ at the start, and let $T_{1}$ be "transfer ₹10 out of the account" while $T_{2}$ is "compute balance times something based on a read".

Step	Transaction	Action	Balance $B$	Committed?
1	$T_{1}$	reads $B$	100	no
2	$T_{1}$	writes $B = 90$	90	no
3	$T_{2}$	reads $B = 90$ (uncommitted!)	90	no
4	$T_{2}$	computes and writes $B = 90 + 50 = 140$	140	yes (or about to commit)
5	$T_{1}$	aborts — rolls back to $B = 100$	100	no (aborted)
6	—	final state	100, but $T_{2}$ 's 140 was already committed	—

The contradiction at step 6: the database says $B = 100$ , yet a committed transaction's work (writing 140) has been undone in effect — or, if we keep 140, the state is inconsistent with the true balance of 100. Sense-check: the root cause is step 3 — $T_{2}$ read a value written by a transaction that had not committed. A recoverable schedule never allows that; it delays $T_{2}$ 's read until $T_{1}$ commits or aborts, so a rollback can never invalidate a committed read.

15.8.4 Non-Recoverable Schedules: Committing on Borrowed Time

The root cause of the disaster is visible now: the second transaction read a data item written by a transaction that had not committed. If I read from a transaction that has not committed, I can easily vouch that I might have trouble in recoverability.

The professor gives a real-world version of the risk: I read what the value of a ticket is at this point of time, or what the value of a room in a hotel is, and I take a decision separately — I should not book it, or I should not purchase this book — and after a month of time the value does not remain the same. Either I must overdo something, or I am inconsistent, because my decision happened outside the database and the data I based it on was not durable.

Recoverable schedule: a schedule is recoverable if no transaction commits until every transaction whose writes it read has committed. Equivalently: a transaction that reads from another may commit only after that writer commits.

Non-recoverable schedule: the violation — $T_{j}$ reads a data item written by $T_{i}$ , $T_{j}$ commits, and only afterwards $T_{i}$ commits (or $T_{i}$ aborts). In symbols: $r_{j} (X)$ after $w_{i} (X)$ , then $c_{j}$ before $c_{i}$ . The professor's verdict on committing after reading uncommitted data: "If I am reading something from the other transaction and I am committing first, this is suicide." Because a failure can happen at any point of time — and if it happens there, the uncommitted writer rolls back, and the committed reader cannot roll back, so the schedule is not recoverable.

In the money example, $T_{2}$ 's read of $B = 90$ and its commit before $T_{1}$ resolved made the schedule non-recoverable. The fix is commit ordering: force $T_{2}$ to wait — its commit may come only after $T_{1}$ commits or aborts. If $T_{1}$ commits, $T_{2}$ 's 140 stands on solid ground; if $T_{1}$ aborts, $T_{2}$ is rolled back too (it has not committed yet, so that is allowed).

15.8.5 Student Questions and Answers

Q: Can you repeat — what is recoverability, or rather non-recoverability?

A: Non-recoverability primarily means this: if a transaction is reading something — reading a data item written by another transaction — which is not committed yet, and I commit first, then I am a non-recoverable schedule. Because suppose a failure happens after my commit. The writer that had not committed will roll back; I cannot roll back — I have committed. So the chances are very high that whatever I read was not final. There are two problems at least. The bigger problem is that I am reading something from a transaction that has not committed. And the other bigger problem is that I am committing before that writer commits. If I read something from the other transaction and I commit first, this is suicide, because a failure can happen at any point of time, and if a failure happens here, I am not a recoverable schedule.

Pitfalls:

Thinking the abort of a failed transaction is the end of the story. The aborted transaction's rollback is only safe if nobody read its uncommitted values — otherwise the rollback cascades or invalidates committed work.
Believing "committed" means "safe from rollback" unconditionally. It does — but only if the schedule was recoverable. A transaction that committed after reading uncommitted data is precisely the one that breaks the promise.
Confusing recoverability with serializability. A schedule can be recoverable and still have the lost-update problem (a serializability issue), and a schedule can be serializable yet non-recoverable. The two theories guard different ACID properties: consistency vs durability.
Treating failure as a rare event. The design principle is the opposite: assume failure can happen between any two instructions, and build the schedule so that recovery is still possible.

Recap + Bridge: serializability protected consistency; recoverability protects durability. The commit promise — durable once committed — holds only if no transaction reads uncommitted data and commits first. The money-transfer example showed the exact disaster: read an uncommitted 90, write back 140, commit — then the writer aborts and the balance becomes 100, stranding the committed 140. Next we see the other failure problem, the chain reaction called cascading rollback, and the stronger schedule property that prevents it.

Real-world: the hotel-room and ticket examples in this section are the product story — a booking decision taken on a price or availability value that was never durable is exactly the failure a recoverable schedule prevents.

15.9 Cascading Rollback and Cascadeless Schedules

15.9.1 The Chain Reaction

There is a second failure problem, distinct from non-recoverability. Suppose transaction $T_{2}$ reads something written by $T_{1}$ , and transaction $T_{3}$ reads something written by $T_{2}$ . This schedule may still be recoverable — we have not committed at the wrong points — but it has a cascading rollback problem.

Intuition — the chain reaction: if something happens to $T_{1}$ — a network error or whatever error may happen (this person might be booking a ticket, or reserving a hotel room, or purchasing an item from Amazon or any other shopping application) — then $T_{1}$ aborts and rolls back. Because $T_{2}$ read something from $T_{1}$ , $T_{2}$ must also roll back. And because $T_{3}$ read something from $T_{2}$ , $T_{3}$ must also roll back. The rollback cascades down the chain. There is no problem with respect to recoverability — no one committed at a forbidden point — but the cascade itself is the problem: work that had nothing to do with the failed transaction is undone anyway.

Worked example — the cascade. Three transactions on item X:

$S = w_{1} (X), r_{2} (X), w_{2} (X), r_{3} (X), w_{3} (X)$

The dependency chain: $T_{2}$ read X written by $T_{1}$ ; $T_{3}$ read X written by $T_{2}$ . Suppose $T_{1}$ fails right after $w_{1} (X)$ and aborts. Then:

$T_{1}$ rolls back: $X$ returns to its pre- $T_{1}$ value.
But $T_{2}$ computed on the basis of $T_{1}$ 's value — its $w_{2} (X)$ is invalid → $T_{2}$ must roll back too.
And $T_{3}$ computed on the basis of $T_{2}$ 's value → $T_{3}$ must roll back as well.

Every transaction in the chain is undone — including $T_{3}$ , whose own work was perfectly fine. Sense-check: the schedule is recoverable (nobody committed before their writer), so recoverability is satisfied; yet one abort destroyed the work of three transactions. The problem is the read-from-uncommitted pattern, not the commit order.

15.9.2 Recoverable versus Cascadeless

The professor draws the distinction sharply, and repeats it: for recoverability, the requirement is that if I am reading a data item written by another transaction, that transaction should commit first. That is a recoverable schedule. For cascadelessness, the requirement is stronger: I should only read a data item written by a transaction that has already committed. Reading from committed data is what prevents cascading rollback — a cascadeless schedule never reads uncommitted values at all. So every cascadeless schedule is recoverable, but a recoverable schedule may still suffer cascading rollbacks.

Cascadeless schedule (avoids cascading rollback): every transaction in the schedule reads only items that were written by transactions that have already committed. If a transaction reads only committed values, then no abort can ever invalidate what it read — its work stands regardless of what happens to other transactions.

The containment: strict schedules ⊆ cascadeless schedules ⊆ recoverable schedules. Every cascadeless schedule is recoverable (a weaker requirement), and every recoverable schedule is not necessarily cascadeless. Textbooks add a third rung — strict schedules, where a transaction can neither read nor write an item until the last transaction that wrote it has committed — which simplifies recovery still further (an aborted write is undone simply by restoring its old value).

Scope — why this hierarchy matters in practice: cascading rollback is expensive — it can undo numerous transactions that never did anything wrong, and it wastes all their work (and the user interactions behind them). Practical protocols aim above mere recoverability: the standard in real engines is strict or cascadeless behavior, so that a single abort never triggers an avalanche. The strict two-phase-locking protocol used by commercial databases holds exclusive locks until commit precisely to guarantee this.

15.9.3 Student Questions and Answers

Q: Usually we do a commit on the write data — commit on the write — in databases. Is commit also possible on read operations?

A: Yes, you can do that — nobody is stopping you from committing after a read. Although you will not make any changes in the database: you just read it and you are committing, so nothing is written back.

Q: To maintain consistency, should we commit after every write?

A: No, no, no. Understand that right now, in our model, a transaction commits only once — and we will discuss this again under recoverability. If I commit every time, there is a performance bottleneck; cascading commits have their own performance implications. We cannot commit after every step. And there is a deeper reason: a transaction is a group of instructions in which everything should happen or nothing should happen. If I am committing halfway, I am saying it is okay for half the work to happen — which is against the atomicity property. In the pure sense of a transaction, commit should happen only at the end.

Q: Can we roll back after a commit operation, if some of the transactions went wrong?

A: After commit, understand that commit means the changes have happened in the hardware, in the secondary storage — and whatever happens in the world, I have promised that they will be persistent. That is what we want for durability. If I roll back a transaction that has already committed, I am moving away from the promise of durability — I am not durable. That is not a good thing, rather a very bad thing for any transaction; it does not follow the ACID properties.

Pitfalls:

Committing after every write "for safety". It breaks atomicity (half-work accepted) and creates a performance bottleneck — a transaction commits exactly once, at the end.
Rolling back committed transactions. Commit = durable; rolling back after commit breaks the durability promise and the ACID contract.
Thinking recoverable means no cascade. Recoverability only orders commits; cascading rollback can still occur in a recoverable schedule. If you want no cascade, require cascadelessness (read only committed data).
Confusing cascading rollback with non-recoverability. In cascading rollback nobody committed wrongly — the chain reaction is the problem; in non-recoverability, a commit order is wrong and recovery becomes impossible.

Recap + Bridge: recoverability says "writers commit before their readers"; cascadelessness says "read only from committed transactions". The second is stronger: every cascadeless schedule is recoverable, but recoverable schedules can still cascade. So the safe engineering target is cascadeless (ideally strict) behavior. We have now seen what correctness requires — serializability for consistency, recoverability and cascadelessness for durability. The final question of the session is how to enforce all of this: the lock-based and timestamp-based concurrency-control protocols.

Real-world: shopping applications, ticket booking, and hotel reservation systems all sit on this exact theory — a customer's cart calculation must never depend on a price that another transaction could later roll back, and one failed booking must never take down the booking attempts that followed it.

15.10 Concurrency Control: Locks and Timestamps

15.10.1 The Scenario: One Database, Many Geographies

The discussion that closes the session is about enforcement: how do we ensure that concurrent access at the database level is correct?

The database has a single copy of each data item — a single item Q, or a single record with an attribute name, or any one data item among A, B, C, D, P, Q, R, S. One user may be executing from one geographical region, another from a different one — and the database is a single one, placed at one place, with the application deployed and running at one place near it. Meanwhile somebody is reading, somebody is writing, somebody else is reading, somebody else is writing — on the same data item. How is that possible, with correctness preserved for everyone?

The professor frames it as a very, very difficult situation, and then names the two classic answers: the lock-based protocol, which works at the physical level of the database, and the timestamp-based protocol. "These are the only ones which we will discuss — other things are not the ones which I am that much interested in."

The two enforcement families:

Lock-based protocols — a transaction acquires a lock on a data item before accessing it; the lock manager grants or denies the request based on what other transactions hold. These are physical-level mechanisms and are what most commercial databases use.
Timestamp-based protocols — each transaction is assigned a unique timestamp at start; conflicting operations are then forced to execute in timestamp order, without any locking at all.

15.10.2 Shared and Exclusive Locks

In the lock-based protocol there are two different types of lock on a data item. If I am writing, I acquire an exclusive lock — and note: only on that item, not on the entire database. If I am reading, I acquire a shared lock, so that others know someone is reading the item.

Shared lock $S L (X)$ and exclusive lock $X L (X)$ on data item $X$ :

Shared lock — read lock: several transactions may hold shared locks on the same item at the same time, because reads do not conflict with reads.
Exclusive lock — write lock: at most one transaction can hold it, and while it is held, no other transaction may read or write the item.

The lock compatibility rules:

$S L (X) ∥ S L (X), S L (X) \neq ∥ X L (X), X L (X) \neq ∥ anything$

where $∥$ means "compatible with". Rendered from the spoken rules: if there are shared locks, other people can also access it; if there is an exclusive lock, a shared lock cannot be accessed; if there is an exclusive lock, no other lock can be accessed.

Current lock on $X$	Requested shared lock	Requested exclusive lock
Shared	compatible (granted)	not compatible (denied)
Exclusive	not compatible (denied)	not compatible (denied)

So shared locks may coexist; an exclusive lock blocks everything, including other exclusive locks.

Scope — the granularity point: the lock is on the data item, not the whole database. Exclusive-locking a single item still leaves every other item open to other transactions — this is what allows concurrency at all. The price of coarser granularity is less concurrency; the price of finer granularity is more lock-management overhead.

15.10.3 Why Locks Alone Are Not Enough

The professor walks through a transaction pair $T_{1}$ and $T_{2}$ where each transaction reads and writes. Step by step: $T_{1}$ wants to write something, so $T_{1}$ acquires a write lock; the lock is granted; $T_{1}$ reads, writes, and unlocks. Then $T_{2}$ acquires a shared lock; granted; $T_{2}$ reads and unlocks. Then $T_{2}$ acquires a shared lock on another item; granted; $T_{2}$ reads and unlocks. Then $T_{1}$ acquires an exclusive lock; granted; $T_{2}$ writes something, and $T_{1}$ releases the lock. Everything looks fine, nothing harmful — but the schedule that results has a conflict edge from $T_{1}$ to $T_{2}$ and a conflict edge from $T_{2}$ to $T_{1}$ . In other words, even though shared and exclusive locks were used, this locking scheme allowed something that is not a conflict serializable schedule.

Worked example — locked, granted, and still wrong. Two transactions $T_{1}$ and $T_{2}$ , items X and Y, where each transaction reads one item and writes another:

$T_{1}$ : $X L (X)$ , $r_{1} (X)$ , $w_{1} (X)$ , $U L (X)$ — then later $X L (Y)$ , $r_{2} (Y)$ , $w_{1} (Y)$ , $U L (Y)$ .
$T_{2}$ : $S L (X)$ , $r_{2} (X)$ , $U L (X)$ — then later $S L (Y)$ , $r_{2} (Y)$ , $U L (Y)$ .

Every lock request is granted legally: shared locks coexist, exclusive locks are exclusive, no rule is broken. Yet the resulting schedule — $r_{1} (X), w_{1} (X), r_{2} (X), r_{2} (Y), w_{1} (Y)$ — has conflicting pairs that force both directions: $w_{1} (X)$ before $r_{2} (X)$ gives $T_{1} \to T_{2}$ , while $r_{2} (Y)$ before $w_{1} (Y)$ gives $T_{2} \to T_{1}$ . A cycle. Sense-check: $T_{1}$ released its lock on X before locking Y — a transaction acquired, released, and acquired again. That acquire-release-acquire pattern is exactly what lets a schedule with a two-direction conflict slip through. Shared/exclusive locking alone does not guarantee serializability.

The lesson: shared/exclusive locking alone does not guarantee serializability — "even if I am following a lock with shared and exclusive, there needs to be a proper method in which I can access; otherwise the lock scheme is allowing me something which is not conflict serializable." If we want to execute only conflict serializable schedules, we must control the physical-level locking so that only correct transactions run — and correct means following the ACID properties.

15.10.4 Two-Phase Locking: Growing and Shrinking

The fix is the discipline of a growing phase and a shrinking phase.

Two-phase locking (2PL): every transaction is divided into two phases:

Growing (expanding) phase — the transaction may acquire locks, but may not release any.
Shrinking phase — the transaction may release locks, but may not acquire any new ones.

As soon as a transaction releases its first lock, it enters the shrinking phase and can never acquire a lock again. The moment of the first unlock is called the lock point; after the lock point, no more lock granting is possible — only lock releasing.

In the growing phase, a transaction may always acquire locks. As soon as it releases one lock, it enters the shrinking phase, and after that point it cannot acquire any other lock. There is a lock point: after the lock point, no more lock granting is possible; only lock releasing.

The problem with the previous walkthrough, if you can visualize it: the transaction released a lock and, after a point of time, started acquiring another lock — it had the possibility of writing at two different points of time on two different data items. And after one transaction released its lock, another could acquire a lock on that data item and do things on it. If a transaction can acquire, release, and acquire again, conflict serializability is very, very difficult to enforce. With only the growing phase, and then pure releasing — "as soon as I am starting releasing, no one is allowed to acquire" — at least let us compute and see what is possible.

The guarantee and its price: the two-phase locking protocol guarantees that every permitted schedule is conflict serializable — the cycle-producing pattern (unlock, then lock again) is structurally impossible. The price is concurrency: a transaction may have to keep holding locks on items it is done with, because releasing them early would put it into the shrinking phase too soon. Real engines accept this price because it removes the need to test schedules at all. The protocol does not prevent deadlock (two transactions each holding a lock the other wants) — that problem is handled separately, typically by detection and aborting one of the deadlocked transactions.

15.10.5 Variants: Conservative, Strict, and Rigorous Locking

The professor previews that this scheme has variations: conservative locking, strict locking, and rigorous locking. Depending on the variant, the questions differ: should a transaction acquire all the locks before it starts? Should it release no lock until it commits? Should it start releasing only the exclusive locks, or only the shared locks? Each answer gives a different version of lock-based access.

The three 2PL variants:

Conservative (static) 2PL — a transaction locks all the items it will ever access before it begins (predeclaring its read-set and write-set); if any item cannot be locked, it locks nothing and waits. Deadlock-free by construction, but impractical because the full access set is rarely known in advance.
Strict 2PL — a transaction does not release any of its exclusive (write) locks until after it commits or aborts. This guarantees strict schedules (no other transaction can read or write an item the transaction wrote until it is resolved) and hence cascadeless recovery. This is the variant used by most commercial DBMSs.
Rigorous 2PL — a transaction does not release any lock, shared or exclusive, until after it commits or aborts. Even simpler to implement, but the least concurrent.

The details are for the coming session — this is explicitly a teaser trailer: in this particular scheme there are two phases, growing and shrinking; in another scheme, as soon as the transaction unlocks it cannot acquire another lock; in yet another, the transaction can only upgrade locks and cannot release them. We will discuss it very soon.

15.10.6 Timestamp-Based Ordering: Tokens for Transactions

The other mechanism is the timestamp-based protocol (the professor also calls it transaction-based access).

Whenever a transaction enters for the first time, a timestamp is noted down — the clock always grows. If a transaction enters at timeline 12, its timestamp is 12; a later transaction may first execute at timeline 14. The heart of timestamp-based concurrency is that the timestamp decides the order.

Intuition — the token analogy: in many restaurants, as soon as you order, you get a token number, and you are comfortable that your order will be served according to your token number. Hospitals work the same way — you take a token and know the doctor will see you in half an hour, one hour, or after six hours or eight hours. Even at religious places the token has arrived: at the Mata Vaishno Devi temple near Katra in Jammu, tokens were introduced — before that, visitors (the professor remembers visits around 2005 and 2012) faced a line of two days, standing and polling to check whether your turn had come; with a token you know the number and come back about when your turn approaches. In transactions the same idea helps: if my transaction is first and somebody else's is later, the timestamp number orders the transactions.

Timestamp ordering (TO): each transaction $T$ receives a unique timestamp $T S (T)$ — its ticket number — assigned in submission order, so $T_{1}$ starting before $T_{2}$ means $T S (T_{1}) < T S (T_{2})$ . Every data item $X$ remembers the timestamps of the transactions that last touched it: $r e a d_T S (X)$ (the largest timestamp among transactions that read X) and $w r i t e_T S (X)$ (the largest among those that wrote X). When a transaction requests an operation, the protocol compares timestamps:

Write rule: $T$ may write $X$ only if $r e a d_T S (X) \leq T S (T)$ and $w r i t e_T S (X) \leq T S (T)$ . If a younger transaction already read or wrote $X$ , $T$ 's write is rejected — it is too late; it would violate the ticket order.
Read rule: $T$ may read $X$ only if $w r i t e_T S (X) \leq T S (T)$ . If a younger transaction already wrote $X$ , $T$ 's read is rejected — it would read a value that, in the timestamp order, it was never supposed to see.

A rejected transaction is aborted and restarted as a brand-new transaction with a new timestamp.

And the seniority carries a penalty for sloppiness: if I am the senior transaction — I entered first — and I make a mistake by reading outside my time, I need to be penalized and start once again. That is the basic idea; the details of the protocol are reserved for the next session, which is based on the timestamp-based protocol and the lock-based protocol in detail.

Pitfalls (preview):

Thinking locks are the only mechanism. Timestamp ordering needs no locks and no waiting — which means deadlock is impossible — but it pays by aborting and restarting transactions that arrive too late.
Believing the timestamp is optional bookkeeping. The timestamp is the order: the whole serial order of a timestamp schedule is fixed by the ticket numbers, unlike 2PL where the order emerges from lock acquisitions.
Forgetting that an aborted restart gets a new ticket. A restarted transaction is a new transaction with a new (later) timestamp — the same job moves to the back of the queue.
Expecting both families to admit the same schedules. Each protocol allows some schedules the other forbids; neither allows all serializable schedules.

15.10.7 The Two Paths Forward

Recap + Bridge: enforcement comes in two families. The lock-based protocol guards every data item with shared/exclusive locks and the two-phase discipline (growing, shrinking, lock point) to guarantee conflict serializability; conservative, strict, and rigorous variants trade concurrency for recoverability guarantees. The timestamp-based protocol hands each transaction a ticket — its timestamp — and forces conflicting operations to respect ticket order, with the seniority penalty for reading outside one's time. Which one allows what, and how it executes, will be analyzed in the next session. The discussion of concurrency control ends with an open invitation for questions.

Summing up, the professor gives the roadmap: there are two different things — the lock-based protocol, which allows access while following certain properties (consistency, recoverability, the cascadeless-rollback property), and the timestamp-based protocol. Which one allows what, and how it executes, will be analyzed in the next session.

Real-world: lock-based protocols (shared and exclusive locks, two-phase locking with growing and shrinking phases) are the physical-level mechanism real database engines use to admit only conflict serializable schedules; the token systems of restaurants, hospitals, and the Mata Vaishno Devi temple are the everyday picture of the timestamp order that transaction-based access implements.

15.11 Assignment and Evaluation Guidance

15.11.1 The Indexing Assignment: Understanding over SQL

Exam note: the assignment on indexing does not ask you to create indexes in SQL. The professor is explicit: "I am not asking you to create indexes in SQL. Read the insight. I just want you to analyze: if you create an index, what will happen? What is the performance implication?" The requirement is your understanding: if I create an index, what index should I create, why should I create it, and what may happen because of creating and having an index — from a theoretical perspective. The deliverable is your understanding, explanation, and detailed reasoning about indexing for the database you created — not SQL statements.

If you have already done it in SQL, that is well and good; if somebody has built a frontend too, you will not be penalized for it — the professor would be happy to help you make it even better — but equally, nobody is penalized for not writing it in SQL. A written theoretical explanation is enough.

Q: In the assignment, when we add primary keys and foreign keys, some automatic indexes are created by the database. Do we really need to create new indexes, or can we just retain the automatic ones?

A: Understand this: the index that SQL creates automatically for a primary key has its purpose. If you create a new index, the purpose will be the same kind of thing. So if you can explain that purpose in words — whenever you are writing something, understand that there is an index, and I am creating an index for this purpose — that is achieving indexing. That is the level of understanding the assignment wants.

Q: So mentioning where and why an index should be added, and how it will help, is enough?

A: Correct. A written theoretical understanding is enough — it is more than enough.

Real-world: automatic indexes on primary and foreign keys are a standard behavior of commercial databases; the assignment asks you to recognize that behavior and articulate its purpose rather than just execute it.

15.11.2 Quizzes, Deadlines, and Makeup Policy

Exam note: the evaluation structure is EC1, EC2, and EC3 as per the handout: for EC1 there are components such as three quizzes and the assignment; EC2 is the mid-semester; EC3 is the comprehensive. A reminder was given that the quiz must be submitted by the 30th — today everyone must submit, or marks may be lost. For any EC1 component there is no provision for makeup — including the three quizzes and including the assignment: the professor cannot open the quiz again, cannot write another 25 questions, cannot create a further assignment. There is an operational limitation behind this, so please ensure you meet the timelines.

15.11.3 Submission Logistics and Student Questions

Q: On the assignment submission portal, I think the deadline dates still show 2023, so it should not be constituted as a delayed submission.

A: Just a minute — you mentioned this last time as well, and it was because of that that a student had an issue; the date could not be edited beforehand. It is uploaded now, and those who have submitted do not need to resubmit. I can see 38 submissions and one draft. So to help others: you will not be penalized for something for which you had due time and could not submit because of that portal issue.

Q: Is it possible to extend the submission time?

A: I am afraid it is not possible. I already extended it by two weeks — that is the maximum I can do. It will take me time to evaluate, and I need to give you your EC1 marks at an appropriate time so that you can come and discuss with me if you want. Because of this reason, I will not be able to extend even by a single day.

Q: How many queries do we need to take screenshots of for the assignment?

A: See that it is reasonable. I cannot say a specific number. Take any good number that is fine — a number that is reasonable for you to justify that you have done the work. Just do not give one that will look very odd. Make sure you are doing a reasonable job.

Pitfalls for the assignment:

Submitting SQL statements instead of understanding. The deliverable is written reasoning — which index, why, and what the performance implication is — not code. SQL is optional and never penalized, but it is also not what is being graded.
Ignoring automatic indexes. Primary and foreign keys come with automatic indexes; the assignment rewards recognizing that fact and explaining the purpose of an index in that context.
Missing the deadlines. The quiz must be submitted by the 30th — today — and no EC1 component (quizzes or assignment) has any makeup provision. The assignment deadline has already been extended by two weeks and cannot move again.

Exam Guidance Summary

The indexing assignment asks for understanding, not SQL: analyze what happens when an index is created, what the performance implication is, which index to create and why — in written words. Creating indexes in SQL or building a frontend is optional and never penalized; a written theoretical explanation is enough.
Mentioning where and why an index should be added and how it helps satisfies the assignment.
Automatic indexes on primary and foreign keys exist in databases; the assignment wants you to articulate the purpose of an index in that context.
Quiz and assignment are both due this week; the quiz must be submitted by the 30th — submit today or marks may be lost.
Evaluation structure: EC1 (three quizzes plus the assignment), EC2 (mid-semester), EC3 (comprehensive), as per the handout. There is no makeup for any EC1 component, including the three quizzes and the assignment.
The assignment deadline cannot be extended further (it was already extended by two weeks); the portal date issue is resolved and no resubmission is needed for the 38 students who already submitted.
The number of query screenshots should be reasonable and justifiable; there is no fixed count.
The next session covers the timestamp-based protocol and the lock-based protocol in detail — including the conservative, strict, and rigorous variants of locking.
For the theory in this session: be able to state the conflict condition (different transactions, same item, at least one write), draw a precedence graph and read a cycle, apply the three view-equivalence conditions, and distinguish recoverable, cascadeless, and strict schedules — each of these is a standard exam question shape.

Key Industry Applications

Real-world: transactions are the unit of banking operations, sales and purchase operations, and anything of that shape — the ACID properties (atomicity, consistency, isolation, durability) are the contract every such application relies on. Airline reservations, credit-card processing, stock trading, and online retail all run as transaction processing systems.
Real-world: cloud deployment patterns — a database (such as an RDS instance in North Virginia) served to applications in different regions (for example Singapore) — reduce to the same concurrency problem, with network delay added to seek time and read time. Geographically distributed applications do not change the concurrency theory; they only add $t_{network}$ to the access cost.
Real-world: the Git workflow is the everyday version of the read-write conflict — committing without pulling overwrites another person's work, exactly like a transaction that writes without having read the latest value.
Real-world: ticket booking, hotel room reservation, and shopping applications depend on not reading prices or availability that are not durable; the non-recoverable-schedule failure (read an uncommitted value, take a decision, the value later rolls back) is the product-level disaster these rules prevent.
Real-world: money transfer is the canonical recoverability example — a transfer reflected in both accounts must stay reflected; an abort must restore the balance; a stale read of an uncommitted balance (90 + 50 = 140 written back) corrupts the database.
Real-world: token-based ordering is everywhere — restaurants, hospitals, and the token system at the Mata Vaishno Devi temple near Katra — and it is the everyday intuition behind timestamp-based concurrency control.
Real-world: commercial databases create B+ tree indexes, and automatic indexes on primary and foreign keys are standard; recognizing the purpose of these indexes is the practical skill the assignment tests.
Real-world: lock-based protocols (shared and exclusive locks, two-phase locking with growing and shrinking phases) are the physical-level mechanism real database engines use to admit only conflict serializable schedules; commercial DBMSs run strict two-phase locking so that aborts never cascade.

DDA Lecture 15 notes · Transactions: Schedules, Serializability, and Recovery

Database Design and Applications· postgraduate· 2026-08-06

Sections Breakdown

115.1 The Story So Far: From Requirements to Transactions

Recap of the course arc — requirements, ER diagram, relational schema, normalization, and indexing — and why many simultaneous users force the transaction concept.

215.2 Transactions and the ACID Properties

The transaction as a unit of program that executes as a chunk, and the four ACID properties: atomicity, consistency, isolation, and durability.

315.3 Transaction States: From Active to Committed or Aborted

The five transaction states from active to committed or aborted, and what commit physically means in secondary storage.

415.4 Schedules and Conflicting Operations

Schedule notation, serial schedules as the ACID yardstick, the three-condition conflict definition, a worked pair table, and student Q&A on distributed access.

515.5 Conflict Serializability: Swapping to a Serial Schedule

Conflict serializability by swapping non-conflicting operations toward a serial schedule, with worked swaps and the impossible-swap case.

615.6 The Precedence Graph: Visualizing Conflicts

Drawing the precedence graph, the cycle test, worked T1/T2 and T3/T4 examples, and the Git commit-without-pull analogy.

715.7 View Serializability and Blind Writes

The three view-equivalence conditions, the blind-write example that passes view but fails conflict serializability, and why the conflict graph is checked first.

815.8 Recoverability: What Happens When Failure Strikes

The failure taxonomy, the commit promise, the money-transfer disaster, and why committing after reading uncommitted data is suicide.

915.9 Cascading Rollback and Cascadeless Schedules

The cascading-rollback chain reaction, recoverable versus cascadeless schedules, and the strict ⊆ cascadeless ⊆ recoverable containment.

1015.10 Concurrency Control: Locks and Timestamps

Shared and exclusive locks, why locks alone are not enough, two-phase locking and its variants, and timestamp-based ordering with the token analogy.

1115.11 Assignment and Evaluation Guidance

The indexing assignment (understanding over SQL), automatic indexes, quiz deadlines, makeup policy, and submission logistics.

12Exam Guidance Summary

Distilled exam guidance: assignment expectations, evaluation structure, deadlines, and the standard theory question shapes.

13Key Industry Applications

Real-world anchors: banking ACID, cloud deployment latency, Git conflicts, bookings and durable values, token ordering, and strict two-phase locking.

Postgraduate students in Database Design and Applications

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

The Story So Far: From Requirements to Transactions

Must-know: The course flow: requirements to ER diagram to relational schema, normalization (1NF-3NF, BCNF), indexes (B+ trees, hashing), and now transactions as the layer that handles concurrent access.

⚠️ Top pitfall: Thinking serial execution is acceptable in production — it wastes processor time and forces every user to wait; the goal is concurrent execution that is still equivalent to a serial one.

Self-check: Why do we want concurrent access to the database instead of serial execution?

Connects to: Transactions and the ACID Properties, Schedules and Conflicting Operations

Transactions and the ACID Properties

Must-know: ACID: atomicity (everything or nothing), consistency (constraints satisfied before and after), isolation (executing concurrently feels like executing alone, as good as serial), durability (once committed, changes persist through any failure). The properties are absolutely uncompromisable.

⚠️ Top pitfall: Committing in the middle of a transaction — it accepts half the work (violates atomicity) and creates a performance bottleneck; commit belongs only at the end.

Self-check: A transfer of 500 from account A to account B: which ACID property is tested by checking that the total money before equals the total money after?

Connects to: The Story So Far: From Requirements to Transactions, Transaction States: From Active to Committed or Aborted

Transaction States: From Active to Committed or Aborted

Must-know: States: active, partially committed, committed, failed, aborted. Commit = all operations complete AND changes durable in secondary storage (log forced to disk); after commit nothing can be rolled back.

⚠️ Top pitfall: Confusing 'finished executing' (partially committed) with 'committed' — persistence, not completion, is what commit guarantees.

Self-check: What happens if the system fails after a transaction writes its changes but before commit?

Connects to: Transactions and the ACID Properties, Recoverability: What Happens When Failure Strikes

Schedules and Conflicting Operations

Must-know: Two operations conflict iff different transactions, same data item, at least one write. Schedule notation: r_i(X) / w_i(X). Access time = t_seek + t_read + t_network for distributed access; reads never conflict.

$o_{i} (X) and o_{j} (X) conflict ⟺ i \neq = j, same data item X, and at least one of o_{i}, o_{j} is a write$

⚠️ Top pitfall: Applying only one condition of the conflict test — same transaction, different data item, or two reads each alone make a pair non-conflicting.

Self-check: Do r_1(A) and w_2(B) conflict? Why?

Connects to: Conflict Serializability: Swapping to a Serial Schedule, The Precedence Graph: Visualizing Conflicts, Recoverability: What Happens When Failure Strikes

Conflict Serializability: Swapping to a Serial Schedule

Must-know: A schedule is conflict serializable if swapping only non-conflicting operations can turn it into a serial schedule; conflicting operations are never swapped because the read-from relationship would change.

⚠️ Top pitfall: Trying to swap conflicting operations — that changes which transaction's value a read sees or which transaction writes the final value.

Self-check: Why is a serial schedule always allowed to run?

Connects to: Schedules and Conflicting Operations, The Precedence Graph: Visualizing Conflicts, Concurrency Control: Locks and Timestamps

The Precedence Graph: Visualizing Conflicts

Must-know: Precedence graph: node per transaction, edge from the transaction that must come first to the one that must come after for every conflicting pair. Conflict serializable iff the graph has no cycle. r3(Q), w4(Q), w3(Q) gives a two-arrow cycle → not serializable.

⚠️ Top pitfall: Reading the schedule as simultaneous operations — a single processor executes one instruction per clock cycle; read = bring block into main memory, write = write back to secondary storage.

Self-check: For the schedule r1(A), w2(A), w1(A): draw the precedence graph — is it conflict serializable?

Connects to: Schedules and Conflicting Operations, Conflict Serializability: Swapping to a Serial Schedule, View Serializability and Blind Writes

View Serializability and Blind Writes

Must-know: View equivalence = same initial reads, same read-from relations, same final writes per item. Conflict serializable ⇒ view serializable, not conversely. Blind write = write without a preceding read in that transaction. Check conflict graph first; view check is exhaustive (n! orders).

$S \equiv_{view} S^{'} ⟺ \forall X : initial read of X by the same transaction, read-from relations the same, final write of X by the same transaction$

⚠️ Top pitfall: Declaring a schedule not view serializable after one failed serial order — the check must exhaust all possibilities.

Self-check: Why is r1(Q), w2(Q), w1(Q), w3(Q) not conflict serializable but view serializable?

Connects to: Conflict Serializability: Swapping to a Serial Schedule, The Precedence Graph: Visualizing Conflicts, Concurrency Control: Locks and Timestamps

Recoverability: What Happens When Failure Strikes

Must-know: A schedule is recoverable iff no transaction commits until every transaction whose writes it read has committed. Reading uncommitted data and committing first is suicide — the committed reader cannot roll back when the writer fails.

$B = 100 transfer out 10 B = 90 B = 90 rollback B = 10090 + 50 = 140 written back$

⚠️ Top pitfall: Thinking an abort only affects the aborted transaction — if another transaction read its uncommitted value, the rollback invalidates committed work.

Self-check: In the money example, what was the root cause of the 100-vs-140 contradiction?

Connects to: Transaction States: From Active to Committed or Aborted, Cascading Rollback and Cascadeless Schedules

Cascading Rollback and Cascadeless Schedules

Must-know: Recoverable: the writer must commit before a reader of its data commits. Cascadeless: read only data written by committed transactions. Every cascadeless schedule is recoverable; recoverable schedules may still cascade. Commit once, at the end; never roll back after commit.

⚠️ Top pitfall: Committing after every write — violates atomicity and creates a performance bottleneck; a transaction commits exactly once at the end.

Self-check: Why is a cascadeless schedule automatically recoverable, but not the other way around?

Connects to: Recoverability: What Happens When Failure Strikes, Concurrency Control: Locks and Timestamps

Concurrency Control: Locks and Timestamps

Must-know: SL coexists with SL; XL blocks everything. Locks alone do not guarantee serializability — 2PL (growing phase, then shrinking; lock point after first unlock) does. Variants: conservative (all locks up front), strict (no exclusive unlock before commit), rigorous (no unlock before commit). Timestamp ordering: the timestamp decides the order; the senior transaction is penalized for reading outside its time.

$S L (X) ∥ S L (X), S L (X) \neq ∥ X L (X), X L (X) \neq ∥ anything$

⚠️ Top pitfall: Acquiring, releasing, and re-acquiring locks — the unlock-then-relock pattern lets a non-serializable schedule through; 2PL forbids it via the lock point.

Self-check: Why did the T1/T2 lock walkthrough produce a conflict cycle even though every lock request was granted legally?

Connects to: Conflict Serializability: Swapping to a Serial Schedule, The Precedence Graph: Visualizing Conflicts, Cascading Rollback and Cascadeless Schedules

Assignment and Evaluation Guidance

Must-know: Assignment: explain the purpose of an index and its performance implication in words (SQL optional, never penalized; automatic PK/FK indexes already exist). Quiz due the 30th; no makeup for any EC1 component; deadline already extended by two weeks.

⚠️ Top pitfall: Writing SQL statements instead of the required theoretical explanation — the assignment grades understanding, not code.

Self-check: Why is 'explaining the purpose of an automatic primary-key index' enough to satisfy the assignment?

Connects to: The Story So Far: From Requirements to Transactions

Exam Guidance Summary

Must-know: Assignment = theoretical understanding of indexing (what an index does, why create it, performance implication); SQL optional. Quiz due the 30th; no makeup for EC1. Next session: lock-based and timestamp-based protocols in detail.

⚠️ Top pitfall: Submitting SQL rather than the required written reasoning.

Self-check: What does the assignment want you to analyze when you create an index?

Connects to: Assignment and Evaluation Guidance

Key Industry Applications

Must-know: Real-world anchors: ACID in banking and retail; network delay adds to access cost in cloud deployments; Git commit-without-pull is the read-write conflict; bookings depend on durable values; token ordering underlies timestamp protocols; strict 2PL is what commercial engines run.

Self-check: How does a Git commit-without-pull scenario map to a transaction conflict?

Connects to: Schedules and Conflicting Operations, Recoverability: What Happens When Failure Strikes, Concurrency Control: Locks and Timestamps

Previous LectureLecture 14 · B+ Trees, Transactions, and ACID

Next LectureLecture 16 · Concurrency Control: Lock-Based and Timestamp-Based Protocols

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

15.1 The Story So Far: From Requirements to Transactions

15.1.1 The Path We Have Walked

15.1.2 The Next Problem: Many People, One Database

15.2 Transactions and the ACID Properties

15.2.1 What a Transaction Is

15.2.2 Atomicity: Everything or Nothing

15.2.3 Consistency: Constraints Before and After

15.2.4 Isolation: The Feeling of Being Alone

15.2.5 Durability: The Promise of Persistence

15.3 Transaction States: From Active to Committed or Aborted

15.3.1 The State Diagram

15.3.2 What Commit Really Means

15.4 Schedules and Conflicting Operations

15.4.1 Schedules and Serial Schedules

15.4.2 Schedule Notation

15.4.3 The Definition of a Conflicting Operation

15.4.4 The T1/T2 Pair Example

15.4.5 Student Questions and Answers

15.5 Conflict Serializability: Swapping to a Serial Schedule

15.5.1 The Brute-Force Idea

15.5.2 The T1/T2 Swap Walkthrough

15.5.3 When Swapping Is Impossible

15.5.4 The Guarantee You Get

15.6 The Precedence Graph: Visualizing Conflicts

15.6.1 Drawing the Graph

15.6.2 The T1/T2 Graph: No Cycle

15.6.3 The T3/T4 Graph: A Cycle

15.6.4 Student Questions and Answers

15.7 View Serializability and Blind Writes

15.7.1 When Conflict Serializability Is Too Strict

15.7.2 View Equivalence: The Three Conditions

15.7.3 The T1/T2/T3 Example with Blind Writes

15.7.4 The Relationship Between the Two Serializabilities

15.7.5 The Cost of View Serializability

15.7.6 Student Questions and Answers

15.8 Recoverability: What Happens When Failure Strikes

15.8.1 Failures Can Happen Anywhere

15.8.2 The Commit Promise

15.8.3 The Money Transfer Example

15.8.4 Non-Recoverable Schedules: Committing on Borrowed Time

15.8.5 Student Questions and Answers

15.9 Cascading Rollback and Cascadeless Schedules

15.9.1 The Chain Reaction

15.9.2 Recoverable versus Cascadeless

15.9.3 Student Questions and Answers

15.10 Concurrency Control: Locks and Timestamps

15.10.1 The Scenario: One Database, Many Geographies

15.10.2 Shared and Exclusive Locks

15.10.3 Why Locks Alone Are Not Enough

15.10.4 Two-Phase Locking: Growing and Shrinking

15.10.5 Variants: Conservative, Strict, and Rigorous Locking

15.10.6 Timestamp-Based Ordering: Tokens for Transactions

15.10.7 The Two Paths Forward

15.11 Assignment and Evaluation Guidance

15.11.1 The Indexing Assignment: Understanding over SQL

15.11.2 Quizzes, Deadlines, and Makeup Policy

15.11.3 Submission Logistics and Student Questions

Exam Guidance Summary

Key Industry Applications

DDA Lecture 15 notes · Transactions: Schedules, Serializability, and Recovery

Sections Breakdown

Exam Revision Notes

The Story So Far: From Requirements to Transactions

Transactions and the ACID Properties

Transaction States: From Active to Committed or Aborted

Schedules and Conflicting Operations

Conflict Serializability: Swapping to a Serial Schedule

The Precedence Graph: Visualizing Conflicts

View Serializability and Blind Writes

Recoverability: What Happens When Failure Strikes

Cascading Rollback and Cascadeless Schedules

Concurrency Control: Locks and Timestamps

Assignment and Evaluation Guidance

Exam Guidance Summary

Key Industry Applications

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat