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.

Practice

1. What does serializability in a database ensure?

easy

A. Transactions appear to run one after another without overlap

B. All transactions run at the same time without any order

C. Data is deleted after each transaction

D. Only one transaction is allowed in the database

Solution

1. Step 1: Understand the meaning of serializability

   Serializability means the database behaves as if transactions are executed one by one, even if they run at the same time.

2. Step 2: Match the definition to the options

   Transactions appear to run one after another without overlap correctly states that transactions appear to run sequentially, which is the core idea of serializability.

3. Final Answer:

   Transactions appear to run one after another without overlap -> Option A

4. Quick Check:

   Serializability = Transactions run one by one [OK]

Hint: Serializability means no overlapping effects visible [OK]

Common Mistakes:

• Thinking transactions must run one at a time physically
• Confusing serializability with locking mechanisms
• Believing serializability deletes data
• Assuming only one transaction can exist

2. Which of the following schedules is not considered serializable?

easy

A. A schedule where transactions run one after another without overlap

B. A schedule where transactions are executed in a serial order

C. A schedule where transactions do not share any data

D. A schedule where transactions read and write the same data in conflicting order

Solution

1. Step 1: Identify what breaks serializability

   Conflicting operations like reading and writing the same data in overlapping order can cause non-serializable schedules.

2. Step 2: Analyze the options

   A schedule where transactions read and write the same data in conflicting order describes conflicting operations that break serializability. Options A, B, and C describe serial or conflict-free schedules.

3. Final Answer:

   A schedule where transactions read and write the same data in conflicting order -> Option D

4. Quick Check:

   Conflicting operations = Not serializable [OK]

Hint: Conflicting read/write means not serializable [OK]

Common Mistakes:

• Assuming all overlapping schedules are serializable
• Ignoring conflicts on shared data
• Thinking non-overlapping means non-serializable
• Confusing serial and serializable

3. Consider two transactions:
T1: Read(A), Write(A)
T2: Read(A), Write(A)
Which schedule is conflict serializable?

medium

A. T2 writes A first, then T1 reads and writes A

B. T1 and T2 read A simultaneously, then both write A simultaneously

C. T1 reads and writes A, then T2 reads and writes A

D. T1 reads A, T2 writes A, then T1 writes A

Solution

1. Step 1: Understand conflict serializability

   A schedule is conflict serializable if it can be rearranged to a serial order without conflicts.

2. Step 2: Analyze each schedule

   T1 reads and writes A, then T2 reads and writes A runs T1 fully before T2, so no conflicts. T1 and T2 read A simultaneously, then both write A simultaneously has simultaneous writes causing conflict. T2 writes A first, then T1 reads and writes A runs T2 before T1. T1 reads A, T2 writes A, then T1 writes A has overlapping writes causing conflict.

3. Final Answer:

   T1 reads and writes A, then T2 reads and writes A -> Option C

4. Quick Check:

   Serial order without conflicts = T1 reads and writes A, then T2 reads and writes A [OK]

Hint: Serial order with no overlapping writes is serializable [OK]

Common Mistakes:

• Thinking simultaneous writes are allowed
• Ignoring order of writes
• Confusing conflict serializability with view serializability
• Assuming any schedule with reads is serializable

4. Identify the error in this schedule:
T1: Read(X), Write(X)
T2: Write(X), Read(X)
Schedule order: T1 Read(X), T2 Write(X), T1 Write(X), T2 Read(X)
What is the problem?

medium

A. This schedule is not conflict serializable due to write-read conflict

B. This schedule is serializable because writes happen in order

C. No error, schedule is correct

D. The schedule has a deadlock

Solution

1. Step 1: Check for conflicts in the schedule

   T1 reads X, then T2 writes X before T1 writes X, causing a write-read conflict.

2. Step 2: Determine serializability

   Because of the conflicting order of operations, the schedule cannot be rearranged into a serial order without conflicts.

3. Final Answer:

   This schedule is not conflict serializable due to write-read conflict -> Option A

4. Quick Check:

   Write-read conflict breaks serializability [OK]

Hint: Write-read conflicts break serializability [OK]

Common Mistakes:

• Assuming writes always serialize correctly
• Ignoring read after write conflicts
• Confusing deadlock with serializability issues
• Thinking schedule order doesn't matter

5. You have three transactions:
T1: Read(A), Write(B)
T2: Write(A), Read(B)
T3: Read(B), Write(A)
Which schedule is conflict serializable?

hard

A. T1 -> T2 -> T3

B. T2 -> T3 -> T1

C. T3 -> T1 -> T2

D. T1 -> T3 -> T2

Solution

1. Step 1: Analyze conflicts between transactions

   T1 and T2 conflict on A and B; T2 and T3 conflict on A and B; T1 and T3 conflict on B and A.

2. Step 2: Check which order avoids cycles in conflict graph

   Order T2 -> T3 -> T1 avoids cycles, making the schedule conflict serializable.

3. Final Answer:

   T2 -> T3 -> T1 -> Option B

4. Quick Check:

   Conflict graph acyclic = T2 -> T3 -> T1 [OK]

Hint: Check conflict graph cycles to find serializable order [OK]

Common Mistakes:

• Ignoring conflicts between transactions
• Assuming any order is serializable
• Not checking for cycles in conflict graph
• Mixing read-write and write-write conflicts