Self-checkedTier 1 8 min readdbms.schedules-serializability

Schedules, conflict and view serializability

Schedules, serial schedules and the idea of serializability as the correctness criterion for concurrent execution; conflicting operations, conflict equivalence, the precedence graph test (acyclic means conflict serializable, topological orders are the equivalent serial schedules), view equivalence and view serializability with blind writes, the relation between the two classes, and counting interleavings; every example is computed from the definitions and cross-checked by independent algorithms.

Why it exists

Running transactions one after another (a serial schedule) is always correct but slow: the disk and the CPU would idle while one transaction waits. Running them interleaved is fast but can produce the anomalies of the previous page. The compromise is to allow only interleavings that are equivalent to a serial schedule, because a serial schedule is correct by assumption (each transaction keeps the database consistent). This page defines "equivalent" in two ways and gives the tests GATE asks for most often.

Prerequisites

You need transactions and their operations (transactions and ACID). Graph cycles are used (graph traversals).

Precise definitions

A schedule $S$ of transactions $T_1, \dots, T_n$ is a sequence of all their operations in which the operations of each $T_i$ appear in their original order. It is serial if the operations of different transactions are not interleaved (each transaction runs from its first to its last operation without interruption). For $n$ transactions there are $n!$ serial schedules.

If the transactions have $k_1, \dots, k_n$ operations, the number of schedules is the multinomial coefficient

\frac{(k_1 + \cdots + k_n)!}{k_1!\,k_2!\cdots k_n!}

(three transactions of two operations each: $6!/(2!)^3 = 90$ ).

Conflicting operations. Two operations conflict if they (1) belong to different transactions, (2) access the same item and (3) at least one of them is a write. So $r$ – $w$ , $w$ – $r$ and $w$ – $w$ conflict; $r$ – $r$ never does. The order of two conflicting operations matters: swapping them can change what some transaction reads or what the database finally contains. Operations that do not conflict can be swapped freely.

Conflict equivalence. Two schedules (of the same transactions and operations) are conflict equivalent if every pair of conflicting operations appears in the same order in both. A schedule is conflict serializable if it is conflict equivalent to some serial schedule.

Precedence graph (serialization graph) of $S$ : a node for each transaction; an edge $T_i \to T_j$ whenever an operation of $T_i$ conflicts with and comes before an operation of $T_j$ .

Theorem (test). $S$ is conflict serializable if and only if its precedence graph has no cycle. Then every topological order of the graph is a serial schedule conflict equivalent to $S$ (and these are all of them).

View equivalence. Two schedules $S$ and $S'$ are view equivalent if

every read reads from the same write operation in both (or from the initial value in both): the reads-from relation is the same;
for every item the final write is by the same operation (transaction) in both.

$S$ is view serializable if it is view equivalent to a serial schedule. The reads-from relation has to name the write operation: if a transaction writes $X$ twice, a read must see the same one of the two writes in both schedules. (The usual textbook wording names only the transaction; the difference appears only for transactions with several writes of one item and the checks of this site found it, see the verification notes.)

Blind write: a write by a transaction that did not read the item before. Blind writes are what make view serializability larger than conflict serializability.

How it works

The precedence graph test

Go through the schedule operation by operation and, for each operation, add an edge from the transaction of every earlier conflicting operation. Then look for a cycle.

Precedence graph of a conflict serializable schedule: start

Computed by a script, not typed

time	1	2	3	4	5	6	7	8	9
T1
T2
T3
new edges

Step 0

Three transactions on A and B. A step adds the operation and the precedence edges it creates: an edge Ti → Tj for every earlier conflicting operation of Ti.

0 / 9

computed by script: schedules are executed on real values, conflicts and classes follow the definitions, locks are granted by a real lock manager. python3 scripts/gen-db5-traces.py

Three transactions: $r_3(B)\ r_1(A)\ w_3(B)\ r_2(A)\ w_1(A)\ w_2(B)$ . The conflicts are $r_2(A)$ before $w_1(A)$ (edge $T_2 \to T_1$ ), and $r_3(B)$ , $w_3(B)$ before $w_2(B)$ (edge $T_3 \to T_2$ ). No cycle; the only topological order is $T_3\,T_2\,T_1$ , so the schedule is conflict equivalent to the serial schedule $T_3, T_2, T_1$ and to no other.

