Multivalued Dependencies and Fourth Normal Form (4NF)

Relational database normalization is a progressive discipline: each successive normal form addresses a category of redundancy that its predecessors cannot detect. Third Normal Form (3NF) and Boyce-Codd Normal Form (BCNF) are built entirely around functional dependencies, where one set of attribute values uniquely determines another. But there exists a distinct class of data anomaly that functional dependency theory is simply blind to — one that arises when an entity legitimately has two or more independent collections of related values, and those collections are stored together in a single table. Understanding this phenomenon requires a new concept: the multivalued dependency. Once multivalued dependencies are understood, the rule for eliminating them — Fourth Normal Form (4NF) — follows naturally as an extension of the BCNF principle.

A multivalued dependency (MVD) is a constraint between attributes in a relation that expresses a fundamentally different kind of determination than a functional dependency. It is written as X ↠ Y and is read as "X multidetermines Y." The precise meaning is this: in any valid tuple of the relation, for a given value of X, the complete set of Y values that appear alongside it is entirely independent of whatever other attributes are present in the relation. In other words, the pairing of X with Y values has nothing to do with any third set of attributes Z.

To make this concrete, consider a university scenario. Suppose a professor can teach multiple courses and also speaks multiple languages, and these two facts are recorded in a single relation:

Dr. Patel teaches Databases and Algorithms. She also speaks English and Hindi. These two facts are completely independent of each other — which courses she teaches has absolutely no bearing on which languages she speaks. Because of this independence, every course must be paired with every language in the table. The relation is expressing two separate MVDs: Professor ↠ Course and Professor ↠ Language. For any given professor, the set of courses is determined solely by the professor (independent of language), and the set of languages is determined solely by the professor (independent of course).

It is important to understand the relationship between MVDs and functional dependencies. Every functional dependency X → Y is also an MVD X ↠ Y, but the converse is not true. A functional dependency says that for each X value there is exactly one Y value — a special case of multidetermination where the "set" of Y values always has exactly one member. An MVD is strictly more general: the set of Y values can have any number of members. This means that functional dependency theory, and the normal forms built on it (including BCNF), cannot detect or repair MVD-driven redundancy. MVDs are a genuine generalization requiring their own analysis.

MVDs arise naturally whenever an entity has two or more independent multi-valued attributes that are forced into a single relation. The key word is independent: if knowing which courses a professor teaches told you anything about which languages she speaks, the relationship would not be an MVD in the pure sense. It is the independence of the two attribute sets with respect to a common determinant that creates the problem.

How MVDs cause redundancy that BCNF cannot resolve is best understood by examining what happens when data changes. In the table above, every combination of course and language must be present for Dr. Patel. This is a Cartesian-product redundancy: if she teaches c courses and speaks l languages, the table must contain c × l rows for her alone. This redundancy immediately produces serious update anomalies:

• Insertion anomaly: If Dr. Patel begins teaching a new course, say "Machine Learning," a new row must be inserted for each language she speaks (English and Hindi), not just one row. Forgetting to insert one of these rows leaves the database in an inconsistent state where the Cartesian-product property is violated.
• Deletion anomaly: If Dr. Patel stops speaking Hindi, every row containing Hindi must be deleted — one for each course she teaches. A partial deletion produces an inconsistent state.
• Update anomaly: The same piece of information — that Dr. Patel speaks Hindi — is stored redundantly in multiple rows, creating opportunities for inconsistency if rows are updated individually.

Crucially, BCNF decomposition offers no remedy here. BCNF requires that for every non-trivial functional dependency X → Y, X must be a superkey. In our Professor–Course–Language table, the only key is the entire tuple {Professor, Course, Language} — no non-trivial functional dependency exists at all, because no single attribute or pair of attributes functionally determines any other. BCNF analysis therefore concludes that the table is already in BCNF and requires no decomposition. Yet the redundancy and anomalies are obvious. This is precisely the gap that Fourth Normal Form is designed to close.

The formal definition of 4NF mirrors the BCNF definition almost word for word, but substitutes multivalued dependencies for functional dependencies. A relation R is in Fourth Normal Form if and only if, for every non-trivial multivalued dependency X ↠ Y that holds in R, X is a superkey of R.

The term non-trivial MVD requires careful definition, because trivial MVDs are satisfied automatically and cause no redundancy. An MVD X ↠ Y in relation R(X, Y, Z) is trivial if either:

• Y is a subset of X (Y is already contained within the determining attributes), or
• X ∪ Y constitutes all the attributes of R (there is no remaining attribute set Z that could form independent combinations).

Any non-trivial MVD where X is not a superkey is a 4NF violation. In our example, Professor ↠ Course is non-trivial (Course is not a subset of Professor, and {Professor, Course} does not cover all three attributes), and Professor is not a superkey of the three-attribute relation. The violation is confirmed.

The following table summarizes the parallel structure of BCNF and 4NF rules:

Identifying 4NF violations in a given relation requires a two-stage analysis. First, you must identify which attributes are genuinely multi-valued for a single entity. Ask the question: "Can one instance of the entity key have more than one value of this attribute?" If yes, the attribute is multi-valued. In our example, a single professor can teach multiple courses and speak multiple languages — both are multi-valued attributes with respect to Professor.

