Database Management Systems (DBMS) Module 7 – Normal forms and decomposition
Multivalued and join dependencies: 4NF and 5NF
What a multivalued dependency is, how to see one in data and reach 4NF, and how join dependencies define 5NF, the form for facts that need three tables.
What you will learn
- Explain why a table in BCNF can still store one fact in many rows
- Recognise a multivalued dependency in a table's rows with the swap rule
- Decompose a relation into 4NF on a dependency whose left side is no superkey
- Explain join dependencies and 5NF with a three-way rule, and recognise a 5NF problem
Before you start
What you’ll learn · Before you start
What you will learn
- Explain why a table in BCNF can still store one fact in many rows
- Recognise a multivalued dependency in a table's rows with the swap rule
- Decompose a relation into 4NF on a dependency whose left side is no superkey
- Explain join dependencies and 5NF with a three-way rule, and recognise a 5NF problem
Before you start
On this page
A course with 4 teachers and 3 textbooks, chosen independently, needs 12 rows in a table course_books(course, teacher, textbook), and one new textbook costs 4 rows. The table is in Boyce-Codd normal form (BCNF): The left-hand side of every non-trivial functional dependency that holds in the relation is a superkey. More in “Boyce-Codd normal form and the 3NF trade-off”, because it has no functional dependency at all: the copies come from a multivalued dependency, course ->> teacher, which says that a course’s teachers do not depend on its textbooks. Fourth normal form (4NF) removes it, and splitting course_books into (course, teacher) and (course, textbook) reaches it.
Join dependencies carry the idea to three or more pieces, and fifth normal form (5NF) removes the ones that the keys do not imply.
BCNF can still store one fact many times
course_books has no functional dependency at all, since a course has several teachers and several textbooks, so its only key is all three attributes and the table is in BCNF. Yet it repeats itself:
-- Each course has a set of teachers and a set of textbooks, chosen independently: every teacher of a course uses
-- every textbook of that course. One table holds both facts.
CREATE TABLE course_books (
course TEXT, teacher TEXT, textbook TEXT,
PRIMARY KEY (course, teacher, textbook));
INSERT INTO course_books
WITH teachers(course, teacher) AS (VALUES ('CS301', 'Iyer'), ('CS301', 'Rao'), ('CS301', 'Sen'), ('CS301', 'Khan'),
('CS302', 'Bose'), ('CS302', 'Das')),
textbooks(course, textbook) AS (VALUES ('CS301', 'Relational Notes'), ('CS301', 'SQL Workbook'),
('CS301', 'Storage Primer'), ('CS302', 'Kernel Notes'),
('CS302', 'Linux Labs'), ('CS302', 'Systems Text'), ('CS302', 'Shell Primer'))
SELECT course, teacher, textbook FROM teachers JOIN textbooks USING (course);
SELECT course, count(*) AS stored_rows FROM course_books GROUP BY course ORDER BY course;
-- A new textbook for CS301 is one fact, but this table needs a row for each of the 4 teachers.
INSERT INTO course_books VALUES ('CS301', 'Iyer', 'Query Tuning'), ('CS301', 'Rao', 'Query Tuning'),
('CS301', 'Sen', 'Query Tuning'), ('CS301', 'Khan', 'Query Tuning');
-- The 4NF split: one table per independent fact, and a join that gives back exactly the same rows.
CREATE TABLE course_teachers AS SELECT DISTINCT course, teacher FROM course_books;
CREATE TABLE course_textbooks AS SELECT DISTINCT course, textbook FROM course_books;
SELECT (SELECT count(*) FROM course_books) AS one_table,
(SELECT count(*) FROM course_teachers) + (SELECT count(*) FROM course_textbooks) AS two_tables,
(SELECT count(*) FROM (SELECT * FROM course_teachers NATURAL JOIN course_textbooks
EXCEPT SELECT * FROM course_books)) AS spurious_after_join;Output
┌────────┬─────────────┐ │ course │ stored_rows │ ├────────┼─────────────┤ │ CS301 │ 12 │ │ CS302 │ 8 │ └────────┴─────────────┘ ┌───────────┬────────────┬─────────────────────┐ │ one_table │ two_tables │ spurious_after_join │ ├───────────┼────────────┼─────────────────────┤ │ 24 │ 14 │ 0 │ └───────────┴────────────┴─────────────────────┘
Recorded with sql.js 1.14.2 (SQLite 3.49.1) on macOS 26 arm64. To run it yourself: sqlite3 -box :memory: < course_books.sql
Runs on this device, in your browser. The first run downloads SQLite (about 0.7 MB), which is kept for the next runs.
Your run, in this browser
CS301 has 4 teachers and 3 textbooks, so it needs 4 × 3 = 12 rows. A new textbook is one fact, and it costs 4 rows, one per teacher; leaving one out would say that a teacher does not use the book. Split into course_teachers and course_textbooks, the same facts take 14 rows instead of 24, a new textbook is one row, and the join gives back exactly the original rows.
A multivalued dependency is a promise about swapped rows
X ->> Y holds in R when, for any two rows that agree on X, the row that takes X and Y from the first and all other attributes from the second is also in R. So for each X value, the Y values and the values of the remaining attributes form every possible combination. Step through the rule on two rows of CS301, then on a table where it fails:
The drawing shows the whole scene; its 6 steps are listed below.
Every step as text
- Two rows that agree on course. Take two rows of CS301 in course_books, (CS301, Iyer, Relational Notes) and (CS301, Rao, SQL Workbook). They agree on course, the left side of the rule.
- Swap the teacher. course ->> teacher promises the row that takes course and teacher from the first row and the textbook from the second, (CS301, Iyer, SQL Workbook). course_books holds it.
- And the other way round. The swap the other way, (CS301, Rao, Relational Notes), is there too. Every pair of CS301's rows passes this test, so the rule holds in these rows.
- A table where the rule fails. In another table, course CS305 has two rows, (CS305, Menon, Graph Notes) and (CS305, Pillai, Network Labs), because each teacher there uses a book of their own.
- The swapped row is missing. The swap gives (CS305, Menon, Network Labs), which that table does not hold. One missing row is enough to refute course ->> teacher for the table.
- What rows can and cannot show. The rule holds when every pair of rows that agree on course passes. Rows can refute it, as here, but never prove it for the rows still to come; it is a rule about every legal state.
Ronald Fagin introduced these dependencies and showed that they include the functional ones as a special case (Multivalued Dependencies and a New Normal Form for Relational Databases). If X -> Y holds, the Y of the two rows is the same, and the swapped row is the second row itself, so X ->> Y holds too. Multivalued dependencies also come in pairs: X ->> Y holds exactly when X ->> Z holds, for Z the attributes outside X and Y, which is the complementation rule. Like a functional dependency, a multivalued dependency is a statement about every legal state: one table can refute it, but no table can prove it.
Key idea
X ->> Y means that every swap of two rows that agree on X is already a row of the table.
Checkpoint
Check: Redundancy that BCNF cannot see · The swap rule of a multivalued dependency
4NF asks for a superkey on the left of every multivalued dependency
A relation is in 4NF when, for every non-trivial multivalued dependency X ->> Y, X is a superkey: A set of attributes whose values identify a row: no two rows of the relation can agree on all of them. More in “Keys: super, candidate, primary, alternate, foreign”. Every functional dependency is a multivalued one, so 4NF implies BCNF. Fagin’s paper also gives the split: R breaks lossless decomposition: A split whose pieces always join back into exactly the rows of the original table, none invented and none lost. More in “Redundancy and update, insert, delete anomalies” into XY and X together with the rest exactly when X ->> Y holds, and every relation can be decomposed into 4NF without loss of information. For course_books, course ->> teacher gives (course, teacher) and (course, textbook), the split drawn below. Both are in 4NF: inside each piece the rule covers every attribute, and a multivalued dependency that covers the whole table is trivial, true of any table.
The 4NF split of course_books
Text description of the diagram
The diagram shows the table course_books and its split into fourth normal form.
- course_books has 24 rows and the key (course, teacher, textbook). Every teacher of a course appears with every textbook of that course, because the two sets are chosen independently: course ->> teacher, and so course ->> textbook.
- The split stores each set once: course_teachers, with 6 rows of course and teacher, and course_textbooks, with 8 rows of course and textbook.
- Joining the two tables on course gives back exactly the same 24 rows, with none invented, because the multivalued dependency holds.
Join dependencies need three pieces, and 5NF removes them
A join dependency *[R1, …, Rn] says that R always equals the join of its projections onto R1 to Rn. A multivalued dependency is the join dependency with two pieces, so join dependencies are the general case. Some join dependencies need three pieces: a dealer sells a brand’s models in a category exactly when the dealer is authorised for the brand, sells the category, and the brand makes it. Step through that rule:
The drawing shows the whole scene; its 5 steps are listed below.
Every step as text
- Three facts, three pairs. A dealer may be authorised for a brand, a dealer may sell a category, and a brand may make a category. Each fact is a pair, kept in a table of its own.
- The rule. A dealer sells a brand's models in a category exactly when all three facts hold, for that dealer, that brand and that category.
- sells is the join of all three. sells holds exactly the combinations the rule allows, so it equals the join of its three two-column projections. That equality is a join dependency with three pieces.
- Two pieces are not enough. Join only two of the projections and the result pairs facts that the third would rule out, so it holds rows that sells never had. No split into two tables gives sells back.
- What 5NF asks. The table's only key is all three columns, and that key does not imply this join dependency, which is exactly what 5NF rules out. A 5NF design stores the three pair tables and joins them.
Then sells(dealer, brand, category) is rebuilt by joining all three of its two-column projections, while any two of them invent rows. A relation is in 5NF, also called projection-join normal form, when every join dependency it satisfies is implied by its candidate keys (Normal Forms and Relational Database Operators).
Two further forms complete the list. Sixth normal form asks that a relation satisfy no non-trivial join dependency at all, a design proposed for data that changes over time (Date, Darwen and Lorentzos). Domain-key normal form asks that every constraint follow from the domains and the keys (A Normal Form Based on Domains and Keys).
GATE CS
In the GATE 2027 computer science syllabus, the databases section says only “normal forms” and names no particular one (GATE 2027 CS syllabus), so this lesson marks 4NF and 5NF as advanced material.
Checkpoint
Check: Fourth normal form and its split · Join dependencies and 5NF
Practise: test a multivalued dependency on rows
The exercise turns the swap rule into a function that answers for a table’s rows.
Exercise · Medium · Python
Test a multivalued dependency on a table's rows
Write mvd_holds(attrs, rows, x, y) in mvd.py. It returns True when the multivalued dependency x ->> y holds in the given rows and False when they break it.
The definition of the lesson is the test: for every two rows that agree on x, the row that takes its x and y values from the first and its other values from the second must also be among the rows. A table's rows can refute a multivalued dependency, but they cannot prove one for every future state, so the function answers only for these rows. The sample tests use the course and staff tables of the lesson.
Starter code · mvd.py
"""Does a multivalued dependency X ->> Y hold in a table's rows?
attrs is the list of the table's attribute names, rows is a list of tuples in that order, and x and y are sets of
attribute names.
"""
def mvd_holds(attrs, rows, x, y):
"""True when, for every two rows that agree on x, the row that takes x and y from the first and every other
attribute from the second is also in rows."""
return TrueThe sample tests · test_mvd.py
from mvd import mvd_holds
COURSE = ["course", "teacher", "textbook"]
def test_independent_sets():
"""every teacher of a course with every textbook of the course: course ->> teacher holds"""
rows = [("CS301", t, b) for t in ("Iyer", "Rao") for b in ("Relational Notes", "SQL Workbook")]
assert mvd_holds(COURSE, rows, {"course"}, {"teacher"}) is True
assert mvd_holds(COURSE, rows, {"course"}, {"textbook"}) is True
def test_teacher_specific_books():
"""each teacher uses a textbook of their own: course ->> teacher fails"""
rows = [("CS303", "Bose", "Kernel Notes"), ("CS303", "Das", "Linux Labs"), ("CS303", "Das", "Shell Primer")]
assert mvd_holds(COURSE, rows, {"course"}, {"teacher"}) is False
rows_ok = rows + [("CS303", "Bose", "Linux Labs"), ("CS303", "Bose", "Shell Primer"), ("CS303", "Das", "Kernel Notes")]
assert mvd_holds(COURSE, rows_ok, {"course"}, {"teacher"}) is True
def test_functional_dependency_is_multivalued():
"""when x -> y holds, x ->> y holds too, and one missing pair breaks an MVD"""
attrs = ["emp", "office", "skill"]
rows = [("Anu", "Pune", "SQL"), ("Anu", "Pune", "Go"), ("Ravi", "Kochi", "SQL")]
assert mvd_holds(attrs, rows, {"emp"}, {"office"}) is True
staff = ["emp", "skill", "language"]
rows = [("Anu", "SQL", "Hindi"), ("Anu", "Go", "English"), ("Anu", "SQL", "English")]
assert mvd_holds(staff, rows, {"emp"}, {"skill"}) is FalseA hint
Loop over every pair of rows t1, t2 (a row may pair with itself). When they agree on every attribute in x, build the row that takes the attributes in x and y from t1 and all the others from t2, position by position with enumerate(attrs). If that row is missing from rows, the dependency fails; if no pair finds a missing row, it holds.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Then practise: your weakest idea comes first, and right answers bring harder questions.
Practice that adapts to you
Practise this lesson
9 questions about 6 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
4NF in depth: a test on data, a false split reproduced, and the rules Pro: opens with a Pro, Premium or Ultimate pass
A multivalued dependency can be checked on data with one grouped query, and splitting on one that does not hold invents rows. This part runs both, proves the rules a design argument needs, and takes a table with a functional and a multivalued dependency to 4NF.
In this part:
- Testing a multivalued dependency with one grouped query
- When the count test misleads: duplicates and NULLs
- The rules a design argument needs, with short proofs
- Decomposing a table with both kinds of dependency into 4NF
3 runnable examples (SQL) · about 9 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Join dependencies and 5NF: a three-way rule rebuilt from its projections Pro: opens with a Pro, Premium or Ultimate pass
A three-way rule produces a table that only three of its projections can rebuild. This part reproduces it with row counts, shows what goes wrong when the rule lives in one table, and gives a practical way to recognise 5NF problems.
In this part:
- Rebuilding the dealers table, every way, with row counts
- What goes wrong when the rule lives in one table
- Recognising a 5NF problem in practice
1 runnable example (SQL) · about 5 minutes
Opening this part with your pass…Pro part. It opens with the same pass as the part above.
Interview questions
-
Fresher to mid · Warm-up
What is a multivalued dependency? Give an everyday example and say which normal form deals with it.
X ->> Y says that the set of Y values that goes with an X value is independent of the other attributes: for any two rows that agree on X, the row that takes X and Y from one and everything else from the other is also present. An everyday example is a course whose teachers and textbooks are chosen independently: in course_books(course, teacher, textbook), every teacher of a course appears with every textbook of it, so a course with 4 teachers and 3 textbooks needs 12 rows, and a new textbook needs 4. Every functional dependency is also a multivalued one. Fourth normal form deals with them: every non-trivial multivalued dependency must have a superkey on its left, and splitting into (course, teacher) and (course, textbook) gets there without losing any row.
-
Mid to senior
A profiles table stores (user_id, skill, language) with every combination of a user's skills and languages. A user with 12 skills adds a language and the app writes 12 rows; some writes failed halfway. Name the problem and redesign it.
-
Fresher to mid
Your table is in BCNF, yet one fact is stored in several rows and a single change touches many of them. How can that be, and how would you prove it from the data?
-
Senior to staff
Explain 5NF with a three-way example. Why can the table not be split into two, and what is the risk of keeping it as one table?
Key takeaways
- A table in BCNF can still repeat a fact when two sets of values combine freely, as course_books does.
- X ->> Y means every swap of two rows that agree on X is a row; every functional dependency is a multivalued one.
- 4NF asks for a superkey on the left of every non-trivial multivalued dependency, and the split into XY and X with the rest is lossless exactly when X ->> Y holds.
- A join dependency says a relation equals the join of some of its projections; 5NF removes those the keys do not imply, such as the dealer rule.
Terms in this lesson
- fifth normal form (5NF)
- Every join dependency that holds in the relation is implied by its candidate keys. Also called projection-join normal form.
- fourth normal form (4NF)
- For every non-trivial multivalued dependency X ->> Y that holds in the relation, X is a superkey. Every relation in 4NF is in BCNF.
- join dependency
- A rule that a relation always equals the join of its projections onto some sets of its attributes. One with two pieces is a multivalued dependency.
- multivalued dependency
- A rule X ->> Y: for any two rows that agree on X, the row that takes X and Y from one and every other attribute from the other is also in the table.
References
- R. Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases (ACM Transactions on Database Systems)
- R. Fagin: Normal Forms and Relational Database Operators (ACM SIGMOD International Conference on Management of Data)
- R. Fagin: A Normal Form for Relational Databases That Is Based on Domains and Keys (ACM Transactions on Database Systems)
- C. Beeri: On the Membership Problem for Functional and Multivalued Dependencies in Relational Databases (ACM Transactions on Database Systems)
- C. J. Date and R. Fagin: Simple Conditions for Guaranteeing Higher Normal Forms in Relational Databases (ACM Transactions on Database Systems)
- C. J. Date, H. Darwen and N. A. Lorentzos: Time and Relational Theory, chapter Database Design I: Structure (Morgan Kaufmann)
- GATE 2027 syllabus for Computer Science and Information Technology (CS) (Indian Institute of Technology Madras (GATE 2027))
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress