Decomposition Quality and Normalization Algorithms in DBMS

Introduction

Splitting a large database table into smaller tables can reduce redundancy, but a smaller design is not automatically a correct design. An unsuitable split can lose the connections between facts or make important rules harder to enforce.

Decomposition quality evaluates these consequences. Lossless joins and dependency preservation establish what a decomposition should retain, while BCNF decomposition and 3NF synthesis provide systematic methods for constructing normalized relations.

What Is Relation Decomposition?

Relation decomposition replaces a relation with two or more relations containing subsets of its attributes. The smaller relations retain shared attributes where necessary to represent their relationships.

A useful decomposition considers four properties:

• Attribute preservation: Every original attribute appears in at least one resulting relation.

• Lossless join: Joining the resulting relations reconstructs exactly the original relation.

• Dependency preservation: The original functional dependencies remain enforceable through dependencies on the individual relations.

• Reduced redundancy: The resulting relations satisfy an appropriate normal form.

Keeping every column is necessary, but it does not guarantee that the original relationships between their values can be recovered.

An Example Relation

Consider a college database that records student details and course enrollments for one academic term.

StudentEnrollment : initial data

The example follows these business rules:

• Student details: Each StudentID identifies one student with one current name and department.

• Department details: Each DeptID identifies one department with one current name.

• Enrollments: A student may take several courses, and a course may have several students. Each student–course pair appears at most once during the term.

• Names: Student names and department names are not assumed to be unique.

The main functional dependencies are:

• StudentID → Name, DeptID

• DeptID → DeptName

Here, → means “determines,” and the comma groups attributes determined by the same left side. These dependencies describe business rules, not conclusions drawn only from the displayed sample.

The candidate key is {StudentID, CourseID}, where braces group attributes. A candidate key uniquely identifies a row without unnecessary attributes; a superkey uniquely identifies a row but may contain additional attributes.

Lossless-Join Decomposition

A decomposition is lossless when joining the projections of every valid original relation produces exactly that relation.

A projection keeps selected columns and retains each distinct resulting row once. For the example, a suitable decomposition produces three relations.

Student

Department

Enrollment

Joining Enrollment with Student on StudentID, and then with Department on DeptID, reconstructs the original four records. The student–course association remains in Enrollment.

For a decomposition into two relations, the functional-dependency test is:

The shared attributes must determine every attribute of at least one resulting relation.

In other words, the shared attributes must form a superkey of at least one side. The condition must follow from the dependencies, rather than merely happen to hold in the current rows.

For example, Student and Enrollment share StudentID, which is a key of Student. Similarly, DeptID identifies the department details when those details are separated.

For a larger decomposition, a sequence of lossless two-relation splits establishes losslessness. Merely finding some common column between every pair of tables is insufficient.

How a Lossy Decomposition Creates False Rows

A lossy decomposition cannot reliably reconstruct the original relation. Despite the name, the problem commonly appears as extra rows after joining: the original associations have been lost.

To see this, focus only on StudentID, DeptID, and CourseID from the initial data. Suppose these columns are split into the following relations.

StudentDept

DeptCourse

Joining them on DeptID produces:

The last row is a spurious tuple, meaning a false combination introduced by the join. It assigns Meera, student 103, to OS even though that enrollment was absent from the original data.

The split preserved which students belong to each department and which courses appear within each department. It did not preserve which student takes which course.

The shared attribute DeptID is not a superkey of either relation. A department can have several students and several courses, so joining on it combines every matching student with every matching course.

Dependency Preservation

A decomposition is dependency preserving when enforcing the dependencies on the individual relations is sufficient to enforce the original functional dependencies.

In the suitable decomposition:

• Student: StudentID → Name and StudentID → DeptID can be enforced within this relation.

• Department: DeptID → DeptName can be enforced within this relation.

• Enrollment: The composite key prevents duplicate student–course pairs.

The original dependencies therefore remain enforceable without joining the tables to check them.

A general dependency-preservation check follows three steps:

1. Identify the dependencies implied by the original rules that involve only attributes of each resulting relation. These are the projected dependencies.

2. Combine those projected dependencies.

3. Check whether they imply every original dependency.

Attribute closure can perform the final check: starting with a dependency’s left-side attributes, repeatedly add attributes determined by the available rules. Its right-side attributes must be reachable.