Precedence graph with a cycle: start

Computed by a script, not typed

time	1	2	3	4	5	6
T1
T2
new edges

Step 0

Two transactions that each touch A and B.

0 / 6

computed by script: schedules are executed on real values, conflicts and classes follow the definitions, locks are granted by a real lock manager. python3 scripts/gen-db5-traces.py

Here $r_1(A)$ before $w_2(A)$ gives $T_1 \to T_2$ , and $w_2(B)$ before $r_1(B)$ gives $T_2 \to T_1$ : a cycle. $T_1$ would have to be both before and after $T_2$ , so no serial schedule is equivalent.

How many serial schedules are equivalent? The number of topological orders of the graph. With edges $T_1 \to T_2$ and $T_1 \to T_3$ only (for example $r_1(A)\ w_1(A)\ r_2(A)\ r_3(A)$ ) there are two: $T_1 T_2 T_3$ and $T_1 T_3 T_2$ .

View serializability

View serializable without being conflict serializable: start

Computed by a script, not typed

time	1	2	3	4	5	6	7
T1
T2
T3
new edges

Step 0

Three transactions, T2 and T3 only write A.

0 / 7

computed by script: schedules are executed on real values, conflicts and classes follow the definitions, locks are granted by a real lock manager. python3 scripts/gen-db5-traces.py

$S = r_1(A)\ w_2(A)\ w_1(A)\ w_3(A)$ is not conflict serializable (cycle $T_1 \to T_2 \to T_1$ ). The serial schedule $T_1\,T_2\,T_3$ has the same reads-from ( $T_1$ reads the initial value of $A$ ; nobody else reads) and the same final write of $A$ (by $T_3$ ), so $S$ is view serializable. The writes of $T_1$ and $T_2$ are overwritten by $T_3$ before anyone reads them: the blind writes of $T_2$ and $T_3$ and the useless write of $T_1$ do not matter.

Relation. Every conflict serializable schedule is view serializable; the converse is false (the example). If a schedule is view serializable but not conflict serializable it contains a blind write. Testing view serializability is NP-complete (quoted from the literature); testing conflict serializability takes time linear in the size of the graph. That is why systems enforce conflict serializability or something stronger.

How many interleavings are serializable

How many interleavings are serializable?: start

Computed by a script, not typed

transactions	interleavings	serial	conflict serializable	view serializable
T1: r(A) w(A); T2: r(A) w(A)
T1: r(A) w(A); T2: r(B) w(B)
T1: r(A) w(B); T2: r(B) w(A)
T1: w(A) w(B); T2: w(A) w(B)
T1, T2, T3: r(A) w(A)

Step 0

Counted by enumerating all interleavings of the given programs (operation order inside a transaction kept) and testing each with the definitions.

0 / 5

computed by script: schedules are executed on real values, conflicts and classes follow the definitions, locks are granted by a real lock manager. python3 scripts/gen-db5-traces.py

Two read-modify-write transactions on the same item have $6$ interleavings, only the $2$ serial ones are serializable. With independent items all $6$ are. With only blind writes ( $w(A)\ w(B)$ twice) $4$ of $6$ are conflict serializable. Three read-modify-write transactions on one item: of $90$ interleavings only the $6$ serial ones are serializable.

Worked examples

EX 1Count the schedules

Easy

$T_1$ has $3$ operations and $T_2$ has $2$ : $5!/(3!\,2!) = 10$ schedules, $2$ of them serial. Three transactions of two operations: $90$ schedules, $6$ serial.

EX 2Which pairs conflict

Easy

