Database Management Systems (DBMS) Module 7 – Normal forms and decomposition

Lossless joins and dependency preservation

How to tell whether a decomposition joins back without spurious rows and keeps every dependency checkable, with the two-table test run on real tables.

Intermediate
20 minutes
Examples run with sql.js 1.14.2, Python 3.14.8 and Pyodide 314.0.7
By MySmartCoPilot

Free: A lossy split adds rows and never loses one · Two pieces join losslessly when their shared attributes determine one of them · A decomposition preserves dependencies when its pieces imply F · 2 more sections. With a pass: 2 in-depth parts and 3 interview answers, about 13 minutes.

What you will learn

Test a split into two tables for lossless joins with the closure of their shared attributes
Apply the chase test to decompositions into three or more tables
Check dependency preservation with closures restricted to one piece at a time, without computing F+
Distinguish lossless joins from dependency preservation, and judge each property of a decomposition on its own

Before you start

Boyce-Codd normal form and the 3NF trade-off

What you’ll learn · Before you start

What you will learn

Test a split into two tables for lossless joins with the closure of their shared attributes
Apply the chase test to decompositions into three or more tables
Check dependency preservation with closures restricted to one piece at a time, without computing F+
Distinguish lossless joins from dependency preservation, and judge each property of a decomposition on its own

Before you start

Boyce-Codd normal form and the 3NF trade-off

On this page

Split a cinema’s 6 tickets into two tables that share only the movie, join them back, and 9 rows come out. Three of them pair a ticket with a show it was never sold for, and nothing in a row says which. A decomposition replaces a relation R with smaller relations whose attributes together cover R; it has lossless joins, and is a 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”, when the natural join of the pieces gives back exactly the rows of R in every legal state, never a row more.

It has dependency preservation: A split preserves dependencies when every functional dependency of the original table can still be checked within the pieces, without a join. when every dependency of R can still be checked inside single pieces: the dependencies that hold in the pieces imply all of F. Lossless joins protect the data and dependency preservation protects the rules. Each can hold without the other, so a design checks both. This lesson runs the test for two pieces on two splits of the tickets, sets the two properties side by side and names the tests for larger decompositions.

A lossy split adds rows and never loses one

Joining the projections of a table always returns every original row, because each row agrees with its own pieces. So a bad split, a lossy decomposition: A split whose pieces join back into rows the original table never had, so the true rows can no longer be told apart. More in “Redundancy and update, insert, delete anomalies”, never loses rows: it adds spurious tuple: A row that the join of a split's pieces returns although the original table never held it. More in “Redundancy and update, insert, delete anomalies” ones, and then nobody can tell which rows are true. Here a cinema’s tickets are split in two ways, each pair of pieces joined back, and the rows compared with the original in both directions with EXCEPT (SQLite: SELECT):

Two splits of tickets, joined back and compared with the original SQL · sql/two_splits.sql

-- Cinema tickets: a ticket is for one show and one seat; a show is one movie on one screen.
CREATE TABLE tickets (ticket_id INTEGER PRIMARY KEY, show_id TEXT, movie TEXT, screen INTEGER, seat TEXT);
INSERT INTO tickets VALUES
  (1, 'S1', 'Lagaan',   1, 'A1'), (2, 'S1', 'Lagaan',   1, 'A2'),
  (3, 'S2', 'Lagaan',   2, 'B4'), (4, 'S3', 'Sholay',   1, 'A1'),
  (5, 'S3', 'Sholay',   1, 'C7'), (6, 'S4', 'Swades',   3, 'D2');

-- Split 1 shares movie, which is a key of neither piece (Lagaan has two shows).
CREATE TABLE p1 AS SELECT DISTINCT ticket_id, movie, seat FROM tickets;
CREATE TABLE p2 AS SELECT DISTINCT movie, show_id, screen FROM tickets;
-- Split 2 shares show_id, which is the key of its second piece.
CREATE TABLE q1 AS SELECT DISTINCT ticket_id, show_id, seat FROM tickets;
CREATE TABLE q2 AS SELECT DISTINCT show_id, movie, screen FROM tickets;

SELECT 'split 1, on movie' AS split,
  (SELECT count(*) FROM p1 NATURAL JOIN p2) AS joined_rows,
  (SELECT count(*) FROM (SELECT ticket_id, show_id, movie, screen, seat FROM p1 NATURAL JOIN p2
                         EXCEPT SELECT * FROM tickets)) AS spurious,
  (SELECT count(*) FROM (SELECT * FROM tickets
                         EXCEPT SELECT ticket_id, show_id, movie, screen, seat FROM p1 NATURAL JOIN p2)) AS missing
