📚 Concurrency Control & Recovery

Brief Overview
This note covers concurrency control and was
created from a 61-page PDF. It covers phantom
reads, index locking, timestamp ordering, snapshot
isolation, and crash recovery.
Key Points
Understand how phantom reads arise and are
prevented.
Learn the rules of the index‑locking protocol
and next‑key locking.
Explore timestamp‑ordering and
validation‑based protocols.
Grasp snapshot isolation, write‑skew, and
recovery via logs and undo/redo.
Insert & Delete Operations, Predicate Reads 🧩
Phantom Phenomenon
Definition: The phantom phenomenon occurs
when a transaction’s predicate read conflicts with
another transaction that inserts, updates, or deletes
tuples satisfying that predicate, even though the
two transactions never access the same physical
tuple.
Example:
Transaction T31 inserts (11111,
'Feynman', 'Physics', 94000) into
instructor.
Transaction T30 executes SELECT
COUNT(*) FROM instructor WHERE
dept_name = 'Physics'.
If T30 reads the newly inserted tuple,
T31 must precede T30 in any equivalent
serial schedule.
If T30 does not read the new tuple, T30
must precede T31.
Neither transaction accesses a common
tuple, yet they conflict on a phantom
tuple.
Update‑induced phantom:
Transaction Ti uses an index to read only
instructors with dept_name = 'Physics'.
 Transaction Tj updates a tuple’s
department to Physics.
Although Ti and Tj never read the same
physical tuple, the predicate result
changes, creating a phantom conflict.
Locking Information About Tuples
A transaction that reads information about
what tuples exist (e.g., a predicate scan) must
lock the relation‑metadata data item in
shared mode.
A transaction that updates that information
(e.g., an insert) must lock the same metadata
item in exclusive mode.
When an index is used to locate tuples, the
index itself must be locked:
Shared lock for lookup operations.
Exclusive lock for inserts, deletes, or
updates that modify index leaf nodes.
Index‑Locking Protocol 🔐
Definition: The index‑locking protocol prevents
phantom conflicts by requiring transactions to lock
index leaf nodes that they read or modify.
Protocol Rules
Operation Required Lock Scope
Relation scan Shared lock on All leaves of at
(treated as all accessed leaf least one index
leaf‑node scan) nodes
Range or point Shared lock on Only the visited
lookup each leaf node leaves
visited
Insert / Delete Exclusive lock The leaf that
on leaf node will receive the
containing the new entry (or
search‑key lose the old
value one)
Update Exclusive lock May involve
on leaf nodes two leaves if
containing the the key changes
old and new
search‑key
values
Every relation must have at least one index
(commonly a B⁺‑tree).
 The protocol turns phantom conflicts into
ordinary lock conflicts on leaf nodes,
preserving serializability while allowing higher
concurrency than locking the whole relation.
Predicate Locking 🔒
Definition: Predicate locking acquires shared locks
on query predicates (e.g., salary > 90000). Inserts,
deletes, or updates that would affect the
predicate’s result are blocked until the lock is
released.
Used to prevent phantom tuples without
relying on index structures.
Not widely adopted because it incurs higher
implementation cost and offers little
advantage over the index‑locking protocol.
Timestamp‑Based Protocols ⏱️
Timestamps
Each transaction Ti receives a unique,
immutable timestamp TS (T ) before it starts.
i ​

Two common generation methods:

 1. System clock value at entry.
2. Logical counter incremented for each
new transaction.
Data‑item timestamps:
W -timestamp(Q) – largest timestamp of
any transaction that successfully executed
write(Q).
R-timestamp(Q) – largest timestamp of

any transaction that successfully executed

read(Q).
Timestamp‑Ordering Protocol
Read operation (read(Q))
If TS (T ) < W -timestamp(Q) → reject read;
i ​

roll back Ti.

Else → execute read and set
R-timestamp(Q) ←

max(R-timestamp(Q), TS (Ti )). ​

Write operation (write(Q))

If TS (T ) < R-timestamp(Q) → reject write;
i ​

roll back Ti.

 If TS (T ) < W -timestamp(Q) → reject write;
i ​

roll back Ti (obsolete value).

Otherwise → execute write and set
W -timestamp(Q) ← TS (T ) . i ​

Properties
Guarantees conflict serializability by
enforcing timestamp order on conflicting
operations.
Deadlock‑free (transactions never wait).
May cause starvation of long transactions if
many short, conflicting transactions keep
aborting them.
Schedules can be made recoverable by:
1. Delaying all writes until transaction
commit (atomic batch).
2. Postponing reads of uncommitted items
until the writer commits.
3. Tracking uncommitted writes and
allowing commit only after dependent
transactions commit.
Example (T25 & T26)
TS (T25 ) < TS (T26 )
​ → schedule where T25
​

reads old values before T26 writes, preserving

 serial order.
Validation‑Based Protocols ✅
Execution Phases
1. Read phase – transaction reads data into local
variables; writes are performed on temporary
copies.
2. Validation phase – system tests whether the
transaction can commit without violating
serializability.
3. Write phase – if validation succeeds, local
writes are flushed to the database (omitted for
read‑only transactions).
Timestamp fields for validation
Timestamp Meaning
StartTS(Ti) Moment Ti begins
execution (start of read
phase).
ValidationTS(Ti) Moment Ti finishes its
read phase and begins
validation.
 FinishTS(Ti) Moment Ti completes
its write phase (or
finishes if read‑only).
View Serializability
Definition: Two schedules are view equivalent if
they satisfy three conditions:
1. Each transaction reads the same initial
values.
2. Every read of a value produced by a write
reads the same write in both schedules.
3. The final write to each data item is
performed by the same transaction in both
schedules.
A schedule is view serializable if it is view
equivalent to some serial schedule.
Blind writes (writes without prior reads)
appear in view‑serializable schedules that are
not conflict‑serializable.
Validation Test
For a transaction Ti to pass validation, all earlier
transactions Tk with TS (T ) < TS (T ) must satisfy
k ​

i ​

one of the following:

Condition Interpretation
FinishTS(Tk) < Tk completed before Ti
StartTS(Ti) began; no conflict
possible.
(WriteSet(Tk) ∩ Tk’s writes do not affect
ReadSet(Ti) = ∅) ∧ Ti’s reads, and Tk’s write
StartTS(Ti) < phase ends before Ti
FinishTS(Tk) < validates.
ValidationTS(Ti)
Only transactions that finish after Ti starts but
validate before Ti need to be checked; earlier
or later transactions are irrelevant for Ti’s
validation.
Multiversion Schemes 📚
Multiversion Timestamp Ordering
Version record for data item Q:
Content – actual value of the version.
 W -timestamp(Qk ) – timestamp of the
​

transaction that created version Q . k ​

R-timestamp(Q ) – largest timestamp of

k ​

any transaction that has successfully read

version Q .
k ​

Write(Q) creates a new version Q new ​

with
W -timestamp = TS (T ) . i ​

Read(Q) selects the latest version whose

W -timestamp is ≤ TS (T ), ensuring that
i

reads see a consistent snapshot according to

​

timestamp order.
Snapshot Isolation 📸
Multiversioning in Snapshot Isolation
Each transaction Ti receives:
StartTS(Ti) – when the transaction
begins.
CommitTS(Ti) – when it requests
validation (also the write‑timestamp for
any versions it creates).
 Read rule: Return the latest version of a data
item whose timestamp ≤ StartTS(Ti).
Consequently, Ti sees a snapshot of the
database as of its start time, never
observing updates that commit after it
began.
Commit: The transition to the committed state
and the application of all updates must be
atomic, guaranteeing that other transactions
either see all of Ti’s changes or none.
Validation Steps
First Commiter Wins
1. After assigning CommitTS(Ti), check each data
item d that Ti intends to write.
2. If a version of d exists with a timestamp in the
interval (StartTS(Ti), CommitTS(Ti)) → abort Ti.
3. If no such version exists → Ti commits and its
updates become visible.
First Updater Wins
 Uses a write‑lock mechanism limited to
update operations:
1. When Ti wants to update d, it requests a
write lock on d.
2. If no concurrent transaction holds the
lock, Ti proceeds; otherwise it waits.
3. After acquiring the lock and completing
its update, Ti releases the lock at
validation/commit time.
Both variants prevent lost updates by ensuring
that only one of the conflicting transactions
can successfully commit its write.
Snapshot Isolation and Serializability Issues 📸
Snapshot Isolation (SI): A concurrency‑control
scheme where each transaction reads from a
snapshot of the database taken at its start time and
commits only if its writes do not conflict with any
concurrent transaction that committed after the
snapshot.
Write‑Skew Anomaly
Write Skew: A non‑serializable pattern in which
two concurrent transactions each read a data item
that the other later writes, yet the two transactions
modify disjoint items.
Example (Figure 18.20):
1. T₁ reads A and B, writes A = B.
2. T₂ reads A and B, writes B = A.
3. Both see the pre‑update snapshot, so
neither sees the other’s write.
4. Both commit → final state swaps the
values of A and B.
5. The precedence graph contains edges T₁
→ T₂ (T₁ reads A before T₂ writes A) and
T₂ → T₁ (T₂ reads B before T₁ writes B),
forming a cycle ⇒ non‑serializable.
Integrity‑Constraint Violations
Integrity constraints (primary‑key, foreign‑key)
are checked on the current database state at
commit, not on the snapshot.
This prevents many violations, e.g., duplicate
primary keys are caught even if both
 transactions read the same snapshot.
