DBMS-M4

What is a transaction in DBMS? What are desirable (ACID) properties of a transaction? [1+4]

• A transaction is a logical unit of work that reads/updates database items.

• ACID:

– Atomicity: all-or-none execution.

– Consistency: takes DB from one consistent state to another.

– Isolation: intermediate results hidden from other transactions.

– Durability: committed changes persist even after failure.

Using a suitable diagram, describe the different states that a database transaction can be in during its lifecycle. (also describe the associated terms: commit, rollback, abort, etc.)

Transaction States

States (refer diagram in text):

• Active: transaction executing normally.

• Partially Committed: last statement executed; waiting for commit checks.

• Failed: error detected; cannot continue.

• Aborted: rolled back to previous consistent state.

• Committed: all changes permanently saved.

Associated:

• Commit: make all updates permanent.

• Rollback: undo all changes.

• Abort: terminate transaction without commit.

Why do we need concurrent execution of different transactions in a database?

3. Need for Concurrent Execution 

• Better system throughput and resource utilization.

• While one transaction waits for I/O, CPU can process another.

Describe the need for concurrency control with proper examples. or Describe the problems of lost update, dirty read (uncommitted dependency), and incorrect summary (inconsistent analysis) using proper examples. [5]/[2 each]

Need for Concurrency Control / Problems with Examples 

• Lost Update: Two transactions overwrite each other’s updates. Example: T1 subtracts ₹10, T2 deposits ₹100; final value misses one update.

• Dirty Read: T2 reads value updated by T1 before T1 commits, but T1 later rolls back → T2 used incorrect value.

• Incorrect Summary: T1 updates values while T2 is reading them for summary; T2 gets mixed old/new values.

What is a schedule of transactions? What are serial and non-serial (interleaved) schedules? Give examples of each. 

5. Schedule, Serial & Non-serial (1+2+2)

• Schedule: sequence of operations of multiple transactions preserving order inside each transaction.

• Serial: no interleaving; T1 completes fully before T2 begins.

• Non-serial: interleaved operations.

Examples:

– Serial → T1: r(X), w(X); then T2: r(Y), w(Y).

– Non-serial → r1(X), r2(Y), w1(X), w2(Y).

What is the serializability of a (non-serial) schedule? or When do we call a schedule serializable? (discuss in the terms of correctness of every serial execution)

Serializability

• A non-serial schedule is serializable if its result is the same as some serial execution of the transactions → ensures correctness.

What is conflict serializability? Explain with an example.

Conflict Serializability

• Schedule is conflict serializable if all conflicting operations (r/w on same item) appear in same order as some serial schedule.

• Example: r1(X), w1(X), r2(X), w2(X) → equivalent to serial T1→T2.

Define view serializability.

View Serializability

• Two schedules are view-equivalent if:

– They read the same initial values.

– Reads see the values from same writes.

– Final writes come from same transaction.

• Schedule is view serializable if view-equivalent to some serial schedule.

9. View serializability is less stringent than conflict serializability—justify. or Every conflict serializable schedule is view serializable, although the converse is not true—justify. or Give an example of a non-serial schedule that is view serializable but not conflict serializable. [3]

9. Conflict vs View Serializability (3)

• View serializability is less strict.

• Every conflict-serializable schedule is view-serializable, but some view-serializable schedules involve blind writes, making them NOT conflict-serializable.

10. What is a blind write operation? [2]

10. Blind Write (2)

• A write operation performed without reading the item first.

11. What is a recoverable schedule? [2]

11. Recoverable Schedule (2)

• A schedule where if Tj reads a value written by Ti, then Ti must commit before Tj commits.

12. Why are read locks called shared and write locks called exclusive? [2] (hint: conflict serializability)

12. Shared vs Exclusive Locks (2)

• Multiple transactions can share-read a data item → shared lock.

• Writes need exclusive access → exclusive lock, disallowing others.

13. State the different granularity (size) of the items that we can lock in a database. [2]

13. Lock Granularity (2)

• Database, File, Page, Record, Field (from coarse to fine).

14. Define/describe the two-phase locking (2PL) protocol. [2]

14. Two-Phase Locking (2)

• Phase 1 (Growing): transaction obtains all locks.

• Phase 2 (Shrinking): transaction releases locks; no new locks allowed.

15. With proper examples, discuss how 2PL helps in preventing the problems discussed in Question 4. [3 each]

15. 2PL Preventing Problems (3 × 3)

• Lost Update: Exclusive lock prevents simultaneous writes.

• Dirty Read: Writer holds exclusive lock until commit; others can't read dirty value.

• Incorrect Summary: Summarization uses shared locks; writers wait until readers finish.

16. What is cascading rollback? Show that cascading rollback is possible in 2PL using an example. [2+3]

16. Cascading Rollback & Example (2+3)

• Occurs when T2 reads value written by T1 but T1 aborts → T2 must also abort.

• In basic 2PL, early unlocking lets T2 read T1’s uncommitted value → cascading abort chain.