UNION ALL
SELECT 'split 2, on show_id',
  (SELECT count(*) FROM q1 NATURAL JOIN q2),
  (SELECT count(*) FROM (SELECT ticket_id, show_id, movie, screen, seat FROM q1 NATURAL JOIN q2
                         EXCEPT SELECT * FROM tickets)),
  (SELECT count(*) FROM (SELECT * FROM tickets
                         EXCEPT SELECT ticket_id, show_id, movie, screen, seat FROM q1 NATURAL JOIN q2));

-- The spurious rows of split 1: tickets 1, 2 and 3 paired with the other Lagaan show.
SELECT ticket_id, show_id, movie, screen, seat FROM p1 NATURAL JOIN p2
EXCEPT SELECT * FROM tickets ORDER BY ticket_id;

Output

┌─────────────────────┬─────────────┬──────────┬─────────┐
│        split        │ joined_rows │ spurious │ missing │
├─────────────────────┼─────────────┼──────────┼─────────┤
│ split 1, on movie   │ 9           │ 3        │ 0       │
│ split 2, on show_id │ 6           │ 0        │ 0       │
└─────────────────────┴─────────────┴──────────┴─────────┘
┌───────────┬─────────┬────────┬────────┬──────┐
│ ticket_id │ show_id │ movie  │ screen │ seat │
├───────────┼─────────┼────────┼────────┼──────┤
│ 1         │ S2      │ Lagaan │ 2      │ A1   │
│ 2         │ S2      │ Lagaan │ 2      │ A2   │
│ 3         │ S1      │ Lagaan │ 1      │ B4   │
└───────────┴─────────┴────────┴────────┴──────┘

Recorded with sql.js 1.14.2 (SQLite 3.49.1) on macOS 26 arm64. To run it yourself: sqlite3 -box :memory: < two_splits.sql

The split that shares movie returns 9 rows from 6, and the second query lists the 3 extra ones: every ticket for Lagaan comes back once with each of its two shows. The split that shares show_id returns the 6 original rows and nothing else. In both splits the column missing counts 0, as it must. Step through the join of the three Lagaan tickets:

Interactive · step by step The Lagaan tickets, joined back after each split Step through the join. Each arrow pairs a ticket row with a show row that has the same value in the shared column.

The drawing shows the whole scene; its 5 steps are listed below.

Every step as text

Split on movie. Split 1 keeps (ticket_id, movie, seat) and (movie, show_id, screen). The three Lagaan tickets keep only the movie, and the second piece holds Lagaan's two shows.
Ticket 1 meets both shows. The natural join pairs rows that agree on movie. Ticket 1 agrees with both Lagaan shows, so it comes back twice, with S1, its real show, and with S2.
Tickets 2 and 3 too. Tickets 2 and 3 pair with both shows as well. Each of the three Lagaan tickets returns one true row and one spurious row.
9 rows from 6. The Sholay and Swades tickets meet one show each, so the join returns 9 rows, the 6 true ones and the 3 dashed ones. Nothing in a row says which kind it is.
Split on show_id. Split 2 keeps show_id beside each ticket instead. A ticket then agrees with exactly one show, its own, so the join returns the 6 rows and nothing else.

Two pieces join losslessly when their shared attributes determine one of them

A split of R into R1 and R2 is lossless exactly when the shared attributes R1 ∩ R2 determine all of R1 or all of R2, a consequence of the theory of joins (Aho, Beeri and Ullman, 1979). Then the shared attributes are 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” of one piece, so each row of the other piece finds exactly one partner, its own. In practice, compute the attribute closure: X+, the set of all attributes that the attributes X determine through the functional dependencies, X itself included. More in “Attribute closure and finding candidate keys” of the shared attributes and compare it with each piece:

Split of the tickets	Closure of the shared attributes	Verdict
Sharing movie	movie alone	Lossy: it covers neither piece
Sharing show_id	show_id, movie and screen	Lossless: it covers the second piece

Two splits of tickets, and what their joins return

Text description of the diagram

The diagram shows the tickets table, with 6 rows and the dependencies ticket_id -> show_id, seat and show_id -> movie, screen, split in two ways.

Split 1 makes the pieces (ticket_id, movie, seat) and (movie, show_id, screen), which share movie. Joining them returns 9 rows, 3 of them spurious, because movie is a key of neither piece: a movie with two shows pairs every ticket with both.
Split 2 makes the pieces (ticket_id, show_id, seat) and (show_id, movie, screen), which share show_id. Joining them returns exactly the original 6 rows, because show_id is the key of the second piece, so each ticket finds one show.

