Unit 3: Database Normalisation - Subjective Questions

A functional dependency (FD) is a constraint between two sets of attributes in a relation. An FD holds if every pair of tuples having the same value of also has the same value of .

• Trivial functional dependency: is trivial when .
  • Example: .
• Non-trivial functional dependency: It is non-trivial when .
  • Example: .
• Completely non-trivial functional dependency: It is completely non-trivial when .
  • Example: .

Functional dependencies describe semantic relationships among attributes and are used to identify keys and perform normalization.

Armstrong's axioms are sound and complete rules for inferring functional dependencies.

1. Reflexivity: If , then .
2. Augmentation: If , then for any set of attributes .
3. Transitivity: If and , then .

Additional rules derived from these axioms include:

• Union: If and , then .
• Decomposition: If , then and .
• Pseudotransitivity: If and , then .

These rules are used to calculate attribute closures, discover implied dependencies, and verify candidate keys.

The closure is calculated as follows:

1. Initially, .
2. From , add : .
3. From , add : .
4. Since both and are present, apply : .
5. From , add : .

Therefore,

Because contains every attribute of , is a superkey. Since contains only one attribute and no proper subset of it can determine all attributes, it is also a candidate key.

Consider the relation ENROLLMENT(StudentID, StudentName, CourseID, CourseName, Instructor), where student and course information is repeated for every enrollment.

• Insertion anomaly: A new course cannot be recorded until at least one student enrolls in it, unless null values are inserted for student attributes.
• Update anomaly: If a course name or instructor changes, every enrollment row for that course must be updated. Missing one row creates inconsistent data.
• Deletion anomaly: Deleting the last enrollment in a course may also remove the only stored information about that course and its instructor.

These anomalies occur because facts about students, courses, and enrollments are stored in one relation. Decomposing it into relations such as STUDENT, COURSE, and ENROLLMENT reduces redundancy and prevents these anomalies.

Normalization is the systematic process of organizing relations to reduce redundancy and prevent modification anomalies.

Its main objectives are:

• Minimize duplicate data.
• Prevent insertion, update, and deletion anomalies.
• Ensure that attributes are stored with the facts they describe.
• Improve data integrity and consistency.
• Produce decompositions that are preferably lossless and dependency-preserving.

The progression is:

1. 1NF: Eliminates repeating groups and requires atomic attribute values.
2. 2NF: Removes partial dependencies of non-prime attributes on candidate keys.
3. 3NF: Removes problematic transitive dependencies and requires every FD to have a superkey determinant or a prime dependent attribute.
4. BCNF: Strengthens 3NF by requiring the determinant of every non-trivial FD to be a superkey.

Each higher normal form addresses additional forms of redundancy, although decomposition may introduce extra joins.

A relation is in First Normal Form (1NF) when:

• Every attribute contains a single, atomic value.
• There are no repeating groups or arrays within a row.
• Values in each column belong to the same domain.
• Each tuple can be uniquely identified by a key.

Suppose CUSTOMER(CustomerID, Name, PhoneNumbers) stores several phone numbers in the PhoneNumbers field. This violates 1NF because the value is not atomic.

It can be converted into:

• CUSTOMER(CustomerID, Name)
• CUSTOMER_PHONE(CustomerID, PhoneNumber)

Each phone number is then stored in a separate tuple of CUSTOMER_PHONE. The key of this relation may be . This design satisfies 1NF and permits any number of phone numbers without adding repeating columns.

A relation is in Second Normal Form (2NF) if:

1. It is already in 1NF.
2. Every non-prime attribute is fully functionally dependent on every candidate key.

A partial dependency occurs when a non-prime attribute depends on a proper subset of a composite candidate key.

Consider ENROLLMENT(StudentID, CourseID, StudentName, CourseName, Grade) with composite key and dependencies:

StudentName and CourseName are partially dependent on the composite key. Therefore, the relation is not in 2NF.

It can be decomposed into STUDENT(StudentID, StudentName), COURSE(CourseID, CourseName), and ENROLLMENT(StudentID, CourseID, Grade).

Assume the following dependencies:

The relation is in 1NF, but it violates 2NF because:

