Two-Phase Locking 2PL: Conflict-Serializability and Lock-Point Serialization Order | AI Research

Two-Phase Locking (2PL): Conflict-Serializability and Lock-Point Serialization Order

Verified Sources

Nov 4, 2026

Two-phase locking {keyword{def="Protocol using a growing phase followed by a shrinking phase for each transaction"} keyword{def="Lock point is the operation where a transaction acquires the lock that first determines ordering"} keyword{def="Precedence graph represents rw/wr/ww order constraints between transactions"} } (2PL) enforces a disciplined way to acquire and release locks so that the resulting schedule is conflict-serializable. Moreover, for each pair of conflicting transactions, their relative order in the equivalent serial schedule is determined by the lock points—the specific lock acquisition events that enforce the conflicts.

At a high level:

To show conflict serializability, we show that the precedence graph of a 2PL schedule is acyclic.
To show the serialization order follows lock points, we define a “lock-based” ordering between transactions implied by the first (or relevant) lock acquisitions, and we prove that this ordering is exactly the serial order captured by the precedence graph.

A crucial idea is that in 2PL, once a transaction begins releasing locks (shrinking phase), it can no longer acquire new locks. This prevents “lock re-acquisition” patterns that would otherwise create cycles in the precedence graph.

Two-Phase Locking (2PL) & Conflict Serializability (Locking-Based Ordering)

Formal setting: schedules, conflicts, and precedence graphs

Let a schedule be an interleaving of operations from transactions. Conflicts arise when two operations from different transactions:

access the same data item, and
at least one is a write, and
the two operations occur in different orders in the schedule.

We build a precedence graph (a directed graph) where each node is a transaction, and we add an edge $T_i \rightarrow T_j$ if the schedule contains a conflict where $T_i$ ’s operation occurs before $T_j$ ’s corresponding conflicting operation on the same item. Then:

The schedule is conflict-serializable iff the precedence graph is acyclic (equivalently, has a topological order corresponding to a serial order).

This is the standard route: prove 2PL ⇒ acyclic precedence graph ⇒ conflict serializable.

Prove that 2PL schedules are conflict-serializable (via acyclicity of the precedence graph)

1
Step 1
Take any 2PL schedule $S$ and construct its precedence graph $PG(S)$ : add edge $T_i \to T_j$ whenever an operation of $T_i$ conflicts with an operation of $T_j$ and $T_i$ occurs earlier in $S$ .
2
Step 2
Assume $PG(S)$ contains a cycle: $T_1 \to T_2 \to \cdots \to T_k \to T_1$ . For each edge $T_m \to T_{m+1}$ , pick a concrete conflicting pair of operations on some data item $X_m$ that witnesses this edge.
3
Step 3
Because operations on a data item must hold compatible/exclusive locks, the conflicting operation order implies that the earlier transaction acquired a lock on its required mode for that item before the later transaction could perform its conflicting operation.
4
Step 4
For any item $X$ , consider the lock acquisitions around its conflicting operations. In a cycle, you would need each transaction to be ‘ahead’ in lock acquisition for the item that creates each edge, but the 2PL growing-then-shrinking rule forbids a transaction that has started releasing locks from later acquiring a lock needed to create a later edge in the cycle.
5
Step 5
In a cycle, you force at least one transaction to acquire (for some edge) a lock after it has begun releasing locks—violating 2PL.
6
Step 6
Since assuming a cycle leads to contradiction, $PG(S)$ must be acyclic. Therefore $S$ is conflict-serializable.

Why the shrinking phase blocks cycles (core intuition)

A precedence-cycle requires “mutual forcing”: transaction $T_1$ must appear before $T_2$ for some item, $T_2$ before $T_3$ , …, and finally $T_k$ before $T_1$ . In lock-based terms, that would require a pattern where the transactions keep acquiring locks in a way that alternates who holds/requests locks “later” in the schedule while still respecting lock compatibility.

Under 2PL, each transaction has:

a growing phase: it may acquire locks, but does not release them, then
a shrinking phase: it may release locks, but does not acquire new ones.

This structure prevents the kind of “after-releasing, later-acquire” behavior that cycles would require. Hence a cycle can’t exist in the precedence graph.

type="tip" title="Tip: Think in terms of ‘who must lock first’" content="Every precedence edge $T_i \to T_j$ comes from a conflicting operation order on some data item $X$ . Under locking, that means $T_i$ must have acquired the decisive lock on $X$ before $T_j$ could do the conflicting operation. In a cycle, these lock-order requirements conflict with the shrinking-phase rule."

type="warning" title="Warning: This relies on the strict 2PL rule" content="If you allow transactions to release some locks but still acquire new ones later (i.e., not strict/2PL), precedence cycles may become possible. The ‘no lock acquisition during shrinking’ property is what blocks the cyclic ordering."

Lock Points and the Corresponding Serialization Order

Definitions: lock points, conflicting transactions, and serialization order

We now refine the result: not only is the schedule conflict-serializable, but the serial order can be chosen based on lock points.

A keyword lock point is commonly taken as the acquisition time of the lock on the data item that is responsible for enforcing the precedence relation.

For a particular pair of transactions $T_i$ and $T_j$ that conflict on some item $X$ , suppose in the schedule there is an operation of $T_i$ before the conflicting operation of $T_j$ . Then the precedence graph has an edge $T_i \\to T_j$ .

Under 2PL, we can show:

The transaction that acquires the relevant lock first becomes earlier in the equivalent serial schedule.
More generally, if we define a serial order consistent with all precedence edges, that serial order equals the ordering induced by these lock points.

Construct the equivalent serial schedule order from lock points

1
Step 1
For every edge $T_i \to T_j$ in $PG(S)$ , select the conflicting operations on a data item $X$ where $T_i$ ’s operation occurs earlier in the schedule.
2
Step 2
For the witnessing operations on $X$ , determine the lock acquisition events that make the second transaction’s conflicting operation possible. The earlier transaction’s decisive lock acquisition is the lock point that supports $T_i \to T_j$ .
3
Step 3
Create an order relation: if $T_i \to T_j$ is forced by a conflict whose decisive lock point for $T_i$ occurs earlier than $T_j$ ’s corresponding decisive lock point, then place $T_i$ before $T_j$ in the serial order.
4
Step 4
Because $PG(S)$ is acyclic under 2PL, the edge constraints are jointly satisfiable by some topological ordering. The lock-point ordering matches these constraints; hence the constructed order yields a valid serial schedule.
5
Step 5
Therefore, the transaction order in the equivalent serial schedule can be chosen to follow the lock points that determine each conflict’s direction.

A visualization: lock points induce precedence edges

Consider a conflict on $X$ between $T_i$ and $T_j$ . The lock point order implies the precedence edge direction.

Because 2PL prevents new lock acquisitions during shrinking, these lock-point-implied edges cannot be arranged into cycles; the resulting graph has a topological order that matches lock-point order.

Relationship between properties

How 2PL constraints translate into graph properties and serializability.

Key nuances and common misconceptions

2PL Conflict Serializability & Lock Points

1 / 5

Question · Term

What must be shown to prove conflict serializability using precedence graphs?

Click to reveal

Answer · Definition

Show the precedence graph is acyclic (then it has a topological order matching some serial schedule).

Knowledge Check

Question 1 of 4

Q1Single choice

To prove a schedule is conflict-serializable using the precedence graph method, which property must you prove about the precedence graph under 2PL?

The precedence graph is acyclic

The precedence graph has exactly one node per data item

The precedence graph is complete

The precedence graph is a tree

Explore Related Topics

Functions of the OSI Session Layer: Session Establishment and Synchronization

Deadlock Handling in DBMS: Prevention, Avoidance, Detection, and Recovery

Log-Based Recovery (Immediate DB Modification + Strict 2PL): Failure at `T2 : commit`

Browse all research articles