Conflict serializability in DBMS Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Conflict Serializability

Which of the following best describes conflict serializability in database transactions?

A A schedule where transactions are executed one after another without overlapping.

B A schedule where all transactions are rolled back to maintain consistency.

C A schedule that allows transactions to execute in parallel without any restrictions.

D A schedule where non-conflicting operations can be swapped to produce a serial schedule.

💡 Hint

Think about how operations can be reordered without changing the final result.

Conflict serializability means that a schedule can be transformed into a serial schedule by swapping non-conflicting operations. This ensures the final database state is the same as if transactions ran one after another.

🔍 Analysis

intermediate

Detecting Conflict Serializability from a Schedule

Given the following schedule of two transactions T1 and T2:

T1: R(A), W(A), R(B), W(B)
T2: R(B), W(B), R(A), W(A)

Is this schedule conflict serializable?

A No, because the conflicting operations create a cycle in the precedence graph.

B Yes, because the schedule is already serial.

C Yes, because the operations on A and B do not conflict.

D No, because transactions are executed simultaneously.

💡 Hint

Try drawing the precedence graph to check for cycles.

The schedule has conflicting operations on A and B that form a cycle in the precedence graph, so it is not conflict serializable.

❓ Comparison

advanced

Conflict Serializability vs View Serializability

Which statement correctly compares conflict serializability and view serializability?

A All conflict serializable schedules are view serializable, but not all view serializable schedules are conflict serializable.

B All view serializable schedules are conflict serializable, but not all conflict serializable schedules are view serializable.

C Conflict serializability and view serializability are exactly the same concepts.

D Neither conflict serializability nor view serializability guarantees correctness of schedules.

💡 Hint

Think about which type of serializability is more general.

Conflict serializability is a stricter condition. Every conflict serializable schedule is view serializable, but some view serializable schedules are not conflict serializable.

❓ Reasoning

advanced

Effect of Conflicting Operations on Schedule Serializability

Consider two transactions T1 and T2 accessing data items X and Y. If T1 writes X before T2 reads X, and T2 writes Y before T1 reads Y, what does this imply about the schedule's conflict serializability?

A The schedule is conflict serializable because writes before reads do not cause conflicts.

B The schedule is not conflict serializable because these conflicting operations create a cycle in the precedence graph.

C The schedule is conflict serializable because the operations are on different data items.

D The schedule is not conflict serializable because reads always conflict with writes.

💡 Hint

Analyze the direction of conflicts and check for cycles.

Conflicting operations in opposite directions on different data items create a cycle in the precedence graph, making the schedule not conflict serializable.

🚀 Application

expert

Determining the Number of Conflict Serializable Schedules

Given two transactions T1 and T2, each with two operations: T1 performs R(A) then W(B), and T2 performs W(A) then R(B). How many possible schedules of these four operations are conflict serializable?

A 2

B 6

C 4

D 8

💡 Hint

List all possible interleavings and check which have no cycles in their precedence graphs.

Out of all possible schedules, only 4 maintain conflict serializability because others create cycles due to conflicting operations on A and B.