Unit 3: Database Normalisation

I. Orientation — Organising Relations by Dependency

Database normalisation, developed from E. F. Codd’s relational model (1970), is the systematic restructuring of relations to reduce redundancy and prevent inconsistent data manipulation. It uses functional dependencies to determine whether each fact is stored in a relation whose attributes accurately reflect that fact’s meaning.

• Relation: A table represented as a relation schema (R(A_1,A_2,\ldots,A_n)), where (R) is the relation name and each (A_i) is an attribute.
• Tuple: One row in a relation; in the pure relational model, duplicate tuples are not permitted.
• Domain: The permitted set of atomic values for an attribute, such as valid dates for DateOfBirth.
• Key convention: A candidate key uniquely identifies every tuple and contains no unnecessary attribute.
  • A superkey uniquely identifies tuples but may contain redundant attributes.
  • A primary key is the candidate key selected for routine identification.
  • A prime attribute belongs to at least one candidate key.
• Dependency principle: Attributes should be grouped according to the facts they describe, not merely because they appear in the same application form or report.
• Decomposition: A relation is replaced by smaller relations, ideally with:
  • Lossless join: Joining the decomposed relations reconstructs exactly the original relation.
  • Dependency preservation: Important dependencies can be enforced without joining relations.
• Progressive forms: The usual sequence is 1NF, 2NF, 3NF and BCNF; each form imposes stricter structural conditions than the preceding form.

II. Dependency Analysis — Identifying Determinants and Update Problems

A. Functional Dependencies and Anomalies

Functional dependencies express semantic constraints between attributes, while anomalies are the practical inconsistencies caused when those constraints are represented with excessive redundancy.

1. Functional dependencies

   • Formal definition: For attribute sets (X) and (Y) in relation (R), (X) functionally determines (Y) if any two tuples agreeing on (X) must also agree on (Y).

X → Y

Here, (X) is the determinant, (Y) is the dependent attribute set, and the arrow means “functionally determines.”

• Semantic basis: A dependency must follow from the rules of the modelled organisation, not from accidental agreement in a current dataset. For example, StudentID → StudentName is valid if each student identifier permanently denotes one student.
• Full functional dependency: (Y) is fully dependent on composite determinant (X) when no proper subset of (X) determines (Y). Thus, (StudentID, ModuleID) → Mark may be full if neither identifier alone determines Mark.
• Partial dependency: A non-key attribute depends on only part of a composite candidate key. If (StudentID, ModuleID) is the key but StudentID → StudentName, then StudentName is partially dependent on the key.
• Transitive dependency: A non-key attribute depends on a key through another non-key attribute. Given EmployeeID → DepartmentID and DepartmentID → DepartmentName, the dependency EmployeeID → DepartmentName is transitive.
• Trivial dependency: (X \rightarrow Y) is trivial when (Y \subseteq X), as in (StudentID, ModuleID) → StudentID.
• Attribute closure: The closure (X^+) is the set of all attributes determined by (X) under dependency set (F). If (X^+) contains every attribute in (R), then (X) is a superkey.
• Armstrong’s axioms: These sound and complete rules derive implied dependencies:
  • Reflexivity: If (Y \subseteq X), then (X \rightarrow Y).
  • Augmentation: If (X \rightarrow Y), then (XZ \rightarrow YZ).
  • Transitivity: If (X \rightarrow Y) and (Y \rightarrow Z), then (X \rightarrow Z).
• Minimal cover: An equivalent dependency set in which each right-hand side contains one attribute, no determinant contains an extraneous attribute, and no dependency is redundant.

2. Anomalies

   • Update anomaly: Repeated facts must be changed in several rows. If DepartmentName occurs in every employee row, renaming a department incompletely creates conflicting names for one DepartmentID.
   • Insertion anomaly: One fact cannot be recorded without an unrelated fact. A department cannot be inserted into an employee table if the primary key requires an EmployeeID.
   • Deletion anomaly: Removing one fact unintentionally removes another. Deleting the final employee in a department may also erase the only stored department address.
   • Underlying cause: The relation mixes facts with different determinants, such as employee facts determined by EmployeeID and department facts determined by DepartmentID.
   • Worked example: Consider:

EMP_DEPT(EmployeeID, EmployeeName, DepartmentID, DepartmentName)
EmployeeID → EmployeeName, DepartmentID
DepartmentID → DepartmentName

 DepartmentName is stored repeatedly because it is transitively dependent on EmployeeID. Decomposing into EMPLOYEE(EmployeeID, EmployeeName, DepartmentID) and DEPARTMENT(DepartmentID, DepartmentName) stores each department name once and prevents the three anomalies.

III. Normalisation — Successive Forms for Well-Structured Relations

A. Normalization Concepts and Forms

Normalisation tests a relation against dependency-based criteria and decomposes it when the relation violates the required normal form.

• Normalisation objective: Store each independent fact once, thereby improving integrity and making insertions, updates and deletions safer.
• Analysis sequence: Identify attributes, determine candidate keys, document valid functional dependencies, test the current normal form, and decompose where necessary.
• Lossless-join condition: A binary decomposition of (R) into (R_1) and (R_2) is lossless with respect to (F) if their common attributes determine all attributes of at least one component.

(R₁ ∩ R₂) → R₁
or
(R₁ ∩ R₂) → R₂