In $r_1(A)\ w_2(A)\ r_3(A)\ w_1(B)\ r_2(B)$ : $r_1(A)$ – $w_2(A)$ conflict ( $T_1 \to T_2$ ), $w_2(A)$ – $r_3(A)$ conflict ( $T_2 \to T_3$ ), $w_1(B)$ – $r_2(B)$ conflict ( $T_1 \to T_2$ ). $r_1(A)$ and $r_3(A)$ do not (two reads). Edges: $T_1 \to T_2$ , $T_2 \to T_3$ : acyclic, equivalent serial schedule $T_1\,T_2\,T_3$ only.

EX 3Lost update is not serializable

Medium

$r_1(A)\ r_2(A)\ w_1(A)\ w_2(A)$ : $r_2(A)$ before $w_1(A)$ gives $T_2 \to T_1$ ; $r_1(A)$ before $w_2(A)$ gives $T_1 \to T_2$ : cycle, not serializable. (The numbers of the previous page, $150$ instead of $120$ , show that this is a real failure.)

EX 4Number of equivalent serial schedules

Medium

Edges $T_1 \to T_2$ and $T_1 \to T_3$ : orders $T_1 T_2 T_3$ and $T_1 T_3 T_2$ , so $2$ . No edges at all (disjoint items) with $3$ transactions: all $3! = 6$ serial schedules are equivalent.

EX 5View but not conflict

GATE level

