Functional Dependencies and Normalization

1. Why Relations Need Careful Structure

A table can be syntactically valid and still represent facts poorly. Consider one table containing:

ENROLLMENT(
    student_id,
    student_name,
    course_id,
    course_title,
    instructor_id,
    instructor_name,
    grade
)

The likely key is a combination such as (student_id, course_id). Student names repeat for every course and course information repeats for every student. Repetition consumes space, but the larger concern is that the same fact is stored in several places and can become inconsistent.

Normalization analyzes dependencies among attributes and decomposes relations so that each fact has an appropriate home.

2. Update Anomalies

An update anomaly occurs when a repeated fact must be changed in several rows. If course_title appears in every enrollment for a course, renaming the course requires updating all matching rows. A missed row leaves contradictory titles for the same course.

The anomaly is structural. A transaction can make one multirow update atomic, but it does not explain why the fact was duplicated or stop a later program from updating only one copy.

Separating COURSE(course_id, course_title) stores the title once and lets enrollments reference it.

3. Insertion Anomalies

An insertion anomaly occurs when one fact cannot be recorded without another unrelated fact. In the combined table, a new course may not be stored until at least one student enrolls because student_id participates in the key.

Using dummy student values hides the design error and pollutes the data. A separate COURSE relation allows a course to exist independently of enrollment, matching its real lifecycle.

4. Deletion Anomalies

A deletion anomaly occurs when deleting one fact unintentionally removes the only stored copy of another fact. If the last enrollment in a course is deleted from the combined table, the database may also lose the course title and instructor information.

Separate relations let deletion follow meaning: deleting an ENROLLMENT removes that association, while the COURSE remains until an explicit course deletion is performed.

5. Functional Dependencies

A functional dependency X → Y states that in every valid instance of a relation, any two tuples equal on attribute set X must also be equal on attribute set Y. X is the determinant and Y is functionally dependent on X.

Examples:

student_id → student_name, date_of_birth
course_id → course_title, credits
(student_id, course_id) → grade

Dependencies express business rules, not accidental patterns in current data. Ten rows with different names do not prove name → student_id. Future people can share a name.

6. Trivial and Nontrivial Dependencies

A dependency X → Y is trivial when Y is a subset of X. For example:

(student_id, course_id) → student_id

It holds from the structure of attribute sets and reveals no additional business rule.

A nontrivial dependency has at least one right-side attribute not already in the determinant. Normal-form definitions focus on nontrivial dependencies because they reveal how distinct facts are determined.

7. Armstrong's Axioms

Functional dependencies can imply other dependencies. Armstrong's axioms provide sound and complete inference rules:

• reflexivity: if Y is a subset of X, then X → Y;
• augmentation: if X → Y, then XZ → YZ;
• transitivity: if X → Y and Y → Z, then X → Z.

Useful derived rules include:

• union: if X → Y and X → Z, then X → YZ;
• decomposition: if X → YZ, then X → Y and X → Z;
• pseudotransitivity: if X → Y and WY → Z, then WX → Z.

These rules support key discovery and decomposition analysis.

8. Attribute Closure

The closure X+ under a dependency set is the set of attributes functionally determined by X. Begin with X, repeatedly add the right side of every dependency whose left side is already contained and stop when nothing changes.

For R(A, B, C, D) with:

A → B
B → C
AC → D

Start A+ = {A}. A → B adds B. B → C adds C. AC → D then adds D. Therefore A+ contains all attributes, so A is a superkey.

Closure also tests whether a dependency is implied: X → Y follows when Y is contained in X+.

9. Finding Candidate Keys

A candidate key is a minimal attribute set whose closure contains every relation attribute.

A practical method is:

1. place attributes that never appear on any dependency's right side into every candidate-key starting set;
2. compute closure;
3. add combinations of remaining attributes until closure covers the relation;
4. remove any unnecessary attribute to verify minimality;
5. search for other minimal combinations.

Minimal means minimal by set inclusion, not the fewest characters or smallest stored number.

