Conflict serializability in DBMS Theory - Mini Project: Build & Apply

Understanding Conflict Serializability in DBMS

📖 Scenario: You are learning how database systems ensure that multiple transactions happen safely without interfering with each other. This is important to keep data correct and consistent.

🎯 Goal: Build a simple example schedule of transactions and check if it is conflict serializable by identifying conflicting operations and creating a precedence graph.

📋 What You'll Learn

Create a list of transactions with their operations in order

Define a helper variable to hold conflicting operation pairs

Write logic to identify conflicts between operations

Construct a precedence graph to check conflict serializability

💡 Why This Matters

🌍 Real World

Database systems use conflict serializability to ensure that concurrent transactions do not cause data errors or inconsistencies.

💼 Career

Understanding conflict serializability is important for database administrators and developers to design safe transaction schedules and troubleshoot concurrency issues.

1

Create the transaction schedule

Create a list called schedule that contains these operations in order: 'T1: R(A)', 'T2: W(A)', 'T1: W(B)', 'T2: R(B)'.

DBMS Theory

# Create the transaction schedule list
# Your code here

Hint

Think of schedule as a list of strings describing each operation in order.

2

Define conflicting operation pairs

Create a list called conflicts containing tuples of operation types that conflict: ('R', 'W'), ('W', 'R'), and ('W', 'W').

DBMS Theory

schedule = ['T1: R(A)', 'T2: W(A)', 'T1: W(B)', 'T2: R(B)']
# Define conflicting operation pairs
# Your code here

Hint

Conflicts happen when one operation reads and the other writes, or both write the same data.

3

Identify conflicts and build edges

Write code to create a list called edges that stores tuples of transaction pairs where conflicts occur. Use a nested loop to compare each pair of operations in schedule. Extract transaction IDs and operation types, and add an edge (from_tx, to_tx) if the operations conflict on the same data item and transactions differ.

DBMS Theory

schedule = ['T1: R(A)', 'T2: W(A)', 'T1: W(B)', 'T2: R(B)']
conflicts = [('R', 'W'), ('W', 'R'), ('W', 'W')]
# Identify conflicts and build edges
# Your code here

Hint

Compare each operation with later ones to find conflicts and record which transaction must come before the other.

4

Complete the precedence graph

Create a dictionary called precedence_graph where keys are transaction IDs and values are lists of transactions that must come after them. Use the edges list to fill this dictionary. Initialize keys for all transactions in schedule.

DBMS Theory

schedule = ['T1: R(A)', 'T2: W(A)', 'T1: W(B)', 'T2: R(B)']
conflicts = [('R', 'W'), ('W', 'R'), ('W', 'W')]
edges = []
for i in range(len(schedule)):
    for j in range(i+1, len(schedule)):
        t1, op1 = schedule[i].split(': ')
        t2, op2 = schedule[j].split(': ')
        op_type1, data1 = op1[0], op1[2]
        op_type2, data2 = op2[0], op2[2]
        if t1 != t2 and data1 == data2 and (op_type1, op_type2) in conflicts:
            edges.append((t1, t2))
# Build the precedence graph dictionary
# Your code here

Hint

Initialize the graph with all transactions, then add edges from the conflict pairs.

Practice

1. What does conflict serializability ensure in database transactions?

easy

A. Transactions produce the same result as if they were executed one after another

B. Transactions run faster by skipping some operations

C. Transactions always lock all data to avoid conflicts

D. Transactions are executed only by one user at a time

Solution

1. Step 1: Understand the goal of conflict serializability

   It aims to keep the database consistent by ensuring concurrent transactions behave like they ran sequentially.

2. Step 2: Compare options with the definition

   Only Transactions produce the same result as if they were executed one after another correctly states that the final result is as if transactions ran one after another.

3. Final Answer:

   Transactions produce the same result as if they were executed one after another -> Option A

4. Quick Check:

   Conflict serializability = Sequential result [OK]

Hint: Think: final result matches some order of transactions [OK]

Common Mistakes:

• Confusing conflict serializability with locking all data
• Thinking it speeds up transactions by skipping steps
• Assuming only one user can run transactions at a time

2. Which of the following is a correct way to check conflict serializability?

