Database Management Systems (AL-502) Unit 3 Notes

How unit 3 is examined

This unit covers normalization (anomalies, normal forms, functional dependencies, decomposition) and query optimization; normal forms, functional dependency and query optimization carry most of the marks.

Introduction to normalization

Medium weight

Definition. Normalization is the process of organising a relation's attributes into smaller well-structured relations, using functional dependencies, so that redundancy and the insertion, deletion and update anomalies are removed without losing information.

Key points.

Redundancy means the same fact is stored many times, which wastes space and lets copies disagree.
An insertion anomaly means a fact cannot be recorded without another, unrelated fact (a department cannot be stored until an employee exists, or a null must be inserted).
A deletion anomaly means deleting one fact destroys another (deleting the only employee of a department deletes the department).
An update anomaly means one fact stored in many rows must be changed everywhere, or the data becomes inconsistent.
Normalization is needed because it removes these anomalies, keeps the join lossless and, where possible, preserves dependencies.

Example. Employee(E_ID, Ename, Dname), key E_ID:

E_ID	Ename	Dname
e1	A	HR
e4	B	HR
e8	C	Finance
e9	D	Null
e2	E	Civil

Insert: a new department cannot be added without an employee, and e9 shows a Null being forced in.
Delete: deleting e8 removes the fact that Finance exists; deleting e2 removes Civil.
Update: renaming HR needs changes in both e1 and e4; missing one leaves HR and its old name together.

Answer frame. Open with the definition; show the sample table; take insert, delete and update anomalies in that order, each with one row of the table; close by saying normal forms remove them.

Asked: [7 marks] (Jun 2020) What is Normalization? Why it is required. Asked: [7 marks] (Nov 2023) Employee(E_ID, Ename, Dname) with E_ID as primary key: discuss the insert, delete and update anomalies.

Normal forms

Definition. A normal form is a rule on a relation's dependencies; a relation in a higher normal form has fewer anomalies.

Key points.

1NF: every attribute value is atomic, with no repeating groups or multivalued cells.
2NF: the relation is in 1NF and no non-prime attribute depends on a proper part of a candidate key (no partial dependency).
3NF: the relation is in 2NF and for every $X \to A$, either $X$ is a superkey or $A$ is prime (no transitive dependency of a non-prime attribute).
BCNF: for every non-trivial $X \to Y$, $X$ must be a superkey, so every determinant is a candidate key. It is stricter than 3NF, which alone allows a non-key determinant whose right side is prime.
4NF: the relation is in BCNF and every non-trivial multivalued dependency $X \twoheadrightarrow Y$ has $X$ as a superkey.
Normalization removes the insertion, deletion and update anomalies. Decomposition is always lossless, but BCNF may lose a dependency, while 3NF can always preserve them.

Steps (find keys, then the form). Attributes never on a right side are in every key. Find every key by closure. Prime = in some key. Check partial dependency (2NF), then non-key determinant (3NF, BCNF).

Example. R(ABCDE): $A \to B, BC \to E, ED \to A$. Keys are $ACD$, $BCD$, $CDE$. All attributes are prime, so no partial or transitive dependency exists: 3NF. $A \to B$ has non-superkey $A$, so not BCNF.

Relation	FDs	Keys	Highest form
R(EFGH)	$E \to F, F \to G, H \to G$	$EH$	$E \to F$ is partial ($E \subset EH$, $F$ non-prime): 1NF
R(ABCDEF)	$A \to BC, C \to E, E \to F, F \to AB$	$AD, CD, DE, DF$	$D$ is in every key; $A \to B$ is partial, $B$ non-prime: 1NF
R(ABCD)	$A \to B, B \to C, C \to D$	$A$	single-attribute key so 2NF; $B \to C$ transitive: not 3NF

Normalize R(ABCD): $A^+ = ABCD$, key $A$. Remove transitive dependencies: R1(A,B), R2(B,C), R3(C,D), all in 3NF and BCNF.

BCNF example. R(Student, Subject, Teacher) with $Teacher \to Subject$, key (Student, Subject): $Teacher$ is not a superkey, so it violates BCNF. Decompose into R1(Teacher, Subject) and R2(Student, Teacher).