All candidate keys matter when evaluating 2NF and 3NF. Looking only at the chosen primary key can miss violations involving another candidate key.

10. Prime Attributes

A prime attribute belongs to at least one candidate key. A non-prime attribute belongs to no candidate key.

Prime does not mean “part of the primary key.” If a relation has candidate keys {email} and {employee_id}, both attributes are prime even if employee_id is selected as primary.

This distinction matters in the formal 3NF condition, which permits a dependency with a non-superkey determinant when every dependent attribute is prime.

11. Decomposition

Decomposition replaces one relation schema with two or more smaller schemas. For example:

ENROLLMENT(student_id, student_name, course_id,
           course_title, grade)

can become:

STUDENT(student_id, student_name)
COURSE(course_id, course_title)
ENROLLMENT(student_id, course_id, grade)

The goal is not merely smaller tables. A useful decomposition should be lossless, should ideally preserve dependencies and should place each important fact where its determinant is a key.

12. Lossless Join

A decomposition is lossless when natural joining the decomposed relations reconstructs exactly the original valid relation, without losing tuples or producing spurious combinations.

For a binary decomposition of R into R1 and R2, it is lossless under dependency set F when the common attributes functionally determine all of R1 or all of R2:

(R1 ∩ R2) → R1

or:

(R1 ∩ R2) → R2

If STUDENT and ENROLLMENT share student_id and student_id is a key of STUDENT, their join is lossless under the rule.

Joining tables merely because they share a similarly named non-key attribute can create spurious tuples.

13. Dependency Preservation

A decomposition preserves dependencies when all original dependencies can be enforced by checking constraints within individual decomposed relations, without joining them.

Lossless join protects information, while dependency preservation protects practical enforceability. They are separate properties. A decomposition may be lossless but require an expensive join to verify an original rule.

3NF synthesis can provide both losslessness and dependency preservation. A BCNF decomposition is lossless but may sacrifice dependency preservation in some schemas.

14. First Normal Form

A relation is in first normal form when each attribute value is atomic for the relational design and repeating groups are absent.

This table is problematic:

CUSTOMER(customer_id, name, phone1, phone2, phone3)

It imposes a fixed number of phones and repeats one logical attribute. A separate relation is clearer:

CUSTOMER(customer_id, name)
CUSTOMER_PHONE(customer_id, phone_number, phone_type)

Atomicity depends on intended operations. A postal address may be stored as one value if never queried by components, though structured columns are needed when city or postal code has independent meaning.

15. Second Normal Form

A relation is in 2NF when it is in 1NF and every non-prime attribute is fully functionally dependent on every candidate key. No non-prime attribute may depend on only a proper subset of a candidate key.

In ENROLLMENT with key (student_id, course_id):

student_id → student_name
course_id → course_title
(student_id, course_id) → grade

student_name and course_title are partial dependencies. Splitting STUDENT and COURSE removes them, while grade remains with the full enrollment key.

A relation whose candidate keys each contain one attribute cannot have a partial-key violation because such a key has no nonempty proper subset.

16. Third Normal Form

A relation is in 3NF when it is in 2NF and does not store non-key facts through other non-key facts. Informally, non-key attributes should depend on keys, the whole keys and not on non-key intermediates.

Consider:

EMPLOYEE(employee_id, department_id, department_name)

with:

employee_id → department_id
department_id → department_name

employee_id determines department_name transitively through department_id. Repeating department_name for every employee creates anomalies. Decompose into EMPLOYEE(employee_id, department_id) and DEPARTMENT(department_id, department_name).

Formally, for every nontrivial dependency X → A in 3NF, X must be a superkey or A must be prime.

17. Boyce-Codd Normal Form

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

BCNF is stricter than 3NF because it does not include the prime-attribute exception. Every determinant of a meaningful functional dependency must identify the whole tuple.

A relation can be in 3NF but not BCNF when a non-superkey determines a prime attribute. Such cases often involve overlapping candidate keys. BCNF removes more dependency-based redundancy, but a lossless BCNF decomposition may not preserve every dependency locally.

18. A 3NF but Not BCNF Pattern

