Skip to content
CampusPrep
CS-502 · Database Management Systems/Quick Revision Short Notes

Database Management Systems (CS-502) - Unit 4 Short Notes

How unit 4 is examined

Serializability, log recovery, locking and distributed databases carry the marks; transaction states, ACID, timestamps and deadlock come next; the last five topics are unasked.

Transaction System

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>A transaction is a logical unit of database work, a sequence of reads and writes that takes the database from one consistent state to another and runs completely or not at all.</mark>

Key points.

  1. Atomicity: all operations happen or none do, so a failed transfer is rolled back.
  2. Consistency: a transaction run alone leaves the database consistent, for example A + B is unchanged by a transfer.
  3. Isolation: concurrent transactions behave as if run one after another, hiding partial updates.
  4. Durability: once committed, changes survive any crash.
  5. States: active (executing), partially committed (last statement done), committed (changes permanent), failed (cannot continue, rolled back), terminated (leaves the system).

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-01" viewBox="0 0 474 252" width="474" height="252" role="img" aria-label="Act = active, PC = partially committed, Com = committed, Fail = failed, Term = terminated"><style>#dsfig-u4-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-01 .t{fill:#16181D;font-weight:500}#dsfig-u4-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-01 .dot{fill:#16181D}#dsfig-u4-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-01 .ah{fill:#454C5A}#dsfig-u4-01 .ah.hi{fill:#2340B8}#dsfig-u4-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-01 .e{stroke:#B1B7C3}html.dark #dsfig-u4-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-01 .t{fill:#E6E8ED}html.dark #dsfig-u4-01 .t.inv{fill:#0F1115}html.dark #dsfig-u4-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-01 .dot{fill:#E6E8ED}html.dark #dsfig-u4-01 .ann{fill:#8FA3FF}html.dark #dsfig-u4-01 .lbl{fill:#858D9C}html.dark #dsfig-u4-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-01 .ah{fill:#B1B7C3}html.dark #dsfig-u4-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M55.8,115.5 L151.5,51.6" marker-end="url(#ah8)"/><path class="e" d="M188,40 L277,40" marker-end="url(#ah8)"/><path class="e" d="M55.8,136.5 L145.7,196.5" marker-end="url(#ah8)"/><path class="e" d="M169,59 L169,184" marker-end="url(#ah8)"/><path class="e" d="M313.8,50.5 L403.7,110.5" marker-end="url(#ah8)"/><path class="e" d="M193.7,203.8 L400.4,134.9" marker-end="url(#ah8)"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">Act</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">PC</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">Com</text><rect class="n" x="144" y="197" width="50" height="30" rx="15"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">Fail</text><rect class="n" x="402" y="111" width="50" height="30" rx="15"/><text class="t" x="427" y="126" dy=".35em" text-anchor="middle">Term</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Act = active, PC = partially committed, Com = committed, Fail = failed, Term = terminated</figcaption></figure>

Example (Nov 2022 T). Steps 1-4 (reads and computing t) keep T active; after Write(B) it is partially committed; then commit makes it committed. A crash at step 5 or 6 moves it to failed (A may be written, B not), so it is rolled back and terminated.

Answer frame. Open with the definition; one sentence per ACID letter with the transfer example; draw the state diagram and map steps 1-6 of T onto it; close that ACID keeps concurrent transactions reliable.

Asked: [7 marks] (Jun 2020) Explain ACID property in detail. Asked: [7 marks] (Nov 2022) Discuss the transaction states active, partially commit, commit, failure and terminated for the given transaction T (Read A, Read B, t = A - 10% of A, B = B + t, Write A, Write B, commit).

Testing of Serializability

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A schedule is conflict serializable if it is conflict equivalent to a serial schedule, tested by drawing a precedence graph and checking that it has no cycle.</mark>

Steps.

Step 1: One node per transaction.
Step 2: Two operations conflict if they are from different transactions, on the same item, and at least one is a Write.
Step 3: For each conflicting pair draw Ti -> Tj, where Ti's operation comes first (R-W, W-R, W-W).
Step 4: A cycle means not conflict serializable.
Step 5: No cycle means serializable; a topological order of the nodes is the equivalent serial schedule.

