DBMS MODULE 3

1. Student database (attributes: sid, sname, sex, major, gpa, activity, fee)

Below I give concrete table instances, explanation which normal form they violate, and the
decomposition to the next normal form. I state keys and constraints for each result.

I. Example not in First Normal Form (1NF)

Non-1NF table (single relation):

StudentBad(

• sid, sname, sex, major, gpa, activity, fee

)

One row example:

sid sname sex major gpa activity fee

S01 Priya Sen F CS 8.5 basketball, drama 1200

Why not 1NF: the activity field contains multiple values (comma separated). 1NF requires
atomic values.

Fix to 1NF: split multi-valued attributes into separate rows (one row per activity) or create a
separate activity relation.

II. Example in 1NF but NOT in 2NF

We need a relation that is 1NF and has a composite primary key with partial dependency (some
non-key attribute depends on part of the composite key).

Relation (1NF):

StudentActivity(

• sid, activity, sname, sex, major, gpa, fee

)

Primary key: (sid, activity) — each student can have many activities.

Example rows (atomic values only):

sid activity sname sex major gpa fee

S01 drama Priya Sen F CS 8.5 1200

S01 football Priya Sen F CS 8.5 1200

Partial dependency (why not 2NF):

• sname, sex, major, gpa, fee depend only on sid (part of the composite key) — not on the
whole key (sid, activity). So partial dependency exists ⇒ not 2NF.
Convert to 2NF (remove partial dependencies):

Decompose into:

1. STUDENT(sid PK, sname, sex, major, gpa, fee)

2. STUDENT_ACTIVITY(sid FK → [Link], activity, PK(sid,activity))

Now non-key attributes (sname,sex,major,gpa,fee) are stored only in STUDENT (dependent on

whole key sid) — 2NF achieved.

Constraints:

• [Link] primary key

• STUDENT_ACTIVITY(sid,activity) primary key; sid foreign key referencing [Link]

III. Example in 2NF but NOT in 3NF

To violate 3NF while in 2NF we need a transitive dependency: a non-key attribute depends on
another non-key attribute (A → B where A is non-key and B is non-key).

Start from STUDENT(sid, sname, sex, major, gpa, fee). Add an attribute that depends on major (a
non-key attribute): e.g. dept_name.

Relation (in 2NF):

STUDENT_FULL(sid PK, sname, sex, major, dept_name, gpa, fee)

Assume FD: major → dept_name (each major belongs to a department name).

Why 2NF but not 3NF:

• Key is sid (single attribute) so there is no partial dependency — 2NF holds.

• But sid → major and major → dept_name produce a transitive dependency sid →
dept_name via major. dept_name is a non-prime attribute dependent on another non-
prime attribute (major) — violates 3NF.

Convert to 3NF:

Decompose into:

1. STUDENT(sid PK, sname, sex, major, gpa, fee)

2. MAJOR_INFO(major PK, dept_name)

Now dept_name is stored with MAJOR_INFO and no transitive dependency remains in

STUDENT.

Constraints:

• [Link] is FK referencing MAJOR_INFO.major.

IV. Example in 3NF but NOT in BCNF (student DB instance)

BCNF is stronger than 3NF: for every FD X → Y, X must be a superkey. 3NF allows X → Y when Y is
a prime attribute even if X not a superkey.

A typical textbook pattern for 3NF but not BCNF uses an FD whose left side is not a superkey but
whose right side is a prime attribute (part of some candidate key).

Concrete student example:

Relation: ENROLLMENT(activity, fee, sid)

Suppose:

• A student can enroll in many activities; composite PK (sid, activity).

• Suppose the policy: activity → fee (each activity has a fixed participation fee).

• Suppose for some reason there is a candidate key that includes fee (e.g., unusual model
where (sid, fee) together can be a candidate key in some contrived design — but to keep
it realistic: we can show a standard textbook example instead).

However, making a realistic student example that is 3NF but not BCNF can be confusing in
natural student schemas. So here I give the standard canonical example (adapt it to student
domain):

Canonical example (adapted):

R(activity, fee, organizer)
FDs:

• activity → fee (each activity has a fixed fee)

• fee → organizer (each fee amount is associated with a particular organizer) — contrived
but possible if only one organizer charges a specific fixed fee

Assume candidate keys are {activity, organizer} (or some keys where fee participates in a key) so
that fee is a prime attribute. Then:

• activity → fee has LHS not a superkey ⇒ BCNF violated.

• But if fee is prime (part of some candidate key), 3NF allows it. So the relation can be in
3NF but not BCNF.

Decomposition to BCNF: Decompose on the violating FD activity → fee into:

1. R1(activity, fee)

2. R2(activity, organizer)

R1 holds the activity→fee rule and is BCNF; R2 holds remaining attributes.