Here, (R_1 \cap R_2) is the shared attribute set, and the implication is evaluated using the functional dependencies (F).

• Dependency preservation: If dependencies projected onto the decomposed relations imply the original set (F), constraints can be checked locally rather than through expensive joins.
• Design limitation: Normalisation does not prove that business rules are correct; inaccurate or omitted dependencies produce an inappropriate schema.

B. 1NF

First Normal Form requires every attribute value to be atomic within the relation’s intended domains and forbids repeating groups.

• Atomic values: Each row-column intersection contains one value, such as one PhoneNumber, rather than a comma-separated list.
• Repeating groups: Columns such as Phone1, Phone2 and Phone3 encode an arbitrary maximum and should normally become rows in a related relation.
• Conversion: A customer with several phone numbers can be represented as:
  • CUSTOMER(CustomerID, CustomerName)
  • CUSTOMER_PHONE(CustomerID, PhoneNumber)
• Key consequence: CUSTOMER_PHONE may use (CustomerID, PhoneNumber) as a composite key, ensuring that one customer-phone pairing appears once.
• Scope: 1NF removes structural repetition but does not eliminate partial or transitive dependencies.

C. 2NF

Second Normal Form requires a relation to be in 1NF and every non-prime attribute to depend fully on every candidate key.

• Relevant case: A 1NF relation with a single-attribute candidate key is automatically in 2NF because no proper subset of that key exists.
• Violation: In ENROLMENT(StudentID, ModuleID, StudentName, ModuleTitle, Mark), suppose:

(StudentID, ModuleID) → Mark
StudentID → StudentName
ModuleID → ModuleTitle

 StudentName and ModuleTitle depend on only part of the composite key.

• Decomposition: Create STUDENT(StudentID, StudentName), MODULE(ModuleID, ModuleTitle) and ENROLMENT(StudentID, ModuleID, Mark).
• Result: Student and module descriptions are stored once, while Mark remains associated with the complete enrolment key.
• Limitation: A 2NF relation may still contain transitive dependencies between non-key attributes.

D. 3NF

Third Normal Form removes problematic transitive dependencies while usually preserving both dependencies and lossless reconstruction.

• Formal condition: For every non-trivial functional dependency (X \rightarrow A), at least one condition must hold:
  • (X) is a superkey; or
  • (A) is a prime attribute.
• Practical interpretation: Non-key attributes should describe the key rather than describe other non-key attributes.
• Violation: In EMPLOYEE(EmployeeID, DepartmentID, DepartmentName), EmployeeID → DepartmentID and DepartmentID → DepartmentName; therefore, the department name is transitively dependent on the key.
• Decomposition: Separate the schema into EMPLOYEE(EmployeeID, DepartmentID) and DEPARTMENT(DepartmentID, DepartmentName).
• Benefit: The department name is maintained in one tuple, while DepartmentID acts as a foreign key linking employees to departments.
• Important allowance: 3NF permits a determinant that is not a superkey when the dependent attribute is prime; this makes 3NF less restrictive than BCNF.

E. BCNF

Boyce–Codd Normal Form strengthens 3NF by requiring every determinant of a non-trivial dependency to be a superkey.

• Formal condition: Relation (R) is in BCNF if, for every non-trivial dependency (X \rightarrow Y), (X) is a superkey of (R).
• Difference from 3NF: BCNF provides no exception merely because the dependent attribute is prime.

• Violation example: Let TEACHING(Student, Subject, Tutor) satisfy:

  • (Student, Subject) → Tutor
  • Tutor → Subject

  Candidate keys are (Student, Subject) and (Student, Tutor). The relation can satisfy 3NF because Subject is prime, but it violates BCNF because Tutor is not a superkey.

• Decomposition: It can be separated into TUTOR_SUBJECT(Tutor, Subject) and STUDENT_TUTOR(Student, Tutor).
• Trade-off: A lossless BCNF decomposition always exists, but it may fail to preserve every original dependency. Designers may therefore retain a 3NF schema when direct constraint enforcement is more important.

IV. Denormalisation — Controlled Redundancy for Performance

A. Denormalization

Denormalisation deliberately introduces redundancy into a normalised design to reduce join costs or accelerate specific read-heavy workloads.

• Purpose: Precompute or duplicate frequently requested data when measured performance requirements justify the added maintenance burden.
• Common techniques:
  • Store OrderTotal in ORDER although it can be calculated from ORDER_LINE.
  • Copy CustomerName into a reporting table to avoid repeated joins.
  • maintain summary tables containing daily sales by product or region.
  • Use materialized views that persist the result of a query and refresh it periodically.
• Performance benefit: Fewer joins, aggregations and table scans can lower query latency, especially in analytical systems with large historical datasets.
• Integrity cost: Redundant values can disagree. If an order line changes, a stored OrderTotal must be recalculated within the same transaction or through a reliable refresh mechanism.
• Operational controls: Triggers, generated columns, scheduled refreshes, application transactions and reconciliation checks can maintain duplicated facts.
• Appropriate contexts: Read-heavy data warehouses, reporting databases, cached projections and distributed systems may favour predictable query speed over strict elimination of redundancy.
• Inappropriate use: Denormalisation should not compensate for missing indexes, poorly written queries or inadequate execution plans.
• Design principle: Begin with a correctly normalised logical schema, measure a concrete bottleneck, denormalise only the affected path, and document the authoritative source of every duplicated value.