Conflict Serializability: Detailed Explanation with Example

Question:

Consider the following schedule:

    S₁: R₁(A); R₁(C); R₂(B); W₂(B); R₃(B); R₁(A); R₃(C); W₃(C); W₁(A)
    S₂: R₂(A); R₁(C); R₂(B); R₃(B); W₂(B); R₁(A); R₃(C); W₃(C); W₁(A)

Which of the above schedules is conflict serializable?

• (a) S₁ only
• (b) S₂ only
• (c) Both S₁ and S₂
• (d) Neither S₁ nor S₂

Solution:

Correct Answer: Option (a)

Explanation:

Schedule S₁:

The precedence graph for schedule S₁ is constructed as follows:

• Transaction T₁ performs R(A), R(C), and W(A).
• Transaction T₂ performs R(B) and W(B).
• Transaction T₃ performs R(B), R(C), and W(C).

The conflict relationships are identified, and the precedence graph shows the following dependencies:

• T₁ → T₃
• T₂ → T₃

Since the precedence graph is acyclic, schedule S₁ is conflict serializable.

Schedule S₂:

The precedence graph for schedule S₂ is constructed as follows:

• Transaction T₁ performs R(A), R(C), and W(A).
• Transaction T₂ performs R(A), R(B), and W(B).
• Transaction T₃ performs R(B), R(C), and W(C).

The conflict relationships are identified, and the precedence graph shows the following dependencies:

• T₁ → T₃
• T₂ → T₃
• T₃ → T₂

Since the precedence graph contains a cycle, schedule S₂ is not conflict serializable.

Conclusion:

Only schedule S₁ is conflict serializable, making the correct answer Option (a).

Conflict Serializability: Minimum Moves for Schedule S

Question:

Consider the following schedule:

    S: r₂(A), r₁(B), w₂(A), r₂(B), r₃(A), w₁(B), w₃(A), w₂(B)

How many minimum numbers of moves (where a move consists of changing the position of one of the operations) are required to convert S into a conflict serializable schedule?

• (a) 1
• (b) 2
• (c) 3
• (d) 4

Solution:

Correct Answer: Option (a)

Explanation:

Step 1: Constructing the Precedence Graph

Based on the schedule S, the precedence graph is constructed. The following dependencies are identified:

• T₁ → T₂: Due to conflict on data item B between r₁(B) and w₂(B).
• T₂ → T₃: Due to conflict on data item A between w₂(A) and r₃(A).
• T₃ → T₁: Due to conflict on data item B between w₃(A) and w₁(B).

The precedence graph is as follows:

Step 2: Analyzing the Cycle

The precedence graph contains a cycle: T₁ → T₂ → T₃ → T₁. This cycle indicates that the schedule is not conflict serializable in its current form.

Step 3: Resolving the Cycle

To resolve the cycle, the operation w₁(B) is shifted after r₁(B). The new schedule becomes:

    S': r₂(A), r₁(B), w₂(A), r₂(B), r₃(A), r₁(B), w₃(A), w₂(B)

In this modified schedule, the precedence graph becomes:

Step 4: Verifying Serializability

The new precedence graph is acyclic. Hence, the schedule S’ is conflict serializable.

Step 5: Minimum Moves

Only one move (shifting w₁(B) after r₁(B)) was required to make the schedule serializable. Therefore, the correct answer is Option (a).

Conclusion:

With one minimum move, the schedule S can be converted into a conflict serializable schedule.

Conflict Equal and Recoverable Schedules in DBMS

Question 3:

Consider two schedules S₁ and S₂ with the same set of transactions, and the precedence graph of S₁ is the same as the precedence graph of S₂. Which of the following statements is true?

• (a) Both S₁ and S₂ are conflict equal and conflict serializable schedules
• (b) Both S₁ and S₂ are conflict equal but may not conflict serializable schedules
• (c) Both S₁ and S₂ are conflict equal but may not equal schedules
• (d) Both S₁ and S₂ are conflict equal but may not view equivalent