Phantom Phenomenon under SI
Phantom Conflict: Insert‑based conflicts where a
transaction’s predicate read interferes with another
transaction’s insert, even though no common tuple
exists.
Scenario: Two transactions each read the
maximum bill number, then insert a new bill
with that number + 1.
Both see the same snapshot, insert identical
bill numbers, and commit → duplicate bills (a
phantom problem).
The conflict is missed by plain SI because the
inserts affect different tuples.
Frequency & Impact
Rare in workloads where constraints are
enforced at commit (e.g., primary‑key checks in
TPC‑C).
Still problematic for financial or regulatory
applications where even occasional anomalies
are unacceptable.
 Examples where anomalies matter:
Banking write‑skew leading to negative
total balance.
University enrollment exceeding class
capacity.
Solutions to Non‑Serializable Snapshot Isolation
✅
Serializable Snapshot Isolation (SSI) 🌐
SSI: An extension of SI that tracks read‑write
conflicts (RW) between concurrent transactions
and aborts a transaction that participates in a cycle
of RW edges.
Conflict Graph: vertices = transactions; edges
= RW conflicts (from reader → writer).
SSI aborts a transaction that has both an
incoming and an outgoing RW edge.
Detecting such a pattern is cheaper than full
cycle detection, though it may cause some
unnecessary rollbacks.
PostgreSQL 9.1+ implements SSI and an
index‑locking technique for phantom
 protection (locks are retained briefly after
commit to catch late conflicts).
Mixed Isolation Levels
Run long read‑only transactions under SI
while updating transactions use the
serializable isolation level (e.g., SQL Server).
Guarantees that read‑only work does not block
updates, yet the combined schedule remains
serializable.
FOR UPDATE Clause
FOR UPDATE: An SQL hint that forces the system
to treat rows read by a SELECT … FOR UPDATE as
if they were written, thereby creating artificial
write‑write conflicts.
Adding FOR UPDATE to the reads in the
write‑skew example forces both transactions
to obtain exclusive locks on A and B → only one
can commit.
Useful when the DB does not support SSI but
allows manual conflict creation.
Formal Conflict‑Insertion Methods
 Formal analysis can determine which
transactions need artificial conflicts (e.g.,
additional FOR UPDATE clauses) to guarantee
serializability.
Applicable when the set of possible
transactions is known in advance; not feasible
for arbitrary ad‑hoc workloads.
Weak Consistency Levels 🛡️
Degree‑Two Consistency
Degree‑Two Consistency: A protocol that uses
shared (S) and exclusive (X) locks like two‑phase
locking, but does not enforce the two‑phase rule.
S‑locks may be released at any time; X‑locks
are held until commit/abort.
Allows non‑repeatable reads: a transaction
can read a tuple, see it change, and read a
different value later.
Example (Figure 18.21):
1. T₃₂ reads Q (S‑lock).
2. T₃₃ writes Q (X‑lock) after T₃₂ releases
its S‑lock.
 reads Q again → sees the new value.
3. T₃₂
This protocol corresponds to the
read‑committed isolation level.
Index Scan Peculiarity
With degree‑two consistency, a scan using an
index may:
Miss a tuple that was updated (deleted
from old index leaf, inserted into new
leaf after the scan passed the first leaf).
See two versions of the same tuple
(once before and once after the update).
Such anomalies disappear when both scan and
update use two‑phase locking.
Cursor Stability
Cursor Stability: A refinement of degree‑two
consistency for cursor‑based iteration.
Locks only the current tuple in shared mode
while it is processed; releases the lock
immediately after.
Modified tuples receive exclusive locks that
persist until commit.
 Increases concurrency on heavily accessed
tables but still does not guarantee
serializability.
Concurrency Across User Interactions
Problem: Long user‑driven steps (e.g., airline
seat selection) would lock resources for the
whole interaction under two‑phase locking,
causing poor availability.
SI Advantage: Allows users to read a
consistent snapshot without blocking updates,
as long as they do not select the same seat.
Limitation: SI must retain update information
until all concurrent transactions finish, which
can be costly for very long interactions.
Version‑Number Optimistic Control
Each tuple stores a version number (initially 0).
Read‑Phase: Transaction reads a tuple and
remembers its version.
Commit‑Phase: For each updated tuple, the
transaction atomically:
1. Checks that the current version matches
the remembered version.
 2. If matched, writes the new value and