Splitting on a dependency X -> Y into XY and the rest of R with X always passes this test, because the shared X determines all of XY. That is why every step of a BCNF decomposition is lossless.

Key idea

For two pieces, compute the closure of what they share: the split is lossless exactly when that closure covers one whole piece.

Checkpoint

Check: What a lossy join adds · The test for two pieces

Question 1 of 2 The split of the tickets that shares movie returns 9 rows from 6. Which rows are the 3 extra ones?
Choose one answer.

Rows with NULL in the screen column The Swades ticket with its seat moved Copies of the Sholay tickets Each Lagaan ticket paired with the Lagaan show it was not sold for

Show the answer: Question 1 of 2

Answer: Each Lagaan ticket paired with the Lagaan show it was not sold for

Ticket 1 comes back with S1 and S2, ticket 2 with S1 and S2, ticket 3 with S2 and S1. One row of each pair is true and the other spurious: 6 true rows and 3 spurious ones.
Question 2 of 2 R(A, B, C, D) has A -> B and C -> D. Is the split into (A, B, C) and (C, D) lossless?
Choose one answer.

No, because A -> B and C -> D lie in different pieces Yes, because the shared C determines all of (C, D) No, because C does not determine A Only if A is a key of R

Show the answer: Question 2 of 2

Answer: Yes, because the shared C determines all of (C, D)

Compute the closure of R1 ∩ R2 = {C}: it is {C, D}, all of R2, so the split is lossless. This is the shape of a split on a dependency, C -> D, into CD and the rest with C.

A decomposition preserves dependencies when its pieces imply F

A decomposition preserves dependencies when the dependencies that hold inside the pieces, the projected dependencies: The dependencies of F+ whose attributes all lie inside one piece of a split. Each piece's normal form is judged by them. More in “Boyce-Codd normal form and the 3NF trade-off”, imply every dependency of F. Then each insert or update can be checked one table at a time. The teaching split of the previous lesson fails: student course -> teacher holds in no piece and follows from nothing that does.

A dependency does not have to fit inside one piece to be preserved. Take three staff identifiers that map one to one: emp_id -> email, email -> badge and badge -> emp_id, split into (emp_id, email) and (email, badge). No piece holds badge -> emp_id, yet it is preserved:

Interactive · message by message badge -> emp_id, checked through two pieces Step through the checks. Each arrow is a dependency that one piece can check on its own.

The drawing shows the whole scene; its 4 steps are listed below.

Every step as text

No piece holds it. The staff identifiers emp_id, email and badge map one to one, and the split keeps (emp_id, email) and (email, badge). badge -> emp_id needs badge and emp_id together, and no piece has both.
Inside (email, badge). In the second piece a badge fixes the email, because badge -> emp_id and emp_id -> email give badge -> email, and both attributes are in that piece.
Inside (emp_id, email). In the first piece the email fixes the emp_id, through email -> badge and badge -> emp_id, so that piece checks email -> emp_id on its own.
Preserved. The two checks, one in each piece, chain into badge -> emp_id. The dependency is preserved although it fits in no single piece.

A test of preservation therefore has to follow chains through the pieces, not look for each dependency inside one.

Lossless joins and dependency preservation are independent

Every combination occurs, so an exam answer or a design decision must check each property on its own:

Split	Lossless join	Dependency preservation
R(A, B, C), A -> B and B -> C, into (A, B) and (B, C)	Yes	Yes
teaching, into (course, teacher) and (student, teacher)	Yes	No: student course -> teacher is lost
R(A, B, C, D), A -> B and C -> D, into (A, B) and (C, D)	No: nothing is shared	Yes
R(A, B, C), A -> B and B -> C, into (A, C) and (B, C)	No: C determines nothing	No: A -> B is lost

Two tests handle what the rule for two pieces cannot. The chase builds one row per piece and makes symbols equal through the dependencies until some row is complete or nothing changes. The restricted-closure test grows each left-hand side with closures taken inside one piece at a time, so it never builds F+.

Checkpoint

Check: Dependency preservation · Two independent properties

Question 1 of 2 The teaching split keeps (course, teacher) and (student, teacher). Why is student course -> teacher lost?
Choose one answer.

Because teacher -> course is lost too Because the split is lossy No piece holds student and course together, and what the pieces check does not imply it Because student course is not a key of R

Show the answer: Question 1 of 2

Answer: No piece holds student and course together, and what the pieces check does not imply it

