Multivalued Dependencies, 4NF, Join Dependencies, and 5NF in DBMS

Introduction

Functional dependencies explain many database design problems, but they do not describe every kind of redundancy. A relation can satisfy Boyce-Codd Normal Form and still repeat information because it combines independent sets of facts.

Multivalued dependencies and join dependencies help identify these remaining problems. They lead to Fourth Normal Form and Fifth Normal Form, which organize facts into smaller relations while preserving the ability to reconstruct valid combinations.

An Example Relation

Consider a college database that records students’ hobbies and spoken languages in a relation named StudentInterests.

StudentInterests : initial data

The example follows these business rules:

• Multiple interests: A student may have several hobbies and speak several languages.

• Independent facts: A student’s hobbies do not depend on which language the student speaks.

• Complete combinations: The combined relation contains every combination of each student’s recorded hobbies and languages.

• Row identification: All three attributes together form the candidate key. No smaller combination is guaranteed to identify a row.

For student 101, two hobbies combined with two languages require four rows. The fact that the student enjoys Chess appears twice, even though it represents one student–hobby relationship.

The examples use distinct rows and non-NULL values. Dependencies describe business rules that must hold for every valid database state; a small sample alone does not establish them.

What Is a Multivalued Dependency?

A multivalued dependency (MVD) describes independence between sets of attribute values within a relation.

The notation X ↠ Y means that, for each fixed value of the attribute group X, the possible values of Y are independent of the values of the remaining attributes. The symbol ↠ means “multidetermines.”

In StudentInterests, the business rules establish:

• StudentID ↠ Hobby: A student’s hobbies are independent of the student’s languages.

• StudentID ↠ LanguageName: A student’s languages are independent of the student’s hobbies.

The second dependency describes the other side of the same independence.

For example, the relation contains (101, Chess, English) and (101, Music, Hindi). Independence requires the combinations (101, Chess, Hindi) and (101, Music, English) to exist as well.

Having several values does not, by itself, establish an MVD. If the table instead recorded which language a student uses for each hobby, particular hobby–language combinations could matter. Separating those attributes could then create combinations that were never valid.

A functional dependency X → Y, where → means “functionally determines,” allows only one Y value for each X value. Every functional dependency also implies an MVD, but an MVD does not necessarily imply a functional dependency.

Fourth Normal Form (4NF)

A relation is in Fourth Normal Form (4NF) if, for every nontrivial multivalued dependency X ↠ Y, X is a superkey. A superkey is an attribute or group of attributes that uniquely identifies a complete row.

An MVD is trivial when either:

• Every attribute in Y already belongs to X.

• X and Y together contain all attributes of the relation.

In StudentInterests, StudentID ↠ Hobby is nontrivial because Hobby is outside StudentID, and LanguageName remains outside their combination.

However, StudentID is not a superkey: one student can appear in several rows. Therefore, the relation violates 4NF.

Under the stated rules, the relation has no nontrivial functional dependencies, so it satisfies BCNF. Its remaining redundancy comes from independent multivalued facts. BCNF does not necessarily imply 4NF.

Decomposing the Relation into 4NF

Separate the two independent relationships into StudentHobby and StudentLanguage.

StudentHobby

StudentLanguage

The primary key of StudentHobby is the combination of StudentID and Hobby. The primary key of StudentLanguage is the combination of StudentID and LanguageName.

Each student–hobby fact and student–language fact now appears once. Adding Painting as another hobby for student 101 requires one new StudentHobby row, rather than a separate row for every language.

Joining these relations on StudentID reconstructs the five original rows. This decomposition is lossless because the MVD guarantees that every reconstructed hobby–language combination is valid.

Notice that StudentID is not a key of either smaller relation. Here, the independence expressed by the MVD provides the lossless-join guarantee.

For a general 4NF decomposition, the process is:

1. Find a nontrivial MVD whose left-hand attributes are not a superkey.

2. Create one relation containing those left-hand attributes and the independent attribute group.

3. Create another relation containing the left-hand attributes and the remaining attributes.

4. Repeat if a resulting relation still violates 4NF.

Under the stated business rules, both relations in this example satisfy 4NF.

What Is a Join Dependency?

A join dependency (JD) states that a relation can be reconstructed exactly by joining specified projections of itself.