increments the version.
3. If not matched, aborts the transaction.
The version number can be replaced by a
timestamp without changing the semantics.
Advanced Topics in Concurrency Control 📚
Optimistic Concurrency Without Read Validation
Optimistic Concurrency (no read validation): A
scheme where reads are performed without
snapshot enforcement, and only write‑set
validation occurs at commit.
Guarantees a weak level of serializability;
does not ensure full serializability because
reads are not validated.
A variant adds read‑validation at commit,
yielding the classic optimistic concurrency
protocol.
Online Index Creation 📈
Online Index Creation: Building an index while
allowing concurrent updates to the underlying
 relation.
Three‑phase process:
1. Snapshot Phase: Capture a snapshot of the
relation; construct the index on this snapshot.
Concurrent updates are logged.
2. Catch‑up Phase 1: Apply logged updates to
the partially built index. New updates may still
occur.
3. Catch‑up Phase 2: Acquire a shared lock on
the relation, apply any remaining logged
updates, then update relation metadata to
declare the index available.
Locks are held only briefly, preserving high
availability.
The same approach applies to materialized
view creation: build the view on a snapshot,
log updates, then apply them before releasing
the lock.
Concurrency in Index Structures
 Indexes can be treated like regular data
structures, but holding long‑duration locks on
them would create severe contention.
Non‑two‑phase locking for indexes is
acceptable as long as the final index state is
correct and each operation sees a consistent
result.
Serializability Definition for Index Operations:
A concurrent execution of index operations is
serializable if there exists an ordering of the
operations that is consistent with both the results
observed by each operation and the final index
state.
Techniques for B⁺‑trees:
Early release of leaf‑node locks after the
operation completes.
Detecting and handling structural
changes (splits, merges) without
violating correctness.
Index‑locking (as used by PostgreSQL for
phantom protection) does not follow the
 two‑phase protocol; locks are retained only
long enough to detect conflicting concurrent
updates and are released without causing
deadlocks.

Crabbing Protocol for B⁺‑Tree Indexes 🦀

Definition: The crabbing protocol is a latch‑based
concurrency technique for B⁺‑tree operations that
acquires and releases locks while traversing the
tree, avoiding a full two‑phase lock hold.
Search (lookup)
1. Acquire a shared latch on the root.
2. Before moving to a child, obtain a
shared latch on the child.
3. Release the latch on the parent after the
child is locked.
4. Repeat until a leaf node is reached.

Insert / Delete
 1. Follow the same shared‑latch descent to
the target leaf.
2. Lock the leaf exclusively and perform
the modification.
3. If a leaf split, coalesce, or redistribution
is needed, lock the parent exclusively.
4. Propagate splits/merges upward,
retaining the parent lock only while its
node is being changed; otherwise
release it.
The protocol’s “crab‑like” motion—alternating
between moving down and back up—allows
other operations to access nodes as soon as
their locks are released.
Deadlock handling:
Conflicts may arise between a
descending search and an upward
split/merge.
The system resolves this by restarting
the conflicted operation from the root
after releasing its held latches.
 Latches vs. locks:
Latches are short‑duration
mutual‑exclusion primitives; they do not
guarantee serializability on their own,
but the crabbing protocol ensures a
serializable execution of index
operations.
B‑Link Tree Locking Protocol 🌐
Definition: A B‑link tree augments every node
(including internal nodes) with a pointer to its right
sibling, enabling lock acquisition on only one
internal node at a time.
Key features
During a lookup, if a node splits, the
search may continue on the right‑sibling
pointer, avoiding the need to lock both
old and new nodes.
Locks are released before acquiring the
lock on the next node (child during
descent or parent during ascent).
 Concurrency advantage