4NF versus BCNF. R(Course, Teacher, Book), where a course has independent sets of teachers and books, has $Course \twoheadrightarrow Teacher \mid Book$. The key is all three attributes, so it is in BCNF, yet every teacher is repeated with every book. 4NF splits it into (Course, Teacher) and (Course, Book), removing this redundancy.

Answer frame. For definitions, open with the anomalies; list 1NF, 2NF, 3NF, BCNF with one example each; close with the anomalies removed. For numericals: closures, keys, prime attributes, then test each form, and write the highest form in bold.

Pitfall: Do not call a relation 3NF just because it has no transitive dependency on the key; test every FD against superkey or prime. Asked: [7 marks] (Dec 2020, Nov 2022, Nov 2023) Find all keys and the highest normal form for R(ABCDE) with $A \to B, BC \to E, ED \to A$; for R(EFGH) with $E \to F, F \to G, H \to G$; for R(ABCDEF) with $A \to BC, C \to E, E \to F, F \to AB$. Asked: [7 marks] (Jun 2020) Explain why 4NF is more desirable than BCNF with the help of an example. Asked: [7 marks] (Dec 2024) Explain about Boyce Codd normal form with an example. Asked: [7 marks] (Dec 2025) Explain normalization and functional dependency. Discuss first, second, and third normal forms. Asked: [7 marks] (Dec 2025) Normalize the relation R(A, B, C, D) with $A \to B, B \to C, C \to D$.

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$; $X$ determines $Y$.

Key points.

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$). They are sound and complete.
Derived rules are union ($X \to Y, X \to Z$ give $X \to YZ$), decomposition and pseudotransitivity.
The closure $F^+$ is the set of all FDs implied by $F$, found with the axioms.
The attribute closure $X^+$ is the set of attributes determined by $X$. Start with $X^+ = X$; repeatedly add $B$ for every FD $Y \to B$ with $Y \subseteq X^+$, until nothing is added.
$X$ is a superkey if $X^+$ is all attributes; a candidate key is a minimal such set. Closures also test whether $X \to Y$ holds and whether two FD sets are equivalent.
An attribute is extraneous if removing it does not change the closure: $A$ in $AX \to Y$ is extraneous if $Y \subseteq X^+$ computed under $F$.
FDs identify redundancy and keys, and drive the 1NF to BCNF decompositions.

Canonical cover. A minimal set of FDs equivalent to $F$, with single-attribute right sides, no extraneous left attribute and no redundant FD.

Step 1: Split every right side into single attributes.
Step 2: Remove extraneous attributes from left sides.
Step 3: Remove any FD implied by the others (closure test).
Step 4: Merge FDs with the same left side.

Example (closures). R(ABCDE), $F = \{AB \to C, B \to D, C \to E, D \to A\}$:

X	$X^+$
$A$	$A$
$B$	$B \to D \to A$; with $AB \to C \to E$: $ABCDE$
$C$	$CE$
$D$	$AD$
$E$	$E$

$B^+$ is everything, so $B$ is the only candidate key.

Example (canonical cover). R(WXYZ): $X \to W$, $WZ \to XY$, $Y \to WXZ$. Split: $X \to W, WZ \to X, WZ \to Y, Y \to W, Y \to X, Y \to Z$. Neither $W$ nor $Z$ is extraneous in $WZ$ ($W^+ = W$, $Z^+ = Z$). $Y \to W$ is redundant ($Y \to X \to W$), and $WZ \to X$ is redundant ($WZ \to Y \to X$). Merge: $X \to W,\ WZ \to Y,\ Y \to XZ$.

Answer frame. Open with the definition and axioms; for closure questions, give the algorithm then the table; for canonical cover, give the four steps then the worked cover; close with its use in keys and normalization.

Asked: [7 marks] (Nov 2019) Explain closure of set of functional dependency and closure of attribute sets. Asked: [7 marks] (Nov 2019) Explain canonical cover and extraneous attributes with examples. Asked: [7 marks] (Jun 2020) Find the attribute closures for R(ABCDE) with $AB \to C, B \to D, C \to E, D \to A$. Asked: [7 marks] (Nov 2023) R(WXYZ) with $X \to W, WZ \to XY, Y \to WXZ$: compute the minimal (canonical) cover. Asked: [7 marks] (Dec 2024) Explain the role of functional dependencies in normalization with suitable examples.

Decomposition