• OrderDate and CustomerID depend only on OrderID.
• ProductName and UnitPrice depend only on ProductID.

These are partial dependencies on parts of the composite key. The 2NF decomposition is:

• ORDER(OrderID, OrderDate, CustomerID)
• PRODUCT(ProductID, ProductName, UnitPrice)
• ORDER_LINE(OrderID, ProductID, Quantity)

In each relation, every non-prime attribute depends on the whole key. The decomposition also reduces repeated order and product information.

A relation is in Third Normal Form (3NF) if it is in 2NF and, for every non-trivial functional dependency , at least one condition holds:

• is a superkey, or
• is a prime attribute, meaning it belongs to some candidate key.

A transitive dependency exists when a key determines a non-key attribute through another non-key attribute.

For EMPLOYEE(EmpID, EmpName, DeptID, DeptName):

Therefore, transitively through DeptID. Since DeptID is not a superkey and DeptName is non-prime, the relation violates 3NF.

A suitable decomposition is:

• EMPLOYEE(EmpID, EmpName, DeptID)
• DEPARTMENT(DeptID, DeptName)

First, express the dependencies with a single attribute on each right-hand side:

This is a minimal cover because the left sides contain no extraneous attributes and none of the dependencies is redundant.

Create a relation for each determinant and its dependent attributes:

• From and : R1(A, B, C)
• From : R2(B, D)
• From : R3(D, E)

The closure contains , so is a candidate key. Since R1 contains , no additional key relation is required.

The resulting decomposition is:

It is in 3NF, preserves the listed dependencies, and the standard 3NF synthesis algorithm guarantees a lossless decomposition when a relation containing a candidate key is present.

A relation is in Boyce-Codd Normal Form (BCNF) if, for every non-trivial functional dependency , is a superkey.

BCNF is stricter than 3NF because 3NF allows an FD when either:

• is a superkey, or
• is a prime attribute.

BCNF does not permit the prime-attribute exception. It requires every determinant of a non-trivial dependency to be a superkey.

Therefore:

• Every BCNF relation is in 3NF.
• A 3NF relation is not necessarily in BCNF.

BCNF removes certain redundancies caused by overlapping candidate keys, but a BCNF decomposition may fail to preserve all original functional dependencies.

Formal conditions:

• 3NF: For every non-trivial FD , must be a superkey or must be prime.
• BCNF: For every non-trivial FD , must be a superkey.

Similarities:

• Both are based on functional dependencies.
• Both reduce redundancy and modification anomalies.
• Both generally require the relation to satisfy lower normal forms.

Differences:

• BCNF has no exception for a prime dependent attribute.
• BCNF removes more dependency-based redundancy than 3NF.
• A lossless BCNF decomposition can always be obtained, but it may not preserve all dependencies.
• The 3NF synthesis algorithm can provide both lossless join and dependency preservation.

In practice, 3NF may be preferred when dependency preservation is important, whereas BCNF may be chosen when eliminating redundancy is the primary objective.

The candidate keys include:

• , because it determines Instructor.
• , because allows it to determine all attributes.

For the dependency , Instructor alone is not a superkey. Therefore, the relation violates BCNF.

Decompose it using the violating dependency into:

• INSTRUCTOR_COURSE(Instructor, Course)
• STUDENT_INSTRUCTOR(Student, Instructor)

The common attribute is Instructor, and it determines all attributes of INSTRUCTOR_COURSE. Hence, the decomposition is lossless.

However, the original dependency cannot be checked within one decomposed relation. Thus, the BCNF decomposition is lossless but does not preserve every original dependency.

A decomposition is lossless if joining the decomposed relations always reconstructs exactly the original relation, without losing tuples or generating spurious tuples.

For a binary decomposition of into and , the decomposition is lossless with respect to if at least one of the following is implied by :

or

Example: Decompose EMPLOYEE(EmpID, DeptID, DeptName) into:

• EMP(EmpID, DeptID)
• DEPT(DeptID, DeptName)

Their intersection is . Since , DeptID determines every attribute of DEPT. Therefore, the decomposition is lossless. A natural join on DeptID reconstructs the original valid relation without spurious tuples.

