Database Management System (AD-402) Unit 4 Notes

How unit 4 is examined

Covers transactions, serializability, recovery, concurrency control (locking, timestamp, validation), distributed databases and OODBMS vs DBMS; locking, timestamp ordering and OODBMS vs DBMS carry the marks.

Transaction System

Not asked since 2022

Definition. A transaction is a logical unit of work, a sequence of read and write operations, that takes the database from one consistent state to another.

Key points.

Atomicity means all operations happen or none do.
Consistency means a transaction preserves database integrity constraints.
Isolation means concurrent transactions do not see each other's partial results.
Durability means committed changes survive failures.
States: active, partially committed, committed, failed, aborted.

Testing of Serializability

Definition. A schedule is conflict serializable if its precedence graph has no cycle.

Steps.

Step 1: Make one node per transaction.
Step 2: For each conflicting pair (same item, different transactions, at least one write) where Ti operates first, draw edge Ti -> Tj.
Step 3: If the graph has a cycle, the schedule is not conflict serializable.
Step 4: If acyclic, a topological order gives an equivalent serial schedule.

Example. S1 = R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B): all conflicts run T1 to T2, so the graph is acyclic and S1 is equivalent to T1 then T2. S2 = R1(A) W2(A) R2(B) W1(B): R1(A) before W2(A) gives T1 to T2, and R2(B) before W1(B) gives T2 to T1, so there is a cycle and S2 is not serializable.