Solution:

Correct Answer: Option (b)

Explanation:

Both S₁ and S₂ are conflict equal but may not be conflict serializable schedules. Conflict equivalence means that both schedules generate the same precedence graph. However, conflict serializability depends on whether the precedence graph is acyclic.

If either S₁ or S₂ is a serial schedule, then S₁ and S₂ become conflict serializable schedules. Otherwise, they are not conflict serializable.

Question 4:

Which of the following schedules are recoverable?

    S₁: r₁(x), r₂(z), r₁(z), r₃(x), r₃(y), w₁(x), C₁, w₃(y), C₃, r₂(y), w₂(y), w₂(z), C₂
    S₂: r₁(x), r₂(z), r₁(z), r₃(x), r₃(y), w₁(x), w₃(y), r₂(y), w₂(z), w₂(y), C₁, C₂, C₃
    S₃: r₁(x), r₂(z), r₃(x), r₁(z), r₂(y), r₃(y), w₁(x), C₁, w₂(z), w₃(y), w₂(y), C₃, C₂

• (a) Only S₁
• (b) Only S₁, S₃
• (c) Only S₂, S₃
• (d) All S₁, S₂, S₃

Solution:

Correct Answer: Option (b)

Explanation:

A schedule is recoverable if a transaction Tᵢ reading a value written by Tⱼ commits only after Tⱼ commits.

• S₁ is recoverable because all read-write dependencies ensure proper commit order.
• S₂ is not recoverable because w₃(y) occurs before r₂(y), but C₂ appears before C₃.
• S₃ is recoverable because the commit order aligns with read-write dependencies.

Hence, the recoverable schedules are S₁ and S₃.

Serializability and Conflict Equivalence in DBMS

Question 5:

For the given schedule, which of the following statements is true?

    S: R₄(A), R₂(A), R₃(A), W₁(B), W₂(C), R₄(B), W₂(B)

• (a) The schedule cannot be serialized
• (b) The schedule is equivalent to T₃, T₄, T₁, T₂
• (c) The schedule is equivalent to T₁, T₄, T₂, T₃
• (d) The schedule is equivalent to T₂, T₃, T₁, T₄

Solution:

Correct Answer: Option (c)

Explanation:

The precedence graph for the given schedule is constructed as follows:

• T₁ → T₂: Due to conflict on data item B.
• T₄ → T₁: Due to conflict on data item A.
• T₁ → T₃: Due to conflict on data item A.

The precedence graph is acyclic, and the serial order equivalent to the schedule is T₁ → T₄ → T₂ → T₃.

Question 6:

Consider the following schedules:

    S₁: R₁(A), W₁(A), R₂(B), R₁(B), W₁(B), W₂(A), R₂(C), R₁(C)
    S₂: R₂(B), W₂(A), R₁(A), W₁(A), R₁(B), W₁(B), R₂(C), R₁(C)
    S₃: R₁(A), W₁(A), R₂(B), W₂(A), R₁(B), W₁(B), R₁(C), R₂(C)
    S₄: R₂(B), R₁(A), W₂(A), W₁(A), R₁(B), W₁(B), R₂(C), R₁(C)

Which of the above schedules are conflict serializable?

• (a) S₁ and S₂ only
• (b) S₂ only
• (c) S₁ only
• (d) None of these

Solution:

Correct Answer: Option (b)

Explanation:

Schedule S₁:

The precedence graph contains a cycle (T₁ → T₂ → T₁). Hence, S₁ is not conflict serializable.

Schedule S₂:

The precedence graph is acyclic. Hence, S₂ is conflict serializable and equivalent to the order T₂ → T₁.

Schedule S₃:

The precedence graph contains a cycle (T₁ → T₂ → T₁). Hence, S₃ is not conflict serializable.

Schedule S₄:

The precedence graph contains a cycle (T₁ → T₂ → T₁). Hence, S₄ is not conflict serializable.

Conclusion:

