Unit 3 — The Relational Model and Normalization

Topics Covered

Syllabus topics: Introduction, CODD rules, relational data model, concept of key, relational integrity, relational algebra, relational algebra operations, advantages of relational algebra, limitations of relational algebra, functional dependencies and normal forms.

This is the hardest unit in the course, and normalization is the hardest part of it. It is also the part most reliably asked as a ten-mark question.

3.1 The relational data model

Proposed by E. F. Codd in 1970. Data is stored in relations — tables of rows and columns.

Degree and cardinality are frequently swapped in exams. Degree counts columns; cardinality counts rows.

Properties of a relation

1. Each cell holds one atomic value — no lists, no repeating groups
2. Every attribute has a distinct name
3. Values in an attribute come from the same domain
4. The order of tuples is irrelevant — a relation is a set
5. The order of attributes is irrelevant
6. No duplicate tuples

Property 4 is why SELECT results have no guaranteed order unless you write ORDER BY. A common source of confusion.

3.2 Codd's 12 rules

Codd published 12 rules (numbered 0 to 12, so thirteen in all) defining what makes a DBMS genuinely relational. Know the concept and be able to name several; few real systems satisfy all of them.

3.3 Relational integrity constraints

Entity integrity exists because a NULL primary key could not identify anything.

Referential integrity is what stops you assigning an employee to department 99 when no such department exists — as demonstrated in 03_employee.sql, where that exact update is tested and correctly rejected.

Referential actions

What happens when a referenced row is deleted or updated:

3.4 Relational algebra

A procedural query language: it specifies how to compute the result. It is the theoretical foundation of SQL, and query optimisers work in terms of it.

Basic operations

Select picks rows, project picks columns. Swapping them is the most common error, largely because SQL's SELECT keyword actually does the projection.

σ_{salary > 50000}(EMPLOYEE)          →  SELECT * FROM Employee WHERE salary > 50000
π_{name, salary}(EMPLOYEE)            →  SELECT name, salary FROM Employee
π_{name}(σ_{dept_id = 2}(EMPLOYEE))   →  SELECT name FROM Employee WHERE dept_id = 2

Derived operations

Union compatibility: ∪, ∩ and − require both relations to have the same number of attributes with matching domains. Without it the operation is undefined.

Advantages of relational algebra

1. A formal mathematical foundation for query languages

2. Enables query optimisation — algebraic equivalences let the optimiser rewrite a query into a cheaper but equivalent form

3. Closure — every operation takes relations and returns a relation, so operations compose freely

4. Procedural clarity — the order of operations is explicit

Limitations of relational algebra

1. No aggregate functions — no COUNT, SUM, AVG in the basic algebra
2. No grouping
3. No sorting — a relation is a set, so it has no order
4. No arithmetic or computed columns

5. No recursion — cannot express transitive closure ("all managers above this employee")

6. No update operations — it is a query language only

7. No null handling in the pure theory

Extended relational algebra adds aggregation and grouping, which is how SQL manages GROUP BY. Mentioning that distinction earns marks.

3.5 Functional dependencies

roll_no → name — the roll number determines the name. Given a roll number, the name is fixed.

name → roll_no is false — two students may share a name.

Types of functional dependency

Partial dependency is what 2NF removes. Transitive dependency is what 3NF removes. Fixing those two definitions in your mind makes normalization mechanical.

Armstrong's axioms

Derived rules: union, decomposition, pseudo-transitivity.

3.6 Normalization

First Normal Form (1NF)

Violates 1NF:

In 1NF:

Or better, a separate STUDENT_PHONE table.

Second Normal Form (2NF)

2NF only matters when the primary key is composite. A single-attribute primary key means partial dependency is impossible, so a 1NF table with a simple key is automatically in 2NF.

Violates 2NF. Key is {roll, course_id}:

student_name depends only on roll, which is part of the key — a partial dependency.

Decomposed into 2NF:

STUDENT(roll PK, student_name)
ENROLMENT(roll FK, course_id FK, marks, PRIMARY KEY(roll, course_id))

Third Normal Form (3NF)

Violates 3NF:

emp_id → dept_id → dept_name, so dept_name depends on the key only transitively.

Decomposed into 3NF:

EMPLOYEE(emp_id PK, emp_name, dept_id FK)
DEPARTMENT(dept_id PK, dept_name)

That is exactly the structure of the Employee lab schema — the lab tables are already in 3NF, which is why they need no decomposition.

Boyce-Codd Normal Form (BCNF)

BCNF is stricter than 3NF. A table in 3NF may still violate BCNF when it has overlapping candidate keys. The classic example:

with {student, subject} → teacher and teacher → subject. The second dependency has a non-super-key on the left, so it is in 3NF but not BCNF.

The memory aid

• The key → 1NF (atomic values keyed properly)
• The whole key → 2NF (no partial dependency)
• Nothing but the key → 3NF (no transitive dependency)

Higher normal forms, briefly

Denormalization

Normalizing to 3NF means more tables and therefore more joins, which can be slower. Denormalization deliberately reintroduces redundancy for read performance — common in data warehouses and reporting systems, which you meet in the Business Intelligence Tools course.

Normalize first; denormalize only when measurement shows you need to.

ORDER(order_id PK, cust_id, cust_name, cust_city)
PRODUCT(product_id PK, product_name, price)
ORDER_ITEM(order_id FK, product_id FK, qty, PRIMARY KEY(order_id, product_id))

CUSTOMER(cust_id PK, cust_name, cust_city)
ORDER(order_id PK, cust_id FK)
PRODUCT(product_id PK, product_name, price)
ORDER_ITEM(order_id FK, product_id FK, qty, PRIMARY KEY(order_id, product_id))

Exam questions from this unit

Two marks

1. Define degree and cardinality of a relation.
2. State the entity integrity rule.
3. Distinguish σ from π in relational algebra.
4. What is a partial functional dependency?
5. State two limitations of relational algebra.

Five marks

1. Explain the integrity constraints of the relational model.
2. Explain the basic operations of relational algebra with examples.
3. Explain 1NF, 2NF and 3NF with examples.
4. Explain the insertion, update and deletion anomalies with one table.
5. Explain BCNF and how it differs from 3NF.

Ten marks

1. Explain Codd's rules.

2. Normalize a given unnormalized table to 3NF, showing every step and the dependencies removed.

3. Explain functional dependencies, their types, Armstrong's axioms, and the normal forms.

Mistakes that cost marks