Eliminates the possibility of deadlock
that exists in the crabbing protocol
because a transaction never holds two
internal node locks simultaneously.
Anomaly detection
Between releasing a node’s lock and
acquiring the parent’s lock, a concurrent
operation may alter the parent’s
structure.
The protocol detects such changes (e.g.,
the original parent no longer references
the child) and retries as needed,
preserving serializability.
Key‑Value and Next‑Key Locking 🔑
Key‑value locking acquires exclusive locks on
individual key values rather than the whole leaf
node, allowing concurrent inserts/deletes on
different keys within the same leaf.
Problem: Naïve key‑value locking still suffers
from the phantom phenomenon because a
transaction inserting a key that falls inside
another transaction’s range read will not
conflict.
Next‑key locking solves this by also locking
the next greater key (the next‑key):
Range/point lookup → lock all keys in
the range plus the immediate successor
key.
Insert → lock the key being inserted and
its successor.
Delete → lock the key being deleted and
its successor.
This ensures that any transaction attempting to
insert a value that would belong to another
transaction’s predicate range will conflict on
the next‑key lock, thus preventing phantoms.
Concurrency Control in Main‑Memory Databases
🧠
When data reside entirely in RAM, the overhead of
fine‑grained lock acquisition can dominate execution
time. Two common strategies are employed:
1. Coarse‑Grained Latching
Lock the entire index (or a large subtree) with
a single short‑duration latch, perform the
operation, then release the latch.
The reduced locking overhead often outweighs
the loss of concurrency because in‑memory
index operations are already very fast.
2. Latch‑Free (Lock‑Free) Data Structures
Use atomic compare‑and‑swap (CAS)
instructions to modify structures without any
explicit latches.
/* Unsafe concurrent insert – for illustration only */
insert(value, head) {
node = new node;
node->value = value;
node->next = head;
head = node;
}
/* Latch‑free insertion using CAS */
insert_latchfree(head, value) {
node = new node;
node->value = value;
repeat
oldhead = head;
node->next = oldhead;
result = CAS(head, oldhead, node);
until (result == success);
}

/* Latch‑free deletion (illustrates the ABA problem) */

delete_latchfree(head) {
repeat
oldhead = head;
newhead = oldhead->next;
result = CAS(head, oldhead, newhead);
until (result == success);
}

ABA problem: A deleted node may be

reinserted between the read of oldhead and
the CAS, causing the CAS to succeed while
pointing to a stale node.
Solution: Attach a counter to each
pointer (forming a pointer‑counter pair)
and perform CAS on the combined
128‑bit value. The counter increments on
every update, so a reinserted node has a
different counter, causing the CAS to fail.
 Modern languages provide robust lock‑free
containers (e.g., Boost for C++,
ConcurrentLinkedQueue for Java); using
these libraries is recommended over
hand‑rolled implementations.

Long‑Duration Transactions ⏳
Characteristics:
Extended user interaction → transaction
duration may span seconds to days.
Uncommitted data exposure → other
transactions may read intermediate results.
Subtask granularity → users may abort a part
of the work without aborting the whole
transaction.
Recoverability → after a crash, the transaction
must be restored to a recent, consistent state.
Performance focus → fast (human‑perceived)
response time rather than high throughput.
Interaction with Concurrency Control
 Snapshot Isolation (SI) and optimistic
concurrency without read validation are
commonly employed because they allow reads
from a consistent snapshot without holding
locks.
However, long‑duration transactions increase
the likelihood of conflicting updates, leading
to more aborts or wait‑times.
Operation‑Based Concurrency Control 🔧
Instead of treating only reads and writes as
fundamental, additional operations can be
incorporated directly into the locking protocol.
Increment Operation
Purpose: Atomically add a value n to a variable
v (e.g., updating a materialized view’s total).
Implementation options
Acquire an exclusive latch on v, perform
the addition, release the latch.
Use CAS (or other atomic instructions)
to avoid explicit latching.
 Compensating operation: If a transaction rolls
back, execute increment(v, -n) to undo the
effect.
Increment Lock Mode
Mode Compatibility
S (shared) Compatible with S only
X (exclusive) Compatible with none
I (increment) Compatible with I only;
not compatible with S or
X
Definition: The increment lock allows multiple
increment operations to proceed concurrently (they
are compatible with each other) but blocks any
shared or exclusive locks on the same variable.
Conditional Increment
Operation: increment_conditional(v, n) adds n
only if the resulting value stays non‑negative; it
returns success or failure.
 Concurrency notes
Even though the operation holds a
short‑term exclusive lock, two
concurrent conditional increments on the
same variable may yield different
outcomes (one succeeds, the other fails)
when the available amount is limited.
This trade‑off is acceptable in many
real‑world scenarios (e.g., ticket sales)
where strict serializability is relaxed for
higher throughput.
Real‑Time Transaction Systems ⏱️
Transactions must respect deadlines:
Deadline type Description
Hard Missing the deadline
may cause catastrophic
failure (e.g., system
crash).
Firm Transaction value drops
to zero after the
deadline; late
completion is useless.
 Soft Value degrades gradually
after the deadline.
Concurrency‑control protocols that force
waiting can cause deadline misses; therefore,
pre‑emptive strategies (e.g., aborting the
lock‑holder) are sometimes employed.
The decision between pre‑empting vs. rolling
back depends on the expected cost of restart
versus the risk of missing a deadline.
Main‑memory databases are preferred for
real‑time workloads because they eliminate
disk‑I/O variability; however, lock contention
and aborts still introduce timing variance.
Empirical studies show that optimistic
concurrency protocols (which avoid waiting)
often result in fewer missed deadlines
compared with extended locking schemes.
Long‑Duration Transactions & Version‑Number
Validation📊
Weak serializability via version numbers –
Applications can store a version number in each
tuple and, at commit time, validate that the
 versions of all tuples written have not changed
since they were read.
This technique can be implemented entirely in the
application layer, requiring no changes to the
underlying DBMS.
Provides optimistic concurrency control: reads
are performed without locks; only the final
writes are checked.
Guarantees a weak level of serializability
(sometimes called read‑committed or snapshot
semantics) because it prevents lost updates
but may still allow anomalies such as
write‑skew.
Suitable for user‑driven workflows where the
transaction spans many seconds or minutes
(e.g., web‑form submissions, airline seat
selection).
Special Concurrency Techniques for B⁺‑Trees 🌳
Non‑serializable B⁺‑tree access with structural
correctness –
Custom protocols permit concurrent operations on
a B⁺‑tree even when they would violate strict
two‑phase locking, as long as the tree’s structural
invariants (sorted order, proper leaf linking) are
preserved and the database operations themselves
remain serializable.
Index‑locking protocol (see earlier section)
protects leaf nodes; however, additional
techniques allow higher concurrency:
Crabbing protocol – locks are acquired
and released while
descending/ascending the tree,
preventing long‑held locks on interior
nodes.
B‑link tree locking – each node contains
a right‑sibling pointer; a transaction
never holds two interior node locks
simultaneously, eliminating deadlock.
Key‑value / next‑key locking – locks
the specific key plus its immediate
successor, preventing phantom inserts
without locking whole leaf pages.
 The goal is to decouple structural correctness
(the index remains a valid B⁺‑tree) from
transactional serializability (the logical
updates to user data must still be serializable).
Latch‑Free Data Structures in Main‑Memory
Databases ⚡
Latch‑free (lock‑free) indices –
In pure main‑memory systems, fine‑grained lock
overhead can dominate. Latch‑free structures rely
on atomic primitives such as compare‑and‑swap
(CAS) to modify nodes without acquiring explicit
locks.
CAS‑based insertion creates a new node,
links it, and atomically swaps the head pointer.
ABA problem: a node removed then
re‑inserted can make a stale CAS succeed;
mitigated by attaching a counter (forming a
128‑bit “pointer‑counter” pair) and using a
double‑word CAS (DCAS).
 Latch‑free designs achieve higher throughput
but require careful handling of memory
reclamation and version counters.
Review of Concurrency‑Control Terminology 📚
Term Brief Meaning
Concurrency control Mechanisms that ensure
correct interleaving of
transactions.
Lock types S (shared) vs. X
(exclusive).
Lock A data‑item lock;
associated with a mode
and a transaction.
Compatibility Whether two lock
requests can coexist.
Request / Wait / Grant Stages of lock
acquisition.
Deadlock Circular waiting among
transactions.
Starvation A transaction never
obtains needed locks.
 Locking protocol Rules governing lock
acquisition/release (e.g.,
2PL).
Legal schedule A schedule that respects
the locking protocol.
Two‑phase locking Growing phase →
(2PL) shrinking phase; no lock
acquisition after release.
Lock point Exact moment a
transaction acquires its
last lock.
Strict 2PL All X‑locks held until
commit/abort.
Rigorous 2PL All locks (S and X) held
until commit/abort.
Lock conversion Upgrade (S→X) or
downgrade (X→S).
Graph‑based protocols Tree protocol, forest
protocol, etc.
 Commit dependency One transaction’s
commit contingent on
another.
Deadlock handling Prevention, detection,
recovery.
Ordered locking Acquire locks in a
predefined order to
avoid cycles.
Preemption Abort a holder to break
a deadlock.
Wait‑die / Wound‑wait Timestamp‑based
deadlock‑avoidance
schemes.
Timeout‑based Abort after a waiting
period.
Multiple granularity Locks at database,
relation, page, tuple
levels.
Intention locks IS, IX, SIX – signals
about lower‑level locks.
Timestamp System‑clock or logical
counter assigned to each
 transaction.
W‑timestamp(Q) Largest timestamp of a
successful write on Q.
R‑timestamp(Q) Largest timestamp of a
successful read on Q.
Timestamp‑ordering Enforces order using
protocol timestamps; Thomas’
write rule applies.
Validation‑based Read → validation →
protocols write phases.
Multiversion timestamp Readers see the latest
ordering version ≤ their
timestamp.
Snapshot isolation Reads see a snapshot at
start; writes validated
against concurrent
commits.
Write‑skew An anomaly possible
under SI where disjoint
writes cause a
non‑serializable
outcome.
 SELECT FOR UPDATE Forces read‑only rows to