A decomposition is dependency-preserving if all original functional dependencies can be enforced by checking the decomposed relations individually, without joining them.

If is the projection of the original dependency set onto relation , then the decomposition preserves dependencies when:

Dependency preservation is important because constraints can be enforced efficiently during insertions and updates.

A conflict may occur with BCNF because decomposing on a determinant that is not a superkey can separate attributes needed to test another dependency. The resulting BCNF relations may be lossless but may not contain all attributes of an original FD together.

Thus, designers sometimes retain a 3NF decomposition because it can offer both lossless join and dependency preservation, even though it may contain slightly more redundancy than BCNF.

To find the candidate keys:

• using , so is a candidate key.
• using , so is also a candidate key.

Thus, the prime attributes are , , and , because each belongs to at least one candidate key.

For , the determinant is a superkey, so it satisfies both 3NF and BCNF.

For :

• is not a superkey, so the dependency violates BCNF.
• is a prime attribute, so the dependency satisfies the prime-attribute exception of 3NF.

Therefore, the relation is in 3NF but not in BCNF.

Denormalization is the deliberate introduction of redundancy into a normalized database to improve read performance or simplify frequently executed queries.

Common techniques include:

• Combining related tables to reduce joins.
• Storing derived or calculated values, such as order totals.
• Duplicating frequently accessed descriptive attributes.
• Maintaining summary or aggregate tables.
• Storing precomputed counts, averages, or balances.
• Creating materialized views.
• Introducing redundant foreign-key paths for faster retrieval.

For example, storing CustomerName in an ORDER table avoids a join with CUSTOMER, but changes to the customer's name must then be propagated correctly.

Denormalization should be based on measured performance requirements because it increases storage usage and creates additional consistency and maintenance responsibilities.

Normalization:

• Objective: Minimize redundancy and improve integrity.
• Advantages: Reduces modification anomalies, simplifies constraint enforcement, and avoids inconsistent duplicate values.
• Disadvantages: May require many joins and can reduce the speed of complex read operations.
• Suitable for: Transaction-processing systems with frequent inserts, updates, and deletes.

Denormalization:

• Objective: Improve read performance by reducing joins or precomputing data.
• Advantages: Faster reporting, simpler read queries, and improved performance for repeated aggregations.
• Disadvantages: More storage, duplicated data, complex update logic, and risk of inconsistency.
• Suitable for: Data warehouses, analytical systems, dashboards, and read-heavy applications.

A balanced design usually begins with normalization. Selective denormalization is then applied only when profiling shows that joins or calculations create unacceptable performance costs.

The principal risks of denormalization are:

• Update anomalies: The same fact must be changed in several places.
• Inconsistent data: Duplicate copies may contain different values.
• Higher storage usage: Repeated and precomputed data consumes additional space.
• Complex write operations: Inserts, updates, and deletes may need extra logic.
• Maintenance overhead: Schema changes and corrections become more difficult.

Consistency can be maintained through:

• Database triggers that synchronize duplicate values.
• Stored procedures or service-layer transactions for coordinated updates.
• Constraints and foreign keys where applicable.
• Scheduled refreshes for summary tables and materialized views.
• Change-data-capture pipelines.
• Reconciliation jobs that compare redundant copies.
• Clear documentation identifying the authoritative source of each fact.

Denormalized values should preferably be generated from a single source of truth rather than independently edited.

The original relation repeats member, book, and publisher data for every borrowing transaction.

Anomalies:

• Updating a publisher name requires changing many borrowing rows.
• A book or publisher cannot be inserted unless a borrowing transaction exists.
• Deleting the last borrowing of a book may remove its descriptive information.

The key is . The dependencies and are partial dependencies, so the relation violates 2NF. In addition, creates a transitive dependency.

A 3NF decomposition is:

• MEMBER(MemberID, MemberName)
• PUBLISHER(PublisherID, PublisherName)
• BOOK(BookID, BookTitle, PublisherID)
• BORROWING(MemberID, BookID, BorrowDate)

In each relation, non-key attributes depend on the key, the whole key, and no non-key determinant. The decomposition reduces redundancy, preserves the stated dependencies, and supports lossless reconstruction through the key and foreign-key relationships.