What is a multivalued dependency in relational design, and what does Fourth Normal Form (4NF) require of a table with respect to multivalued dependencies?
answer
- X double-arrow Y, set-valued determination
- free recombination forces the cross product
- nontrivial MVD needs a superkey
- 4NF implies BCNF, strictly stronger
- Fagin: split into (X,Y) and (X,Z), lossless
basics
~20 sA multivalued dependency X to Y means fixing X fixes a whole set of Y values, independently of the table's other columns. 4NF says every nontrivial multivalued dependency must have a superkey on its left side, otherwise split the table so each independent set lives on its own.
solid answer
~50 sA functional dependency says one value of X determines exactly one value of Y. A multivalued dependency, written X double-arrow Y, is the set-valued version: one value of X determines a whole set of Y values, and that set is independent of the remaining columns. Formally, if two rows agree on X you can swap their Y parts and the resulting rows must also be in the table. That free recombination is what forces the cross product. 4NF requires that for every nontrivial multivalued dependency X double-arrow Y, X is a superkey of the table. Since every functional dependency is also a multivalued dependency, 4NF implies BCNF, it is strictly stronger. The repair is Fagin's decomposition: if X double-arrow Y holds in R with the rest called Z, then splitting into (X, Y) and (X, Z) is lossless, the join rebuilds R exactly. In practice you detect it by asking whether one row is a single fact or an accidental pairing of two independent many-valued facts.
code
text · 6 linesemployee_id | skill | language
------------+-------+---------
Ann | Java | English
Ann | Java | German
Ann | SQL | English
Ann | SQL | German <- required, or the table implies a false pairinggo deeper
Recall the plain-language version: two independent lists in one table force every combination, so split them. The formal notation is not expected.
State the definition, the superkey condition, that 4NF implies BCNF, and show the decomposition on a concrete example.
Add Fagin's theorem in both directions, the BCNF-satisfying-but-redundant example, and how you would validate independence with the domain owner before splitting.
Position 4NF as the boundary where dependency theory stops being derivable from data and starts needing semantics, and say how that shapes review practice.
## From functional to multivalued dependencies Normal forms up to BCNF are defined entirely in terms of functional dependencies. A functional dependency X determines Y means: pin down a value of X and you have pinned down exactly one value of Y. employee_id determines employee_name. A multivalued dependency generalises this to sets. Written X double-arrow Y in a table R whose remaining columns are Z, it holds when: for any two rows that agree on X, the table also contains the rows you get by swapping their Y values. Put plainly, for a given X the Y values and the Z values combine freely, so the table must contain every combination. The set of Y values attached to an X does not depend on which Z you are looking at. Example: EmployeeFacts(employee_id, skill, language). Ann has skills Java and SQL, and speaks English and German. Skills and languages are unrelated, so all four combinations must appear. employee_id double-arrow skill holds, and so does employee_id double-arrow language, the two always come in pairs. ## Trivial versus nontrivial A multivalued dependency is trivial when Y is a subset of X, or when X and Y together are all the columns of the table. Trivial ones say nothing and are ignored by the definition. Only nontrivial ones can violate a normal form. Every functional dependency is a multivalued dependency where the determined set happens to have one element. That is why 4NF subsumes BCNF: a table in 4NF is automatically in BCNF, but not the reverse. EmployeeFacts is in BCNF, its only key is all three columns and there are no nontrivial functional dependencies at all, yet it is clearly redundant. That gap is precisely what 4NF closes. ## The 4NF rule A table is in 4NF if, for every nontrivial multivalued dependency X double-arrow Y, X is a superkey. In EmployeeFacts, employee_id double-arrow skill is nontrivial and employee_id is not a superkey, so the table violates 4NF. The intuition behind the rule: if X were a superkey, X would identify one row, and there would be no set of Y values to spread across multiple rows in the first place. ## Fagin's decomposition theorem The theorem that makes the repair sound: R decomposes losslessly into (X union Y) and (X union Z) if and only if X double-arrow Y holds in R. So EmployeeFacts splits into EmployeeSkill(employee_id, skill) and EmployeeLanguage(employee_id, language), and the natural join of the two returns exactly the original rows. Note the if and only if, the multivalued dependency is not just the problem, it is also the licence to split. If the columns were genuinely correlated, the multivalued dependency would not hold and the split would lose information. ## What it buys you Storage shrinks from m times n rows to m plus n. Each write touches one row instead of a fan-out. A half-finished multi-row write can no longer leave behind a pairing nobody asserted. Aggregates stop double counting. ## Detecting it without the algebra Interviewers rarely want the formal proof. The working test is: does this table contain two many-valued attributes that vary independently of each other? If yes, and neither is determined by the other, you have a 4NF violation. If a sample of data shows a complete cross product for every key value, that is strong evidence, though only the domain expert can confirm the independence is a rule rather than a coincidence in the current data.
- How is a multivalued dependency different from a functional dependency?A functional dependency determines exactly one value; a multivalued dependency determines a whole set of values that recombines freely with the table's other columns. Every functional dependency is a multivalued dependency with a one-element set, so the multivalued notion is the weaker constraint and 4NF the stronger normal form.
- Can a table be in BCNF but not in 4NF?Yes, and that is the whole point of 4NF. A table whose only key is all of its columns has no nontrivial functional dependencies, so it satisfies BCNF trivially, yet it can still store a full cross product of two independent multi-valued attributes. BCNF cannot see that redundancy because it only reasons about functional dependencies.
saying these in an interview costs you the question
- Treating a multivalued dependency as just a functional dependency with a list on the right
- Claiming a BCNF table is automatically free of redundancy
- Splitting a table on two columns that are actually correlated, which loses the pairing information
- Saying 4NF requires the left side to be a candidate key, when superkey is the correct condition