Only schedule S₂ is conflict serializable.

Conflict Serializability and 2-Phase Locking in DBMS

Question 7:

Which of the following is true with regards to the correct answer for the above question?

• (a) S₁ is conflict serializable to T₁, T₂
• (b) S₂ is conflict serializable to T₂, T₁
• (c) Both (A) and (B)
• (d) None of these

Solution:

Correct Answer: Option (b)

Explanation:

Schedule S₁:

The precedence graph for S₁ contains a cycle, indicating that S₁ is not conflict serializable.

Schedule S₂:

The precedence graph for S₂ is acyclic, indicating that S₂ is conflict serializable with the order T₂ → T₁.

Question 8:

Which among the following 2-phase locking protocols is deadlock free?

• (a) Basic 2PL
• (b) Strict 2PL
• (c) Rigorous 2PL
• (d) Conservative 2PL

Solution:

Correct Answer: Option (d)

Explanation:

Conservative 2-Phase Locking (2PL) is deadlock-free because it requires all locks to be acquired before the transaction begins, thus avoiding circular wait conditions.

Key Characteristics of 2PL Variants:

• Basic 2PL: Allows deadlock as it acquires locks dynamically.
• Strict 2PL: Prevents cascading aborts but does not eliminate deadlocks.
• Rigorous 2PL: Similar to Strict 2PL but holds all locks until the transaction commits.
• Conservative 2PL: Deadlock-free but requires pre-acquisition of locks.

Example Transaction Schedules:

The following transaction schedules demonstrate the working of different 2PL protocols:

    Schedule 1: T₂: Rₓ, T₂: Rᵧ, T₁: Wₓ, T₃: Wᵧ, T₃: Wz, T₁: Rz, T₂: Wᵧ
    Schedule 2: T₂: Rₓ, T₂: Wᵧ, T₃: Rᵧ, T₃: Wₓ, T₃: Wz, T₁: Rz, T₁: Rᵧ, T₂: Wᵧ

In Conservative 2PL, locks are acquired before the transactions start, preventing deadlocks entirely.

Conflict Serializability in DBMS

Question 9:

Which of the given schedules is conflict serializable?

• (a) Schedule 1
• (b) Schedule 2
• (c) Schedule 3
• (d) Schedule 4

Solution:

Correct Answer: Option (d)

Explanation:

Schedule 1:

The precedence graph contains a cycle involving transactions T₁, T₂, and T₃. Thus, Schedule 1 is not conflict serializable.

Schedule 2:

The precedence graph contains a cycle involving transactions T₁, T₂, and T₃. Thus, Schedule 2 is not conflict serializable.

Schedule 3:

The precedence graph contains a cycle involving transactions T₁, T₂, and T₃. Thus, Schedule 3 is not conflict serializable.

Schedule 4:

The precedence graph does not contain any cycles. Thus, Schedule 4 is conflict serializable, and the equivalent serial schedule is T₃ → T₁ → T₂.

Conclusion:

Only Schedule 4 is conflict serializable, with the equivalent serial schedule being T₃ → T₁ → T₂.

Conflict and View Serializability in DBMS

Question 10:

For the conflict serializable schedule found in the previous question, the equivalent serial schedule possible:

• (a) T₃ → T₁ → T₂
• (b) T₂ → T₁ → T₃
• (c) T₃ → T₂ → T₁
• (d) None of these

Solution:

Correct Answer: Option (a)

Explanation:

The precedence graph for Schedule 4 (as identified in Question 9) does not contain any cycles. The serial schedule equivalent is determined from the topological order of the precedence graph. The order is T₃ → T₁ → T₂.

Question 11:

Which of the following is true about the given schedule S?

    T₁: R(A) → A = A + 100 → W(A) → R(B) → B = B - 100 → W(B)
    T₂: R(A) → A = A * 2 → W(A) → R(B) → B = B / 2 → W(B)

• (a) It is conflict serializable
• (b) It is view serializable but not conflict serializable
• (c) It is conflict serializable but not view serializable
• (d) It is not serializable