acquire X‑locks, turning
them into writes.
Phantom phenomenon Insert/delete/updates
affect results of
predicate reads without
touching the same tuple.
Degree‑two S‑locks may be released
consistency early; X‑locks held to
commit.
Cursor stability Locks only the current
cursor tuple.
Optimistic concurrency Validates only writes;
without read validation reads are unchecked.
Crabbing protocol Latch protocol that
releases parent latch
before locking child.
B‑link tree Right‑sibling pointers
allow lock‑free upward
traversal.
Next‑key locking Locks range key plus its
successor to prevent
 phantoms.
Compare‑and‑swap Atomic instruction used
(CAS) in latch‑free structures.
Practice Exercises 📝
1. 2PL → conflict‑serializability – prove lock
points yield a serial order.
2. Lock insertion for T34/T35 – add lock/unlock
calls; discuss potential deadlock.
3. Rigorous 2PL benefits – compare with basic
2PL and strict 2PL.
4. Tree protocol with dummy vertices – show
increased concurrency.
5. Tree vs. 2PL schedules – give examples of
schedules exclusive to each protocol.
6. Page‑level locking via OS protection –
describe use of mprotect‑style mechanisms.
7. Increment operation lock mode – prove 2PL
serializability and increased concurrency.
8. W‑timestamp definition change – discuss
effect on protocol correctness.
9. Granularity impact on lock count &
concurrency – provide contrasting scenarios.
10. Practical suitability of protocols – evaluate
each listed protocol for real‑world use cases.
11. Two‑phase validation vs. strict 2PL – explain
performance advantage (disk I/O).
12. Cascading abort & starvation in timestamp
ordering – construct a livelock schedule.
13. Phantom‑free timestamp protocol – outline a
design.
14. Early lock release in B⁺‑tree splits – identify
conditions permitting it.
15. Snapshot isolation validation
(first‑committer‑wins) – detail steps using
timestamps and update sets.
16. First‑updater‑wins scheme – assign write
timestamps, show repeatability of validation.
17. ABA problem in latch‑free insert/delete –
explain occurrence and mitigation with
counters.
18. Strict 2PL pros & cons – list benefits and
drawbacks.
19. Popularity of strict 2PL – give three reasons
for widespread adoption.
20. Forest protocol non‑serializability –
demonstrate a violating schedule.
21. When deadlock avoidance is cheaper –
describe favorable conditions.
22. Starvation under deadlock‑avoidance –
discuss possibility and reasoning.
23. Implicit vs. explicit locking – define the
difference in multiple‑granularity context.
24. Uselessness of XIS mode – explain why it
provides no additional functionality.
25. Parent lock mode restrictions – reason why
S/IS cannot be granted when parent is SIX or
S.
26. Lock strategy for heavy
read‑then‑few‑update workloads – suggest
appropriate lock hierarchy and scaling solution.
27. Timestamp reuse after abort – why a new
timestamp is required.
28. Schedules exclusive to 2PL vs. timestamp
protocol – give illustrative examples.
29. Commit‑bit test to avoid cascading aborts –
explain its effect on reads vs. writes.
30. Snapshot isolation vs. multiversion
timestamp ordering – pinpoint the key
difference affecting serializability.
31. Similarities/differences between
first‑committer‑wins SI and optimistic
 concurrency without read validation –
outline main points.
32. Non‑serializable execution of max‑A‑value
insertion – analyze both with and without
primary‑key constraint.
33. Phantom phenomenon recap – why it can
break 2PL despite predicate locking.
34. Degree‑two consistency rationale and
disadvantages – summarize.
35. Key‑value locking without next‑key – show
phantom‑triggering schedules.
36. Ordering operations to increase concurrency
for common/private item updates – propose
an ordering technique.
37. Lock‑ordering protocol (only
higher‑numbered items may be locked) –
demonstrate a non‑serializable schedule.
Buffer Management & Crash Risks 📦
Definition: The buffer manager mediates between
main memory and disk.
input(BX) – brings block BX from disk into a
buffer.
 output(BX) – writes the current contents of
buffer BX back to disk (a force‑output when
the system explicitly issues output(B)).
read(X) – a transaction reads data item X for
the first time; this may require an input if X is
not already in a buffer.
write(X) – the transaction updates X in its
buffer; the actual output(BX) can be delayed
because the buffer may contain other items
still in use.
If a crash occurs after write(X) but before
output(BX), the new value of X is lost. Recovery
mechanisms therefore must guarantee that updates
of committed transactions survive such failures.

