Database Management System (AD-402) Unit 3 Notes

How unit 3 is examined

This unit covers normalization, normal forms up to 4NF, functional and multivalued dependencies, decomposition, and query optimization. Normal forms, functional dependency (closure, equivalence) and normalization carry most of the marks.

Introduction to normalization

Medium weight

Definition. Normalization is the process of decomposing a relation into smaller well-structured relations, using functional dependencies, so that redundancy and the insertion, deletion and modification anomalies are removed.

Key points.

The objective is to minimise redundancy, because the same fact stored in many rows wastes space and can become inconsistent.
It removes update anomalies, so each fact is stored once and changed in one place.
The decomposition must be lossless: joining the parts must give back exactly the original relation, with no spurious tuples.
Ideally it is dependency preserving: every original FD can be checked on the decomposed relations without a join.
Each step moves the relation up a normal form (1NF, 2NF, 3NF, BCNF, 4NF); higher forms mean less redundancy but more joins in queries.

Example. Take EMP_DEPT(EmpID, Name, DeptID, DeptName). DeptName repeats for every employee of a department.

Insertion anomaly: a new department with no employee cannot be stored, as EmpID is the key and cannot be null.
Deletion anomaly: deleting the last employee of a department also deletes the department's name.
Modification anomaly: renaming a department must change every one of its rows, and missing one leaves inconsistent data.

Fix: EMP(EmpID, Name, DeptID) and DEPT(DeptID, DeptName).

Answer frame. Open with the definition; list the objectives as points 1-4; draw the EMP_DEPT table and show the three anomalies; close with the decomposed tables. For Q5, keep the three anomalies as the main body.

Asked: [7 marks] (Jun 2024) Explain the objectives of normalization, such as minimizing redundancy and dependency preservation. Asked: [7 marks] (Jun 2025) Illustrate insertion, deletion and modification anomalies with suitable examples.

Normal forms

Definition. A normal form is a rule on the dependencies of a relation; a relation is in a given normal form when it satisfies that rule, and each higher form removes one more kind of redundancy.

Key points.

1NF: every attribute holds one atomic (indivisible) value, so there are no multivalued attributes or repeating groups.
2NF: the relation is in 1NF and no non-prime attribute depends on part of a candidate key (no partial dependency); it matters only for composite keys.
3NF: the relation is in 2NF and no non-prime attribute depends transitively on the key; for every $X \to A$, either $X$ is a superkey or $A$ is prime.
BCNF: for every non-trivial FD $X \to Y$, $X$ must be a superkey, so every determinant is a candidate key.
4NF: the relation is in BCNF and has no non-trivial multivalued dependency other than those with a superkey on the left.
The forms nest: $4NF \subset BCNF \subset 3NF \subset 2NF \subset 1NF$.
BCNF is stricter than 3NF: 3NF allows $X \to A$ when $A$ is prime, BCNF does not.

Example (1NF and 2NF). STUDENT(RollNo, Name, Phones) with Phones = {111, 222} is not in 1NF. Give one row per phone: STU(RollNo, Name, Phone), key (RollNo, Phone). Name depends only on RollNo, a partial dependency, so it is not in 2NF. Decompose into S1(RollNo, Name) and S2(RollNo, Phone).

Example (BCNF). R(Student, Subject, Teacher) with FDs $(Student, Subject) \to Teacher$ and $Teacher \to Subject$. Keys: (Student, Subject) and (Student, Teacher). It is in 3NF as Subject is prime, but $Teacher \to Subject$ has a non-superkey determinant, so it is not in BCNF. Decompose into R1(Teacher, Subject) and R2(Student, Teacher); this is lossless as Teacher is the key of R1, but $(Student, Subject) \to Teacher$ is no longer preserved.

Example (Q8, normalise to 3NF). STUDENT(SID, Name, Course, Faculty, FacultyPhone) with $SID \to Name, Course$; $Course \to Faculty$; $Faculty \to FacultyPhone$.