A projection keeps selected columns and removes duplicate rows. A natural join combines rows that agree on all shared attribute names.

For a join dependency to hold, the reconstruction must produce every original row without introducing false combinations. This must remain true for every valid database state.

A join dependency is trivial if one of its component projections contains the entire original relation schema. Otherwise, it is nontrivial.

An MVD is a special case of a join dependency involving two projections. More general join dependencies can require three or more projections and may not be expressible as a sequence of lossless two-relation splits.

A Three-Way Relationship Example

Consider a relation named SupplyEligibility. It records which supplier–part–project combinations are permitted, rather than recording completed deliveries.

SupplyEligibility : initial data

The business rule states that a combination is permitted if and only if all three conditions hold:

• Supplier-part: The supplier offers the part.

• Supplier-project: The supplier is approved for the project.

• Part-project: The project requires the part.

There are no additional restrictions on individual triples. No pair of attributes is assumed to determine the third, so all three attributes together form the candidate key.

The projections of the initial relation are:

SupplierPart

SupplierProject

PartProject

The join dependency can be expressed as:

SupplyEligibility = SupplierPart ⋈ SupplierProject ⋈ PartProject

Here, ⋈ means natural join, and = means that both sides contain exactly the same rows.

Joining only SupplierPart and SupplierProject would produce the combination (S1, P2, J2). That combination is invalid because PartProject does not contain (P2, J2).

Including the third relation removes that false combination and reconstructs exactly the four original rows.

This decomposition depends on the stated business rule. If a supplier could be prohibited from supplying a particular part to a particular project despite satisfying all three pairwise conditions, the triple would carry additional information and this decomposition would not be valid.

Fifth Normal Form (5NF)

A relation is in Fifth Normal Form (5NF) if every nontrivial join dependency that holds on it is implied by its candidate keys. It is also called Project-Join Normal Form (PJNF).

“Implied by candidate keys” means that the join dependency follows from the uniqueness rules themselves, without requiring an additional business rule about how smaller relationships combine.

In SupplyEligibility, the three-way join dependency comes from the eligibility rule. It does not follow merely from the uniqueness of the complete supplier–part–project combination.

For example, removing (S1, P1, J1) would still leave all remaining triples unique. However, the three projections would remain unchanged, and joining them would recreate the removed row. The key alone therefore does not enforce the join dependency.

Under the stated rules, the original relation can satisfy 4NF while violating 5NF: there is no required nontrivial MVD, but there is an additional nontrivial three-way join dependency.

Decomposing it into SupplierPart, SupplierProject, and PartProject resolves this issue. Under these assumptions, the three resulting relations are in 5NF.

5NF does not mean that no further lossless decomposition is possible. It means that any remaining nontrivial join dependencies follow from candidate keys.

4NF vs 5NF

The number of tables alone does not determine a normal form. The deciding factors are the business rules, dependencies, and whether the decomposition preserves the original information.

A Compact Example

The following original relation is repeated for reference. The implementation stores its three pairwise projections and joins them to reconstruct the permitted combinations.

SupplyEligibility : reference data

Each smaller table uses both of its columns as a composite primary key, ensuring that the same pair cannot be stored twice.

Consider the following queries to store the three pairwise relationships and reconstruct the valid supplier–part–project combinations.

Expected result

Both queries return the following four rows, ordered by SupplierID, PartID, and ProjectID.

The aliases sp, sj, and pj provide shorter names for the three tables. The first join matches suppliers; the second checks that the particular part is required by the particular project. AND requires both of those comparisons to hold.

The invalid combination (S1, P2, J2) does not appear because its part–project pair is absent. The final result matches the reference relation exactly.

The composite primary keys prevent duplicate pairs. The business rule explains why combining these pairwise facts is sufficient to represent the original eligibility relationship.

Summary

Multivalued dependencies describe independent sets of facts associated with the same identifying attributes. Fourth Normal Form separates these facts when a nontrivial MVD has a left side that is not a superkey, removing unnecessary repetition while allowing lossless reconstruction.

Join dependencies describe exact reconstruction from multiple projections. Fifth Normal Form addresses nontrivial join dependencies that do not follow from candidate keys. Correct decomposition depends on the actual business rules, so independence and reconstruction requirements must be established before splitting a relation.