Recovery & Atomicity Principles 🔄

Goal: Ensure that each transaction’s effects are
all‑or‑nothing—either every modification reaches
stable storage or none does.
When a transaction like Ti transfers $50 from account
A to B:
 Step Action Result
(pre‑crash)
1 output(BA) A = $950
(block of A)
2 – crash – B still $2000
The database ends in an inconsistent state because
we cannot determine whether Ti committed. To
enforce atomicity we must first log the intention of
modifications before touching the database.

Log Records 📓
Definition: A log record is an entry stored on
stable storage describing a database update or
transaction event.
Record Type Fields Example
Update Transaction ID,
Data‑item ID,
Old value, New
value
Start Transaction ID
 Commit Transaction ID
Abort Transaction ID
The update record must be written before the
corresponding database write (write‑ahead
logging).
Log records remain on stable storage (disk) so
they survive system crashes.
When a transaction aborts, the old‑value field
lets the system undo the change; the
new‑value field enables redo after a crash.
The log can become large; later sections
discuss safe truncation.
Shadow Copy & Shadow Paging 📂
Shadow Copy: Create a full copy of the database,
perform all updates on the copy, and discard the
copy if the transaction aborts.
Commit steps:
1. Ensure all pages of the new copy are
flushed (fsync).
2. Atomically write a db‑pointer (located in
a single disk sector) to point to the new
 copy.
3. Delete the old copy.

Shadow Paging: Only pages that change are

copied; a new page table points to new pages
while unchanged pages are shared. The db‑pointer
is atomically switched to the new page table at
commit.
Advantages: Simple abort (just delete the
copy).
Disadvantages: Expensive for large
databases; poor support for concurrent
transactions (rarely used in DBMS).
Database Modification Techniques 🛠️
1. Computation in the transaction’s private
memory.
2. Modify the disk buffer holding the data item.
3. Output the buffer to disk (optional at this
point).
Immediate‑modification – updates are
written to buffers while the transaction is still
active.
 Deferred‑modification – all updates are kept
in private copies until the transaction commits;
only then are they applied to buffers.
The recovery algorithms presented work with
immediate modification but can be optimized for
the deferred case.

Concurrency Control & Recovery Interaction 🔐

To avoid undoing the work of another
transaction, a data item updated by T1 must
not be modified by T2 until T1 either commits
or aborts.
Enforced by acquiring an exclusive lock on the
item and holding it until the transaction’s end
(strict two‑phase locking).
Snapshot isolation and validation‑based
protocols also obtain exclusive locks at
validation time and keep them until commit,
satisfying the same requirement.
Some systems relax this rule (see Section 19.8),
but the default assumption is strict locking.
Transaction Commit Protocol ✅
 Commit Criterion: A transaction is considered
committed when its commit log record () has been
output to stable storage.
All preceding log records are already persisted,
guaranteeing enough information for redo
after a crash.
The actual data blocks modified by the
transaction need not be flushed immediately;
they may be written later (Section 19.5.2).
Redo & Undo Using the Log ↩️
Redo (redo(T_i))
Sets each updated item to its new value.
Must respect the original execution order; a
single forward scan of the log performs redo
for all transactions efficiently.
Undo (undo(T_i))
Restores each updated item to its old value
using the log record.
Writes redo‑only log records (new value = old
value) for the undo actions.
 After undo finishes, a record is appended,
signaling that the transaction has been fully
rolled back.
Determining Action After a Crash
Undo if the log contains and lacks both and .
Redo if the log contains and either or (the
latter case includes the undo‑generated
redo‑only records).
Crash Scenarios & Recovery Example 🚨
Consider two transactions:
T0: read(A); A := A – 50; write(A);
read(B); B := B + 50; write(B);
T1: read(C); C := C – 100; write(C);

Log fragment (Figure 19.2):

Log entry Meaning
T0 begins
A changed from $1000
to $950
B changed from $2000
to $2050
 T0 committed
T1 begins
C changed from $700 to
$600
T1 committed
Scenario 1 – Crash after write(B) but before its
output
Log contains but no or .
Action: undo(T0) → restore A = $1000, B =
$2000.
Scenario 2 – Crash after write(C) of T1
Log shows (so T0 must be redone) and
without or (so T1 must be undone).
Actions:
1. undo(T1) → C restored to $700.
2. redo(T0) → A = $950, B = $2050.

In both cases, the recovery procedure uses the log to

bring the database back to a consistent state
respecting atomicity.