17. Describe one variant of 2PL that can prevent cascading rollback. Also discuss how it helps in preventing the same over classical/basic 2PL. [1+2]

17. Strict / Rigorous 2PL (1+2)

• Strict 2PL: all exclusive locks held till commit.

• Prevents cascading rollback by ensuring no other transaction can read uncommitted data.

18. What is a deadlock? Show that deadlock is possible in 2PL using an example. [2+3]

18. Deadlock & Example in 2PL (2+3)

• Deadlock: two transactions wait indefinitely for each other’s locks.

• Example:

T1 locks X → wants Y

T2 locks Y → wants X

Neither proceeds → deadlock.

19. Briefly discuss the shortcomings of the 2PL protocol. [3] (cascade rollback, deadlock)

19. Shortcomings of 2PL (3)

• Deadlock possible.

• Cascading rollbacks (in basic 2PL).

• Reduced concurrency due to strict lock rules.

20. Define the timestamp-based locking protocol. What is Thomas’s write rule? Why is it useful? [2+2+1]

20. Timestamp Protocol, Thomas’s Rule, Usefulness (2+2+1)

• Timestamp protocol orders transactions by timestamps; aborts younger/older ones on conflict.

• Thomas’s Write Rule: ignore obsolete writes instead of aborting → increases concurrency.

• Useful because it allows more schedules compared to strict conflict rules.

21. State the notion of a victim in the context of deadlock recovery. What are wait-die and wound-wait protocols for deadlock recovery? [1+2+2]

21. Victim, Wait-Die & Wound-Wait (1+2+2)

• Victim: transaction chosen to abort to break deadlock.

• Wait-Die: Older waits; younger dies (abort & restart).

• Wound-Wait: Older wounds (aborts) younger; younger waits for older.

22. Prove that the wait-die and wound-wait protocols avoid deadlock and starvation. [5]

22. Why Wait-Die & Wound-Wait Avoid Deadlock & Starvation (5)

• Both use timestamps, ensuring no cyclic waits.

• Older always has priority, ensuring no circular dependency.

• Restarted transactions retain timestamps, eventually become oldest → no starvation.

23. What is starvation? Discuss how starvation is avoided in timestamp-based locking protocol. [1+4]

23. Starvation & Avoidance in Timestamp Protocol (1+4)

• Starvation: transaction repeatedly prevented from progressing (always aborted).

• Timestamping avoids it because restarted transactions get newer timestamps, eventually becoming recent enough to proceed without rollback loops.

24. What are the different causes of database failures? / Why database recovery may be required? [3]

24. Causes of Database Failures / Need for Recovery (3)

• Hardware failures (crashes, power failure).

• Software failures (bugs, aborted transactions).

• Media failures (disk crash), human errors, malicious actions.

25. What is a log file? What are the before-image and after-image of a data item? [1+1+1]

25. Log File, Before & After Image (1+1+1)

• Log file: record of all transaction actions.

• Before-image: value of data item before update.

• After-image: value after update.

26. What is a checkpoint? How does it help in log-based data recovery? [1+2]

26. Checkpoint & Recovery Use (1+2)

• Checkpoint: point where all DB buffers & log entries are flushed to disk.

• Helps recovery by limiting how far back log needs to be scanned.

27. Briefly describe the database recovery using immediate update and deferred update. What is shadow paging? [2+2+2]

27. Immediate Update, Deferred Update, Shadow Paging (2+2+2)

• Immediate Update: changes written to DB before commit; log required for undo.

• Deferred Update: changes written only after commit; avoids undo operations.

• Shadow Paging: maintain shadow copy of pages; commit by swapping page tables.

28. Conflict Serializability of Schedules (2/3 each)

Let X be the only shared item.

a. r1 X; r3 X; w1 X; r2 X; w3 X

Conflicts: T1 → T3 (w1 then w3), T1 → T2 (w1 before r2), T3 → T2? (w3 before r2: yes).

Edges: 1→3, 1→2, 3→2. No cycles → Serializable.

Serial order: T1 → T3 → T2.

b. r1 X; r3 X; w3 X; w1 X; r2 X

Conflicts: 3→1 (w3 before w1), 1→2 (w1 before r2), 3→2 (w3 before r2).

Edges: 3→1, 3→2, 1→2 → no cycles → Serializable.

Serial order: T3 → T1 → T2.

c. r3 X; r2 X; w3 X; r1 X; w1 X

Conflicts: 3→2? (w3 after r2 → no), 3→1 (w3 before r1), 1→? (w1 last).

Edges: 3→1 → no cycle → Serializable.

Serial order: T3 → T1 → T2 (or T3→T1→T2 since T2 doesn’t conflict except read).

d. r3 X; r2 X; r1 X; w3 X; w1 X

Conflicts: 3→1 (w3 before w1).

No conflicts toward T2 (only reading).

Serializable: Yes.

Order: T3 → T1 → T2 (T2 can be anywhere before final writes since it only reads).