Serializability in DBMS Theory - Step-by-Step Execution

Concept Flow - Serializability

Start Transactions

↓

Execute Operations

↓

Check Graph

↓

No Cycles

↓

Schedule is

↓

Serializable

↓

End

Transactions run operations, then the system checks the conflict graph for cycles. If no cycles, the schedule is serializable, meaning it behaves like transactions ran one after another.

Execution Sample

DBMS Theory

T1: Read(A)
T2: Write(A)
T1: Write(B)
T2: Read(B)

Two transactions perform read and write operations on data items A and B in an interleaved manner.

Analysis Table

Step	Transaction	Operation	Data Item	Conflict Check	Conflict Result	Serializable?
1	T1	Read	A	No previous conflicting operation	No	Yes
2	T2	Write	A	Conflicts with T1 Read(A)?	Yes (Read-Write conflict)	Yes
3	T1	Write	B	No previous conflicting operation	No	Yes
4	T2	Read	B	Conflicts with T1 Write(B)?	Yes (Write-Read conflict)	Yes
5	Conflict Graph	Add edge T1->T2	Due to Write(B) then Read(B)	Cycle? No	Yes	Yes
6	Final	No cycles in conflict graph	-	-	Schedule is Serializable	Yes

💡 No cycles found in conflict graph, so schedule is serializable

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
Conflict Graph Edges	None	None	None	None	Edge T1->T2 added	No cycles	No cycles

Key Insights - 2 Insights

Why do we check for conflicts between operations?

Because conflicts indicate operations that cannot be swapped without changing the result, which affects serializability. See execution_table steps 4 and 5 where conflicts lead to edges in the graph.

What does it mean if the conflict graph has a cycle?

A cycle means the schedule cannot be rearranged to a serial order without changing results, so it is not serializable. Our example has no cycles (step 6), so it is serializable.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what type of conflict is detected?

A Write-Read conflict

B Read-Write conflict

C Write-Write conflict

D No conflict

💡 Hint

Check the 'Conflict Result' column at step 4 in execution_table

At which step is the edge added to the conflict graph?

A Step 3

B Step 5

C Step 4

D Step 6

💡 Hint

Look at the 'Conflict Graph' row in execution_table where edges are added

If a cycle was found in the conflict graph, what would be the serializability result?

A Schedule is partially serializable

B Schedule is serializable

C Schedule is not serializable

D Schedule is always serializable

💡 Hint

Refer to key_moments about cycles in conflict graph and serializability

Concept Snapshot

Serializability ensures concurrent transactions produce results as if run one after another.
Check conflicts between operations (read/write) on same data.
Build conflict graph with edges for conflicting operations.
If graph has no cycles, schedule is serializable.
This guarantees consistency in databases.

Full Transcript

Serializability is a concept in database management that ensures when multiple transactions run at the same time, the final result is the same as if the transactions ran one by one in some order. We start transactions and execute their operations. Then, we check for conflicts between operations on the same data. Conflicts happen when one transaction writes data that another reads or writes. We build a conflict graph with edges showing which transaction must come before another. If this graph has no cycles, the schedule is serializable, meaning it is safe and consistent. If there is a cycle, the schedule is not serializable and may cause inconsistent data. This process helps databases keep data correct even with many users working at once.