<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 338 80" width="338" height="80" role="img" aria-label="Precedence graph of S2, cycle so not serializable"><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="ah4" 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="ahh4" 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="M58.4,44.6 Q169,72 277.6,45.1" marker-end="url(#ah4)"/><path class="e" d="M279.6,35.4 Q169,8 60.4,34.9" marker-end="url(#ah4)"/><g class="wl"><rect x="158.9" y="49.4" width="19.2" height="18" rx="9"/><text class="t" x="168.5" y="58.4" dy=".35em" text-anchor="middle">A</text></g><g class="wl"><rect x="159.9" y="12.6" width="19.2" height="18" rx="9"/><text class="t" x="169.5" y="21.6" dy=".35em" text-anchor="middle">B</text></g><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="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">T2</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Precedence graph of S2, cycle so not serializable</figcaption></figure>

Asked: [7 marks] (Jun 2023) Discuss the procedure to test serializability of a schedule with an example.

Serializability of schedules

Definition. A schedule is serializable if its result equals that of some serial schedule of the same transactions.

Key points.

A serial schedule runs transactions one after another with no interleaving; n transactions have n! serial schedules.
A serial schedule is always correct but gives poor concurrency.
A non-serial schedule is acceptable only if it is serializable.
Two forms exist: conflict serializability and view serializability.

Conflict and view serializable schedule

Definition. A schedule is conflict serializable if it can be turned into a serial schedule by swapping adjacent non-conflicting operations.

Key points.

Operations conflict if they are on the same item, by different transactions, and at least one is a write.
Conflict serializability is tested with the precedence graph.
View equivalence needs the same initial reads, the same read-from relations and the same final writes.
Every conflict serializable schedule is view serializable, but not the reverse; the difference is blind writes.
Testing view serializability is NP-complete.

Recoverability

Definition. A schedule is recoverable if a transaction commits only after every transaction whose data it read has committed.

Key points.

A dirty read of uncommitted data followed by an early commit makes a schedule unrecoverable.
A cascading rollback happens when one abort forces dependent transactions to abort.
A cascadeless schedule lets a transaction read only committed values, which prevents cascading rollback.
A strict schedule neither reads nor overwrites uncommitted data.
Strict implies cascadeless, and cascadeless implies recoverable.

Recovery from transaction failures

Definition. Recovery restores the database to the last consistent state after a failure.

Key points.

A transaction failure comes from a logical error or a system error such as deadlock.
A system crash loses main memory but not disk contents.
A disk failure destroys stored data and is recovered from backups or archives.
Rollback undoes the effects of an aborted transaction using the log.

Log based recovery

Definition. A log is a sequential record of all updates; recovery uses it to undo uncommitted and redo committed transactions.

Key points.

Records are of the form <T, start>, <T, X, old, new> and <T, commit>.
Write-ahead logging (WAL) forces the log record to disk before the data page is written.
Deferred modification writes to the database only after commit, so only REDO is needed.
Immediate modification writes early, so both UNDO and REDO are needed.
On crash, redo transactions that have start and commit records and undo those with start but no commit.
A checkpoint flushes buffers and logs a record, so recovery scans only from the last checkpoint.

Asked: [7 marks] (Jun 2026) Discuss the database recovery process and explain how checkpoints and log files help restore the database after system failures or transaction crashes.

Checkpoints and deadlock handling

Definition. A deadlock is a state where each transaction in a set waits for a lock held by another in the set.

Key points.

A checkpoint writes all buffers and a checkpoint record to disk, limiting how far back recovery scans.
Prevention uses wait-die (older waits, younger dies) or wound-wait (older wounds younger).
Detection builds a wait-for graph, and a cycle means deadlock.
Recovery picks a victim, rolls it back and restarts it, avoiding starvation.
A timeout is a simple practical alternative.

Concurrency control

Definition. Concurrency control is the mechanism that manages simultaneous transactions so that isolation and consistency are preserved.

Key points.

It is needed because uncontrolled interleaving causes anomalies.
Lost update: two transactions read the same value and one overwrites the other's write.
Dirty read: a transaction reads data written by an uncommitted transaction.
Unrepeatable read: two reads of one item in a transaction return different values.
Techniques are locking, timestamp ordering, validation (optimistic) and multiversion schemes.

Example. T1 and T2 both read A = 100, T1 subtracts 10, T2 adds 20 and both write; the last write wins, so one update is lost.

Asked: [7 marks] (Jun 2026) Discuss the concept of concurrency control in a database system.

Locking techniques for concurrency control

Definition. Locking controls access to a data item: a transaction must hold a lock on an item before reading or writing it.

Key points.

A shared lock (S) allows reading; many transactions may hold S on the same item.
An exclusive lock (X) allows reading and writing; only one transaction may hold it.
Compatibility: S with S is allowed; S with X, X with S and X with X are refused.

Held \ Requested	S	X
S	Yes	No
X	No	No

Two-phase locking (2PL) has a growing phase, where locks are only acquired, and a shrinking phase, where locks are only released; after the first unlock no lock may be taken.
2PL guarantees conflict serializability, but it does not prevent deadlock or cascading rollback.
Strict 2PL holds all X locks until commit or abort, so it is cascadeless; rigorous 2PL holds all locks until commit.
Deadlock: prevent it with wait-die or wound-wait, detect it with a wait-for graph cycle and abort a victim.

Example. T1: lock-X(A); read A; write A; lock-X(B); unlock(A); unlock(B). Lock points precede all unlocks, so T1 is two-phase.

Answer frame. Open with the definition of locking; draw the compatibility table; develop lock types, 2PL phases, variants, then deadlock handling; close with 2PL guarantees serializability.

Asked: [7 marks] (Jun 2024) Explain locking techniques for concurrency control, including exclusive locks, shared locks, and deadlock detection/prevention mechanisms. Asked: [7 marks] (Jun 2026) What is Two-Phase Locking (2PL) protocol and write Two-Phase Locking (2PL) protocol.

Timestamp ordering protocols

Definition. Timestamp ordering assigns each transaction a unique timestamp TS(T) when it starts and forces conflicting operations to run in timestamp order.

Key points.

Each item Q keeps $R\text{-}TS(Q)$, the largest timestamp of any successful read, and $W\text{-}TS(Q)$, the largest timestamp of any successful write.
Read(Q) by T: if $TS(T) < W\text{-}TS(Q)$, abort T; else execute and set $R\text{-}TS(Q) = \max(R\text{-}TS(Q), TS(T))$.
Write(Q) by T: if $TS(T) < R\text{-}TS(Q)$, abort T; if $TS(T) < W\text{-}TS(Q)$, abort T (Thomas write rule: ignore the write instead); else execute and set $W\text{-}TS(Q) = TS(T)$.
An aborted transaction restarts with a new timestamp.
The protocol is free of deadlock and ensures conflict serializability.
Drawbacks: starvation of restarted transactions and possible cascading rollbacks.

Example (Jun 2025). TS(T1) = 5:15 < TS(T2) = 5:16; initial R-TS = W-TS = 0 (clock zero). Each does read A, A = A - 100, write A, read B, B = B + 100, write B.

Step	Operation	Check	Result
1	T1 read A	W-TS(A) = 0 ≤ 5:15	run, R-TS(A) = 5:15
2	T1 write A	R-TS = 5:15 ≤ 5:15	run, W-TS(A) = 5:15
3	T2 read A	W-TS(A) = 5:15 ≤ 5:16	run, R-TS(A) = 5:16
4	T2 write A	R-TS = 5:16 ≤ 5:16	run, W-TS(A) = 5:16
5-8	same on B in order T1 then T2	all allowed	both commit

The schedule is R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B), equivalent to T1 then T2.

