B+ Trees, Transactions, and ACID

14.1 The B+ Tree: Structure and Node Capacity

14.1.1 Why the B+ Tree Exists

The indexing story so far: a single-level index was fine until it consumed too much memory, so we built a multi-level index out of it. A multi-level index tells us where the actual block is on disk, and within that block we can locate the actual data — we studied several variants of this, including dense index, sparse index, and so on. But multi-level indexing had a serious flaw: insertion and deletion were a pain. Every time a record was inserted or deleted, the index had to be rebuilt or rearranged, and that was an expensive affair.

The B-tree was the response: insertion and deletion became relatively fine. Adding or removing values and making whatever changes were required in a B-tree was no longer impossible or prohibitively expensive. But even the B-tree left one gap — range queries were not easy. Whenever we had to answer a range query (give me all keys from $K_2$ to $K_Q$), things became very, very difficult.

The analogy's break point: a B+ tree is not a fixed set of drawers — its blocks split and merge, so the structure grows and shrinks with the data. The "filing drawer" picture captures the layout, not the dynamics; the dynamics come in Sections 14.2 and 14.3.

Real-world: any real database system that creates an index through SQL creates a B+ tree under the hood — that is the default structure behind the create index statement. Oracle, SQL Server, and PostgreSQL all ship B+ tree–style indexes as their workhorse index type, precisely because real workloads are dominated by range scans ("all orders between these two dates"), not just point lookups.

14.1.2 The Node Layout: Keys and Pointers

A B+ tree node is described by a single number called the p value (spoken as "p-value"): p tells us how many pointers a particular block can hold.

• In the root or at any intermediate level, a node holds keys $K_1,K_2,\dots ,K_n$ and, between and around them, pointers. With $n$ keys there are $n+1$ pointers:

$$n\text{ keys}\Rightarrow n+1\text{ pointers},p=n+1$$

Each pointer in an internal node is a block pointer: it points to another block of the tree — the next level of the index. The keys between two pointers are the routing values: everything in the subtree under a pointer is bounded by the keys around that pointer.

• At the leaf level (also called the child level), the node contains the actual data values, which we again call keys, and each key has a record pointer pointing to the physical block on disk that contains the record with that key. That is the crucial structural difference: in internal nodes the pointers are block pointers (they point to the next level of index), but at the leaf level the pointers are record pointers (they point to the actual records). The last slot of a leaf node holds one more pointer — a pointer to the next leaf block coming after it.

That next-leaf pointer is what makes range queries easy. For a range query from $K_2$ to $K_Q$ spanning different blocks, we start at the leaf level from the block holding $K_2$, follow the record pointers, and when one leaf is exhausted we just walk the next-leaf pointer to the next block, without climbing back up the tree. We have all the record pointers for the whole range laid out in order. This is how searching in a B+ tree becomes easier for range queries.

14.1.3 The Capacity Rules

The capacity rules of a B+ tree follow directly from p:

• Maximum keys in a block: $p-1$.
• Minimum keys in a block: $\lceil \frac{p}{2}\rceil -1$ (the spoken description was "four divided by two, ceiling minus one", which for $p=4$ gives $\lceil 4/2\rceil -1=2-1=1$).

For our running example, $p=4$: at most we can store three keys in a block, and the pointers are at most four. The minimum number of keys is one — fall below one and the block is in trouble, which is what triggers deletion restructuring (see Section 14.3).

These are not idle bookkeeping numbers: they are the boundaries that decide when a block must split on insertion and when it must merge on deletion.

(Real-world connection: the same $p$ rules are why a B+ tree on a 8 KB disk block keeps its height at 2–4 levels even for tables with millions of rows — each level multiplies the fan-out, so log-like search cost translates directly into a handful of physical disk reads.)

14.2 Building a B+ Tree by Hand (p = 4): The Worked Construction

14.2.1 The Values and the Rules

We construct a B+ tree from the values 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and later add 21, 13, and 11, with $p=4$. Two conventions must be fixed before we start, because a B+ tree split has freedom in it:

1. Median ordering. When a block overflows and has to split, we pick the median value to promote. With an even number of keys there are two middle values, and we may choose either — left ordering or right ordering. In the previous session left ordering was used; today we use right ordering: always take the right value when there is a clash. Whatever we decide, we must use it consistently throughout the tree.
2. Equal-to rule. When a promoted key value equals a value in the leaves, we must decide which side the equal value lives on. The rule used today: whenever a value is equal to a promoted key, it stays on the left-hand side block. (Last time it was placed on the right-hand side — either is fine as long as it is applied everywhere.)

A strong piece of advice given before the walkthrough: attempt the construction yourself along with the walkthrough, even if you get it wrong. The attempt is what makes you attentive, and it exposes what you don't know you don't know — a mistake made before seeing the solution is worth more than a silent agreement with it.

14.2.2 Inserting 1 Through 4: The First Split

Inputs & outputs. Input: a stream of key values with their record pointers, plus $p=4$ (so max 3 keys per leaf, min 1). Output: a height-balanced tree in which every leaf holds between 1 and 3 keys and every internal node between 1 and 3 keys.

We start with a leaf block (a child node) and insert in sorted order.

• Insert 1: leaf holds $1$ plus its record pointer.
• Insert 2: leaf holds $1,2$.
• Insert 3: leaf holds $1,2,3$ — still exactly at the maximum of three keys, no problem.

Step 1 — the split. As soon as we insert 4, the block holds $1,2,3,4$ — four keys, which is one over the maximum. This is an overflow, so we take the median. With right ordering, the median of $\{1,2,3,4\}$ (middle values 2 and 3, take the right one) is 3. The value 3 is copied up and becomes the root node; it stays in the leaf too, because in a B+ tree the data always resides in the leaf, with its record pointer. The root's single block pointer points to the leaf block holding the values less than 3 — and by our equal-to rule, the value equal to 3 goes on the left-hand side as well. So:

• Root: $3$ (one key, two block pointers).
• Left leaf: $1,2,3$, each with its record pointer.
• Right leaf: $4$ with its record pointer.

The tree now has two levels:

             [ 3 ]
            /     \
      [1 2 3]     [4]

14.2.3 Inserting 5 Through 7: The Second Split

Insert 5 and 6 — no problem, the right leaf becomes $4,5,6$. (From here on the record pointers and block pointers are understood; they are implicit.)

Step 2 — the second split. Inserting 7 overflows the right leaf: $\{4,5,6,7\}$. Right ordering — middle values 5 and 6, take the right one — promotes 6. The root gains 6: root is now $3,6$. The bounds split the range:

• Leaf $1,2,3$ for everything less than 3.
• Leaf $4,5,6$ for everything greater than 3 and less than or equal to 6 (the professor's phrasing: "greater than three, not equal to; greater than three and less than or equal to six").
• Leaf $7$ for everything greater than 6.

            [ 3   6 ]
           /    |    \
     [1 2 3] [4 5 6] [7]

Boundary reading. The interval structure is: $(\le 3)$, $(3<x\le 6)$, $(>6)$. Every value in a middle leaf is strictly greater than the left separator and less than or equal to the right separator. The "strict on the left, inclusive on the right" pattern comes straight from the equals-on-left rule — the equal value 6 lives in the middle leaf, so its upper bound is inclusive.

14.2.4 Inserting 8 Through 10: The Third Split

Insert 8 and 9 — no problem, the last leaf becomes $7,8,9$. Inserting 10 overflows it: $\{7,8,9,10\}$, middle values 8 and 9, right ordering promotes 9. The root becomes $3,6,9$, and the leaves are:

• $1,2,3$
• $4,5,6$
• $7,8,9$
• $10$

             [ 3   6   9 ]
            /    |    |    \
      [1 2 3] [4 5 6] [7 8 9] [10]

Step 3 — pattern recognition. All three splits so far share one shape: a leaf overflows at four keys, the right-of-the-two-middle values is promoted, the equal value stays left, and a new leaf opens with a single value. The root simply collects one promoted value per split. Notice what has not happened yet: no internal node has overflowed, because the root has absorbed exactly one key per split.

14.2.5 Adding 21, 13, and 11: The Deepest Split

The tree now has more values arriving: 21 and 13 (existing values that belong after 10), then 11. The last leaf holds $10,21$, then $10,13,21$ — three keys, still fine. When 11 arrives it is inserted in sorted order: $10,11,13,21$. That is an overflow, so we take the median: middle values 11 and 13, right ordering promotes 13.

Where does 13 go? Into the root, which currently holds $3,6,9$. Adding 13 gives the root four keys — $3,6,9,13$ — and that is another overflow, so the root itself must split. With right ordering, the median of the four values is 9 (middle values 6 and 9, take the right one). 9 rises to a brand new root, and — this is the key detail — 9 is not repeated in the lower levels: "even though 9 is at the top, 9 will not be repeated in the lower levels." The second level takes the remaining two keys: the left node holds $3,6$ and the right node holds $13$.

The final B+ tree for the values 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 21, 13, 11 therefore looks like this:

• Root (level 1): $9$
• Level 2: node $3,6$ and node $13$
• Leaves (level 3):
• under $3,6$: $1,2,3$ (equal-to-3 on the left, consistent with the rule), $4,5,6$, $7,8,9$
• under $13$: $10,11$ on its left (12 was never one of the values), and $21$ on its right

                     [ 9 ]
                    /     \
              [ 3  6 ]    [ 13 ]
             /   |   \     /    \
       [1 2 3] [4 5 6] [7 8 9] [10 11]  [21]

Notice that the $7,8,9$ leaf stays exactly as it was after the third split — equal values remain on the left-hand side, so nothing moved when 9 was promoted. The leaf ordering $10,11$ then $21$ preserves sorted order end to end, which is what the next-leaf pointers exploit for range queries.

(Real-world connection: this hand-run trace is the literal algorithm executed by a DBMS on every INSERT into an indexed table — the only difference is that the DBMS chooses the node size from the disk block size, so a real B+ tree with millions of keys stays at 2–4 levels and a single insertion touches only the blocks on the path from root to leaf.)

14.3 Deleting from a B+ Tree

14.3.1 Deleting 5 and 4: No Restructuring Needed

Deletion uses the same boundaries as insertion: in any block, at most 3 keys, at least 1 key (for $p=4$). As soon as a block falls below 1, we have a problem and must restructure.

Take the finished tree from Section 14.2 (root $9$; level 2: $3,6$ and $13$; leaves $1,2,3\mid 4,5,6\mid 7,8,9\mid 10,11\mid 21$) and delete 5. The value 5 lives only in the leaf $4,5,6$; it is not part of any internal node (no index value to clean up). The leaf becomes $4,6$ — two keys, still above the minimum. No problem at all: the deleted value is simply not part of the record any more, and the tree keeps working.

The real problem comes across only when we miss the boundaries. Delete 4 as well: the leaf $4,6$ becomes $6$ — one key, still exactly at the minimum. Still no problem.

14.3.2 Deleting 6: Underflow and Restructuring

Now delete 6. The leaf $6$ becomes empty — that is below the minimum of 1, so this entire block cannot exist any more, and whatever is remaining must be restructured and refactored properly.

What remains in this part of the tree: the leaves $1,2,3$ and $7,8,9$, plus the upper levels. The first decision is which way to merge: we had the option of merging on the right-hand side or merging on the left-hand side. Either way, we end up with a single pool of data values, and then we create the index out of them as well.

14.3.3 Merge Options and the Empty Pointer

Merging produces a configuration where the values less than 3 are still fine, and the pointer that used to cover the deleted range — the one between 3 and 6 — becomes an empty pointer. The structure at the above level can still work ahead with whatever is presently there, so this is not a very significant change: only one block goes away (the emptied leaf), and the index above it remains workable.

The caveat: if the value at that boundary also disappears, then again the entire thing needs to be restructured properly. The takeaway from the walkthrough is that deletion in a B+ tree is mostly local — you delete keys, and only when a block underflows (falls below $\lceil p/2\rceil -1=1$ keys) do you merge with a neighbor and rebuild the small index over the merged pool. The boundaries, not the individual keys, are what force the work.

14.3.4 Worked Deletion: The Complete Mechanics, With Merges

The syllabus asks for the deletion and node-merging mechanics in full, so this supplement runs one complete deletion sequence on the finished tree of section 14.2 — root $9$; level 2 nodes $3,6$ and $13$; leaves $1,2,3\mid 4,5,6\mid 7,8,9\mid 10,11\mid 21$ — and exercises every rule: plain leaf deletion, separator replacement, leaf merging, index-node underflow, and tree shrink. The boundary rule for $p=4$ throughout: every node must hold between 1 and 3 keys.

Step 1 — delete 8 (plain leaf deletion). The value 8 lives only in the leaf $7,8,9$. Removing it leaves $7,9$ — two keys, still above the minimum. No restructuring. This is the common case: most deletions are exactly this, a removal inside one leaf.

Step 2 — delete 9 (separator replacement). The leaf $7,9$ becomes $7$ — exactly at the minimum, still legal. But 9 was also the root separator: the root's single key 9 no longer exists anywhere in the leaves, and a B+ tree separator must be a real boundary. The rule: replace the deleted separator with the smallest key of the leaf to its right — the leaf $10,11$ — so the root becomes $10$. The tree is unchanged in shape; one key changed value at the root.

Step 3 — delete 10 (separator replacement again). Leaf $10,11$ becomes $11$ — still legal. The root separator 10 is again gone, so it is replaced by the smallest key of the right leaf: the root becomes $11$.

Step 4 — delete 11 (leaf underflow → merge). The leaf $10,11$ becomes empty — zero keys, below the minimum of 1. The block cannot exist. Two remedies exist; this walkthrough takes the merge path. Merge the empty leaf with its right sibling $21$, drop the separator 13 that stood between them, and collapse the two leaf pointers in the parent node $13$ into one. The parent $13$ now holds zero keys — it has underflowed as an index node. Because the parent is below the minimum, it merges in turn with its sibling $3,6$: the merged index node holds $3,6,13$ — three keys, exactly at the maximum — and the root $11$, now pointing to a single child, holds zero keys.

Step 5 — the empty root (tree shrink). A root with zero keys is discarded, and its only child becomes the new root. The tree has shrunk by one level.

The final tree: root $3,6,13$ with the leaves $1,2,3\mid 4,5,6\mid 7\mid 21$. Every leaf still holds at least one key, every index node holds between one and three keys, all leaves sit at the same depth — the B+ tree invariants are restored, and the whole sequence of five steps is what "deletion and node merging" means mechanically.

Before:          [ 9 ]                       After:
             /          \                    [ 3  6  13 ]
         [ 3 6 ]        [ 13 ]              /    |    |    \
        /  |   \        /    \      →   [1 2 3] [4 5 6] [7] [21]
 [1 2 3] [4 5 6] [7 8 9] [10 11] [21]

14.3.5 The Alternative: Borrowing (Redistribution) Instead of Merging

Merging is not the only remedy for underflow — and it is not always allowed. Before merging, the standard algorithms try redistribution: if a sibling has more than the minimum number of keys, borrow one key from it. The borrowed key moves across the sibling boundary, and the separator in the parent is updated to the new boundary value; no parent node ever loses a pointer, so no merge is needed at the upper levels. The rule of thumb: redistribute (borrow) when the sibling can afford it, merge when both siblings are at the minimum. In the walkthrough above, the leaf $7$ at step 4 had exactly one key — the minimum — so borrowing was impossible and merging was forced. Had the sibling held $7,9,10$, the leaf $11$ could have borrowed, say, 9 or 10, the separator would move, and the parent would never have underflowed. Merging and redistribution together are the complete deletion toolkit, and an exam answer should name both and say when each applies.

(Real-world connection: redistribution is what keeps B+ tree space occupancy near 67% in production systems — a tree that merges eagerly burns fewer disk blocks, and a tree that borrows avoids expensive parent cascades; commercial indexes combine both to keep block I/O low on every delete-heavy workload.)

14.4 Functional Dependencies First: The Normalization Prerequisite

14.4.1 Normalization Cannot Begin Without Functional Dependencies

The first student question of the session was about a table that looks like a weak entity — a table where no key value is visible. What normal form is such a table in? Could we call it 3NF, or better?

The crucial rule, restated three ways in the exchange: normalization can only occur whenever there are functional dependencies. Without the explicit mention of functional dependencies, we can never say a relation is in 2NF, 3NF, BCNF, or 4NF — the discussion point does not even arise. We can never prove or disprove any normal form unless the table states what functional dependencies are there.

But is it even possible to have no functional dependency at all? A follow-up pushed on exactly this: what if the table has no known key and no functional dependency?

14.4.2 No Key at All? There Is Always a Primary Key

The chain of reasoning is worth spelling out: a relation cannot exist without a primary key; a primary key functionally determines every other attribute individually; therefore every relation has at least one functional dependency. Once that minimum exists, the normal-form discussion becomes possible.

So the answer has a pleasant shape: a relation with one key and no other dependencies is a candidate for BCNF — the same answer the professor gave when asked "can we say 3NF?" — the point being the normal form is whatever your written functional dependencies prove, never whatever you assert by table counting.

The final question in this cluster was about the other extreme — a table that contains nothing but foreign keys.

14.4.3 Foreign Keys Are Constraints, Not Functional Dependencies

This is a vocabulary correction in miniature: a foreign key is a constraint, not a functional dependency. It restricts which values may appear in a column and what happens on deletion of the referenced row; it does not participate in the 2NF/3NF/BCNF/4NF discussion.

Why does all this matter in practice? Functional dependencies tell us what type of redundancies occur within a relation. We may remove redundancy across relations, but within a relation, if functional dependencies are present, there is a high chance of redundancies, of storing things separately, and of anomalies inside the relation. We can normalize the relation to make sure we have lesser redundancies and lesser chances of a lot of null entries. This is a discussion that many people fail to reciprocate, and the professor explicitly called it out: people who have heard this correction are at least an order better than those who have not.

(Real-world connection: every real schema — a university database, an e-commerce catalogue, a banking ledger — ships with both kinds of lines: functional dependencies that the design team wrote down during modeling, and referential-integrity constraints (default/restrict/cascade) enforced by the DBMS at runtime. Tooling like the MySQL ON DELETE clauses and ER tools' "identifying relationships" are the operational forms of these two ideas.)

14.5 Assignment Guidance: What Is Expected

14.5.1 Diagrams and Report Format

The assignment has no mandatory tool. You can draw your ER diagram with your hand — a clear hand drawing that communicates the structure is more than fine. If you prefer, use PowerPoint, eDraw, or some other tool where you can nicely draw the boxes and arrows — that is also perfectly fine. The report part can be handwritten or typed; both are accepted.

The SQL queries must be pasted as they are, and for each query you need to provide a snapshot of the output. Write a few important queries that are relevant and practical — four, five, six queries is fine; less than four would be very less. The purpose is that you write a handful of important, practical queries. Make sure you have a good combination: DDL (data definition language) queries, and data manipulation queries that actually do something — inserting, deleting, updating; even just searching is okay. Whatever queries you write, share their working through snapshots inside the documentation, so the query is visible, the database is visible, and the running output is visible.

14.5.2 The Index-Theory Component

A query-related question that came up: when we create an index through SQL, what is expected about indexes in the assignment? The answer is important — you are not expected to write any SQL index creation query. The index part is a theoretical discussion.

The theoretical discussion expected: suppose you create an index on attribute Q. This will significantly impact my retrieval time. So you need to write the balance — to create an index on Q I need to do such and such things, in terms of the space, the computation power, and the time needed to create and maintain that index; and on the reward side, how much faster retrieval becomes for Q. Go into the depth of why I am having the index on Q: why it is a B+ tree, why it is a B-tree, why it is just a multilevel index or a single-level index, what a hash index or a bitmap index would be — all of that is an addition. A numerical number quantifying the time saving would be really, really great; even otherwise, whatever value you write, it is critical and will be accepted with both hands — and given the fact that you would anyway be doing this value addition in the comprehensive examination, it is worth writing a proper perspective on why you are creating an index and how it may impact retrieval.

14.5.3 Tools, Platforms, and the Virtual Lab

You may use any SQL application — SSMS (though the professor had not personally used it and could not comment on it), MySQL, Microsoft SQL Server, Oracle, or any other platform. Microsoft Access also provides some way to do it. There are many tools and softwares that allow you to create a database and write queries on it; some are open source, some are paid. Use any of them.

A note on user-friendly tools that write the SQL for you: make sure you are writing the SQL query yourself. The query must be visible to the evaluator — the database visible, the running query visible, the output visible — which is why the snapshot requirement exists. The deadline for the assignment is the 30th; whatever the deadline is, ensure you submit within that point of time.

14.5.4 Functional Dependencies and the 3NF Proof

A direct question settled one requirement firmly:

The final exchange of the session came from a student who had already submitted and worried the missing functional dependencies would sink the submission.

14.6 Transactions: Why Concurrent Access Is a Problem

14.6.1 Every Real Application Is Multi-User

This is the point where the course turns practical. Whatever application you create — a desktop application, a mobile application, any such application — it will be concurrently accessed by multiple people. Think of a banking application, railway reservation, hotel reservation, a library system, or the more practical giants: Facebook, Amazon, and other marketplaces. Every mobile application you can look at, from Coursera or Udemy onward, from Gmail to messaging applications, from social media to entertainment to learning applications — there is a database involved. That database is accessed by multiple people simultaneously, through whatever medium — mobile phone, desktop, through the internet — and it is hosted at a particular IP address, on a central server machine, or on a cloud application, or any blockchain application.

Why does that deserve study? A natural pushback: if the database is accessible to multiple people, so what? If a hundred people ask what my marks are, I can reply to all of them. If a hundred people check IRCTC status, they look. If a hundred people ask whether a book is available in the library, we answer yes or no. If 20 or 30 people access a banking application, each accesses their own account. Isn't the database already handling complex SQL and ACID queries? Why can't it handle simple multi-user access?

That pushback is exactly the setup — and the professor insisted students genuinely agree there is a problem before moving on, because the entire rest of the course (transactions, concurrency control, recovery) is the answer to it.

14.6.2 What a Database Write Really Does: Blocks, Memory, and Persistence

To see the problem, walk through what a money transfer physically does. A transaction is a unit of a program — a unit of a set of instructions taken at a time. Say I transfer some amount, 50 rupees, from account A to account B. The processor works in main memory. The value of A is not in main memory — it is in a separate block on secondary storage. So:

1. Read the entire block in which A resides into main memory — irrespective of whether there is an index or not, bring the block in.
2. Read the value of A from that block, make it minus 50, and write the block back to the same secondary storage.
3. Read the next block, where the value of B resides.
4. Increase the value of B by 50 and write the block back into the hard disk wherever it resides.

Why write back at all? Because changes happening in main memory are not persistent. If there is a power failure, a hardware failure, or a system crash, the main-memory changes vanish. Changes in secondary storage are persistent, so we write the changed block back into the database.

This block-level detail matters: we never update "the value of A" directly — the entire block containing one record is read, one record in it is updated, and the whole block is written back.

14.6.3 The Power-Failure Nightmare: Debited but Not Credited

Now the failure: you have read A's block, made the changes, written the value of A back to the hard disk — and before you could read the block where B resides, there is a power failure; the system crashes. The value of A has been debited from its place, but the value of B has not been increased.

You are now in a precarious situation. The client says: "My hard-earned money has been debited from my account and not credited to the other account — how are you making sure of this?" A bank cannot defend this by explaining buffer management, blocks, and main memory; that explanation will never be acceptable to clients. The professor's framing was blunt: if the transfer from Ganesh's account to Priti's account debits one side and never credits the other, all of you will chase the bank asking what is happening — and no technical excuse about where the write happened will satisfy anyone.

This single scenario is the entire motivation for transactions: a group of instructions where the two or three operations depend on each other, and where a failure at the wrong moment leaves the database in a state no one can defend.

14.6.4 The Ordering Problem and the Penalty

There is a second, subtler problem: order of execution. Say four people are sending money to you and you are sending money to three people, and the amounts are neck to neck — you receive 50, you send 50. You are careful: you first receive the four, then you send the three. But the order can get shifted, because these are requests submitted to the operating system. We cannot even say the priority of the first one is higher or lower — everything sits in a queue, and the processor will take any of the processes to execute. We cannot guarantee which executes first and which later.

The processor can execute one query at a time, one process at a time — even with a multi-core processor, every core processes one operation at a time. If the order shifts, you suddenly have a penalty levied on you: "insufficient balance, and still you paid the other person" — a heavy penalty, and the bank account shows the charge with no explanation you can defend.

So there are two enormous reasons to study concurrent execution: hardware failures can interrupt a dependent sequence of operations, and the concurrent execution of multiple transactions in the same order as they were requested is very, very important — but we are not in control of the processor. The order in which we specify the instructions must be the order in which they execute, and that guarantee is exactly what transaction management provides.

(Real-world connection: the 50-rupee transfer is, at heart, how every bank's ledger works — debit and credit as two block writes — and why banking cores run on transactional databases; the ordering problem is why payment systems validate against a live balance and why your bank statement can show a penalty even when "the money arrived later".)

14.7 The ACID Properties

The four properties — atomicity, consistency, isolation, durability (the "ACID" properties; the spoken name in the session is sometimes garbled as "asset properties", but the four named properties below are stated explicitly) — are the contract a transaction offers. Because of them, we group a unit of instructions into a program in which either everything executes or nothing executes, and whatever happens, consistency, isolation, and durability are respected.

14.7.1 Atomicity: Everything or Nothing

The atomicity requirement: not only for three or six of the instructions — either all of them execute or none of them should execute. I do not want my money debited from my account and not created in the other person's account. Either the money is transferred completely, reflecting on the other bank account, or nothing is changed — the status quo before and after is the same.

That is a very basic requirement, and it is exactly what failed in the power-failure scenario: the transaction executed till a point, the processor changed B's value in main memory — it was reflecting for a greater point of time — but it did not write the block back to the hard disk, so physically, after the power failure, the 50 rupees was never added to B's account. Atomicity forbids this state.

14.7.2 Consistency: No Money from Thin Air

Before and after a transaction, the sum of money should be the same — the total sum of balances should be the same. You should not create money out of thin air, and you should not remove money into thin air. Whatever constraints exist need to be respected at no point of time should we see that before and after, things are not consistent.

There is an honest caveat: the logical part of consistency is written by the programmer — the constraint logic itself is your code. But it should not be a problem in execution; the database system must not let a sudden execution order create money or lose it. "We have burned the money and we don't know where it has gone" — that is precisely the situation consistency prevents at the system level.

14.7.3 Isolation: You Should Feel Alone

Isolation is very important: at whatever point of time, if things are working, somebody needs the value of A, somebody needs the value of B — say someone prints the value of A and B. Who might that be? A person calculating interest for both accounts; an auditor auditing the bank account; a joint account where a spouse reads because both persons have access; a company account where all the directors have access. Whoever it is, when they print A plus B, they must not see an intermediate state — they should see a consistent snapshot.

How would T2 (the reader) even know that another transaction is concurrently changing things? If the value visibly moves between two reads, that is not a healthy sign. The guarantee needed: whenever I am working, I must appear to be working in isolation — as if I am the only one accessing the database, starting from the beginning of the transaction till its end.

The airline ticket is the everyday proof that this matters. When I access the price of an airline ticket, I see a price; when I click the same ticket moments later, the price fluctuates. Somebody else is manipulating the ticket price — someone is reserving seats. But here is the legitimate mechanism behind the fluctuation: the airline may have decided that the first 25% of seats are sold at one price, the next 50% at another, the next 15% at another, and the last 10% at a very high price. When I first look, the seat is available at the current tier; when I look again, someone has booked the flight, and even though the seat is still available to me, it is available at a different price. That is a legitimate business rule, and the fluctuation tells me I am not the only one working.

The violation to prevent is different: if I start booking, I am allowed to pay, and then I am told the seat is not available — that is a gross violation. From the moment I press the first amount till the seat is booked to me, nobody should be able to take the seat away. That is isolation: the first time I am working in isolation, the seat should be there for me. Either I get the seat or the transaction never happened — but never "seat available, payment taken, seat gone."

14.7.4 Durability: Earthquake-Proof Changes

Once I have done it, it needs to be persistent, durable. Whether an earthquake happens, a tsunami, a power failure, a hard disk failure, or a main memory failure — main memory is an electronic device, it can fail — my database should not be changeable; the change should survive. We read blocks into main memory and the processor works there; unless we require to write back, we don't write back. Because of power failures and other failures, the durability of my system must not depend on main memory — once committed, the change must be in physical storage and stay there.

Every client wants this package: the payment application must be atomic, the reservation must appear as if executed in isolation, the seat I reserved must be mine at the airport or railway station (it must be durable), and before and after, the database must be consistent — the number of seats must never become more than the number of seats that were actually possible at the starting point.

(Real-world connection: every payment app, reservation system, and marketplace runs on this exact contract — UPI transfers, IRCTC bookings, and airline seats are all ACID transactions; the seat-tier pricing story is literally how revenue-management systems price flights.)

14.8 Why We Cannot Just Run Transactions One at a Time

14.8.1 The Price of a Serial Queue

If concurrency is so dangerous, why not simply queue the requests — ten people want to access the database, so let them go one by one, one transaction at a time? The answer is practical, not theoretical.

First, consider a read: a person wants the current status of the number of books available on Amazon or any marketplace. You cannot tell them: "Another person is accessing the database, you are not allowed to even read the database now." Nobody will accept waiting an hour just to learn the price of a particular book or a particular phone — "I may go back to the local store and come back by that point of time." Response time is very important; I cannot stop and wait until every other person has executed 100%.

Second, consider a write: if one transaction has started writing, it cannot withhold all other transactions — including readers — just because it has begun. Context switching makes this unavoidable: the processor shares time, the process gets its share, then the processor does context switching, another process starts executing and wants to read the database — but the previous process was already writing. The second process goes back through the processor; it cannot do something now, and the other process does not have access to the database. Until the first process completes all its instructions, the others become redundant and can do nothing at all — that is a very bad situation for the entire operation.

14.8.2 Why Concurrency Wins

So serial execution is unacceptable because it destroys response time and starves everyone behind a writer. The benefits of allowing multiple transactions to execute simultaneously: the average time is reduced, the performance of the processor is better, and disk utilization is better. For these reasons, we must allow multiple transactions to execute simultaneously — and then manage the correctness of that concurrency. (A related personal note from the professor: handling multiple threads and accesses is a tedious task in traditional languages like Python and Java; that is why dedicated database software must be designed to handle it appropriately — just as a separate software layer was needed over the file access system in earlier sessions because of the complex constraints specific to the database system.)

And the deeper motivation, aimed squarely at the student: the industry does not pay you for work — the industry pays you for the value you are adding there. Understanding, practicing, and becoming skillful at concurrency control is exactly the kind of value the industry pays for.

(Real-world connection: this is why real systems use thousands of concurrent sessions — every banking, railway, and marketplace application depends on interleaved execution; and it is why database engineering (locking, isolation levels, schedulers) is a paid specialization: the value added is precisely the ability to make concurrency safe.)

14.9 The Life of a Transaction: States and the Log

14.9.1 The State Transitions

A transaction passes through distinct states, and the states define what guarantees hold at each moment:

• Active. The transaction has been submitted and has got its fair share of the processor — it is executing.
• Partially committed. The transaction has executed its last statement — all instructions are done — but the changes are done only in the main memory; nothing has been written to physical secondary storage yet.
• Committed. Not only has the last instruction executed, the changes have been made in the physical, secondary storage as well. Only then is the stage committed.
• Failed. Due to some reason — network failure, power failure, system failure, or hardware failure — the transaction could not execute all its instructions. If a transaction is a program of 10 instructions and we wanted the whole program to run completely or nothing at all, but after three, five, or six instructions an exception or error occurred, the entire program (transaction) has failed.
• Aborted. The failed transaction is rolled back: every change made so far is undone, so the database returns to exactly the state it was in at the start of the transaction. The state before and after is the same.

The transitions form a clear flow: a transaction starts, and either it gets partially committed or it fails. If it fails, we abort — rollback. If it is partially committed, it must ultimately result in the committing stage very, very soon — the changes need to be returned back to the secondary storage. The key phrase the professor emphasized repeatedly: either I write the entire changes or I write none of the changes at all. "This is super, super, super important."

                 partially
   start         committed
     │               │
     ▼               ▼
   ACTIVE ────────────► PARTIALLY ─────► COMMITTED
     │               COMMITTED
     │                   │
     │  failure/error    │  (writes forced
     ▼                   ▼   to secondary storage)
   FAILED ──────────► ABORTED
        (rollback,
         undo all changes)

14.9.2 Commit versus Partial Commit

So "committed" is a storage fact, not a logical one: the last instruction executed is not enough — the dirty pages must reach the disk.

14.9.3 Rollback and the Log File

<T, start>
<T, A, 5, 10>     "A changed from 5 to 10"
<T, B, 10, 5>     "B changed from 10 to 5"
<T, commit>       or <T, abort>

The correction here is a valuable one: rollback is not magic. Someone designed the log, someone wrote the recovery logic; the DBMS's apparent automatism is the product of the log-based recovery process — which is precisely the topic (recovery, shadow paging) coming later in the course.

(Real-world connection: every commercial DBMS — Oracle, SQL Server, MySQL, PostgreSQL — implements exactly this design in its transaction log (redo/undo log); a DBA reading a crash log is reading the modern form of "A changed from 5 to 10".)

14.10 Schedules and Serial Schedules

14.10.1 What a Schedule Is

With multiple transactions allowed to run concurrently, we need vocabulary for their interleaving. A schedule is the chronological order in which instructions of multiple transactions execute — the order in which T1 started executing something, T2 started executing, T3 started executing. Any such ordering is a schedule:

• T1 completes entirely, then T2 completes entirely — a schedule.
• T2's instructions execute first, then T1's — also a perfectly valid schedule.
• T1 does some instructions, T2 does some, T1 does some more, T2 does some more — also a schedule.

The second kind is the serial schedule: everything for T1 first, till committing, then everything for T2, till committing. A serial schedule always follows the ACID properties — if everything executed first for T1 and it committed, then everything for T2, that is definitely atomic and definitely consistent. If a failure happens at any point, we roll back to the last commit — at every failure point the properties hold.

14.10.2 The Equivalence Test

So the central question becomes: when a jumbled, interleaved schedule is proposed, is it equivalent to a serial schedule? If it is equivalent to a serial schedule, we know it follows ACID, because serial schedules always follow ACID. If it is not equivalent to a serial schedule, we are not confident that it follows ACID, and we should hold and stop that schedule. Some non-serial schedules do follow ACID — but for the sake of confidence, the test is: can we find an equivalent serial schedule? For my sake of confidence, at least find out if the schedule is equivalent to a serial one; then it is easier to find out that ACID will be followed.

(Real-world connection: the "is this schedule safe?" question is asked millions of times a day inside a DBMS — the schedulers and isolation-level engines of Oracle, PostgreSQL, and SQL Server are implementing exactly this equivalence check, with locking protocols that guarantee serializable schedules.)

14.11 Conflict Serializability

14.11.1 The Conflict Definition and Swap Rule

Two instructions are conflicting when they come from two different transactions, operate on the same data item, and at least one of them is a write:

$$T_i\text{ and }{T}_j(i\ne j)\text{ conflict on data item }X\text{ iff one of the two operations on }X\text{ is a write.}$$

Formally, the conflicting pairs on the same data item are read–write, write–read, and write–write across two different transactions. Two reads never conflict — "read, read... one of them is not a write, so there is no conflict here." And two operations on different data items never conflict — "even though there are two different transactions, but on a different data item, I can swap them easily."

To test whether an interleaved schedule is equivalent to a serial schedule, we keep swapping adjacent instructions — but we may only swap non-conflicting instructions. The instructions we can never swap are the conflicting ones: two different transactions on the same data item where one of them is a write. If by swapping non-conflicting instructions we can rearrange the schedule into a fully serial one, the schedule is conflict serializable, and we allow it, because it will follow the ACID property.

There is a second way to run the same test, the precedence graph method: write the transactions as nodes T1, T2, and whenever there is a conflicting operation where T1's operation happened first and T2's later, draw an arrow from T1 to T2. After exhausting all the instructions: if the graph has no cycle, the schedule is equivalent to a serial schedule; if there is a cycle, it is not equivalent to any serial schedule.

14.11.2 Worked Check: The Serializable Schedule

Consider two transactions over data items a and b, each doing a read and a write on both items:

• T1: read a, write a, read b, write b
• T2: read a, write a, read b, write b

The interleaving to check runs: T1 read a; T1 write a; T2 read a; T2 write a; T1 read b; T1 write b; T2 read b; T2 write b.

  T1: r(a)  w(a)                 r(b)  w(b)
  T2:              r(a)  w(a)              r(b)  w(b)
order: 1    2     3     4      5    6      7     8

      T1 ──────► T2      (all arrows one direction, no cycle)

The same conclusion can be reached by the swap test: this read can go all the way up, that instruction can be swapped with this one, then this one — the entire block of T1's non-conflicting instructions can be taken up, and T2's block goes down, until the schedule is T1 in full followed by T2 in full. Equivalent to a serial schedule — allowed.

S:  r1(a) w1(a) r2(a) w2(a) r1(b) w1(b) r2(b) w2(b)

1.  r1(b) w1(b) swap up past r2(a) w2(a):
    r1(b) vs r2(a): different items — legal
    r1(b) vs w2(a): different items — legal
    w1(b) vs r2(a): different items — legal
    w1(b) vs w2(a): different items — legal
    →  r1(a) w1(a) r1(b) w1(b) r2(a) w2(a) r2(b) w2(b)

    T1's four instructions now all precede T2's four. Done — SERIAL.

14.11.3 Worked Check: The Schedule with a Cycle

Now change the interleaving so the a-operations cross: T1 read a; T2 read a; T1 write a; T2 write a (with the b operations arranged similarly).

  T1: r(a)        w(a)
  T2:      r(a)        w(a)
order: 1    2     3     4

      T1 ──────► T2
      ▲          │
      └──────────┘   cycle!

14.11.4 The Precedence Graph, Summarized

The method, cleanly: mark an arrow from where to where the conflicting operations are; if after exhausting all the transactions the graph does not have any cycle, the schedule is equivalent to a serial schedule; if not, it is not. This is the entire point of the session's work — we just evaluated, for two schedules, whether they are conflict serializable. Conflict serializable schedules we can allow, because they are equivalent to a serial schedule and they will follow the ACID property. That is the basic point.

(Real-world connection: database engines use locking protocols (e.g., strict two-phase locking) precisely to force every executed schedule to be serializable — the cycle-free graph is what the lock manager protects at runtime; SQL isolation levels (READ COMMITTED, REPEATABLE READ, SERIALIZABLE) are the user-facing knobs of this machinery.)

14.12 Where the Discussion Goes Next

14.12.1 The Roadmap So Far

The roadmap laid out in the opening: hashing (internal, external, dynamic) is done; indexing (single-level, multi-level) is done; the B-tree and B+ tree discussion is now complete. From here the course moves fully into transactions: this session covered why transactions exist and the ACID properties; the next sessions continue with schedules — view serializability (what it is and how we test it) comes next, then recoverability: if there is a failure, is the schedule recoverable or not recoverable; then cascading rollbacks — does the schedule have cascading rollbacks or not; and finally the judgment of whether a schedule should be allowed to run through or not. After the transaction discussion, recovery continues with shadow paging, and the last part works on the challenges as well.

The sequence ahead, in order:

1. View serializability — what it is and how we test it: a weaker sibling of conflict serializability, based on what each transaction sees, not on which operations conflict.
2. Recoverability — if a failure happens, is the schedule recoverable or not?
3. Cascading rollbacks — does the schedule force cascading rollbacks or not?
4. The judgment — whether a schedule should be allowed to run through or not.

14.12.2 The Evaluative Components

The evaluative components are also on the horizon — quiz 3 is live and should be attempted within time, and mid-semester results are delayed this time (a separate team takes care of the evaluation).

(Real-world connection: the topics ahead — recoverability and cascading rollbacks — are the difference between a database that silently corrupts on crash and one that comes back to a defensible state; the judgment "allow this schedule or not" is executed every millisecond by the isolation engines of every commercial database.)

Exam Guidance Summary

• Assignment — functional dependencies are mandatory: For every relation, write down its functional dependencies and prove the relation is in 3NF. Saying "ER to relational conversion is always 3NF" is not enough — the FD lines (the "FD" keyword) must be present; 3NF means no partial functional dependency and no transitive dependency, and that must be shown, not asserted. (See Sections 14.4 and 14.5.4.)
• Assignment — what to submit: The ER diagram (hand-drawn, or PowerPoint/eDraw, all acceptable), the report (handwritten or typed), and 4–6 practical SQL queries pasted as-is with snapshots of their working output. Include a good mix of DDL and DML (insert, delete, update, search).
• Assignment — the index-theory component: No SQL index creation query is expected. Write the theoretical balance: why you create an index on a chosen attribute, why it would be a B+ tree versus a B-tree versus a multi-level or single-level index versus a hash or bitmap index, the space/computation/time cost to create and maintain it, and the retrieval-time reward. A concrete numerical figure for the time saving is appreciated; this is value addition that you would anyway be doing in the comprehensive examination. (See Section 14.5.2.)
• Assignment — platforms: Any professional SQL platform (MySQL, Microsoft SQL Server, Oracle, Microsoft Access, SSMS) or the university's virtual lab. Online SQL editors are not accepted as an excuse for missing functionality — the query, the database, and the output must all be visible.
• Assignment — deadline: the 30th; submit within that point of time.
• Quiz 3 should be attempted within its time window.
• Mid-semester results are delayed this time; a separate team handles the evaluation.
• Core concept to master for exams: the transaction states (active → partially committed → committed, or failed → aborted) and the meaning of commit (changes written to physical/secondary storage) versus partial commit (changes only in main memory) were flagged as super, super important. Expect the conflict serializability test (swap non-conflicting instructions, or precedence graph + cycle check) in some form — it was worked fully in the session. (See Sections 14.9 and 14.11.)
• Structure to remember for the B+ tree questions: capacity rules $p-1$ maximum and $\lceil p/2\rceil -1$ minimum keys per block; right-ordering median with equals-on-left applied consistently; index splits never duplicate the promoted key, leaf splits do; deletion merges/redistributes only below the minimum. (See Sections 14.1–14.3.)
• Upcoming topics to watch: view serializability, recoverability, cascading rollbacks, recovery and shadow paging, and the challenges of the whole system.

Key Industry Applications

• Real-world: banking applications are the canonical transaction use case — fund transfers must be atomic (debit without credit is unacceptable), consistent (total balance constant), isolated (auditors, interest calculators, joint-account holders must see consistent snapshots), and durable (survive power failure). The 50-rupee transfer of Section 14.6 is the physical shape of every wire transfer and UPI payment.
• Real-world: railway reservation (IRCTC), hotel reservation, and library systems are classic concurrent-access systems where reads must never be blocked by writes and seats/rooms must never be double-booked — the isolation guarantee of Section 14.7 in production.
• Real-world: airline ticket pricing — the 25% / 50% / 15% / 10% seat-tier pricing model explains why prices fluctuate between two clicks; the system must still guarantee that once you start booking, the seat cannot be taken away.
• Real-world: marketplaces like Amazon, social platforms like Facebook, mail (Gmail), messaging, entertainment, and learning applications (Coursera, Udemy) — every one of them runs on a database accessed concurrently by thousands, which is exactly why the concurrency and correctness machinery of this lecture exists.
• Real-world: SQL index creation in every commercial database system creates a B+ tree under the hood, because range queries dominate real workloads — the p-capacity rules of Section 14.1 decide how many disk blocks the index needs and how few reads a lookup costs.
• Real-world: traditional languages (Python, Java) can implement multi-threaded database access, but it is a tedious task — which is why database software exists to handle concurrency and recovery properly, just as a dedicated software layer was needed over the file access system.
• Real-world: log files are the persistent, append-style record of every change (e.g., "A changed from 5 to 10") that makes recovery possible after any failure — the basis of the recovery and shadow-paging techniques coming later in the course; every commercial engine (Oracle, SQL Server, MySQL, PostgreSQL) ships one.