Second, and more critically, you must verify independence. Ask: "Does knowing which values of attribute A are present tell us anything about which values of attribute B are present, for a fixed key value?" If the answer is no — if the sets of values are completely independent of each other — then you have a genuine MVD, and the two attribute sets will generate Cartesian-product redundancy when combined in a single relation. If, on the other hand, there is some application-level constraint linking the two (for example, a professor only teaches a course in one specific language, making Course and Language dependent on each other), then no MVD holds, and the combination does not constitute a 4NF violation.

A practical checklist for identifying 4NF violations:

• List all attributes in the relation and identify those that can take multiple values per entity instance.
• For each pair of multi-valued attributes, ask whether their value sets are independent of each other given the key.
• If independent, write out the MVD: Key ↠ AttributeSetA and Key ↠ AttributeSetB.
• Check whether the left-hand side (Key) is a superkey of the entire relation. If the relation has additional attributes beyond Key, AttributeSetA, and AttributeSetB, the answer is no — and a violation exists.
• Examine the actual data: if you see rows that look like every combination of two sets of values is required for completeness, that is a strong empirical signal of an MVD.

Decomposing relations to achieve 4NF follows a clean, principled procedure. Given a relation R with attributes (X, Y, Z) where X ↠ Y is a non-trivial MVD and X is not a superkey, decompose R into two relations:

• R1(X, Y) — captures the relationship between X and the independently multi-valued attribute set Y.
• R2(X, Z) — captures the relationship between X and the remaining attribute set Z.

Applying this to the Professor–Course–Language example:

Each resulting relation now stores only one independent multi-valued fact per row. Adding a new course for Dr. Patel requires inserting exactly one row into ProfessorCourse, with no corresponding requirement to touch ProfessorLanguage. The Cartesian-product redundancy is completely eliminated.

A vital property of this decomposition is that it must be lossless-join: joining R1 and R2 on X must reproduce the original relation R exactly, with no spurious tuples and no missing tuples. The theoretical guarantee here is provided by the definition of MVDs themselves — when X ↠ Y holds in R, the decomposition into R1(X, Y) and R2(X, Z) is provably lossless. This is analogous to the lossless-join guarantee for BCNF decompositions based on functional dependencies.

To verify: joining ProfessorCourse and ProfessorLanguage on Professor yields:

This is exactly the original relation — the decomposition is lossless. The decomposition process should be applied iteratively: after splitting a relation, each resulting relation must itself be examined for further 4NF violations. It is possible for R1(X, Y) or R2(X, Z) to contain their own MVDs if X, Y, or Z are themselves composite sets of attributes with independent subsets. Continue decomposing until every relation in the schema satisfies 4NF.

Finally, it is essential to appreciate the trade-offs and practical considerations involved in applying 4NF. Several important points must guide real-world decisions:

• Domain knowledge is indispensable. MVDs are not derivable from the data alone without understanding the business rules. Two attributes that appear to be independent in the current dataset may actually be constrained in ways not yet reflected in the data. For instance, if a company policy dictates that certain skills are only relevant in combination with specific project types, those attributes are not truly independent, and no MVD exists. Misidentifying a dependency as an MVD leads to incorrect decomposition.
• Increased number of relations. Decomposing to 4NF splits relations that were combined, potentially doubling or tripling the number of tables in a schema. Queries that previously required reading a single table now require joins, which can increase query complexity and execution time. In read-heavy analytical workloads, this trade-off may favor keeping some redundancy in denormalized structures, while in write-heavy transactional systems, 4NF is strongly beneficial.
• Relationship to 5NF. 4NF is a necessary stepping stone toward Fifth Normal Form (5NF), also called Project-Join Normal Form (PJNF). While 4NF handles the case where one relation decomposes into two projections based on an MVD, 5NF addresses the more exotic case of join dependencies — where a relation can only be losslessly decomposed into three or more projections, but not into any two. Getting 4NF correct is therefore not only valuable in its own right but also a prerequisite for understanding and achieving the highest standard of normalization.
• MVDs in composite contexts. It is worth noting that a relation can have MVDs that are not directly apparent from the key alone. For example, in a relation with attributes (A, B, C, D), it might be that A, B together multidetermines C independent of D. Such MVDs must also be checked and resolved. The analysis of all possible left-hand sides — not just the primary key — is important for thorough 4NF verification.

In summary, multivalued dependencies represent an important class of constraint that falls entirely outside the scope of functional dependency theory. They arise whenever an entity has two or more independent multi-valued attributes stored in the same relation, and they produce a distinctive Cartesian-product redundancy that BCNF is powerless to address. Fourth Normal Form closes this gap by requiring that the left-hand side of every non-trivial MVD be a superkey, and the decomposition strategy — splitting R(X, Y, Z) into R1(X, Y) and R2(X, Z) — is both intuitive and theoretically guaranteed to be lossless. Applying 4NF demands careful business-domain analysis, an iterative approach to decomposition, and a clear-eyed evaluation of the resulting trade-offs between data integrity and query performance.