easy

A. Build a precedence graph and check for cycles

B. Count the number of transactions running simultaneously

C. Verify if all transactions use the same isolation level

D. Check if transactions use locks on all data items

Solution

1. Step 1: Recall the method to test conflict serializability

   It involves creating a precedence graph where nodes are transactions and edges show conflicts.

2. Step 2: Understand the graph's role

   If the graph has no cycles, the schedule is conflict serializable.

3. Final Answer:

   Build a precedence graph and check for cycles -> Option A

4. Quick Check:

   Precedence graph + no cycles = conflict serializable [OK]

Hint: Use graph cycles to detect conflicts fast [OK]

Common Mistakes:

• Thinking counting transactions shows serializability
• Confusing isolation levels with conflict serializability
• Assuming locking all data guarantees serializability

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

medium

A. None of the above

B. Read(A) by T1, Read(A) by T2, Write(A) by T1, Write(A) by T2

C. Read(A) by T2, Read(A) by T1, Write(A) by T2, Write(A) by T1

D. T1 followed by T2

Solution

1. Step 1: Analyze schedules for conflicts

   Schedules where one transaction runs fully before the other have no conflicts and are serializable.

2. Step 2: Check interleaved schedule

   Interleaving reads and writes on the same data causes conflicts and cycles in the precedence graph.

3. Final Answer:

   T1 followed by T2 -> Option D

4. Quick Check:

   Non-interleaved = serializable [OK]

Hint: Serial schedules are always conflict serializable [OK]

Common Mistakes:

• Assuming interleaved schedules are always serializable
• Ignoring write-write conflicts on same data
• Thinking any order of reads is conflict free

4. Given a schedule with transactions T1 and T2:
T1: Read(X), Write(X)
T2: Read(X), Write(X)
The schedule is:
Read(X) by T1, Read(X) by T2, Write(X) by T2, Write(X) by T1.
What is the problem with this schedule?

medium

A. It is a serial schedule with no conflicts

B. It causes a deadlock between T1 and T2

C. It is not conflict serializable due to a cycle in the precedence graph

D. It is conflict serializable because reads happen before writes

Solution

1. Step 1: Build the precedence graph

   T1 reads X before T2 writes X, so edge T1 -> T2; T2 writes X before T1 writes X, so edge T2 -> T1.

2. Step 2: Detect cycle in graph

   Edges T1 -> T2 and T2 -> T1 form a cycle, meaning schedule is not conflict serializable.

3. Final Answer:

   It is not conflict serializable due to a cycle in the precedence graph -> Option C

4. Quick Check:

   Cycle in graph = not conflict serializable [OK]

Hint: Look for cycles in transaction dependency graph [OK]

Common Mistakes:

• Confusing deadlock with conflict serializability
• Assuming reads before writes always mean serializable
• Thinking schedule is serial when it is interleaved

5. You have three transactions:
T1: Read(A), Write(A)
T2: Read(B), Write(B)
T3: Read(A), Write(B)
If the schedule is:
Read(A) by T1, Read(B) by T2, Read(A) by T3, Write(A) by T1, Write(B) by T3, Write(B) by T2,
Is this schedule conflict serializable? If yes, what is a possible serial order?

hard

A. Yes, serial order: T2 -> T1 -> T3

B. No, schedule is not conflict serializable due to cycles

C. Yes, serial order: T1 -> T3 -> T2

D. Yes, serial order: T3 -> T1 -> T2

Solution

1. Step 1: Identify conflicts and build precedence graph

   T3 reads A before T1 writes A -> T3 -> T1.
   T2 reads B before T3 writes B -> T2 -> T3.
   T3 writes B before T2 writes B -> T3 -> T2.

2. Step 2: Check for cycles and find serial order

   Cycle T2 -> T3 -> T2 exists, so the schedule is not conflict serializable.

3. Final Answer:

   No, schedule is not conflict serializable due to cycles -> Option B

4. Quick Check:

   Precedence graph has cycle = not serializable [OK]

Hint: Build graph, check for cycles: cycle = not serializable [OK]

Common Mistakes:

• Missing edges like T2 read B before T3 write B
• Missing edges in the precedence graph
• Confusing read-write order causing edges