Example 1 (Nov 2022, Dec 2025). S: R1(A), R2(A), R1(B), R3(B), W2(A), W3(B), W1(B). Item A: R1(A) before W2(A) gives T1 -> T2. Item B: R1(B) before W3(B) gives T1 -> T3; R3(B) before W1(B) gives T3 -> T1.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-02" viewBox="0 0 252 252" width="252" height="252" role="img" aria-label="Precedence graph of S with a T1-T3 cycle"><style>#dsfig-u4-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-02 .t{fill:#16181D;font-weight:500}#dsfig-u4-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-02 .dot{fill:#16181D}#dsfig-u4-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-02 .ah{fill:#454C5A}#dsfig-u4-02 .ah.hi{fill:#2340B8}#dsfig-u4-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-02 .e{stroke:#B1B7C3}html.dark #dsfig-u4-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-02 .t{fill:#E6E8ED}html.dark #dsfig-u4-02 .t.inv{fill:#0F1115}html.dark #dsfig-u4-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-02 .dot{fill:#E6E8ED}html.dark #dsfig-u4-02 .ann{fill:#8FA3FF}html.dark #dsfig-u4-02 .lbl{fill:#858D9C}html.dark #dsfig-u4-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-02 .ah{fill:#B1B7C3}html.dark #dsfig-u4-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah9" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh9" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M57,117.5 L193.2,49.4" marker-end="url(#ah9)"/><path class="e" d="M58.8,135.4 L193.2,202.6" marker-end="url(#ah9)" marker-start="url(#ah9)"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">T1</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">T2</text><circle class="n" cx="212" cy="212" r="18"/><text class="t" x="212" y="212" dy=".35em" text-anchor="middle">T3</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Precedence graph of S with a T1-T3 cycle</figcaption></figure> T1 -> T3 -> T1 is a cycle, so S is not conflict serializable.

Example 2 (Dec 2025). R1(X), W1(X), R2(X), W2(X), R1(Y), W1(Y). X gives only T1 -> T2; Y belongs to T1 alone. No cycle, so conflict serializable, equivalent serial order T1, T2.

Example 3 (Nov 2023). Taking the usual interleaving R1(A), W1(A), R2(A), W2(A), R1(B), W1(B), R2(B), W2(B): A gives T1 -> T2 and B gives T1 -> T2.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-03" viewBox="0 0 252 80" width="252" height="80" role="img" aria-label="Precedence graph for Nov 2023"><style>#dsfig-u4-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-03 .t{fill:#16181D;font-weight:500}#dsfig-u4-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-03 .dot{fill:#16181D}#dsfig-u4-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-03 .ah{fill:#454C5A}#dsfig-u4-03 .ah.hi{fill:#2340B8}#dsfig-u4-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-03 .e{stroke:#B1B7C3}html.dark #dsfig-u4-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-03 .t{fill:#E6E8ED}html.dark #dsfig-u4-03 .t.inv{fill:#0F1115}html.dark #dsfig-u4-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-03 .dot{fill:#E6E8ED}html.dark #dsfig-u4-03 .ann{fill:#8FA3FF}html.dark #dsfig-u4-03 .lbl{fill:#858D9C}html.dark #dsfig-u4-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-03 .ah{fill:#B1B7C3}html.dark #dsfig-u4-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah10" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh10" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L191,40" marker-end="url(#ah10)"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">T1</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">T2</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Precedence graph for Nov 2023</figcaption></figure> No cycle, so conflict serializable; equivalent serial schedule is T1 followed by T2.

Answer frame. Open with the definition; list conflicting pairs item by item; draw the labelled graph; state the cycle check and the serial order; close with the verdict.

Asked: [7 marks] (Nov 2022, Dec 2025) Draw the precedence graph for the given concurrent schedule (T1, T2, T3 on A and B; and R1(X), W1(X), R2(X), W2(X), R1(Y), W1(Y)) and determine if it is conflict serializable. Asked: [7 marks] (Dec 2020) How is precedence graph made to check serializability? Asked: [7 marks] (Nov 2023) Show the precedence graph for the given concurrent schedule of T1 and T2 on A and B and find the equivalent serial schedule.