(If you want a strictly student-domain, fully realistic 3NF-but-not-BCNF example, I can produce
one with a clear candidate-key calculation — tell me and I'll make it explicit.)

V. Why higher normal forms (4NF, 5NF, DKNF)? Which is the highest?

Short answer and intuition:

 • 4NF (Fourth Normal Form): removes multi-valued dependency anomalies. Use when
an attribute has independent multi-valued facts (example: student has multiple skills
AND multiple hobbies — skills and hobbies are independent).

• 5NF (Project-Join Normal Form / PJNF): addresses cases where a relation must be split
to avoid redundancy due to join dependencies that are not expressible as FDs. It
ensures every join dependency in the relation is implied by candidate keys.

• Domain/Key Normal Form (DKNF): the strongest (conceptual) normal form: every
constraint on the relation is a logical consequence of domain constraints and key
constraints. In practice DKNF is rare and often unnecessary.

Highest normal form in theory: Domain/Key Normal Form (DKNF) is the strongest. In practice
BCNF/4NF/5NF are more commonly considered; DKNF is more of a theoretical ideal.

2. REFRIG( M, Y, P, Mp, C ) with F = { M → Mp, MY → P, Mp → C }

Let R = (M, Y, P, Mp, C). I'll answer parts (i)–(v).

(i) Evaluate the following as candidate keys: M, MY, MC.

We compute attribute closures under F:

• Closure of M:
From M → Mp, M gives Mp. From Mp → C, M gives C. So M⁺ = {M, Mp, C}. It does not
include Y or P. So M is not a key.

• Closure of MY:
From M → Mp, MY gives Mp. From Mp → C, we get C. From MY → P, with M and Y present
we get P. So MY⁺ = {M, Y, Mp, C, P} — all attributes. So MY is a candidate key. It's
minimal because neither M alone nor Y alone is a key, so MY is minimal.

• Closure of MC:
MC contains M and C. From M → Mp you get Mp, from Mp → C gives C (already present).
You still do not get Y or P (MY → P needs Y). So MC⁺ = {M, Mp, C}. Not all attributes ⇒ MC
is not a key.

Answer: M → not a key; MY → candidate key; MC → not a key.

(ii) Is REFRIG in 3NF? Give reasons.

We check every FD X → A in F:

F contains:

1. M → Mp

2. MY → P

3. Mp → C

Candidate key(s): we found {M,Y} is a candidate key. So the prime attributes are M and Y
(attributes that appear in some candidate key).
3NF condition for each FD X → A:

• either X is a superkey, OR

• A is a prime attribute (i.e., part of some candidate key).

Check each:

1. M → Mp: LHS M is not a superkey (M⁺ ≠ all). RHS Mp is not prime (Mp is not in any
candidate key). ⇒ violates 3NF.

2. MY → P: LHS MY is a candidate key → OK.

3. Mp → C: LHS Mp is not a superkey; RHS C is not prime → violates 3NF.

Therefore REFRIG is NOT in 3NF (because of M→Mp and Mp→C).

(iii) Is REFRIG in BCNF? Give reasons.

BCNF requires for every non-trivial FD X → A that X is a superkey.

• MY → P: LHS is a superkey — OK.

• M → Mp: LHS M is NOT a superkey — violates BCNF.

• Mp → C: LHS Mp is NOT a superkey — violates BCNF.

Thus REFRIG is NOT in BCNF.

(iv) Consider decomposition D = ( R1(M, Y, P) and R2(M, Mp, C) ). Is this decomposition

lossless? Show why.

We use the standard lossless decomposition test for R = R1 ⨝ R2.

• Intersection: R1 ∩ R2 = {M}.

• Check whether (R1 ∩ R2) → R1 or → R2 using the original F (or its closure).

We ask: does M → attributes of R2 (M, Mp, C) hold?

• From M → Mp (given) and Mp → C (given), M determines Mp and then C. So M → Mp,C

holds. Thus M → (M,Mp,C) i.e. M → R2.

When the intersection {M} functionally determines all attributes of one of the decomposed
relations (here R2), the decomposition is lossless.

Conclusion: The decomposition into R1(M,Y,P) and R2(M,Mp,C) is lossless.

(v) Is the decomposition dependency-preserving?

We must check whether every FD in the original set F can be checked (enforced) using the FDs
that hold on the decomposed relations (i.e., projections of F onto R1 and R2) without doing a
join.
Project F onto R1(M,Y,P):

• From original F, the only FD projected onto R1 is MY → P (since it uses only M,Y,P).

Project F onto R2(M,Mp,C):

• From original F, the FDs whose attributes are subset of R2 are: M → Mp and Mp → C.

All original FDs are present in the projection sets:

• M → Mp: in R2

• Mp → C: in R2

• MY → P: in R1

Therefore the decomposition is dependency-preserving.

Summary for Q2:

• Candidate key(s): {M, Y} is a candidate key (MY).

• REFRIG is not in 3NF and not in BCNF.

• Decomposition R1(M,Y,P), R2(M,Mp,C) is lossless and dependency-preserving.

Q3 — Relation

R = (A B C D E F G)
F = { AB → CD, AF → D, DE → F, C → G, F → E, G → A }

(i) Candidate keys of R — full reasoning

First note which attributes appear on RHS of some FD: {C, D, F, G, E, A}.
The only attribute not on any RHS is B, so B must appear in every key.

We need minimal sets X such that X⁺ (closure under F) = {A,B,C,D,E,F,G}.

Test small combinations including B:

• {A, B, F}:

o AB → C,D ⇒ add C, D

o C → G ⇒ add G

o G → A ⇒ A already present

o F → E ⇒ add E

o With D,E we also have DE → F (already have F)

=> closure = all attributes. So {A,B,F} is a key. Minimality: neither {A,B}, {A,F}, nor
{B,F} closes to all, so it is minimal.

• {B, C, F}:
 o C → G ⇒ add G

o G → A ⇒ add A

o AB → C,D: with A and B we get C (already) and D

o F → E ⇒ add E
=> closure = all attributes. Minimal (no subset closes), so {B,C,F} is a key.

• {B, G, F}:

o G → A ⇒ add A

o with A,B ⇒ AB → C,D ⇒ add C,D

o F → E ⇒ add E
=> closure = all attributes. Minimal as well. So {B,G,F} is a key.

You can check there are no smaller keys. So the candidate keys are:
{A, B, F}, {B, C, F}, {B, G, F}.

(Observation: each key contains B and F, plus one of {A,C,G}.)

(ii) Apply closure algorithm and find closure of F (interpretation & useful attribute
closures)

If by “closure of F” we mean compute attribute closures to find keys / implications, useful

closures are:

• A⁺ = {A} (no FD with A alone on LHS)

• B⁺ = {B}

• C⁺ = {C, G, A}

• D⁺ = {D}

• E⁺ = {E}

• F⁺ = {F, E} (by F → E)

• G⁺ = {G, A}

We also computed useful multi-attribute closures:

• AB⁺ = {A,B,C,D,G}

• AF⁺ = {A,F,D,E}

• CF⁺ = {A,C,D,E,F,G}

• BCF⁺ = all attributes → {B,C,F} is a key

• ABF⁺ = all attributes → {A,B,F} is a key

(If you intended the set of all FDs implied by F (theoretic F⁺), that set is large. For normal
form work we normally compute closures of attribute sets and produce a minimal/canonical
cover — see next part.)

(iii) Minimal (canonical) cover of F

Start with F:

1. AB → C D → split to AB → C and AB → D

2. AF → D

3. DE → F

4. C → G

5. F → E

6. G → A

Now check extraneous LHS attributes and redundant FDs:

• All LHS sides are already minimal (no single attribute can be removed without losing the
FD).

• None of the FDs is implied by the others (test removing each one and computing
closures shows they are necessary).

So a minimal / canonical cover (RHS split into singletons) is:

Gc = { AB → C, AB → D, AF → D, DE → F, C → G, F → E, G → A }

(You may present them grouped: AB→C,D; AF→D; DE→F; C→G; F→E; G→A.)

(iv) Is R in 1NF / 2NF? If not convert

• 1NF: Problem statement says atomic values ⇒ R is in 1NF.

• 2NF check: 2NF concerns partial dependency of non-prime attributes on part of a

candidate key.
Candidate keys (found above) have size 3. Prime attributes (appear in some candidate
key) = {A, B, F, C, G}. Non-prime attributes = {D, E}.

We have AB → D and AF → D. Both AB and AF are proper subsets of the candidate key {A,B,F}
and they determine D (a non-prime attribute). That is a partial dependency, so R is NOT in
2NF.

Convert to 2NF (one correct decomposition): remove relations that express partial
dependencies so that non-prime attributes are not partially dependent on part of a key. One
reasonable 2NF decomposition (lossless, dependency-preserving for this case) is:

• R1( A, B, C, D ) — captures AB → C, D (PK: AB)

• R2( A, F, D, E ) — captures AF → D and F → E and DE → F (PK: AF)

• R3( C, G ) — captures C → G (PK: C)

(You can also include R4(G,A) for G→A if you want to keep that FD separately, but R3 plus
R1/R2 allow derivation of G and A as needed.)

This decomposition eliminates the partial dependency problem because in each relation
the determinant is a key of that relation.

(v) Is R in 3NF / BCNF? If not convert (and provide relations, check lossless /
dependency preserving)

Check 3NF for original R: 3NF requires for each nontrivial X→Y either:

• X is a superkey, or

• each attribute in Y is prime.

Look at FDs:

• AB → C: AB is not a superkey (AB⁺ ≠ all), but C is a prime attribute (C is in candidate key

{B,C,F}). So AB→C does not violate 3NF (because RHS attribute C is prime).

• AB → D: AB not superkey; D is non-prime ⇒ violates 3NF.

• AF → D: AF not superkey; D non-prime ⇒ violates 3NF.

• DE → F: DE not a superkey (DE⁺ not all) and F is prime (F is in all candidate keys) — since
F is prime this FD does not violate 3NF.

• C → G: C not superkey but G is prime (G appears in candidate key {B,G,F}) — OK for 3NF.

• F → E: F not superkey; E is non-prime ⇒ violates 3NF.

• G → A: G not superkey; A is prime (A appears in key {A,B,F}) — OK.

So because AB→D, AF→D, and F→E have non-prime RHS with non-superkey LHS, R is NOT in
3NF.

Canonical 3NF decomposition (algorithm via minimal cover): For each FD X→Y in
canonical cover make relation (X ∪ Y). Using our canonical cover, form relations:

• R1( A, B, C ) from AB→C

• R2( A, B, D ) from AB→D

• R3( A, F, D ) from AF→D

• R4( D, E, F ) from DE→F

• R5( C, G ) from C→G

• R6( F, E ) from F→E

• R7( G, A ) from G→A

Then ensure at least one relation contains a candidate key of R. Our candidate key {A,B,F} is
not contained in any single relation above, so add:
• Rkey( A, B, F )

This classical 3NF decomposition is:

{ R1(AB C), R2(AB D), R3(AF D), R4(DE F), R5(CG), R6(F E), R7(G A), Rkey(A B F) }

Properties:

• It is dependency-preserving (each original FD appears in the projection on one of the

relations).

• It can be shown to be lossless because the added Rkey relation contains a key of the
original R and the decomposition was built from the canonical cover.

BCNF check: In each of the relations above the FDs used to create them have left sides that
are keys for that relation (e.g., in R4, DE→F, DE is a key for R4; in R6, F→E F is key for R6; etc.).
So each of these component relations is in BCNF. Therefore the canonical decomposition
into those relation schemas yields relations that are BCNF. (The original R was not BCNF,
because it had FDs like M→Mp analogs where LHS is not a superkey.)

Q4 — Relation

R(A, B, C, D, E, F, G, H, I, J)
Functional dependencies:
FD = { AB → C, A → DE, B → F, F → GH, D → IJ }

(i) What is the key for R?

Find attributes that never appear on RHS: scanning RHS values {C, D, E, F, G, H, I, J} — both
A and B do not appear on RHS. So both must be in any key. Compute AB⁺:

• From AB → C add C

• From A → DE add D, E

• From D → I,J add I, J

• From B → F add F

• From F → G,H add G,H

Thus AB⁺ = {A,B,C,D,E,F,G,H,I,J} = all attributes. So AB is a key. Minimality: A alone and B

alone do not close to all ⇒ AB is a candidate key (in fact the candidate key).

(ii) Is R in 2NF? If not, convert

2NF: since AB is a composite key, check for partial dependencies (some non-prime attr
dependent on part of the key).

• A → D,E: A is part of key AB and D,E are non-prime (do not appear in any candidate key)
⇒ partial dependency ⇒ not 2NF.

• B → F: B is part of key AB and F is non-prime ⇒ also a partial dependency.

So R is NOT in 2NF.
Decomposition to 2NF (example):
Separate the partial dependencies so that attributes dependent on a single part are in
separate relations:

• R1( A, D, E, I, J ) — because A → D,E and D → I,J. Here A is the key of R1. (D→IJ is kept
inside R1.)

• R2( B, F, G, H ) — because B → F and F → G,H. Here B is the key of R2.

• R3( A, B, C ) — because AB → C and AB is the key for the original relation.

This decomposition removes partial dependencies: D and E now depend on A within R1 (A is

the full key of R1); F,G,H depend on B within R2 (B is the full key of R2); AB→C remains in R3.

(You can treat R1 and R2 as the 2NF components and R3 as the linking relation. This
decomposition is intuitive and commonly used in normalization exercises.)

(iii) Is R in 3NF? If not, convert

Compute minimal cover first (split RHS):

FDs broken into single RHS:

• AB → C

• A→D

• A→E

• B→F

• F→G

• F→H

• D→I

• D→J

All LHS are minimal; no FD is redundant.

3NF decomposition (from canonical cover): create a relation for each FD of the canonical
cover:

• R1( A, D, E ) from A → D, A → E (A is key here)

• R2( B, F ) from B → F (B is key)

• R3( F, G, H ) from F → G, F → H (F is key)

• R4( D, I, J ) from D → I, D → J (D is key)

• R5( A, B, C ) from AB → C (AB is key here)

We must ensure at least one relation contains a candidate key of the original relation; R5(
A,B,C ) contains AB so OK.

This decomposition:
• is dependency-preserving (every original FD appears in some relation),

• and by construction each relation has the FD determinant as a key of that relation. So
each component relation is in 3NF, and in fact each is in BCNF (because determinant is
key for that component).

Hence the above canonical 3NF decomposition is correct; you can also combine some
relations if you want (e.g. R1 and R4 could be merged into (A,D,E,I,J) because D→IJ is still
preserved there).

(iv) Find the closure of the set FD (F⁺) — practical closures

If by closure you mean calculate closures to check keys and implications: useful closures
are:

• A⁺ = {A, D, E, I, J} (A → D,E ; D → I,J)

• B⁺ = {B, F, G, H} (B → F ; F → G,H)

• AB⁺ = all attributes (AB is key)

• F⁺ = {F, G, H}

• D⁺ = {D, I, J}

If you want the full implied FD set F⁺ (all FDs implied by FD), it can be deduced from the
minimal cover above (every FD that can be computed from closures of LHS sets).

(v) Find the closure of attribute A (A⁺)

As computed:

• From A → D,E add D,E

• From D → I,J add I,J

No other FD gives new attributes from {A,D,E,I,J}. So:

A⁺ = { A, D, E, I, J }.

MODULE - 5
1. Break down the role of each ACID property and analyze the consequences of their
violation.

ACID stands for Atomicity, Consistency, Isolation, Durability. These properties ensure
reliable transaction processing.

1. Atomicity

Atomicity ensures a transaction is treated as a single indivisible operation—either all steps

happen or none happen.

• Role: Guarantees complete execution of a transaction.

• Violation Consequence:

o Partial updates occur.

o Inconsistent or corrupt data (e.g., money deducted from one account but not
credited to another).

2. Consistency

Consistency ensures that a transaction takes the database from one valid state to another
valid state, maintaining integrity constraints.

• Violation Consequence:

o Constraint violations (e.g., negative balance, broken foreign keys).

o Database no longer represents correct information.

3. Isolation

Isolation ensures that concurrent transactions do not interfere with each other.

• Violation Consequence:

o Dirty reads

o Lost updates

o Non-repeatable reads

o Phantom reads
These lead to inconsistent query results.

4. Durability

Durability ensures that committed data is permanently saved, even if the system crashes.

• Violation Consequence:

o Loss of committed transactions

o System restores old data, causing reliability issues.

Conclusion

ACID properties together guarantee that transactions maintain database correctness.

Violating any property impacts correctness, integrity, and reliability of the system.

2. Justify the need for serializability in concurrent transaction processing with real-life
consequences of ignoring it.

Serializability ensures that the outcome of concurrent transactions is equivalent to some

serial execution order.

Need for Serializability

1. Guarantees correctness under parallel execution.

2. Prevents inconsistent or unexpected results.

3. Allows maximum concurrency without compromising reliability.

Problems if serializability is ignored

1. Dirty Read – T1 reads uncommitted data written by T2.

Banking Example: Balance shows incorrect value.

2. Lost Update – Two transactions modify the same data; one overwrites the other.
Example: Two people withdrawing money simultaneously; one withdrawal disappears.

3. Non-Repeatable Read – A transaction reads different values for the same item.
Example: E-commerce stock count changes mid-process.

4. Phantom Read – Different number of rows appear in repeated queries.

Example: New orders appear unexpectedly during report generation.

Real-Life Consequences

• Wrong financial records in banks

• Incorrect online inventory

• Duplicate bookings in travel systems

• Corrupted billing data in telecom systems

Conclusion

Serializability ensures predictable and correct results in multi-user database systems. It is

essential to avoid data corruption and maintain integrity.

3. Illustrate log-based recovery using undo and redo operations for a system crash
situation.

Log-based recovery records actions in a log file before applying them to the database
(Write-Ahead Logging – WAL).

Example Log

<T1 start>

<T1, X, 20, 30>

<T2 start>

<T2, Y, 50, 60>

<T1 commit>

<System Crash>

Case 1: Transaction committed → REDO

• T1 has committed before crash → Redo T1

• Reapply T1’s updates even if already done

• X = 30

Case 2: Transaction not committed → UNDO

• T2 did not commit → Undo T2

• Restore old value

• Y = 50

Steps in Recovery

1. Scan log backward:

o Undo all uncommitted transactions.

2. Scan log forward:

o Redo all committed transactions.

Result

• Database returns to a correct state.

• No committed change is lost (Durability).

• No partial update remains (Atomicity).

4. Analyze the differences between recoverable, cascadeless, and strict schedules

with examples.

1. Recoverable Schedule

A schedule where a transaction commits only after the transaction from which it read data
has committed.

Example:
T2 reads X written by T1 → T2 commits after T1 commits.

Advantage: Avoids cascading aborts.

Disadvantage: Not as strong as cascadeless or strict.

2. Cascadeless Schedule

T2 cannot read uncommitted data written by T1.

Example:
T2 reads X only after T1 commits.

Advantage: No cascading rollback.

Better than recoverable.
3. Strict Schedule

A transaction cannot read or write a data item modified by another uncommitted

transaction.

Example:
T2 cannot read or write X until T1 commits/aborts.

Advantage:

• Easiest recovery

• Guarantees no lost updates

• Used in real DBMS

Hierarchy
Strict → Cascadeless → Recoverable

5. Differentiate between shadow paging and log-based recovery protocols and identify
scenarios best suited for each.

Shadow Paging

• Maintains a shadow copy of pages.

• At commit: swap shadow and current page tables.

• No undo/redo logs needed.

Advantages:

• No log storage

• Fast commit

Disadvantages:

• Page fragmentation

• High copying cost

• Not good for large DBs

Best for:
Small databases, embedded systems, simple transactional workloads.

Log-Based Recovery

• Maintains log records for all updates.

• Uses WAL, undo, redo.

• Efficient for large, concurrent databases.

Advantages:
• Supports fine-grained recovery

• Efficient for large multi-user systems

• Supports checkpoints

Best for:
Commercial RDBMS (Oracle, MySQL), large-scale transaction systems.

6. Recommend a suitable recovery strategy for a distributed database system based on

the nature of updates and failures.

Requirements in Distributed Systems

• Network failures

• Site failures

• Message delays

• Coordinated commits

Recommended Strategy: Two-Phase Commit (2PC) + Log-Based Recovery

Why 2PC?

• Ensures global atomicity

• All sites either commit or abort

• Coordinator prepares and commits

Why Log-Based Recovery?

• Logs stored locally at each site

• Redo/Undo possible even after site crash

• Supports checkpoints for faster recovery

Nature of failures & solution

1. Site Crash:

o Use local logs → redo/undo.

2. Coordinator Failure:

o Participants follow 2PC protocol rules.

3. Network Failure:

o Timeouts → abort safely.

Conclusion

2PC combined with log-based recovery ensures reliable and synchronized recovery across
distributed nodes.
7. Design a transaction schedule that is recoverable but not cascadeless, and explain
the implications.

Schedule

T1: W(X)

T2: R(X)

T1: Commit

T2: Commit

Properties

• Recoverable:
T2 reads X from T1, and commits after T1 commits → OK.

• Not Cascadeless:
T2 read X before T1 commits → violates cascadeless rule.

Implications

1. If T1 aborts, T2 must also abort → cascading rollback.

2. Increases recovery cost.

3. More complex error handling.

4. Lower system performance.

8. Assess the pros and cons of using immediate update recovery methods in mission-
critical systems.

Immediate Update

Changes are written to the database before commit, but undo logs are maintained.

Pros

1. Fast execution – pages updated immediately.

2. Supports concurrency – useful for high-transaction environments.

3. Allows partial writes → Reduces buffering overhead.

4. Crash recovery possible using undo logs.

Cons

1. Requires both undo and redo, increasing complexity.

 2. Higher chance of inconsistent data during crash.

3. Difficult to implement in distributed environments.

4. More log management cost.

Suitability

Useful for mission-critical systems ONLY when:

• Strong recovery mechanism (WAL + strict schedules) is present.

• System requires high concurrency (banking, stock markets).

MODULE – 6 (Concurrency Control)

10-MARK ANSWERS

1. Implement a concurrency control mechanism using time-stamp ordering protocol for

two conflicting transactions.

Given:

Two conflicting transactions T1 and T2 both operate on data item X.

Let:

• TS(T1) = 5

• TS(T2) = 10

Case Example:

T1: W(X)

T2: R(X)

Timestamp Ordering Rules

Each data item maintains:

• R-TS(X): Largest timestamp of any transaction that read X

• W-TS(X): Largest timestamp of any transaction that wrote X

Initially,
R-TS(X) = 0,
W-TS(X) = 0.
Step-by-step Execution

Step 1 – T1 issues W(X)

Check condition:
If TS(T1) < R-TS(X) → reject
If TS(T1) < W-TS(X) → reject

Here:
TS(T1)=5 > R-TS(X)=0
TS(T1)=5 > W-TS(X)=0 → Write allowed

Update:
W-TS(X)=5, X updated.

Step 2 – T2 issues R(X)

Check condition:
If TS(T2) < W-TS(X) → reject (T2 would read obsolete value)

Here:
TS(T2)=10 > W-TS(X)=5 → Read allowed

Update:
R-TS(X)=10

Final Outcome

• T1 writes first

• T2 reads later

• No rollback

• Serializability order: T1 → T2

This demonstrates a conflict resolved using timestamp ordering without deadlock or starvation.

2. Illustrate the Thomas Write Rule with a practical example and show how it differs from
basic time-stamp protocol.

Basic Time-Stamp Write Rule

If an older transaction tries to write after a newer write, it is rejected and rolled back.

Thomas Write Rule (TWR)

Allows ignoring an obsolete write instead of aborting the transaction.

Example
TS(T1) = 5
TS(T2) = 10

Operations:

T2: W(X) → allowed (W-TS(X)=10)

T1: W(X) → older write comes AFTER the newer write

Under Basic TO Protocol

T1 is aborted because TS(T1)<W-TS(X).

Under Thomas Write Rule

• Check: TS(T1) < W-TS(X) → obsolete write

• Ignore T1’s write instead of aborting T1

• Do not update X or timestamp

Difference Summary

Feature Basic TO Protocol Thomas Write Rule

Obsolete writes Cause abort Ignored safely

Abort rate High Low

Throughput Lower Higher

Correctness Conflict-serializable View-serializable

Thomas Write Rule improves performance while still maintaining view-serializability.

3. Analyze the difference between lock-based and timestamp-based concurrency control

techniques.

Lock-Based Protocols

• Use shared (S) and exclusive (X) locks

• Follow 2-Phase Locking (2PL): growing + shrinking phase

• Prevent conflicts through blocking

Problems

• Deadlocks

• Cascading rollbacks

• Lock table overhead

Timestamp-Based Protocols

• Every transaction gets a timestamp

• Operations ordered by timestamp

• Prevent conflicts using validation rather than locking

• No blocking → no deadlock

Problems

• High abort rate when timestamps conflict

• Costly timestamp maintenance

Comparison Table

Feature Lock-Based Timestamp-Based

Control Mechanism Locks Timestamps

Deadlocks Yes No

Blocking Yes No

Abort Rate Low High

Throughput Lower Higher

Suitability High contention Low contention, read-heavy

4. Compare the working of two-phase locking protocol with the tree protocol in terms of
transaction safety and performance.

Two-Phase Locking (2PL)

Working:

• Growing phase → acquire locks

• Shrinking phase → release locks

• Guarantees conflict serializability

Performance:

• Causes deadlocks

• Higher waiting time

• Good for general-purpose workloads

Tree Protocol

Working:

• Locks must be acquired following a tree structure

• A transaction cannot lock a node unless it locked its parent first

• Released locks cannot be reacquired

Properties:

• Deadlock-free

• Does not guarantee serializability in all cases

• Works best for indexed data structures

Comparison Table

Feature 2PL Tree Protocol

Deadlock Possible Impossible

Serializability Always guaranteed Not always guaranteed

Locking freedom Any order Must follow tree

Performance Slower under contentions Fast for hierarchical access

Applications Databases Index traversal (B-trees)

5. Assess the trade-offs between pessimistic and optimistic concurrency control.

Pessimistic Concurrency Control

(Example: 2PL, locking)

Pros

• Prevents conflicts in advance

• Ensures safety in high-contention environments

• Good for mission-critical databases (banking)

Cons

• High waiting time due to blocking

• Deadlocks possible

• Reduced throughput
Optimistic Concurrency Control

(Example: Validation, timestamp-based)

Pros

• No blocking → high concurrency

• No deadlock

• High performance in low-contention environments

Cons

• High abort rate

• Expensive validation checks

• Wasteful if many transactions conflict

Trade-off Summary

• High contention → Pessimistic best

• Low contention → Optimistic best

• Must balance abort rate vs waiting time.

6. Devise your own deadlock prevention strategy using ordering of resource allocation and
explain how it works.

Strategy: Global Resource Ordering (GRO)

1. Assign a unique order to each database resource.

Example:

2. X < Y < Z < A < B

3. Each transaction must request resources in increasing order only.

4. A transaction can request X before Y, but never Y before X.

Why it prevents deadlock

Deadlock requires a cycle in the wait-for graph.

Global ordering ensures:

• No cycle can form

• All waits are unidirectional

• Therefore, deadlock becomes impossible

Example
T1 requests X → allowed
T2 requests Y → allowed
T1 requests Y → allowed (X < Y)
T2 requests X → not allowed (violates order)

Thus cycle avoided.

7. Create a complete locking protocol that includes lock conversion, compatibility checks,
and deadlock avoidance.

Proposed Protocol: Enhanced Dynamic Locking Protocol (EDLP)

1. Lock Types

• S (Shared) → read

• X (Exclusive) → write

• IS, IX, SIX → intention locks (for multi-granularity)

2. Lock Conversion

• S → X allowed (upgrade)

• X → S allowed (downgrade)

• Rules:

o Upgrades only during growing phase

o Downgrades only during shrinking phase

3. Compatibility Matrix

Request Held S Held X

S ✓ ×

X × ×

4. Deadlock Avoidance

Use Wait-Die protocol:

• If older transaction waits → allowed

• If younger waits → abort

Ensures no cycle.
Protocol Steps

1. Check lock compatibility

2. If compatible → grant lock

3. If conflicting → apply Wait-Die

4. Allow conversions under phase rules

5. Maintain intention locks for hierarchies

6. Release all locks at commit

This protocol ensures:

• High concurrency

• No deadlocks

• Multi-level locking supported

8. Critically evaluate how multi-granularity locking can help optimize database

performance.

What is Multi-Granularity Locking?

Allows locking at different levels:

• Database

• Table

• Page

• Row

Uses intention locks (IS, IX, SIX) to coordinate locking at multiple levels.

Benefits

1. Improves Concurrency

• Allows row-level operations while table-level transactions continue

• Reduces unnecessary blocking

2. Reduces Locking Overhead

• Large operations (e.g., backup) lock at higher levels

• Small operations lock only required rows

3. Avoids Conflicts
Intention locks ensure safety:

• IX on table prevents conflicting operations at row level

4. Supports Hierarchical Access

Especially useful in:

• B-trees

• Index scans

5. Balances Performance & Safety

• Fine-grained locks: more concurrency

• Coarse-grained locks: less overhead

Drawbacks

• Complex implementation

• More lock types to maintain

• Additional lock table overhead

MODULE – 7
1. Explain how the CAP theorem influences the design of distributed NoSQL systems. (10
Marks)

CAP Theorem (proposed by Eric Brewer) states that a distributed database cannot
simultaneously guarantee all three properties:

1. Consistency (C) – Every read returns the most recent write.

2. Availability (A) – Every request gets a response, even if some nodes fail.

3. Partition Tolerance (P) – The system continues to work even when network failures
occur and nodes cannot communicate.

In a distributed environment, network partitions are unavoidable, so systems must choose

either Consistency or Availability when a partition happens.

Influence on NoSQL Design

1. Trade-off Decisions
NoSQL databases are designed based on which two properties they prioritize:

o AP systems (Availability + Partition tolerance)

Eventual consistency, fast responses.
Examples: Cassandra, Riak, DynamoDB.
 o CP systems (Consistency + Partition tolerance)
Strong consistency, may reduce availability.
Examples: MongoDB, HBase, Bigtable.

2. Replication Strategies
AP systems replicate data asynchronously to maximize availability.
CP systems use synchronous replication to ensure consistent copies.

3. Consistency Models
CAP leads to different consistency levels:

o Strong Consistency (CP)

o Eventual Consistency (AP)

o Causal Consistency

o Read-your-write consistency

4. System Architecture Choices

o Master–slave vs. peer-to-peer replication

o Quorum-based reads/writes (DynamoDB, Cassandra)

5. Application-Specific Design
The choice depends on system requirements:

o Banking → CP (strong consistency)

o Social media, IoT → AP (high availability)

Conclusion

CAP theorem guides NoSQL architects to balance consistency, availability, and partition
tolerance, influencing core database design, replication, query behaviour, and application
suitability.

2. Compare the features of Document databases and Graph databases with real-world use
cases. (10 Marks)

Feature Document Databases Graph Databases

Data Model JSON/XML documents Nodes & edges (graph)

Schema Schema-less Schema-flexible

Focus Storing semi-structured data Storing relationships

Query Language MongoDB Query, CouchDB queries Cypher (Neo4j), Gremlin

Best for Hierarchical, nested data Highly interconnected data

Feature Document Databases Graph Databases

Strength Flexible documents, indexing Faster relationship traversal

Scalability Horizontally scalable Scales well with graph partitioning

Document DB Use Cases

1. E-commerce product catalogs

Products vary in attributes; document model handles flexible schemas.

2. Content Management Systems (CMS)

Blog posts, metadata, comments stored easily.

3. User Profiles
User preferences and settings stored as JSON.

Examples: MongoDB, CouchDB, Firebase Firestore.

Graph DB Use Cases

1. Social Networks
Represent friends, followers, relationships.

2. Recommendation Engines
“Users similar to you also bought…”

3. Fraud Detection
Detects relationship patterns between accounts, transactions.

Examples: Neo4j, Amazon Neptune, JanusGraph.

Conclusion

Document databases focus on flexible storage of semi-structured data, while graph databases
excel at fast relationship querying and complex graph traversal.

3. Write short notes on: (10 Marks)

(a) Column-family databases

• Store data in columns, grouped into column families.

• Designed for distributed, high-performance read/write operations.

• Based on Google Bigtable model.

• Supports sparse data, wide tables, and horizontal scalability.

• Excellent for analytical workloads.

Use Cases:
Time-series data, IoT sensor data, logs, large-scale analytics.

Examples: Cassandra, HBase, ScyllaDB.

(b) Key-value stores

• Simplest NoSQL model: key → value pairs.

• Values can be strings, JSON, blobs, or objects.

• Extremely fast due to O(1) hash lookup.

• Ideal for high-throughput, low-latency applications.

Use Cases:
Caching (Redis), session storage, shopping cart data, leaderboards.

Examples: Redis, DynamoDB, Riak, Memcached.

4. Explain the different types of NoSQL databases in detail. Highlight their data models,
use cases, and examples. (10 Marks)

1. Key–Value Stores

• Data stored as key-value pairs.

• Use cases: Caching, session data, real-time applications.

• Examples: Redis, DynamoDB.

2. Document Databases

• Store semi-structured data in JSON-like documents.

• Use cases: CMS, product catalogs, mobile apps.

• Examples: MongoDB, CouchDB, Firebase.

3. Column-Family Stores

• Data stored into rows and dynamic columns, grouped into families.

• Use cases: Big Data storage, time-series, analytics.

• Examples: Cassandra, HBase.

4. Graph Databases

• Represent data as nodes, edges, properties.

 • Use cases: Social networking, fraud detection, recommendations.

• Examples: Neo4j, Amazon Neptune.

5. Object Databases (less common)

• Stores objects directly as in object-oriented programming.

• Use cases: Embedded systems, CAD, engineering.

• Examples: db4o, ObjectDB.

Conclusion

Each NoSQL type solves specific problems—high performance, horizontal scalability,

relationship modeling, and flexible schemas.

5. Discuss in detail how NoSQL databases support Big Data analytics and give examples
from industry. (10 Marks)

1. Handling Volume

NoSQL databases scale horizontally across clusters to store petabytes of data.

2. High Velocity Processing

Designed for rapid reads/writes; useful for streaming and real-time analytics.

3. Variety Support

Stores structured, semi-structured, and unstructured data:

• JSON

• logs

• images

• clickstreams

4. Distributed Architecture

Sharding, replication, and partitioning enable fault-tolerant analytics.

5. Integration with Big Data Ecosystem

Works with:

• Hadoop

• Spark

• Kafka

• Flink
6. Schema Flexibility

Analysts can ingest new data formats without redesigning schemas.

7. Real-world Industry Examples

• E-commerce (Amazon, Flipkart)

Use DynamoDB and Cassandra for user sessions, recommendations.

• Social Media (Facebook, Instagram)

Use Cassandra and RocksDB for message feeds and timelines.

• Finance (PayPal, Mastercard)

Use NoSQL for fraud detection and transaction analytics.

• IoT Platforms
Use time-series NoSQL databases for sensor analytics (e.g., InfluxDB).

Conclusion

NoSQL provides scalable, flexible, and high-performance solutions needed for Big Data
analytics across e-commerce, social media, IoT, and finance industries.

6. Compare RDBMS and NoSQL databases in terms of schema design, query languages,
scalability, and consistency. (10 Marks)

Feature RDBMS NoSQL

Schema Design Fixed, predefined schema Schema-less or flexible

Data Model Tables, rows, columns Key-value, document, column-family, graph

Query Language SQL MongoQL, CQL, REST APIs, Gremlin

Scalability Vertical scaling Horizontal scaling

Transactions ACID BASE (eventual consistency)

Consistency Strong consistency Tunable / eventual consistency

Best For Banking, ERP, structured data Big Data, IoT, analytics, fast-changing data

Joins Supports complex joins Limited or no joins (except graph DBs)