Key: $SID^+$ = all attributes, so SID is the only key. It is already 1NF (atomic) and 2NF (the key is a single attribute, so no partial dependency).
$SID \to Course \to Faculty \to FacultyPhone$ are transitive dependencies, so 3NF fails.
Split on $Course \to Faculty$: STUDENT(SID, Name, Course) and R(Course, Faculty, FacultyPhone).
Split R on $Faculty \to FacultyPhone$.

Final 3NF schema: STUDENT(SID, Name, Course), COURSE(Course, Faculty), FACULTY(Faculty, FacultyPhone).

Answer frame. For Q6, open with the 1NF and 2NF conditions, draw the unnormalised table, convert to 1NF, then remove the partial dependency. For Q9, define BCNF, give the R(Student, Subject, Teacher) example, show why it fails, then decompose; add a 3NF-versus-BCNF line. For Q7, define normalization first, then 4NF with the example in the multivalued dependencies topic. For Q8, list the FDs, find the key, name the transitive chain, decompose, and box the schema.

Pitfall: BCNF and 3NF differ only when a prime attribute is determined by a non-superkey; do not say a 3NF relation is automatically BCNF.

Asked: [7 marks] (Jun 2023) Discuss the conditions required for a relation to be in 1NF and 2NF with a suitable example. Asked: [7 marks] (Jun 2025) What is Normalization? Explain about 4NF with an example. Asked: [7 marks] (Jun 2026) Consider STUDENT(SID, Name, Course, Faculty, Faculty Phone) with SID -> Name, Course; Course -> Faculty; Faculty -> Faculty Phone. Normalize the relation up to 3NF. Asked: [7 marks] (Jun 2026) What is Boyce Codd normal form (BCNF)? Explain with an example.

Functional dependency

Definition. A functional dependency $X \to Y$ holds in a relation when any two tuples that agree on $X$ also agree on $Y$; that is, $X$ determines $Y$.

Key points.

Examples: $EmpID \to Name, Dept$ (an employee has one name and department) and $(RollNo, Subject) \to Marks$.
Trivial: $X \to Y$ with $Y \subseteq X$, such as $AB \to A$. Non-trivial otherwise.
Full dependency: $Y$ depends on all of a composite $X$ and on no proper subset. Partial: $Y$ depends on only part of the key, e.g. $(RollNo, Subject) \to Name$ when $RollNo \to Name$.
Transitive: $X \to Y$ and $Y \to Z$ give $X \to Z$ through a non-key $Y$.
FDs identify keys ($K$ is a key if $K^+$ is all attributes) and drive 2NF, 3NF and BCNF.

Armstrong's axioms. Reflexivity: if $Y \subseteq X$ then $X \to Y$. Augmentation: $X \to Y$ gives $XZ \to YZ$. Transitivity: $X \to Y$, $Y \to Z$ give $X \to Z$. Derived: union ($X \to Y, X \to Z$ give $X \to YZ$), decomposition ($X \to YZ$ gives $X \to Y$) and pseudotransitivity.

Closure $F^+$ is the set of all FDs implied by $F$. Attribute closure $X^+$:

Step 1: result = X
Step 2: for each FD U -> V in F with U inside result, add V to result
Step 3: repeat Step 2 until result stops changing

$F^+$ is found by applying the axioms repeatedly; in practice, $X \to Y \in F^+$ exactly when $Y \subseteq X^+$.

Example ($F^+$). $F = \{A \to B, B \to C\}$. Then $A \to C$ (transitivity), $AD \to BD$ (augmentation), $A \to A$ (reflexivity) and $A \to BC$ (union) all lie in $F^+$; $A^+ = \{A, B, C\}$.

Example (Q3). R(A,B,C,D,E); set i) $A \to B, AB \to C, D \to AC, D \to E$; set ii) $A \to BC, D \to AE$.

Using i): $A^+ = ABC$, so $A \to BC$ holds; $D^+ = D \to AC \to E$, then $A \to B$, giving $ABCDE$, so $D \to AE$ holds. So i) implies ii).
Using ii): $A^+ = ABC$ gives $A \to B$ and $AB \to C$; $D^+ = DAE$ then $BC$, so $D \to AC$ and $D \to E$ hold. So ii) implies i).

Both sets imply each other, so they are equivalent.

