Conflict serializability in DBMS Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is conflict serializability in database systems?

Conflict serializability is a property of a schedule (sequence of operations) where the schedule can be transformed into a serial schedule by swapping non-conflicting operations. It ensures that concurrent transactions produce the same result as some serial execution.

beginner

What does it mean for two operations to be conflicting?

Two operations conflict if they belong to different transactions, access the same data item, and at least one of them is a write operation.

intermediate

Why is conflict serializability important in databases?

It ensures consistency by allowing concurrent transactions to execute without interfering in a way that causes incorrect results, making the schedule equivalent to some serial order.

intermediate

How can you check if a schedule is conflict serializable?

By constructing a precedence graph (or serialization graph) where nodes are transactions and edges represent conflicts. If the graph has no cycles, the schedule is conflict serializable.

intermediate

What is a precedence graph in the context of conflict serializability?

A directed graph where each node represents a transaction and edges represent conflicting operations that enforce order. It helps detect cycles to determine serializability.

Which of the following pairs of operations conflict?

A Write from T1 and Read from T1 on different data items

B Read from T1 and Write from T2 on the same data item

C Write from T1 and Write from T1 on the same data item

D Read from T1 and Read from T2 on the same data item

Operations conflict if they are from different transactions, access the same data item, and at least one is a write. Option B fits this.

What does a cycle in a precedence graph indicate?

A The schedule is conflict serializable

B The schedule is serial

C The transactions are independent

D The schedule is not conflict serializable

A cycle means there is no way to order transactions serially without conflicts, so the schedule is not conflict serializable.

Conflict serializability ensures that concurrent transactions produce results equivalent to:

A A random schedule

B A schedule with deadlocks

C A serial schedule

D A schedule with lost updates

Conflict serializability guarantees equivalence to some serial schedule, preserving correctness.

Which operation pair does NOT cause a conflict?

A Read T1 and Read T2 on same data

B Write T1 and Read T2 on same data

C Write T1 and Write T2 on same data

D Write T1 and Write T2 on different data

Two reads from different transactions on the same data do not conflict.

What is the first step to check conflict serializability?

A Build a precedence graph

B Run transactions serially

C Check for deadlocks

D Lock all data items

Building a precedence graph helps identify conflicts and cycles to determine serializability.

Explain conflict serializability and why it matters in managing database transactions.

Think about how transactions run together without causing errors.

Describe how to use a precedence graph to determine if a schedule is conflict serializable.

Imagine drawing arrows between transactions based on their conflicting operations.