Let R(Student, Course, Instructor) have rules:

(Student, Course) → Instructor
Instructor → Course

Candidate keys include (Student, Course) and (Student, Instructor). Every attribute is prime. Instructor → Course satisfies 3NF because Course is prime, but it violates BCNF because Instructor is not a superkey.

Decomposing to INSTRUCTOR_COURSE(Instructor, Course) and STUDENT_INSTRUCTOR(Student, Instructor) removes the BCNF violation and is lossless under Instructor → Course. Whether all intended dependencies remain directly enforceable must be checked separately.

19. Minimal Covers

A minimal or canonical cover is an equivalent dependency set with a simple form:

1. each dependency has one attribute on the right;
2. no left-side attribute is extraneous;
3. no dependency is redundant.

To test whether an attribute in X is extraneous in X → A, compute closure after removing that attribute under the appropriate dependency set. To test whether a dependency is redundant, remove it and see whether its right side remains in the determinant's closure.

Minimal covers are useful in 3NF synthesis because they isolate essential rules.

20. 3NF Synthesis

A common dependency-preserving 3NF construction is:

1. find a minimal cover;
2. create a relation containing X ∪ {A} for each dependency X → A, combining compatible determinants;
3. remove relation schemas contained entirely in another;
4. if no created relation contains a candidate key of the original relation, add one relation containing a candidate key.

The result is in 3NF, preserves dependencies and has a lossless join under the standard construction.

Design still requires meaningful names, correct types and constraints; an algorithm does not replace domain understanding.

21. BCNF Decomposition

If R violates BCNF through X → Y, decompose it into:

R1 = X ∪ Y
R2 = R − (Y − X)

The decomposition is lossless because the intersection contains X, which determines R1. Continue until every resulting relation satisfies BCNF.

At each step, project dependencies onto the new relations and re-evaluate keys. Do not assume that keys and dependencies transfer unchanged.

22. Multivalued Dependencies and 4NF

A multivalued dependency X ↠ Y means that, for a fixed X, the set of Y values is independent of the remaining attributes.

Suppose an Instructor has independent Skills and Languages:

INSTRUCTOR_DETAIL(instructor, skill, language)

If every skill combines with every language, the table stores their cross-product. Decompose into INSTRUCTOR_SKILL and INSTRUCTOR_LANGUAGE.

A relation is in 4NF when every nontrivial multivalued dependency has a superkey determinant. Functional dependencies are special cases within this broader concern.

23. Join Dependencies and 5NF

Fifth normal form addresses join dependencies that require decomposition into three or more projections. A relation satisfies 5NF when every nontrivial join dependency follows from candidate keys.

A classic Supplier-Part-Project relation may contain facts reconstructable from several pairwise relations under a specific business rule. Decomposition avoids storing redundant combinations, but incorrect assumptions can create combinations that were never valid.

5NF situations are less common in ordinary application schemas and require precise semantic evidence. Do not decompose merely because three foreign keys appear together; the ternary fact may be irreducible.

24. Denormalization

Denormalization deliberately stores redundant or derived data for a measured performance or availability reason. Examples include cached totals, reporting snapshots or prejoined analytical structures.

It reintroduces consistency work. The design must define:

• which copy is authoritative;
• when and how derived copies update;
• what happens on partial failure;
• how inconsistencies are detected and repaired;
• which workload measurement justifies the tradeoff.

Denormalization is not a substitute for indexes, query analysis or correct relational design.

25. A Reliable Normalization Method

Begin with one relation and a complete set of business dependencies. Identify candidate keys through closure. Check 1NF structure, then partial dependencies for 2NF, transitive and formal dependency conditions for 3NF and all determinants for BCNF.

For each decomposition, prove lossless join and evaluate dependency preservation. Add primary, unique, foreign-key, not-null and check constraints that implement the resulting rules.

Normalization is a reasoning process about facts. The objective is not the largest possible number of tables; it is a schema in which each fact is stored with the key that determines it, updates preserve one consistent truth and joins reconstruct the required information correctly.