$r_1(A)\ w_2(A)\ w_1(A)\ w_3(A)$ (commits omitted): cycle between $T_1$ and $T_2$ , so not conflict serializable; view equivalent to $T_1 T_2 T_3$ (checked: the only read is of the initial value, the final write is $T_3$ 's). Another equivalent serial order is $T_2 T_1 T_3$ ? Then $T_1$ 's read would see $T_2$ 's write instead of the initial value, so it is not equivalent: only $T_1 T_2 T_3$ works.

Cheat box

Conflict: different transactions, same item, at least one write.
Conflict serializable $\iff$ precedence graph acyclic; equivalent serial schedules = topological orders.
View equivalent: same reads-from, same final writes. View serializable contains conflict serializable; the difference needs blind writes.
Schedules for $k_i$ operations: $(\sum k_i)!/\prod k_i!$ ; serial: $n!$ .
Testing conflict serializability is easy, view serializability NP-complete.

Traps and GATE patterns

Connections

Builds on

Transactions and ACID

Unlocks

Transactions and ACIDuses Recoverable, cascadeless and strict schedulesPrerequisite of Recoverable, cascadeless and strict schedulesuses Two-phase locking and its variantsPrerequisite of Two-phase locking and its variantsuses Timestamp orderingPrerequisite of Timestamp orderinguses

Across subjects

No cross-subject links yet.

Within this subject

Transactions and ACIDuses Recoverable, cascadeless and strict schedulesuses Two-phase locking and its variantsimplemented-by Timestamp orderingimplemented-by

Serializability is the formal meaning of isolation (transactions and ACID). Two-phase locking (two-phase locking) and timestamp ordering (timestamp ordering) are protocols that guarantee it. A serializable schedule can still be unrecoverable (recoverability).

PYQs

18 previous year questions from your book. I re-solved each one myself (16 by running or simulating, 2 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2026 · Set 2 · MCQ · 1 markQ1 · page 433 of the book

Consider concurrent execution of two transactions T1
and T2 in a DBMS, both of which access a data object
A. For these two transactions to not conflict on A, which
one of the following statements must be true?

(a)Both T1 and T2 only read A
(b)T1 reads A and T2 writes A
(c)T1 writes A and T2 reads A
(d)Both T1 and T2 write A

GATE 2025 · Set 2 · MSQ · 2 marksQ2 · page 433 of the book

Consider the database transactions T1and T2, and data
items X and Y. Which of the schedule(s) is/are conflict
serializable?

Transaction T1 : R1(X) ; W1(Y) ; R1(X) ; W1(X) ;
COMMIT(T1)
Transaction T2 : W2(X); W2(Y) ;COMMIT(T2)

(a)R1(X),W2(X),W1(Y),W2(Y),R1(X), W1(X),COM MIT(T2),COMMIT(T1)
(b)W2(X),R1(X),W2(Y),W1(Y),R1(X),COMMIT (T2),W1(X),COMMIT(T1)
(c)R1(X),W1(Y),W2(X),W2(Y),R1(X),W1(X), COMMIT(T1),COMMIT(T2)
(d)W2(X),R1(X),W1(Y),W2(Y),R1(X), COMMIT(T2),W1(X),COMMIT(T1)

GATE 2024 · Set 2 · MSQ · 2 marksQ7 · page 434 of the book

Consider the following read-write schedule S over three
transactions T1,T2 and T3, where the subscripts in the
schedule indicate transaction IDs:

S: r1(z); w1(z);r 2(x); r3(y); w3(y); r2(y); w2(x);
w2(y);

Which of the following transaction schedules is/are
conflict equivalent to S?

(a)T1T2T3
(b)T1T3T2
(c)T3T2T1
(d)T3T1T2

GATE 2022 · MCQ · 2 marksQ8 · page 434 of the book

Let Ri(z) and Wi(z) denote read and write operations on
a data element z by a transaction Ti, respectively.
Consider the schedule S with four transactions.

S: R4(x) R2(x) R3(x) R1(y) W1(y) W2(x) W3(y) R4(y)

Which one of the following serial schedules is conflict
equivalent to S ?

(a)T1→T3→T4→T2
(b)T1→T4→T3→T2
(c)T4→T1→T3→T2
(d)T3→T1→T4→T2

year not read yetQ10 · page 434 of the book

Let S be the following schedule of operations of three
transactions T1, T2 and T3 in a relational database system:

R2(Y), R1(X), R3(Z), R1(Y), W1(X), R2(Z), W2(Y),
R3(X), W3(Z)

Consider the statements P and Q below:

P: S is conflict-serializable.

Q: If T3 commits before T1 finishes, then S is recoverable.

Which one of the following choices is correct?

(a)Both P and Q are true.
(b)P is false and Q is true.
(c)Both P and Q are false.
(d)P is true and Q is false.

GATE 2021 · Set 1 · MCQ · 2 marksQ11 · page 434 of the book

Let ri(z) and wi(z) denote read and write operations
respectively on a data item z by a transaction Ti. Consider
the following two schedules.

S1 : r1(x) r1(y) r2(x) r2(y) w2(y) w1(x)

S2 : r1(x) r2(x) r2(y) w2(y) r1(y) w1(x)

Which one of the following options is correct?

(a)S1 is not conflict serializable, and S2 is conflict serializable.
(b)Both S1 and S2 are conflict serializable.
(c)Neither S1 nor S2 is conflict serializable.
(d)S1 is conflict serializable, and S2 is not conflict serializable.

GATE 2020 · MCQQ13 · page 435 of the book

Consider a schedule of transactions T1 and T2 :

Here, RX stands for "Read(X)" and WX stands for
"Write(X)". Which one of the following schedules is
conflit equivalent to the above schedule?

GATE 2017 · Set 2 · NAT · 2 marksQ15 · page 435 of the book

Two transactions T1 and T2 are given as:

T1 : r1(X)w1(X)r1(Y)w1(Y)

T2 : r2 (Y)w2(Y)r2(Z)w2(Z)

where r i(V) denotes a read operation by transaction T i on
a variable V and w i(V) denotes a write operation  by
transaction T i on a variable V. The total number of conflict
serializable schedules that can be formed by T1 and T2 is
_____.

GATE 2016 · Set 2 · MCQ · 1 markQ16 · page 435 of the book

Suppose a database schedule S involves transactions
T1,...,Tn. Construct the precedence graph of S  with
vertices representing the transactions and edges
representing the conflicts. If S is serializable, which one
of the following orderings of the vertices of the
precedence graph is guaranteed to yield a serial schedule?

(a)Topological order
(b)Depth-first order
(c)Breadth-first order
(d)Ascending order of the transaction indices.

GATE 2016 · Set 1 · NAT · 1 markQ20 · page 436 of the book

Consider the following directed graph:

The number of different topological ordering of the
vertices of the graph is ____ .

GATE 2014 · Set 3 · MCQ · 2 marksQ24 · page 437 of the book

Consider the transactions T1,T2,andT3 and the
schedules S1 and S2  given below.

T1:r1(X);r1(Z);w1(X);w1(Z)

T2:r2(Y);r2(Z);w2(Z)

T3:r3(Y);r3(X);w3(Y)

S1:r1(X);r3(Y);r3(X);r2(Y);r2(Z);w3(Y);w2(Z);r1(Z);
w1(X);w1(Z)

S2:r1(X);r3(Y);r2(Y);r3(X);r1(Z);r2(Z);w3(Y);w1(X);
w2(Z);w1(Z)

Which one of the following statements about the
schedules is TRUE?

(a)Only S1 is conflict-serializable.
(b)Only S2 is conflict-serializable.
(c)Both S1 and S2 are conflict-serializable
(d)Neither S1 nor S2 is conflict-serializable.

GATE 2014 · Set 1 · MCQ · 2 marksQ25 · page 437 of the book

Consider the following four schedules due to three
transactions (indicated by the subscript) using read and
write on a data item x, denoted by r(x) and w(x)
respectively. Which one of them is conflict serializable?

(a)r1 (x); r2 (x);w1 (x); r3 (x); w2 (x)
(b)r2 (x); r1 (x);w2 (x); r3 (x); w1 (x)
(c)r3 (x); r2 (x);r1 (x); w2 (x); w1 (x)
(d)r2 (x); w2 (x);r3 (x); r1 (x); w1 (x)

GATE 2014 · Set 2 · MCQQ26 · page 437 of the book

Consider the following schedule S of transactions T1, T2,
T3, T4:

T1
T3
T3
T.
Writes
(X)
Commit

Writes
(Y)
Reads (Z)
Commit

Reads
(X)
Reads
(Y)
Commit

Which one of the following statements is CORRECT?

(a)S is conflict-serializable but not recoverable
(b)S is not conflict-serializable but is recoverable
(c)S is both conflict-serializable and recoverable
(d)S is neither conflict-serializable nor is it recoverable

GATE 2012 · MCQ · 2 marksQ27 · page 437 of the book

Consider the following transactions with data items P and
Q initialized to zero:

T1 : read (P);

  read (Q) ;

   if P = 0 then
Q : = Q + 1 ;

 write (Q) ;
T2 : read (Q);

read (P) ;

  if Q = 0 then
P : = P + 1 ;

 write (P) ;

Any Non-serial interleaving of T1 and T2 for concurrent
execution leads to
Read
(X)
Writes (X)
Commit

DATABASE MANAGEMENT  SYSTEM

(a)a serializable schedule
(b)a schedule that is not conflict serializable
(c)a conflict serializable schedule
(d)a schedule for which a precedence graph cannot be drawn

GATE 2010 · MCQ · 2 marksQ29 · page 438 of the book

Consider the following schedule for transactions T1, T2
and T3:

Which one of the schedules below is the correct
serialization of the above?
T1
T2
T3
Read(X)

Read (Y)

Read (Y)

Write (Y)

Write (X)

Write (X)

Read (X)

Write (X)

(a)T1 → T3 → T2
(b)T2 → T1 → T3
(c)T2 → T3 → T1
(d)T3 → T1 → T2

GATE 2009 · MCQQ30 · page 438 of the book

Consider two transactions T1 and T2, and four schedules S1,
S2, S3, S4 of T1 and T2 as given below:

T1 : R1[x] W1[x] W1[y]

T2 : R2[x] R2[y] W2[y]

S1 : R1[x] R2[x] R2[y] W1[x] W1[y] W2[y]
S2 : R1[x] R2[x] R2[y] W1[x] W2[y] W1[y]
 S3 : R1[x] W1[x] R2[x] W1[y] R2[y] W2[y]
 S4 : R2[x] R2[y] R1[x] W1[x] W1[y] W2[y]

Which of the above schedules are conflict-serializable?

(a)S1 and S2
(b)S2 and S3
(c)S3 only
(d)S4 only

GATE 2008 · MCQQ31 · page 438 of the book

Consider the following three schedules of transactions T1,
T2 and T3.
(Notations: In the following, NYO represents the action Y
(R for read, W for write) performed by transaction N on
object O.)

S1:
2RA 2WA 3RC 2WB 3WA 3WC
1RA 1RB 1WA 1WB

S2:
3RC 2RA 2WA 2WB 3WA 1RA
1RB 1WA 1WB 3WC

S3:
2RA 3RC 3WA 2WA 2WB 3WC
1RA 1RB 1WA 1WB

Which of the following statements is TRUE?

(a)S1, S2 and S3 are all conflict equivalent to each other
(b)No two of S1, S2 and S3 are conflict equivalent to each other
(c)S2 is conflict equivalent to S3, but not to S1
(d)S1 is conflict equivalent to S2, but not to S3

GATE 2007 · MCQQ32 · page 438 of the book

Consider
the
following
schedules
involving
two
transactions. Which one of the following statements is
TRUE?

S1 : r1(X); r1(Y); r2(X); r2(Y); w2(Y); w1(X)

S2 : r1(X); r2(X); r2(Y); w2(Y); r1(Y); w1(X)

(a)Both S1 and S2 are conflict serializable.
(b)S1 is conflict serializable and S2 is not conflict serializable.
(c)S1 is not conflict serializable and S2 is conflict serializable.
(d)Both S1 and S2 are not conflict serializable. DATABASE MANAGEMENT SYSTEM

Self-check

Question 1

Is $r_1(X)\ r_2(X)\ w_2(X)\ w_1(X)$ conflict serializable?

Show answer

Conflicts: $r_1(X)$ before $w_2(X)$ gives $T_1 \to T_2$ ; $r_2(X)$ before $w_1(X)$ gives $T_2 \to T_1$ ; $w_2(X)$ before $w_1(X)$ gives $T_2 \to T_1$ . Cycle: no.

Question 2

How many serial schedules exist for $4$ transactions?

Show answer

$4! = 24$ .

Question 3

Why is every conflict serializable schedule view serializable but not conversely?

Show answer

Swapping non-conflicting operations preserves reads-from and the final writes, so conflict equivalence implies view equivalence. The converse fails when blind writes are overwritten, as in $r_1(A)\ w_2(A)\ w_1(A)\ w_3(A)$ .

Revision card

One-screen revision

Serial = no interleaving; serializable = equivalent to a serial schedule.
Conflict = different transactions, same item, one write. Precedence graph acyclic $\iff$ conflict serializable.
View: same reads-from and final writes; blind writes make the difference.
Count: $(\sum k_i)!/\prod k_i!$ schedules, $n!$ serial.

References

·Silberschatz, Korth, Sudarshan, Database System Concepts (7th edition), Chapter 17, Section 17.5 (Serializability)
·Elmasri, Navathe, Fundamentals of Database Systems (7th edition), Chapter 20, Section 20.5 (Characterizing schedules based on serializability)

Verification

scripts/enum-checks/db_txn_check.py on 4000 random schedules of 2 or 3 transactions: (1) the precedence graph test agrees with a second algorithm that searches for a serial schedule reachable by swapping adjacent non-conflicting operations, and the set of reachable serial orders equals the set of topological orders of the graph; (2) the definition of view serializability agrees with SYMBOLIC EXECUTION (reads return terms, writes store terms over what the transaction has read), which is the semantic meaning of view equivalence; (3) every conflict serializable schedule is view serializable and schedules that are view but not conflict serializable exist (the blind-write example); the counts in the table are enumerations of all interleavings. DEFINITION CHOICE found by the checks: view equivalence must compare the reads-from relation between WRITE OPERATIONS, not between transactions - for transactions that write the same item twice the transaction-level definition calls two schedules equivalent although a read sees a different value. Textbooks usually state it per transaction and avoid the case; the pages state the operation-level version. QUOTED, not proved here: that testing view serializability is NP-complete (Papadimitriou), the statement that a view serializable schedule that is not conflict serializable contains a blind write was checked on the random schedules but is not proved here. Textbook chapter references are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and re-derived against the textbook definitions and the sample database. No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Log-based recovery and checkpoints

Recoverable, cascadeless and strict schedules