Serializability of schedules

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>A schedule is the chronological order in which operations of concurrent transactions execute, keeping each transaction's own order.</mark>

Key points.

  1. A serial schedule runs transactions one after another and is always correct.
  2. A concurrent schedule interleaves operations, for example R1(A), R2(A), W1(A), W2(A), for higher throughput.
  3. A schedule is serializable if its result equals some serial schedule; n transactions have n! serial schedules.
  4. A recoverable schedule commits a reader only after the writer it read from.

Asked: [7 marks] (Jun 2020) What do you mean by Schedule?

Conflict and view serializable schedules

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>A schedule is conflict serializable if swapping adjacent non-conflicting operations gives a serial schedule; it is view serializable if it is view equivalent to a serial schedule.</mark>

Key points.

  1. View equivalence needs the same initial reads, the same reads-from pairs and the same final write on each item.
  2. Conflict serializability is tested by a precedence graph in polynomial time; testing view serializability is NP-complete.
  3. Every conflict serializable schedule is view serializable, but not the converse.
  4. The difference comes from blind writes (write without a read).
  5. Example: S = R1(A), W2(A), W1(A), W3(A) has edges T1 -> T2 and T2 -> T1, a cycle, so it is not conflict serializable; it is view equivalent to T1, T2, T3 (T1 reads the initial A, T3 writes last), so it is view serializable.
Basis Conflict View
Equivalence Same order of conflicting operations Same initial read, reads-from, final write
Test Precedence graph, no cycle View equivalence to a serial schedule
Complexity Polynomial NP-complete
Scope Subset Superset
Blind writes Rejects some Accepts them
Use Used in practice Mostly theoretical

Answer frame. Open with transaction processing and ACID if asked; define both; draw the table; give the blind-write example; close that conflict serializable implies view serializable.

Asked: [7 marks] (Jun 2020) Differentiate conflict serializability and view serializability with suitable example. Asked: [7 marks] (Dec 2025) Explain transaction processing and serializability. Differentiate between conflict and view serializability.

Recoverability

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>A schedule is recoverable if whenever Tj reads a value written by Ti, Ti commits before Tj commits.</mark>

Key points.

  1. Recoverable: W1(A), R2(A), C1, C2.
  2. Non-recoverable: W1(A), R2(A), C2, then T1 aborts; T2 has committed on data that vanished.
  3. Cascading rollback occurs when T1 aborts before commit and T2 must abort too; cascadeless schedules read only committed data.

Asked: [7 marks] (Nov 2023) Explain the concept of recoverability in DBMS. Show any recoverable schedule consisting of two transactions.

Recovery from transaction failures

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Recovery restores the database to the latest consistent state after a transaction, system or disk failure, preserving atomicity and durability.</mark>

Key points.

  1. Transaction failure (logic error, deadlock) is handled by rolling back with the log.
  2. After a system crash, committed work is redone and uncommitted work undone.
  3. Shadow paging keeps a shadow page table of old pages; commit switches to the current table, abort discards it, and no log is needed.
  4. Log-based recovery and checkpoints are covered below.

Asked: [7 marks] (Dec 2024) What is Transaction? Discuss about transaction recovery techniques.

Log based recovery

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A log is an append-only file on stable storage that records every update of every transaction; log-based recovery uses it to undo uncommitted and redo committed changes after a failure.</mark>

Key points.

  1. Records are <T start>, <T, X, V_old, V_new>, <T commit> and <T abort>.
  2. Write-ahead logging (WAL): the log record reaches stable storage before the data block it describes, and all of T's records before T commits.
  3. Deferred modification writes to the database only after commit, so the log holds new values and recovery only redoes.
  4. Immediate modification lets updates reach the database before commit, so the log holds old and new values and recovery uses undo and redo.
  5. Recovery: redo T if both <T start> and <T commit> are present; undo T (immediate only) if <T start> has no commit.
  6. A checkpoint record lists active transactions, so after a crash only the log from the last checkpoint is scanned.