Definition. Decomposition replaces a relation $R$ by two or more smaller relations whose attributes together are all of $R$.

Key points.

It is done to remove redundancy and anomalies found by normalization.
A good decomposition is lossless (the natural join gives back exactly $R$) and preferably dependency preserving.
A bad decomposition is lossy: the join produces spurious tuples.
Every decomposition must cover all attributes of $R$.

Dependency preservation and lossless join

Definition. ==A decomposition of $R$ into $R_1, R_2$ is lossless if $R_1 \bowtie R_2 = R$ for every legal instance; it is dependency preserving if the union of the FDs projected on each $R_i$ implies all of $F$.==

Key points.

Lossless join means no information is lost and no spurious tuples appear; without it, queries on the decomposed database give wrong answers.
Binary test: the decomposition is lossless if $R_1 \cap R_2 \to R_1$ or $R_1 \cap R_2 \to R_2$ is in $F^+$, that is, the common attributes are a key of one part.
For many parts, use the tableau (chase) test, or join step by step with the binary test.
Dependency preservation lets every FD be checked inside one relation, without joins, on updates.
Test: compute $F_i$ (FDs of $F^+$ whose attributes lie in $R_i$), take $G = \bigcup F_i$, and check $G^+ = F^+$, that is, every FD of $F$ follows from $G$.
BCNF always gives lossless joins but may lose dependencies; 3NF gives both.

Example. R(ABCD), $F = \{A \to B, B \to C, C \to D, D \to A\}$, decomposed into R1(AB), R2(BC), R3(CD). Every attribute determines all others, so $F_1 = \{A \to B, B \to A\}$, $F_2 = \{B \to C, C \to B\}$, $F_3 = \{C \to D, D \to C\}$. Check the lost FD $D \to A$: $D \to C$ ($F_3$), $C \to B$ ($F_2$), $B \to A$ ($F_1$). So $D \to A$ follows from the union, and $A \to B, B \to C, C \to D$ are directly present. Dependency preservation holds.

Answer frame. Open with the definition; state the binary test; work the example by listing $F_i$ and checking each FD; close with why lossless join avoids spurious tuples.

Asked: [7 marks] (Dec 2020) What is lossless decomposition in database? How it is useful in database? Asked: [7 marks] (Nov 2022) R(ABCD) with $A \to B, B \to C, C \to D, D \to A$ decomposed into R1(AB), R2(BC), R3(CD): does it satisfy dependency preservation?

Null values and dangling tuples

Definition. A null is a special marker for a value that is unknown, missing or inapplicable; it is not zero or blank.

Key points.

Any comparison with null gives unknown, so SQL uses three-valued logic (true, false, unknown) and $WHERE$ keeps only true rows.
Nulls let a tuple exist when some data is not yet known, so the model stays flexible; outer joins use them to pad unmatched tuples.
A dangling tuple has no matching tuple in the other relation, so it is lost in a natural join, but an outer join keeps it with nulls.
Problems: nulls break aggregates, joins and key constraints (a primary key cannot be null); handle them with $IS\ NULL$, $NOT\ NULL$ and defaults.

Asked: [7 marks] (Dec 2024) Explain the importance of Null values in Relational Model.

Multivalued dependencies

Definition. A multivalued dependency $X \twoheadrightarrow Y$ holds if, for a given $X$, the set of $Y$ values is independent of the remaining attributes, so tuples can be swapped between rows sharing $X$.

Key points.

It arises when two independent multivalued facts sit in one relation, giving redundancy that FDs cannot show; 4NF removes it.
A join dependency $\bowtie(R_1, \dots, R_n)$ says $R$ equals the join of its projections on $R_1 \dots R_n$; 5NF (project-join normal form) removes it.

Basis	Multivalued dependency	Join dependency
Meaning	one attribute set independently fixes two others	$R$ equals the join of $n$ projections
Parts	always splits into two	any number of parts
Normal form	4NF	5NF (PJNF)
Relation	a special case of a join dependency	the general case
Example	$Course \twoheadrightarrow Teacher$	(SP, PJ, JS) triple

Asked: [7 marks] (Jun 2020) Differentiate Multivalued dependency and Join dependency.

Query Optimization: Introduction

Definition. Query optimization is the process of choosing, among many equivalent evaluation plans for a query, the one with the lowest estimated cost.