Answer frame. For Q1, define $F^+$, state the three axioms, give the closure algorithm, then the example. For Q2, define $X \to Y$, give the examples, show trivial, full and partial, and close with keys and normalization. For Q3, compute closures both ways and conclude.

Asked: [7 marks] (Jun 2023) Define closure of F. Where F is the set of functional dependencies. Explain computing F+ with suitable examples. Asked: [7 marks] (Jun 2024) Provide examples illustrating functional dependencies in relational databases. Asked: [7 marks] (Jun 2025) Given below are the two sets of FD's for a relation R(A, B, C, D, E), are they equivalent? Explain. i) A -> B, AB -> C, D -> AC, D -> E; ii) A -> BC, D -> AE

Decomposition

Definition. Decomposition replaces a relation $R$ by two or more relations $R_1, \dots, R_n$ whose attributes together equal those of $R$.

Key points.

It is the tool normalization uses to remove redundancy and anomalies.
A good decomposition is lossless and, ideally, dependency preserving.
A lossy decomposition produces spurious tuples on natural join, so information is lost.
Over-decomposition makes queries need many joins.

Dependency preservation and lossless join

Definition. ==A decomposition of $R$ into $R_1, R_2$ is lossless if $R_1 \bowtie R_2 = R$, and dependency preserving if $(F_1 \cup F_2)^+ = F^+$.==

Key points.

Lossless test for two relations: $R_1 \cap R_2 \to R_1$ or $R_1 \cap R_2 \to R_2$, i.e. the common attributes form a key of one part.
Dependency preservation lets every FD be checked inside a single relation, avoiding joins on update.
Decomposition into BCNF is always lossless but may lose dependencies; decomposition into 3NF can always be both.
Example: R(A,B,C) with $A \to B$ splits losslessly into (A,B) and (A,C), since A is the key of (A,B).

problems with null valued and dangling tuples

Definition. A null is a marker for an unknown or inapplicable value; a dangling tuple is a tuple that has no matching tuple in the relation it is joined or referenced with.

Key points.

Nulls waste space, make comparisons three-valued (true, false, unknown) and give wrong results in aggregates and joins.
Nulls in a join attribute make tuples vanish from a natural join, so information is lost.
Dangling tuples appear in a join result only under an outer join; the natural join drops them.
Referential integrity (foreign key constraints) prevents dangling tuples, and good design avoids nullable attributes.

multivalued dependencies

Definition. A multivalued dependency $X \twoheadrightarrow Y$ holds in $R(X, Y, Z)$ if, for each $X$ value, the set of $Y$ values is independent of the $Z$ values, i.e. the tuples $(x,y,z_1)$ and $(x,y',z_2)$ imply $(x,y,z_2)$ and $(x,y',z_1)$ also exist.

Key points.

MVDs arise when two independent multivalued facts about the same key are stored in one relation.
Every FD is an MVD, but not conversely; an MVD is trivial if $Y \subseteq X$ or $X \cup Y = R$.
MVDs come in pairs: $X \twoheadrightarrow Y$ implies $X \twoheadrightarrow Z$ (complementation).
4NF: a relation is in 4NF if it is in BCNF and, for every non-trivial $X \twoheadrightarrow Y$, $X$ is a superkey.
Decompose a violating relation into $R_1(X,Y)$ and $R_2(X,Z)$; this is lossless.

Example. COURSE(Course, Teacher, Book) with $Course \twoheadrightarrow Teacher$ and $Course \twoheadrightarrow Book$. All three attributes form the key, so it is in BCNF, but a course with 2 teachers and 3 books needs 6 rows, repeating every teacher with every book. Course is not a superkey, so 4NF fails. Decompose into CT(Course, Teacher) and CB(Course, Book): 2 + 3 rows, no redundancy.

Answer frame. Open with the MVD definition and notation; draw the COURSE table with its 6 rows; state the 4NF condition; show the two-table decomposition; close by noting the redundancy is eliminated.

Asked: [7 marks] (Jun 2024, Jun 2026) Discuss the role of fourth normal form (4NF) in handling multivalued dependencies. What is multivalued dependency and Fourth Normal Form (4NF) with proper example.