Preservation does not require every implied dependency to appear literally within one table. For example, StudentID → DeptName still follows from StudentID → DeptID and DeptID → DeptName.

Losslessness and dependency preservation are separate properties. Reconstructing the original rows does not, by itself, prove that every dependency can be enforced locally.

The BCNF Decomposition Algorithm

Boyce-Codd Normal Form, or BCNF, requires the determinant of every non-trivial functional dependency to be a superkey. The determinant is the left side; a dependency is non-trivial when its right side contains an attribute not already on the left.

The algorithm repeatedly splits relations that violate this condition:

1. Find a violation: Identify a dependency X → Y whose determinant X is not a superkey of the current relation.

2. Create the first relation: Include the attributes of X and Y.

3. Create the second relation: Keep the remaining attributes together with X. The shared determinant must remain on both sides.

4. Repeat: Examine the dependencies implied on each new relation until every relation satisfies BCNF.

For StudentEnrollment, the process is:

• First split: DeptID → DeptName violates BCNF. Create Department(DeptID, DeptName) and keep StudentID, Name, DeptID, and CourseID in the remaining relation.

• Second split: In that remaining relation, StudentID → Name, DeptID violates BCNF because a student can have several courses. Create Student(StudentID, Name, DeptID) and Enrollment(StudentID, CourseID).

• Finish: All three resulting relations satisfy BCNF under the stated dependencies.

Each split is lossless because its shared determinant identifies the first relation. However, the BCNF algorithm does not guarantee dependency preservation, even though this particular example preserves the dependencies.

The 3NF Synthesis Algorithm

Third Normal Form, or 3NF, permits a non-trivial dependency when its determinant is a superkey or its single right-side attribute belongs to a candidate key. An attribute belonging to a candidate key is called prime.

The 3NF synthesis algorithm builds relations from a simplified dependency set:

1. Find a minimal cover: Produce an equivalent set with single-attribute right sides, no unnecessary left-side attributes, and no redundant dependencies.

2. Build relations: For each dependency, create a relation containing its left and right sides. Dependencies with the same left side may be grouped.

3. Remove contained relations: Remove a relation if all its attributes already occur within another generated relation.

4. Include an original candidate key: If no generated relation contains a candidate key of the original relation, add a relation containing one.

For the example, a minimal cover is:

• StudentID → Name

• StudentID → DeptID

• DeptID → DeptName

Grouping dependencies with the same determinant produces:

• Student(StudentID, Name, DeptID)

• Department(DeptID, DeptName)

Neither relation contains the original candidate key {StudentID, CourseID}. The algorithm therefore adds:

• Enrollment(StudentID, CourseID)

This last step is essential. Without Enrollment, the design would not retain which courses each student takes.

The completed synthesis produces a lossless, dependency-preserving decomposition into 3NF relations. In this example, the resulting relations also satisfy BCNF.

A Compact Example

The following example demonstrates decomposition through SQL projections and reconstructs the original records with joins.

StudentEnrollment : reference data

StudentEnrollment supplies the original rows. Department, Student, and Enrollment represent the decomposed design.

Consider the following queries:

SELECT DISTINCT keeps one copy of each selected combination. For example, department 10 appears in three original rows, but its department details are inserted into Department only once.

The primary keys enforce uniqueness in the decomposed tables. The foreign keys maintain valid department and student references.

Expected Result

Both queries return the following records, ordered by StudentID and then CourseID.

The aliases s, d, and e represent Student, Department, and Enrollment. Each enrollment matches one student, and each student matches one department.

All four original rows are reconstructed. The false 103-OS enrollment does not appear because the student-course association was retained in Enrollment.

This output demonstrates reconstruction for the sample. The lossless-join reasoning establishes why the decomposition works for every original relation satisfying the stated dependencies.

Summary

A good decomposition preserves the original attributes and relationships while reducing unnecessary repetition. Lossless joins prevent spurious combinations, and dependency preservation allows the original functional dependencies to remain enforceable through the smaller relations.

BCNF decomposition repeatedly splits relations on violating dependencies, while 3NF synthesis builds relations from a minimal cover and adds a candidate-key relation when necessary. Their guarantees help distinguish a correct normalized design from a collection of smaller tables.