Diagram. <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 534.2 252" width="534.2" height="252" role="img" aria-label="Query processing: Q = SQL query, Par = parser and translator (relational algebra), Opt = optimizer, Eng = evaluation engine, Out = result; the optimizer uses the data dictionary (Dic) and statistics (Stat)"><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="ah7" 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="ahh7" 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,126 L130.8,126" marker-end="url(#ah7)"/><path class="e" d="M170.8,126 L242.6,126" marker-end="url(#ah7)"/><path class="e" d="M282.6,126 L354.4,126" marker-end="url(#ah7)"/><path class="e" d="M394.4,126 L466.2,126" marker-end="url(#ah7)"/><path class="e" d="M263.6,59 L263.6,105" marker-end="url(#ah7)"/><path class="e" d="M263.6,186 L263.6,147" marker-end="url(#ah7)"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">Q</text><circle class="n" cx="151.8" cy="126" r="18"/><text class="t" x="151.8" y="126" dy=".35em" text-anchor="middle">Par</text><circle class="n" cx="263.6" cy="126" r="18"/><text class="t" x="263.6" y="126" dy=".35em" text-anchor="middle">Opt</text><circle class="n" cx="375.4" cy="126" r="18"/><text class="t" x="375.4" y="126" dy=".35em" text-anchor="middle">Eng</text><circle class="n" cx="487.2" cy="126" r="18"/><text class="t" x="487.2" y="126" dy=".35em" text-anchor="middle">Out</text><circle class="n" cx="263.6" cy="40" r="18"/><text class="t" x="263.6" y="40" dy=".35em" text-anchor="middle">Dic</text><rect class="n" x="238.6" y="197" width="50" height="30" rx="15"/><text class="t" x="263.6" y="212" dy=".35em" text-anchor="middle">Stat</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Query processing: Q = SQL query, Par = parser and translator (relational algebra), Opt = optimizer, Eng = evaluation engine, Out = result; the optimizer uses the data dictionary (Dic) and statistics (Stat)</figcaption></figure>

Key points.

A query can be written in many equivalent ways whose costs differ hugely, so optimization avoids slow plans; it is the system, not the user, that chooses.
The parser checks syntax, and the translator converts SQL to a relational algebra expression or query tree.
The optimizer picks an execution plan: an algebra expression annotated with the algorithm for each operator.
The evaluation engine runs the plan and returns the result.
Heuristic (rule-based) optimization applies rules, such as pushing selections and projections down, without costing.
Cost-based optimization estimates the cost (mainly disk I/O) of candidate plans from statistics (relation sizes, distinct values, indexes) and picks the cheapest.
Example: $\sigma_{dept='CS'}(Student \bowtie Enrol)$ is far cheaper if the selection is done before the join.

Answer frame. Open with the definition and need; draw the block diagram; explain parse, optimize, evaluate; then heuristic versus cost-based with the example; close with the performance benefit.

Asked: [7 marks] (Dec 2020, Dec 2024) Explain the concept of query optimization / give a brief note on query optimization. Asked: [7 marks] (Nov 2019) Diagrammatically illustrate and discuss the steps involved in processing a query. Asked: [7 marks] (Dec 2025) Explain query optimization and its importance. Describe heuristic and cost-based optimization.

Steps of optimization

Definition. Query processing runs in three major steps: parsing and translation, optimization, and evaluation.

Key points.

Parsing and translation checks syntax and relation names, then translates SQL into relational algebra (an internal query tree).
Optimization has two parts: transform the algebra into equivalent expressions using equivalence rules, then choose the cheapest plan by cost estimation.
Evaluation executes the chosen plan with the algorithms picked for each operator and outputs the result.
Cascade of selection: $\sigma_{c_1 \wedge c_2}(R) = \sigma_{c_1}(\sigma_{c_2}(R))$; a combined condition can be split into a sequence of selections, which can then be pushed down separately.
Other rules: selections commute, and selection distributes over join when its condition uses one relation.
Cost estimation uses statistics such as number of tuples, block count and indexes to compare the plans.

Answer frame. Open by naming the three steps; explain each in order; give the sigma cascade example and one equivalence; close with cheapest-plan selection.

Asked: [7 marks] (Nov 2022, Nov 2023) Discuss the three major steps in query optimization. What do you understand by sigma cascade operation?