To check student course -> teacher, a database would have to join the two pieces on every insert. The split keeps the data and loses the rule.
Question 2 of 2 R(A, B, C) has A -> B and B -> C. Which properties does the split into (A, C) and (B, C) have?
Choose one answer.

Lossless joins only Dependency preservation only Neither, because C determines nothing and A -> B fits in no piece Both

Show the answer: Question 2 of 2

Answer: Neither, because C determines nothing and A -> B fits in no piece

Run both tests every time. Here the closure of the shared C is C alone, so the join is lossy, and A -> B is lost because nothing the pieces check leads from A to B.

Practise: lossless or lossy

The exercise asks for the test for two pieces as a function, and its sample tests try lossless and lossy splits of three relations of this module.

Exercise · Easy · Python

Write the lossless-join test for a split into two tables

Write lossless_pair(r1, r2, fds) in lossless.py. It receives the two pieces of a split as sets of attribute names and the dependencies of the relation as a list of (lhs, rhs) pairs of sets, and returns True when the split is lossless and False when its join can produce spurious rows.

Use the rule of this lesson for two pieces. closure is already written for you. The sample tests try three relations of this module: hostel, tickets and duties, with lossless and lossy splits of each.

Starter code · lossless.py

"""The two-piece test for a lossless join. Attributes are strings; a dependency is a pair of sets (lhs, rhs)."""


def closure(attrs, fds):
    """Every attribute that attrs determine under fds."""
    result = set(attrs)
    grew = True
    while grew:
        grew = False
        for lhs, rhs in fds:
            if lhs <= result and not rhs <= result:
                result |= rhs
                grew = True
    return result


def lossless_pair(r1, r2, fds):
    """Whether splitting a relation into the pieces r1 and r2 (sets of attributes) is lossless under fds."""
    return False

The sample tests · test_lossless.py

from lossless import lossless_pair


def fd(text):
    lhs, rhs = text.split("->")
    return set(lhs.split()), set(rhs.split())


HOSTEL = [fd("roll_no -> room"), fd("room -> block"), fd("block -> warden")]
TICKETS = [fd("ticket_id -> show_id seat"), fd("show_id -> movie screen")]
DUTIES = [fd("driver route -> bus"), fd("bus -> route"), fd("bus -> depot")]


def test_hostel():
    """hostel: the shared block determines the second piece"""
    assert lossless_pair({"roll_no", "room", "block"}, {"block", "warden"}, HOSTEL) is True
    assert lossless_pair({"block", "warden"}, {"roll_no", "room", "block"}, HOSTEL) is True
    assert lossless_pair({"roll_no", "room"}, {"block", "warden"}, HOSTEL) is False


def test_hostel_through_a_chain():
    """hostel: roll_no reaches warden only through room and block, whatever the order of the dependencies"""
    assert lossless_pair({"roll_no", "warden"}, {"roll_no", "room", "block"}, HOSTEL[::-1]) is True


def test_tickets():
    """tickets: shared show_id is a key of one piece; shared movie is a key of neither"""
    assert lossless_pair({"ticket_id", "show_id", "seat"}, {"show_id", "movie", "screen"}, TICKETS) is True
    assert lossless_pair({"ticket_id", "movie", "seat"}, {"movie", "show_id", "screen"}, TICKETS) is False


def test_duties():
    """duties: a lossless split that still loses a dependency, and a lossy one"""
    assert lossless_pair({"bus", "route", "depot"}, {"driver", "bus"}, DUTIES) is True
    assert lossless_pair({"driver", "route"}, {"route", "bus", "depot"}, DUTIES) is False

A hint

Only the attributes the two pieces share can match their rows in a join. Compute the closure of r1 & r2 and ask whether it reaches every attribute of r1, or every attribute of r2: then the shared attributes are a key of that piece, and each row of the other piece finds at most one partner.

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 try lossy joins, the two-piece test, preservation and independence, weakest first.

The chase for three or more pieces, step by step, with a counterexample Pro: opens with a Pro, Premium or Ultimate pass

A pairwise test cannot judge a decomposition into three or more pieces. This part runs the chase step by step on a lossless and a lossy split, then turns the failed chase into a real table whose join invents rows.

In this part:

Why pairwise tests are not enough for three pieces
The chase, traced on a lossless and a lossy split
A failed chase is a counterexample you can run
Why the chase is correct, with the invariant that drives it

1 diagram · 2 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.

Choose a pass I have a 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).

Checking dependency preservation without F+, with costs and an exam item Pro: opens with a Pro, Premium or Ultimate pass

Projecting F+ onto every piece costs exponential work, yet the question it answers can be decided in polynomial time. This part traces the restricted-closure test, proves it, counts its work against projection, and works a multiple-select item option by option.