Solution:

Correct Answer: Option (d)

Explanation:

The given schedule involves overlapping operations on data items A and B between T₁ and T₂. A precedence graph would reveal cycles, indicating that it is not conflict serializable.

Additionally, the schedule is not view serializable because the final write operations on data items do not preserve the same result as any serial schedule. Therefore, the schedule is not serializable.

Conclusion:

The schedule S is neither conflict serializable nor view serializable, making it non-serializable.

Irrecoverable Schedules in DBMS

Question 12:

Which among the following schedules is an irrecoverable schedule?

        T₁: R(A), W(A), Abort
        T₂: R(A), W(A), Commit

        T₁: R(A), W(A), Abort
        T₂: R(A), W(A), Abort

        T₁: R(A), W(A), Abort
        T₂: R(A), W(A), Commit

        T₁: R(A), W(A), Abort
        T₂: R(A), W(A), Commit

Solution:

Correct Answer: Option (d)

Explanation:

An irrecoverable schedule occurs when a transaction reads a value from another uncommitted transaction (a dirty read) and commits before the transaction from which it read the value aborts. In this case, the system cannot ensure the correctness of the committed transaction, making it irrecoverable.

In Option (d):

• Transaction T₂ performs a dirty read on data item A written by T₁.
• T₂ commits before T₁, but T₁ aborts, making the committed data of T₂ invalid.

This makes the schedule irrecoverable.

Other Options:

• (a): Transaction T₁ aborts, and T₂ commits after reading the data. This does not lead to an irrecoverable schedule.
• (b): Both transactions abort, so no irrecoverability occurs.
• (c): Although T₁ aborts and T₂ commits, no dirty read occurs.

Conclusion:

Option (d) is the irrecoverable schedule because T₂ commits based on dirty data from T₁, which later aborts.

Irrecoverable and Cascadeless Schedules in DBMS

Question 13:

Suppose a schedule with 2 transactions T₁ and T₂:

    T₁: Read(A), Write(A), Read(A), Abort
    T₂: Read(A), Commit

The above schedule is:

• (a) Cascadeless schedule
• (b) Recoverable schedule
• (c) Irrecoverable schedule
• (d) None of these

Solution:

Correct Answer: Option (c)

Explanation:

In this schedule, T₂ reads a value written by T₁, and T₂ commits before T₁ aborts. As the value of A read by T₂ becomes invalid after T₁ aborts, the schedule is irrecoverable.

Question 14:

There are 2 transactions, T₁ with 2 instructions and T₂ with 5 instructions. Find the number of serial and concurrent schedules respectively.

• (a) 2, 2
• (b) 21, 21
• (c) 2, 20
• (d) 21, 2

Solution:

Correct Answer: Option (c)

Explanation:

• The number of serial schedules = Number of transactions = 2.
• The number of concurrent schedules is calculated as:

              Total schedules = (5 + 2)! / 5! = 21
              Concurrent schedules = Total schedules - Serial schedules = 21 - 2 = 20
  

Question 15:

Which of the following statements are true about recoverable and cascadeless schedules?

    (P) All cascadeless schedules are also recoverable
    (Q) All recoverable schedules are also cascadeless
    (R) All strict schedules are cascadeless and recoverable
    (S) All cascadeless and recoverable schedules are strict schedules

• (a) P and R are correct
• (b) P and S are correct
• (c) P, R, and S are correct
• (d) P, Q, and S are correct

Solution:

Correct Answer: Option (a)

Explanation:

• (P): True, because cascadeless schedules avoid cascading aborts and are always recoverable.
• (R): True, because strict schedules ensure recoverability and avoid cascading aborts, making them cascadeless.
• (Q): False, as not all recoverable schedules are cascadeless (cascadeless schedules are a subset of recoverable schedules).
• (S): False, because not all cascadeless and recoverable schedules are strict schedules (strict schedules are a subset of cascadeless schedules).