Basis Deferred Immediate
Database write After commit Before commit allowed
Log content New value Old and new values
Recovery Redo only Undo and redo

Example. Log: <T1 start>, <T1, A, 100, 90>, <T1 commit>, <checkpoint>, <T2 start>, <T2, B, 50, 70>, crash. T1 committed before the checkpoint, so nothing to do. T2 has no commit, so undo restores B = 50 (immediate); in deferred mode T2 is ignored.

Answer frame. Open with the log definition; list record types and WAL; draw the deferred versus immediate table for Nov 2019; give the checkpoint example for Dec 2025; close that the log gives atomicity and durability.

Asked: [7 marks] (Nov 2019) Explain the deferred and immediate modification versions of the log based recovery scheme. Asked: [7 marks] (Dec 2020, Jun 2020) What is Log? How is it maintained? Asked: [7 marks] (Dec 2025) Explain Log-based recovery and checkpoints with an example.

Checkpoints and deadlock handling

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>A checkpoint forces buffered log and modified blocks to disk and logs a checkpoint record; a deadlock is a state where transactions wait for locks held by each other, so none proceeds.</mark>

Key points.

  1. Example: T1 holds A and waits for B while T2 holds B and waits for A.
  2. Prevention uses wait-die (older waits, younger dies) and wound-wait (older wounds younger) by timestamp, or locks all items before starting.
  3. Detection builds a wait-for graph with edge Ti -> Tj when Ti waits for Tj; a cycle means deadlock.
  4. Resolution: choose a cheap victim, roll it back and restart it, avoiding starvation of one victim.

Asked: [7 marks] (Dec 2020) What do you mean by deadlock handling? How can we resolve deadlock?

Concurrency control

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Concurrency control manages simultaneous execution of transactions so they do not interfere, keeping the database consistent by enforcing serializable schedules.</mark>

Key points.

  1. Lost update: T1 and T2 read X and both write back, so one update is overwritten.
  2. Dirty read: T2 reads T1's uncommitted write, and T1 later aborts.
  3. Unrepeatable read: T1 reads X twice and T2 changes X in between.
  4. Phantom or inconsistent analysis (Nov 2022): T2 reads avg(balance), T1 inserts (222, 40000) and commits, and T2's second avg differs.
  5. Concurrency is still wanted for throughput and resource use, so control is needed for consistency and isolation.
  6. Protocols: lock-based (2PL), timestamp-based, validation and multiversion.
  7. Locking uses shared (S) locks to read and exclusive (X) locks to write; timestamping orders conflicting operations by transaction timestamps.

Example (Nov 2023). T1: R(X), W(X) with X = X - 100, R(Y), W(Y) with Y = Y + 100. T2: R(X), W(X) with X = 1.1X, R(Y), W(Y) with Y = 1.1Y. Start X = Y = 1000. Interleave R1(X), W1(X), R2(X), W2(X), R2(Y), W2(Y), R1(Y), W1(Y): X = 990, Y = 1100 + 100 = 1200, total 2190, but serial order gives X = 990, Y = 1210, total 2200. The interleaving corrupts the database.

Answer frame. Open with the definition; list the four problems with one-line examples; say why control is needed; describe locking and timestamps in two lines each; close with serializability as the goal.

Asked: [14 marks] (Dec 2020) Write short note on any three: i) Concurrency control ii) Multivalued dependency iii) Hashing technique iv) Join dependency v) Various keys in DBMS. Asked: [7 marks] (Nov 2019, Dec 2025) How concurrency is performed? Explain the protocol used to maintain concurrency; explain locking and time-stamping protocols. Asked: [7 marks] (Jun 2020, Nov 2022) Why the concurrency control is needed? Discuss the issues with interleaved execution of T1 and T2. Asked: [7 marks] (Nov 2023) Give an example of another transaction T2 that, run concurrently with T1 = R(X), W(X), R(Y), W(Y) without concurrency control, could interfere with T1.