In this part:

The restricted-closure test, traced on two splits
Why the test is right: the invariant
Closures counted against projection
A multiple-select item, option by option

2 runnable examples (Python) · about 7 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.

Choose a pass I have a 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).

Interview questions

Fresher to mid · Warm-up

What does it mean for a decomposition to be lossless, and how do you test a split into two tables?

A decomposition is lossless when joining its pieces gives back exactly the original rows, in every legal state of the table. The join of the projections always contains the original rows, so a lossy split adds spurious rows that were never there. For a split into two pieces R1 and R2 there is a short test: compute the closure of their shared attributes. The split is lossless exactly when that closure contains all of R1 or all of R2, that is, when the shared attributes are a key of one piece. Splitting a ticket table on show_id, the key of its shows piece, is lossless; splitting it on movie, a key of neither piece, joins 6 rows into 9. For three or more pieces, the chase decides it instead of tests on pairs.
Mid to senior

A migration splits an order_lines table of 40 million rows into orders, lines and products. Before you drop the old table, how do you show, from the dependencies and from the data, that the split is lossless?

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Fresher to mid

Is every lossless decomposition dependency preserving? Is every dependency-preserving decomposition lossless? Give a counterexample each way, and say which property you would give up in a production schema.

Model answer, Pro. First step and follow-ups
Senior to staff

Explain why the chase test is correct. Why does a row of a's prove the join lossless, and why does a chase that stops without one prove it lossy?

Model answer, Pro. First step and follow-ups

Key takeaways

A lossless decomposition joins back to exactly the original rows; a lossy one adds spurious rows, never loses them, as the split of the tickets on movie added 3.
Two pieces are lossless exactly when the closure of their shared attributes covers one whole piece.
A decomposition preserves dependencies when the dependencies inside its pieces imply all of F, even when a dependency fits in no single piece.
The two properties are independent: check each one, every time.

Terms in this lesson

chase: A test for lossless joins of any number of pieces: one row per piece, with symbols made equal through the dependencies until a row of distinguished symbols appears or nothing changes.
dependency preservation: A split preserves dependencies when every functional dependency of the original table can still be checked within the pieces, without a join.
tableau: The table the chase works on: one row per piece of a decomposition and one column per attribute, holding symbols instead of values.

References

A. V. Aho, C. Beeri and J. D. Ullman: The Theory of Joins in Relational Databases (ACM Transactions on Database Systems)
C. Beeri and P. Honeyman: Preserving Functional Dependencies (SIAM Journal on Computing)
J. Rissanen: Independent Components of Relations (ACM Transactions on Database Systems)
SQLite: SELECT (NATURAL JOIN and compound SELECT with EXCEPT) (SQLite)
GATE 2027 question paper pattern (MCQ, MSQ and NAT) (Indian Institute of Technology Madras (GATE 2027))

Report a problem with this lesson

In this module: Normal forms and decomposition

First, second and third normal forms Free lesson, Pro answers: 20 minutes
Boyce-Codd normal form and the 3NF trade-off Free core, Pro depth: 8 of 20 minutes free
Lossless joins and dependency preservation Free core, Pro depth: 7 of 20 minutes free
3NF synthesis and BCNF decomposition algorithms Free core, Pro depth: 8 of 20 minutes free
Multivalued and join dependencies: 4NF and 5NF Free core, Pro depth: 8 of 20 minutes free
Practical schema design and denormalisation Free core, Pro depth: 8 of 20 minutes free

Your country

Lossless joins and dependency preservation

What you will learn

Before you start

What you will learn

Before you start

A lossy split adds rows and never loses one

Two pieces join losslessly when their shared attributes determine one of them

A decomposition preserves dependencies when its pieces imply F

Lossless joins and dependency preservation are independent

Practise: lossless or lossy

Write the lossless-join test for a split into two tables

Results of the sample tests

The chase for three or more pieces, step by step, with a counterexample Pro: opens with a Pro, Premium or Ultimate pass

Checking dependency preservation without F+, with costs and an exam item Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

What does it mean for a decomposition to be lossless, and how do you test a split into two tables?

A migration splits an order_lines table of 40 million rows into orders, lines and products. Before you drop the old table, how do you show, from the dependencies and from the data, that the split is lossless?

Is every lossless decomposition dependency preserving? Is every dependency-preserving decomposition lossless? Give a counterexample each way, and say which property you would give up in a production schema.

Explain why the chase test is correct. Why does a row of a's prove the join lossless, and why does a chase that stops without one prove it lossy?

Key takeaways

References

Related tools