Answer frame. Open with the definition of TS(T); list R-TS and W-TS, then the read rule, write rule and Thomas rule; for the numerical give the table above; close with deadlock-free but starvation-prone.

Asked: [7 marks] (Jun 2023) Discuss in detail time stamp based concurrency control protocol. Asked: [7 marks] (Jun 2025) Consider the two transactions T1 and T2, both subtract 100 from A and add to B, with time stamps 5:15pm and 5:16pm. Illustrate a schedule if the entire system clock is set to zero.

Validation based protocol

Definition. The validation (optimistic) protocol lets transactions run without locks and checks for conflicts only before commit.

Key points.

Phases: read (work on local copies), validation (test against other transactions), write (apply to database).
If validation fails, the transaction is rolled back and restarted.
Advantages: no locking, no deadlock and high concurrency when conflicts are rare.
Disadvantages: repeated restarts under high conflict, possible starvation of long transactions, and wasted work and validation overhead.

Asked: [7 marks] (Jun 2025) Write the advantages and disadvantages of validation protocol.

Multiple granularity

Definition. Granularity is the size of the data item that is locked, from the whole database down to a single field.

Key points.

The hierarchy is database, table (file), page, tuple (record), field.
Coarse granularity means few locks and low overhead but less concurrency.
Fine granularity means high concurrency but more locks, memory and management overhead.
Intention locks (IS, IX, SIX) on ancestors let a transaction lock at any level safely.
Best choice: fine locks for short transactions, coarse for those touching many rows.

Asked: [7 marks] (Jun 2025) How does the granularity of data items affect the performance of concurrency control? Explain.

Multi version schemes

Definition. Multiversion concurrency control keeps several versions of each item so readers never wait for writers.

Key points.

Each write creates a new version stamped with the writer's timestamp.
A read picks the latest version with timestamp not later than the reader's.
Read-only transactions are never blocked or aborted.
The cost is storage for old versions, which must be garbage collected.

Recovery with concurrent transaction

Definition. Recovery with concurrent transactions uses one shared log and checkpoints, and undoes or redoes all active transactions together.

Key points.

Strict 2PL keeps rollbacks of one transaction from affecting others.
At a checkpoint the log lists all active transactions.
Recovery builds redo-list and undo-list from the log after the last checkpoint.
ARIES does analysis, redo and undo passes using log sequence numbers.

Introduction to distributed databases

Definition. A distributed database is a collection of logically related data stored at several sites connected by a network and managed by a distributed DBMS.

Key points.

Fragmentation splits a relation into horizontal (rows), vertical (columns) or mixed fragments stored at different sites.
Replication keeps copies at several sites for availability, but every update must reach all copies to stay consistent.
Transparency (location, fragmentation, replication) hides distribution from users but is hard to provide.
A distributed transaction needs two-phase commit (prepare, then commit) so that all sites commit or all abort.
Recovery must handle site and link failures, and distributed deadlock needs global detection.

Asked: [7 marks] (Jun 2024) Discuss the challenges associated with distributed database management, such as data fragmentation, replication, and distributed transaction management.

Data mining

Definition. Data mining is the extraction of hidden, useful patterns from large data sets, also called knowledge discovery.

Key points.

Steps: cleaning, integration, selection, mining, pattern evaluation.
Tasks: classification, clustering, association rules and prediction.
Example: market basket analysis finds that customers who buy bread also buy butter.

Data warehousing

Definition. A data warehouse is a subject-oriented, integrated, time-variant and non-volatile collection of data for decision support.

Key points.

It is fed from many sources by extract, transform, load (ETL).
OLAP runs multidimensional analysis such as roll-up, drill-down, slice and dice.
OLTP handles daily transactions, while a warehouse handles historical analytical queries.
Schemas are star and snowflake.

Object technology and DBMS

Definition. An object DBMS stores data as objects that combine state (attributes) and behaviour (methods).

Key points.

Concepts: object identity, class, encapsulation, inheritance and polymorphism.
Complex types and relationships are stored directly, avoiding joins.
The query language is OQL and the standard is ODMG.
Object-relational DBMS adds object features to relational systems.

Comparative study of OODBMS vs DBMS

