DBMS UNIT 4
What is Conflict Serializability?
When multiple transactions run at the same time in a database, their operations (like reading
or writing data) can overlap. Conflict serializability ensures that even if operations are
mixed (interleaved), the result will be the same as if the transactions ran one by one (serially).
A schedule (the order of operations) is conflict-serializable if we can rearrange the
operations (without breaking any rules) into a serial schedule by swapping non-conflicting
operations.
What Are Conflicting Operations?
Two operations conflict if:
1. They happen on the same data item (e.g., A).
2. They belong to different transactions.
3. At least one operation is a write (modifies data).
Example: Is This Schedule Conflict-Serializable?
Let’s say there are two transactions:
Transaction 1 (T1): Reads and Writes on A.
Transaction 2 (T2): Reads and Writes on A.
Here’s a schedule SS:
T1: Read(A)
T2: Read(A)
T1: Write(A)
T2: Write(A)
To check if this is conflict-serializable:
1. Draw a graph where each transaction is a node.
2. Add arrows (dependencies) for conflicts:
o T1T1's Write(A) happens before T2T2's Read(A): Add arrow T1→T2T1 →
T2.
o T2T2's Write(A) happens before T1T1's Read(A): Add arrow T2→T1T2 →
T1.
3. If the graph has a cycle (like T1→T2→T1T1 → T2 → T1), the schedule is not
conflict-serializable.
Why Focus on Conflict Serializability Instead of View Serializability?
1. Easier to Check:
o Conflict serializability uses a graph to check for cycles, which is simple and
fast.
o View serializability requires more detailed checks and is harder to implement.
2. Matches Real Systems:
o Most databases use techniques like locks or timestamps, which naturally
produce conflict-serializable schedules.
o View serializability includes more cases, but they rarely happen in real life.
3. Practical and Reliable:
o Conflict serializability is good enough to ensure correctness and is much
easier for database systems to use.
So, we emphasize conflict serializability because it’s simpler, practical, and works well with
how databases are built.
Explain the two-phase lock protocol for concurrency control. Also
explain its two versions: strict two-phase lock protocol and rigorous
two-phase lock protocol.
What is the Two-Phase Locking (2PL) Protocol?
The two-phase locking (2PL) protocol is a method used in databases to ensure that concurrent
transactions maintain consistency and avoid conflicts. It works by controlling how
transactions acquire and release locks on data.
How 2PL Works
Each transaction has two phases:
1. Growing Phase:
o The transaction can acquire locks (read or write) as needed.
o It cannot release any lock in this phase.
2. Shrinking Phase:
o Once the transaction releases its first lock, it cannot acquire any new locks.
o It can only release locks during this phase.
This ensures that no two conflicting transactions can access the same data item at the same
time.
Why Use 2PL?
By following this protocol, the schedule of transactions is guaranteed to be conflict-
serializable (equivalent to running transactions one after the other).
Versions of 2PL
1. Strict Two-Phase Locking Protocol
Definition:
o All exclusive (write) locks are held by the transaction until it finishes
(commits or aborts).
Behavior:
o Transactions release their write locks only after they are done, ensuring no
other transaction can read or write to the locked data until the transaction
completes.
Advantages:
o Prevents dirty reads (reading uncommitted data).
o Simple recovery from failures because no uncommitted changes are visible to
other transactions.
Example:
1. Transaction T1T1 writes to AA and locks it.
2. T1T1 completes and releases the lock.
3. Only after T1T1 finishes, T2T2 can access AA.
2. Rigorous Two-Phase Locking Protocol
Definition:
o All locks (both read and write) are held until the transaction finishes (commits
or aborts).
Behavior:
o Transactions do not release any locks until they are done, making it even
stricter than strict 2PL.
Advantages:
o Ensures a simpler and safer protocol for recovery.
o Prevents both dirty reads and unrepeatable reads (data changing mid-
transaction).
Example:
1. T1T1 reads and writes to AA, locking it.
2. T1T1 completes and releases all locks.
3. T2T2 can access AA only after T1T1 is fully done.
Comparison of Strict vs. Rigorous 2PL
Aspect Strict 2PL Rigorous 2PL
Only write locks are held until
Lock Release All locks (read and write) are held.
commit.
Concurrency Higher concurrency. Lower concurrency.
Complexity Moderate. Simpler for recovery.
Used where simplicity and safety are
Use Case Common in practical systems.
key.
Key Takeaways
Two-phase locking ensures that transactions are conflict-serializable.
Strict 2PL is commonly used because it balances concurrency and safety.
a) What is R-timestamp(Q) and W-timestamp(Q) Explain the necessary
condition used by time stamp ordering protocol to execute for a read /
write operation.