Locking techniques for concurrency control

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Two-phase locking (2PL) makes every transaction acquire locks in a growing phase and release them in a shrinking phase, and never acquire a lock after its first release.</mark>

Key points.

  1. A shared lock (S) allows reading by many; an exclusive lock (X) allows writing by one.
  2. S with S is compatible; S with X and X with X conflict, so the requester waits.
  3. 2PL schedules are serializable in the order of their lock points (last lock taken).
  4. Basic 2PL can deadlock and can cause cascading rollback, since locks are released before commit.
  5. Strict 2PL holds all X locks until commit or abort, giving cascadeless, recoverable schedules.
  6. Rigorous 2PL holds all locks, S and X, until commit.

Example (Nov 2023 conversion). Given: Lock-S(A), Read(A), Lock-X(B), Read(B), B = B + A, Write(A), Write(B), Unlock(A), Unlock(B), Commit.

  • Strict: ..., Write(B), Unlock(A), Commit, Unlock(B) (X locks held to commit).
  • Rigorous: ..., Write(B), Commit, Unlock(A), Unlock(B) (all locks held to commit).
Basis 2PL Strict 2PL
Lock release Any time in shrinking phase X locks only after commit or abort
Serializability Guaranteed Guaranteed
Deadlock Possible Possible
Cascading rollback Possible Avoided
Recoverability Not guaranteed Guaranteed
Concurrency Higher Lower

Versus timestamps (Nov 2019). Strict 2PL orders transactions by lock point, makes conflicting ones wait, and may deadlock. Timestamp ordering fixes the order by start time, rolls back the late operation instead of waiting, and never deadlocks.

Answer frame. Open with the 2PL definition and phases; sketch locks rising then falling, with a two-transaction example (Lock-X(A), Write(A), Lock-X(B), Unlock(A), Write(B), Unlock(B)); develop points 1-5; add the table or the two rewritten schedules as asked; close that 2PL ensures serializability and strict 2PL adds recoverability.

Pitfall: 2PL guarantees serializability, not freedom from deadlock.

Asked: [7 marks] (Dec 2020, Nov 2022) What is two phase locking (2PL)? Describe with an example; illustrate 2PL and its variants. Asked: [7 marks] (Nov 2019) Discuss on strict two-phase locking protocol and time stamp-based protocol. Asked: [7 marks] (Nov 2023) Convert the given schedule S (Lock Shared(A) ... Commit) to strict and rigorous two-phase locking. Asked: [7 marks] (Dec 2024) What is 2-phase locking protocol? Compare 2PL with Strict 2PL protocol.

Timestamp protocols for concurrency control

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>In timestamp ordering each transaction gets a unique timestamp TS(Ti) at start, and conflicting operations execute in timestamp order.</mark>

Key points.

  1. Each item Q keeps R-TS(Q) and W-TS(Q), the largest timestamps of its readers and writers.
  2. Read(Q): if TS(Ti) < W-TS(Q), roll Ti back; else execute and set R-TS(Q) = max(R-TS(Q), TS(Ti)).
  3. Write(Q): if TS(Ti) < R-TS(Q) or TS(Ti) < W-TS(Q), roll Ti back; else execute and set W-TS(Q) = TS(Ti).
  4. Thomas write rule: an obsolete write with TS(Ti) < W-TS(Q) is ignored instead of rolling back.
  5. Advantages: serializable and deadlock free. Disadvantages: starvation and cascading rollback.

Asked: [7 marks] (Dec 2024) Explain Timestamping protocols for concurrency control.

Validation based protocol

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Optimistic control runs transactions without locks and checks for conflicts only at the end.</mark>

Key points.

  1. Phases: read (local copies), validation, write.
  2. Ti passes against earlier Tj if Tj finished before Ti started or wrote nothing Ti read; failure means restart.

Multiple granularity

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Multiple granularity locking locks at several levels of a hierarchy (database, file, page, record) using intention locks.</mark>

Key points.

  1. Intention modes are IS, IX and SIX.
  2. Before an S or X lock on a node, intention locks are taken on all its ancestors, from the root down.

Multi version schemes

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Multiversion control (MVCC) keeps several versions of each item so a read can use a suitable older one.</mark>

