Database Normalization and Indexing Principles

1. Functional Dependency (FD)

A functional dependency A → B means: if you know the value of attribute A, you can always determine the value of attribute B. In other words, no two rows can have the same A value but different B values.

Example: In a table Student(StudentID, Name, Email): StudentID → Name, Email (Given a StudentID, the Name and Email are always uniquely determined.)

2. Boyce-Codd Normal Form (BCNF)

A relation is in BCNF if, for every functional dependency X → Y, X is a superkey.

• Compliance: Every determinant in the table is a candidate key—no changes needed.
• Evaluation: Whenever there is a non-trivial FD X → Y where X is not a superkey. This means some attribute depends on only part of a key, or on a non-key attribute—causing redundancy and anomalies. In that case, we decompose the table into smaller tables until every determinant is a key.

Example: Bookings(Room, Time, Manager) where Room, Time → Manager and Manager → Room (each manager oversees only one room).

3. Indexing Non-Key Attributes

Q: What evaluations decide if we need to index a non-key attribute?

A:

• Query frequency (WHERE/JOIN/ORDER BY)
• Selectivity (distinct values)
• Read/write ratio
• Table size
• Storage cost

4. Inference Rules

Inference rules let us derive all the functional dependencies that logically follow from a given set, without checking the data itself. This is essential for finding candidate keys and for normalization.

Key rules include:

• Reflexivity: If B is a subset of A, then A → B.
• Augmentation: If A → B, then AC → BC (for any C).
• Transitivity: If A → B and B → C, then A → C.

5. Second Normal Form (2NF)

Q: Give the definition of Second Normal Form (2NF) and an example.

A: 1NF + every non-key attribute fully depends on the whole primary key (no partial dependency).

Example: OrderItems(OrderID, ProductID, ProductName, Quantity) — ProductName depends only on ProductID, which violates 2NF.

6. B+ Tree Indexing

A B+ tree is a balanced, multi-level tree used for indexing:

• Internal (index) nodes: Contain only key values used to guide the search—no actual data—and pointers to child nodes.
• Leaf nodes: Contain the actual key values with pointers to the corresponding data records (or the data itself), and are all at the same depth (balanced).
• Linked leaves: Leaf nodes are linked together in a sequential chain (like a linked list), which makes range queries and sequential scans fast.