Definition. An OODBMS stores data as objects with classes and inheritance, while a traditional (relational) DBMS stores data as tables of rows and columns.

Key points.

OODBMS suits complex data such as CAD, multimedia and GIS; RDBMS suits simple, structured business data.
RDBMS is mature and widely standardised, with strong tool support.
OODBMS navigates by object references, which is fast for connected data but weaker for ad hoc queries.
OODBMS removes the impedance mismatch with object-oriented programs.

Basis	OODBMS	DBMS (relational)
Data model	Objects, classes, inheritance	Tables, rows, columns
Identity	Object ID	Primary key
Query language	OQL, method calls	SQL
Relationships	Direct object references	Foreign keys and joins
Data types	Complex, user-defined	Simple built-in
Behaviour	Methods stored with data	Stored procedures separate
Standards	ODMG, less mature	SQL, very mature
Performance	Fast for complex navigation	Fast for set queries

Answer frame. Open with definitions of both; draw the table; develop data model, query, relationships, applications, performance, standards; close with which suits which scenario.

Asked: [7 marks] (Jun 2023, Jun 2024) Differentiate between OODBMS and DBMS; provide a comparative study of OODBMS vs. DBMS, highlighting their strengths and weaknesses in different scenarios.

Temporal, deductive, multimedia, web and mobile database

Definition. These are specialised databases: temporal (time-aware), deductive (rule-based), multimedia (images, audio, video), web (internet data) and mobile (intermittently connected devices).

Key points.

A temporal database stores valid time and transaction time, so history is kept.
A deductive database derives new facts from stored facts using logic rules (Datalog).
A multimedia database needs content-based retrieval and large storage.
A mobile database handles disconnection and limited bandwidth by caching and synchronising.

Last-minute revision

ACID: atomicity, consistency, isolation, durability.
Conflict pair: same item, different transactions, at least one write.
Precedence graph cycle means not conflict serializable.
Strict implies cascadeless implies recoverable.
WAL: log reaches disk before the data.
Locks: S with S is the only compatible pair.
2PL: growing then shrinking; ensures serializability, not deadlock freedom.
Strict 2PL holds X locks till commit.
TO rules: read aborts if TS < W-TS; write aborts if TS < R-TS or W-TS.
Thomas rule ignores an obsolete write.
Validation phases: read, validation, write.
Wait-die and wound-wait prevent deadlock; a wait-for cycle detects it.

Memory hooks

ACID: A tomic, C onsistent, I solated, D urable.
2PL: grow, then shrink, never both.
Wait-die: older waits; wound-wait: older wounds.
Validation: RVW (read, validate, write).
Coarse means cheap but blocking; fine means parallel but costly.

Coverage checklist

Transaction System: ACID, states.
Testing of Serializability: Jun 2023 precedence graph.
Serializability of schedules: serial vs serializable.
conflict & view serializable schedule: conflict, view.
recoverability: recoverable, cascadeless, strict.
Recovery from transaction failures: failure types, rollback.
Log based recovery: Jun 2026 log and checkpoint recovery.
Checkpoints deadlock handling: checkpoint, prevention, detection.
Concurrency Control Techniques: Concurrency Control: Jun 2026.
locking Techniques for concurrency control: Jun 2024, Jun 2026.
time stamping protocols for concurrency control: Jun 2023, Jun 2025.
validation based protocol: Jun 2025.
multiple granularity: Jun 2025.
Multi version schemes: MVCC.
Recovery with concurrent transaction: shared log, ARIES.
Introduction to Distributed databases: Jun 2024.
data mining: KDD.
data warehousing: OLAP, ETL.
Object Technology and DBMS: objects.
Comparative study of OODBMS Vs DBMS: Jun 2023, Jun 2024.
Temporal, Deductive, Multimedia, Web & Mobile database: definitions.

Account

Database Management System (AD-402) - Unit 4 Short Notes

How unit 4 is examined

Transaction System

Testing of Serializability

Serializability of schedules

Conflict and view serializable schedule

Recoverability

Recovery from transaction failures

Log based recovery

Checkpoints and deadlock handling

Concurrency control

Locking techniques for concurrency control

Timestamp ordering protocols

Validation based protocol

Multiple granularity

Multi version schemes

Recovery with concurrent transaction

Introduction to distributed databases

Data mining

Data warehousing

Object technology and DBMS

Comparative study of OODBMS vs DBMS

Temporal, deductive, multimedia, web and mobile database

Last-minute revision

Memory hooks

Coverage checklist