Query Optimization: Introduction

Definition. Query optimization is choosing, from the many equivalent ways to evaluate a query, the execution plan with the lowest estimated cost.

Key points.

SQL states what is wanted; the optimizer decides how, so the same query can differ enormously in cost.
Cost is mainly disk I/O (block transfers), plus CPU and memory use.
The optimizer works on the relational algebra form of the query.
It is done automatically by the DBMS, so the user need not write efficient code.

steps of optimization

Definition. Query processing turns a SQL query into a chosen execution plan through parsing, translation, optimization and evaluation.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-01" viewBox="0 0 527.2 80" width="527.2" height="80" role="img" aria-label="SQL, parser, translator, optimizer, evaluation engine"><style>#dsfig-u3-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-01 .t{fill:#16181D;font-weight:500}#dsfig-u3-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-01 .dot{fill:#16181D}#dsfig-u3-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-01 .ah{fill:#454C5A}#dsfig-u3-01 .ah.hi{fill:#2340B8}#dsfig-u3-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-01 .e{stroke:#B1B7C3}html.dark #dsfig-u3-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-01 .t{fill:#E6E8ED}html.dark #dsfig-u3-01 .t.inv{fill:#0F1115}html.dark #dsfig-u3-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-01 .dot{fill:#E6E8ED}html.dark #dsfig-u3-01 .ann{fill:#8FA3FF}html.dark #dsfig-u3-01 .lbl{fill:#858D9C}html.dark #dsfig-u3-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-01 .ah{fill:#B1B7C3}html.dark #dsfig-u3-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" 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="ahh3" 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 L130.8,40" marker-end="url(#ah3)"/><path class="e" d="M170.8,40 L242.6,40" marker-end="url(#ah3)"/><path class="e" d="M282.6,40 L354.4,40" marker-end="url(#ah3)"/><path class="e" d="M394.4,40 L466.2,40" marker-end="url(#ah3)"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">SQL</text><circle class="n" cx="151.8" cy="40" r="18"/><text class="t" x="151.8" y="40" dy=".35em" text-anchor="middle">Par</text><circle class="n" cx="263.6" cy="40" r="18"/><text class="t" x="263.6" y="40" dy=".35em" text-anchor="middle">Tra</text><circle class="n" cx="375.4" cy="40" r="18"/><text class="t" x="375.4" y="40" dy=".35em" text-anchor="middle">Opt</text><circle class="n" cx="487.2" cy="40" r="18"/><text class="t" x="487.2" y="40" dy=".35em" text-anchor="middle">Eva</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">SQL, parser, translator, optimizer, evaluation engine</figcaption></figure>

Key points.

Parsing checks syntax and relation names and builds a parse tree.
Translation converts it into a relational algebra expression or query tree.
Optimization applies equivalence rules (heuristic) and estimates costs (cost-based) to pick the cheapest plan; for example, push selections below joins.
Evaluation executes the chosen plan and returns the result.

Asked: [7 marks] (Jun 2023) List and explain the steps for optimizing the Query.

various algorithms to implement select

Definition. Selection $\sigma_{cond}(R)$ is implemented by a file scan or an index scan, chosen by the condition and the available indexes.

Key points.

Linear search scans every block and tests each record; cost is $b_r$ block transfers and it works for any condition.
Binary search on a file sorted on the attribute costs about $\lceil \log_2 b_r \rceil$ for equality.
A primary index on a key attribute retrieves one record for equality; a secondary index may fetch many.
Comparison conditions ($<, >$) can use a primary ordered index or a B+-tree range scan.

project and join operations of relational algebra

Definition. Project $\pi_A(R)$ keeps only the attributes $A$ and removes duplicates; join $R \bowtie S$ combines tuples of two relations that satisfy the join condition.

Key points.

Join is the costliest operation, so the optimizer picks its algorithm and order carefully.
Nested-loop join compares every pair of tuples and suits small inputs or missing indexes; index nested-loop uses an index on the inner relation.
Sort-merge join sorts both inputs on the join attribute and merges them; good for sorted or large inputs.
Hash join partitions both inputs by a hash of the join attribute and joins matching partitions; best for equijoins on large relations.
Join order: join the smallest intermediate results first, and push selections and projections before joins.

Example. $\sigma_{dept=CS}(EMP \bowtie DEPT)$ is better as $(\sigma_{dept=CS} EMP) \bowtie DEPT$, since the join then sees far fewer tuples.

Asked: [7 marks] (Jun 2026) Explain the technique join optimization techniques with proper example.

optimization methods: heuristic based

Definition. Heuristic optimization rewrites the query tree using relational algebra equivalence rules that almost always reduce cost, without estimating costs.

Key points.

Perform selections as early as possible, since they shrink relations.
Perform projections early to drop unneeded attributes.
Break a conjunctive selection into a cascade: $\sigma_{c1 \wedge c2}(R) = \sigma_{c1}(\sigma_{c2}(R))$.
Join is commutative and associative, so reorder joins to do the most restrictive first; replace a Cartesian product followed by a selection with a join.

cost estimation based

Definition. Cost-based optimization estimates the cost of each candidate plan from catalog statistics and chooses the cheapest.

Key points.

Catalog information includes the number of tuples $n_r$, number of blocks $b_r$, tuple size, distinct values $V(A,r)$ and index heights.
Cost is mostly block transfers and seeks; CPU is often ignored.
Selectivity of $A = v$ is about $n_r / V(A,r)$ tuples.
The optimizer enumerates join orders and algorithms, often with dynamic programming, and picks the least-cost plan.

Last-minute revision

Normalization decomposes relations using FDs to remove redundancy and insertion, deletion and modification anomalies.
1NF: atomic values; 2NF: no partial dependency; 3NF: no transitive dependency; BCNF: every determinant is a superkey; 4NF: BCNF plus no non-trivial MVD.
Armstrong's axioms: reflexivity, augmentation, transitivity; $X \to Y \in F^+$ iff $Y \subseteq X^+$.
Two FD sets are equivalent if each implies the other (compare closures).
Q8 answer: STUDENT(SID, Name, Course), COURSE(Course, Faculty), FACULTY(Faculty, FacultyPhone).
BCNF example: R(Student, Subject, Teacher), $Teacher \to Subject$ splits into (Teacher, Subject) and (Student, Teacher).
4NF example: COURSE(Course, Teacher, Book) splits into (Course, Teacher) and (Course, Book).
Lossless join: common attributes must be a key of one part.
Query steps: parse, translate, optimize, evaluate.
Heuristics: push selection and projection down, join the smallest first.
Join algorithms: nested-loop, sort-merge, hash.

Memory hooks

1NF, 2NF, 3NF: "The key, the whole key, and nothing but the key."
BCNF: "Every determinant is a candidate key."
MVD gives 4NF: two independent lists in one table means split them.
PLOT for query steps: Parse, Translate, Optimize, Evaluate (run the plan).
Selection first, join last: shrink before you combine.

Coverage checklist

Introduction to normalization: Q4 (Jun 2024), Q5 (Jun 2025).
Normal forms: Q6 (Jun 2023), Q7 (Jun 2025), Q8, Q9 (Jun 2026).
Functional dependency: Q1 (Jun 2023), Q2 (Jun 2024), Q3 (Jun 2025).
Decomposition: covered, no past question.
Dependency preservation and lossless join: covered, no past question.
problems with null valued and dangling tuples: covered, no past question.
multivalued dependencies: Q10 (Jun 2024, Jun 2026).
Query Optimization: Introduction: covered, no past question.
steps of optimization: Q12 (Jun 2023).
various algorithms to implement select: covered, no past question.
project and join operations of relational algebra: Q11 (Jun 2026).
optimization methods: heuristic based: covered, no past question.
cost estimation based: covered, no past question.

Account

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

How unit 3 is examined

Introduction to normalization

Normal forms

Functional dependency

Decomposition

Dependency preservation and lossless join

problems with null valued and dangling tuples

multivalued dependencies

Query Optimization: Introduction

steps of optimization

various algorithms to implement select

project and join operations of relational algebra

optimization methods: heuristic based

cost estimation based

Last-minute revision

Memory hooks

Coverage checklist