Key points.

  1. Each write creates a new version stamped with its writer's timestamp.
  2. A read returns the version with the largest write timestamp not above TS(Ti), so reads never wait.

Recovery with concurrent transaction

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>With concurrent transactions there is one shared log, and checkpoints list all active transactions.</mark>

Key points.

  1. Strict 2PL is needed so that rolling back T does not affect others.
  2. Restart finds the last checkpoint, builds redo and undo lists, redoes forward, then undoes backward.

Introduction to distributed databases

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A distributed database is a collection of logically related databases stored at multiple network sites and managed by a distributed DBMS so that users see one database.</mark>

Key points.

  1. A homogeneous system uses the same DBMS at every site; a heterogeneous system uses different ones.
  2. Fragmentation splits a relation into pieces stored at different sites; replication keeps copies at several sites for availability, at the cost of update consistency.
  3. Horizontal fragmentation splits rows by selection, for example EMP-CS = sigma dept='CS' (EMP); the original is rebuilt by union.
  4. Vertical fragmentation splits columns by projection, for example (eid, name) and (eid, salary), each keeping the key; the original is rebuilt by join.
  5. Mixed fragmentation applies both, for example a horizontal split by department and then a vertical split of each part.
  6. Advantages are fast local access, reliability and easy growth; disadvantages are complex query processing, harder concurrency control and cost.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-04" viewBox="0 0 1249 198" width="1249" height="198" role="img" aria-label="Fragmentation of relation EMP by rows and by columns"><style>#dsfig-u4-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-04 .t{fill:#16181D;font-weight:500}#dsfig-u4-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-04 .dot{fill:#16181D}#dsfig-u4-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-04 .ah{fill:#454C5A}#dsfig-u4-04 .ah.hi{fill:#2340B8}#dsfig-u4-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-04 .e{stroke:#B1B7C3}html.dark #dsfig-u4-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-04 .t{fill:#E6E8ED}html.dark #dsfig-u4-04 .t.inv{fill:#0F1115}html.dark #dsfig-u4-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-04 .dot{fill:#E6E8ED}html.dark #dsfig-u4-04 .ann{fill:#8FA3FF}html.dark #dsfig-u4-04 .lbl{fill:#858D9C}html.dark #dsfig-u4-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-04 .ah{fill:#B1B7C3}html.dark #dsfig-u4-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah11" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh11" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="612.5" y1="39" x2="270.5" y2="103"/><line class="e" x1="612.5" y1="39" x2="954.5" y2="103"/><line class="e" x1="270.5" y1="103" x2="99.5" y2="167"/><line class="e" x1="270.5" y1="103" x2="441.5" y2="167"/><line class="e" x1="954.5" y1="103" x2="783.5" y2="167"/><line class="e" x1="954.5" y1="103" x2="1125.5" y2="167"/><circle class="n" cx="612.5" cy="39" r="17"/><text class="t" x="612.5" y="39" dy=".35em" text-anchor="middle">EMP</text><rect class="n" x="194" y="88" width="153" height="30" rx="8"/><text class="t" x="270.5" y="103" dy=".35em" text-anchor="middle">Horizontal (rows)</text><rect class="n" x="66" y="152" width="67" height="30" rx="8"/><text class="t" x="99.5" y="167" dy=".35em" text-anchor="middle">EMP-CS</text><rect class="n" x="408" y="152" width="67" height="30" rx="8"/><text class="t" x="441.5" y="167" dy=".35em" text-anchor="middle">EMP-EE</text><rect class="n" x="874" y="88" width="161" height="30" rx="8"/><text class="t" x="954.5" y="103" dy=".35em" text-anchor="middle">Vertical (columns)</text><rect class="n" x="742" y="152" width="83" height="30" rx="8"/><text class="t" x="783.5" y="167" dy=".35em" text-anchor="middle">eid,name</text><rect class="n" x="1076.5" y="152" width="98" height="30" rx="8"/><text class="t" x="1125.5" y="167" dy=".35em" text-anchor="middle">eid,salary</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Fragmentation of relation EMP by rows and by columns</figcaption></figure>

Answer frame. Open with the definition; for fragmentation define it, then horizontal, vertical and mixed each with a small EMP example and the rebuild operator; add replication in one line; close with advantages.

Asked: [14 marks] (Nov 2019) Write short note on: a) Distributed database b) Nested and parameterized cursors c) Branching and looping constructs in ANSI SQL. Asked: [7 marks] (Dec 2020, Jun 2020) Explain Fragmentation and its types in detail; explain data fragmentation with types. Asked: [7 marks] (Dec 2024) Explain briefly: i) Distributive Databases ii) Triggers iii) Join operations.

Data mining

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Data mining discovers useful patterns in large databases.</mark>

Key points.

  1. It is one step of knowledge discovery: selection, cleaning, mining, evaluation.
  2. Tasks are classification, clustering, association rules and prediction.

Data warehousing

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>A data warehouse is a subject-oriented, integrated, time-variant, non-volatile collection of data supporting decisions.</mark>

Key points.

  1. Data arrives from operational systems through extract, transform, load (ETL).
  2. OLAP analyses it with roll-up, drill-down, slice and dice.

Object technology and DBMS

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>An OODBMS stores data as objects combining attributes and methods, with classes, inheritance and encapsulation.</mark>

Key points.

  1. Each object has a unique object identifier (OID).
  2. Subclasses inherit attributes and methods.

Comparative study of OODBMS vs DBMS

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>An OODBMS stores objects with behaviour; a relational DBMS stores flat tables of atomic values.</mark>

Key points.

  1. Data: objects and OIDs versus rows and keys.
  2. Query: OQL and navigation versus SQL and joins.

Temporal, deductive, multimedia, web and mobile databases

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Specialised databases: temporal (time-varying data), deductive (rule-derived facts), multimedia (images, audio, video), web and mobile.</mark>

Key points.

  1. Temporal databases keep valid time and transaction time.
  2. Deductive databases infer facts from rules.

Last-minute revision

  • ACID: Atomicity, Consistency, Isolation, Durability; states active, partially committed, committed, failed, terminated.
  • Precedence graph edge Ti -> Tj per conflicting pair (R-W, W-R, W-W); a cycle means not conflict serializable.
  • View equivalence: same initial reads, reads-from, final writes; blind writes separate view from conflict.
  • Log record <T, X, old, new>; WAL writes the log first; deferred is redo only, immediate is undo and redo.
  • 2PL: growing then shrinking; strict holds X locks to commit; rigorous holds all locks to commit.
  • Fragmentation: horizontal (selection, union), vertical (projection, join), mixed.

Memory hooks

  • 2PL: grow, then shrink, never grow again.
  • Strict = X locks to commit; rigorous = every lock to commit.
  • Cycle kills serializability.
  • Deferred = redo only; immediate = undo and redo.

Coverage checklist

  • Transaction System: Jun 2020, Nov 2022
  • Testing of Serializability: Nov 2022, Dec 2025, Dec 2020, Nov 2023
  • Serializability of schedules: Jun 2020
  • conflict & view serializable schedule: Jun 2020, Dec 2025
  • recoverability: Nov 2023
  • Recovery from transaction failures: Dec 2024
  • Log based recovery: Dec 2020, Jun 2020, Nov 2019, Dec 2025
  • Checkpoints deadlock handling: Dec 2020
  • Concurrency Control Techniques: Dec 2020, Nov 2019, Dec 2025, Jun 2020, Nov 2022, Nov 2023
  • locking Techniques for concurrency control: Dec 2020, Nov 2022, Nov 2019, Nov 2023, Dec 2024
  • time stamping protocols for concurrency control: Dec 2024
  • validation based protocol
  • multiple granularity
  • Multi version schemes
  • Recovery with concurrent transaction
  • Introduction to Distributed databases: Nov 2019, Dec 2024, Dec 2020, Jun 2020
  • data mining
  • data warehousing
  • Object Technology and DBMS
  • Comparative study of OODBMS Vs DBMS
  • Temporal, Deductive, Multimedia, Web & Mobile database
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in