Conflict serializability in DBMS Theory - Step-by-Step Execution

Concept Flow - Conflict serializability

Start with schedule of transactions

↓

Identify conflicting operations

↓

Build precedence graph

↓

Check for cycles in graph

The flow shows how to check if a schedule is conflict serializable by identifying conflicts, building a graph, and checking for cycles.

Execution Sample

DBMS Theory

T1: R(A) W(A)
T2: R(A) W(A)
Schedule: R1(A) R2(A) W1(A) W2(A)

This schedule shows two transactions reading and writing the same data item A in an interleaved way.

Analysis Table

Step	Operation	Conflict With	Precedence Graph Edge	Cycle Detected?
1	R1(A)	None	None	No
2	R2(A)	None	None	No
3	W1(A)	R2(A)	T2 -> T1	No
4	W2(A)	W1(A)	T1 -> T2	Yes

💡 Cycle detected between T1 and T2, so schedule is NOT conflict serializable

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4
Precedence Graph Edges	{}	{}	{}	{"T2->T1"}	{"T2->T1", "T1->T2"}
Cycle Detected	No	No	No	No	Yes

Key Insights - 2 Insights

Why does writing after reading cause a conflict?

Because writing changes data that was read, the order matters. In the table, step 3's W1(A) conflicts with step 2's R2(A), creating an edge T2->T1.

What does a cycle in the precedence graph mean?

A cycle means transactions depend on each other in a loop, so the schedule cannot be rearranged into a serial order without conflicts. See step 4 where cycle is detected.

Visual Quiz - 3 Questions

Look at the execution table, which step first adds an edge to the precedence graph?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Check the 'Precedence Graph Edge' column in the execution table rows.

At which step does the cycle appear in the graph?

A Step 2

B Step 4

C Step 3

D No cycle appears

💡 Hint

Look at the 'Cycle Detected?' column in the execution table.

If the last operation W2(A) was moved before W1(A), what would happen to the cycle?

A Cycle would disappear

B Cycle would remain

C New cycle would form

D Graph would have no edges

💡 Hint

Think about how changing operation order affects edges in the precedence graph.

Concept Snapshot

Conflict serializability checks if a schedule can be reordered into a serial one by:
- Identifying conflicting operations (read/write on same data by different transactions)
- Building a precedence graph with edges for conflicts
- Detecting cycles in the graph
No cycles mean the schedule is conflict serializable.

Full Transcript

Conflict serializability is a way to check if a schedule of database transactions can be rearranged without conflicts. We look at operations that conflict, like reads and writes on the same data by different transactions. We build a graph showing which transaction must come before another. If this graph has no cycles, the schedule is conflict serializable. If there is a cycle, it means transactions depend on each other in a loop, so the schedule cannot be safely reordered.