Algorithms for select, project and join

Definition. These are the physical methods the evaluation engine uses to run each relational algebra operator.

Key points.

Select uses a linear file scan, or binary search on sorted data, or an index (primary or secondary).
Project drops attributes and then removes duplicates by sorting or hashing.
Join uses nested-loop join (compare every pair), block nested-loop, index nested-loop, sort-merge join (sort both, then merge) or hash join (partition by a hash of the join key).
Sort-merge and hash join suit equi-joins on large relations, and nested loop works for any condition.

Optimization methods: heuristic based

Definition. Heuristic optimization rewrites the query tree using rules that almost always reduce cost, without computing exact costs.

Key points.

Perform selections as early as possible to reduce the number of tuples.
Perform projections early to reduce tuple width.
Replace a Cartesian product followed by a selection with a join, and do the smallest joins first.
Break a conjunctive selection into a cascade and push each part down, then execute the resulting query tree.

Cost estimation based

Definition. Cost-based optimization estimates the resource cost of every candidate plan and picks the cheapest.

Key points.

Disk I/O (block reads and writes) is the main cost, and CPU time is the second.
Communication cost matters in distributed and parallel systems, where data is shipped between sites.
Buffer size, storage layout and index access change the block counts, so they enter the cost.
The estimates depend on statistics: tuples, blocks, distinct values and selectivity (fraction of tuples selected).

Asked: [7 marks] (Nov 2023) Discuss various cost components for query execution.

Last-minute revision

Normalization removes redundancy and insert, delete and update anomalies.
1NF atomic; 2NF no partial dependency; 3NF no transitive dependency; BCNF every determinant is a superkey; 4NF no non-trivial MVD.
Attribute closure: repeat adding $B$ for each $Y \to B$ with $Y \subseteq X^+$.
R(ABCDE): keys $ACD$, $BCD$, $CDE$; 3NF, not BCNF.
R(EFGH): key $EH$; 1NF. R(ABCDEF): keys $AD, CD, DE, DF$; 1NF.
R(ABCD), $A \to B \to C \to D$: key $A$; decompose to (AB), (BC), (CD).
Canonical cover of R(WXYZ): $X \to W, WZ \to Y, Y \to XZ$.
Lossless test: $R_1 \cap R_2$ is a key of $R_1$ or $R_2$.
The AB, BC, CD decomposition of the cyclic FD set preserves dependencies.
Query processing: parser, optimizer, evaluation engine.
Cost is mostly disk I/O; $\sigma_{c_1 \wedge c_2} = \sigma_{c_1}(\sigma_{c_2})$.

Memory hooks

Normal forms ladder: "The key, the whole key, and nothing but the key" (1NF, 2NF, 3NF).
BCNF: every determinant is a candidate key.
Lossless: the common part must be a key.
Query optimization: push selections down, join small first.
Processing: Parse, Optimize, Execute.

Coverage checklist

Introduction to normalization: Jun 2020 what is normalization; Nov 2023 Employee anomalies.
Normal forms: three keys and normal-form numericals; 4NF versus BCNF; BCNF; 1NF to 3NF; normalize R(ABCD).
Functional dependency: closures; canonical cover; attribute closures of R(ABCDE); minimal cover of R(WXYZ); role in normalization.
Decomposition: definition, lossless and preserving.
Dependency preservation and lossless join: lossless decomposition; R(ABCD) preservation.
problems with null valued and dangling tuples: importance of null values.
multivalued dependencies: multivalued versus join dependency.
Query Optimization: Introduction: concept; query processing diagram; importance, heuristic and cost-based.
steps of optimization: three steps and sigma cascade.
various algorithms to implement select, project and join operations of relational algebra: scan, index, nested loop, sort-merge, hash.
optimization methods: heuristic based: selection and projection pushdown.
cost estimation based: cost components.

Account

Database Management Systems (AL-502) - Unit 3 Short Notes

How unit 3 is examined

Introduction to normalization

Normal forms

Functional dependency

Decomposition

Dependency preservation and lossless join

Null values and dangling tuples

Multivalued dependencies

Query Optimization: Introduction

Steps of optimization

Algorithms for select, project and join

Optimization methods: heuristic based

Cost estimation based

Last-minute revision

Memory hooks

Coverage checklist