Normalisation and decomposition

Dependencies describe the allowed facts

A relation schema names a set of attributes, the columns in the relation. Write R(order_id, line_no, product_id, quantity, unit_price) for the order-line schema. A relation on that schema is a set of rows. The formal analysis here uses ordinary values, equality and sets: no duplicate rows and no SQL NULL. Values, missing data and equality explains where SQL needs further care.

A functional dependency, or FD, X → Y says that any two rows agreeing on every attribute in X must agree on every attribute in Y. Both sides can be sets. Thus (order_id, line_no) → (product_id, quantity, unit_price) says that two claims about the same numbered line must agree on all three line facts. The left side is the determinant.

The rule concerns every legal state. It does not say that a quantity can never change: changing the one authoritative row can leave the dependency true. Nor does it require every possible order and line number to have a row. It rules out two simultaneous, conflicting answers for one determinant.

Consider a flattened relation that also stores customer_id and customer_name on every line. We declare these rules:

The agreed unit_price belongs to the line. P7’s later catalogue price of 22.00 does not replace the 20.00 agreed on order 103. Declaring product_id → unit_price would impose the wrong business rule. Likewise, the sample’s distinct customer names do not justify customer_name → customer_id.

A dependency is trivial when its right side is contained in its left: (order_id, line_no) → order_id merely repeats something already supplied. We care about non-trivial dependencies because they add information. Let F name the declared FD set. Its closure, F⁺, is the set of all FDs logically implied by those rules, including ones we have not written down.

Attribute closure and candidate keys

To decide whether a set of attributes determines another, collect everything it can reach. Start with the supplied attributes. Whenever the whole left side of a dependency is in the collection, add its right side. Repeat until a full pass adds nothing. The resulting attribute closure, X⁺ under F, is a set of attributes, rather than the set of dependencies denoted by F⁺.

Start the flattened line’s closure with order_id and line_no. Together they supply the product, quantity and agreed unit price. The order ID also supplies the customer ID, which in turn supplies the current customer name. No further dependency adds an attribute.

The pair reaches all seven attributes. The order alone reaches the customer and current name, but says nothing about which line, its product, quantity or agreement. That is the difference between identifying one order and identifying one flattened line row.

The closure gives three tests. F implies X → Y exactly when every attribute of Y appears in X⁺. X is a superkey of R when X⁺ contains all of R. It is a candidate key when it is a superkey and no proper subset is. To test minimality, remove each attribute in turn and compute the closure again. If no one-attribute removal remains a superkey, no smaller subset can be one either.

Finding every candidate key

Finding one key is not always enough. An attribute belonging to any candidate key is called prime; one belonging to none is non-prime. The distinction affects normal forms even after a primary key has been chosen.

A useful starting point is any attribute absent from every dependency’s right side. The closure cannot acquire it from elsewhere, so every key must include it. Remove trivial right-side occurrences first if using this shortcut. Add combinations of the remaining attributes, test their closures, and retain only minimal superkeys. Once a key is found, supersets of it need not be tested as candidate keys. This can still be a large search when there are many attributes.

For the flattened line relation, order_id and line_no never occur on a right side. Every key needs both, and their pair reaches everything. It is the only candidate key under these FDs.

Now consider the independent relation buyer_advice(customer_id, tea_style, advisor_id). Each adviser advises one tea style, and each customer has at most one adviser for a style:

Customer is absent from the right sides, so every key includes it. Customer alone fails; either of the two remaining attributes completes it. Those are all the candidate keys. Every attribute is prime, although neither adviser nor style is a key alone. Selecting (customer_id, tea_style) as the primary key does not make the other candidate disappear.

Why the inference rules work

The closure procedure rests on Armstrong’s axioms. Each rule can be understood by taking any pair of legal rows and asking where they must agree.

• Reflexivity: if Y is contained in X, then X → Y. Agreement on a set includes agreement on its parts.
• Augmentation: from X → Y, infer XZ → YZ, where juxtaposition means set union. Rows agreeing on X and Z agree on Y by the given rule, and on Z already.
• Transitivity: from X → Y and Y → Z, infer X → Z. Agreement passes through Y.

These rules are sound and complete for implication by FDs: they derive only consequences of the rules, and can derive every such consequence. Adding a dependency’s right side during closure is one compact use of that reasoning. We need not enumerate F⁺ to answer a particular implication or key question.

Lossless joins and dependency preservation

A decomposition replaces a relation schema by smaller schemas whose attributes together cover it. A projection retains the selected columns of its rows, removing duplicate projected rows. A natural join combines rows that agree on all their shared attributes.

A decomposition is lossless when joining the projections of every legal original relation gives exactly that relation back. Every original row necessarily survives the round trip: its own pieces match each other. The danger is extra rows made from pieces of different originals. The information lost is which pieces belonged together.

Mina’s order 101 was placed on 12 October 2026 at 09:30 UTC, and order 103 on 20 October at 10:15 UTC. Both belong to customer 1. Splitting these rows into (order_id, customer_id) and (customer_id, placed_at) keeps every value but loses the order–timestamp association. Joining on customer 1 pairs each order with both timestamps, producing four rows instead of two.

Testing a binary decomposition

For a split into schemas R₁ and R₂, calculate the closure of their shared attributes. Under FDs alone, the split is lossless if and only if the intersection determines every attribute of at least one side:

(R₁ ∩ R₂) → R₁ or (R₁ ∩ R₂) → R₂.

That split shares only customer_id. A customer can have several orders and timestamps, so neither test passes. Retaining order_id on both sides would pass: an order determines its customer and timestamp. There is little reason to split these particular order facts in practice; the example isolates the reconstruction test.

Why does determining one side suffice? For a proposed join row, take the original row that supplied its other side. Both agree on the shared attributes. The dependency forces the determined side to match too, so the proposed row was already present. With FDs as the only constraints, failure of both conditions permits a counterexample. With other kinds of dependency, this FD test remains sufficient but need not be necessary; the independent memberships below are one such case.

Testing several projections

A sequence of proven lossless binary splits establishes that the final decomposition is lossless. For an arbitrary set of projections, an FD chase can test the guarantee directly. Instead of trying particular customers and orders, it follows arbitrary symbols constrained by the FDs.

Take the smaller flattened schema (order_id, line_no, customer_id, customer_name), with order_id → customer_id and customer_id → customer_name. The proposed projections are order/line, order/customer and customer/name. Build a tableau, a table of symbols with one row per projection and one column per original attribute. Each column has one distinguished target symbol, an a. A projection’s row has those targets in the columns it retains; its missing columns start with fresh b symbols.

Abbreviate the four columns as O, L, C and N, in that order. The order/line row starts as (aO, aL, b1C, b1N). The order/customer row is (aO, b2L, aC, b2N), and the customer/name row is (b3O, b3L, aC, aN). Each different symbol initially stands for a potentially different value.

When two tableau rows agree on an FD’s determinant, merge the corresponding right-side symbols everywhere they occur. Prefer the distinguished symbol when either symbol is distinguished; otherwise keep one of the two ordinary symbols. Continue applying all FDs until a row is entirely distinguished, or no merge remains possible.

The first two rows agree on order aO. Applying order_id → customer_id replaces b1C with aC. All three rows now agree on that customer, so customer_id → customer_name merges their name symbols into aN.

The first row becomes (aO, aL, aC, aN), the whole target tuple. Any tuple assembled from the projections is therefore forced to be an original tuple. If a fully chased tableau has no such row, the decomposition is lossy under the FDs. The symbols then supply a counterexample. This is a test of all legal states, unlike successfully joining today’s sample. Chases for other dependency languages have additional rules; this small procedure is specifically for FDs.

Testing the dependencies that remain

Dependency preservation asks a separate question: do the FDs that can be checked within the resulting relations together imply all the original FDs? For each component Rᵢ, project all implied FDs onto it. Call the result Fᵢ. Its determinants and dependent attributes must both lie within Rᵢ. Let G be the union of these local FD sets.

For each original X → Y, compute X⁺ using G. Every attribute of Y must be reached. This proves that local checks suffice. Since every rule in G was implied by F already, the other direction of equivalence is automatic.

Do not merely keep the dependencies originally written on paper. For example, order_id → customer_id and customer_id → customer_name imply order_id → customer_name. That last dependency belongs in the projection onto an order/name schema, even though it was never written separately. A small schema’s projected set can be obtained by computing the original closure of each subset, then retaining the reached attributes that lie inside the component.

The chase decomposition preserves both original rules: order/customer checks one, customer/name checks the other. A different split into (order_id, line_no, customer_id) and (order_id, customer_name) covers all four attributes and is lossless: the shared order_id determines the whole second component. Yet the local FDs together do not imply customer_id → customer_name. Comparing names across one customer’s orders would require information from both.

From second normal form to Boyce–Codd normal form

Normal forms diagnose different dependencies that make facts repeat. The analysis begins with the ordinary first-normal-form relation described above. All candidate keys count, regardless of which one the database calls primary.

Second normal form, or 2NF, requires every non-prime attribute to depend fully on every candidate key: no proper subset of a candidate key may determine it. In the flattened line relation, the only key is (order_id, line_no). Customer depends on order_id alone, so it fails 2NF. Customer and current name belong with their own determinants, rather than being repeated for each line.

After moving line facts apart, suppose an order relation still contains (order_id, customer_id, customer_name). It passes 2NF with its single-attribute order key, but retains order_id → customer_id → customer_name. Many orders can repeat the same customer’s current name.

The precise third normal form, or 3NF, test is this: for every implied non-trivial FD X → A with one right-side attribute, either X is a superkey or A is prime. The order relation fails: customer is not a superkey and current name is non-prime. Moving names into customers(customer_id, name) removes that repetition.

Boyce–Codd normal form, or BCNF, removes the prime-attribute exception. Every implied non-trivial FD must have a superkey determinant. BCNF therefore implies 3NF. The familiar advice to remove partial and transitive dependencies explains the shop’s initial repair, but the exact test matters when keys overlap.

Return to buyer_advice. Its two candidate keys are customer/style and customer/adviser. All three attributes are prime, so the schema meets 3NF. Yet advisor_id → tea_style violates BCNF: an adviser can advise several customers and does not identify a whole assignment. The same adviser’s style will be repeated on those assignments.

Decomposing into BCNF

To split a schema R on a violating FD X → Y, make one component X ∪ Y and the other R − (Y − X). In words, take the determinant and its dependent attributes into one relation, then remove the dependent attributes from the original while retaining the determinant. The two sides share X, which determines the first side, so the split is lossless.

Repeat for every component that still violates BCNF, using the FDs implied on that component. A dependency whose intermediate attribute has moved elsewhere may still imply a local dependency. Rechecking only the original written rules can miss it. Each genuine violation makes both schemas smaller, so the process terminates. The result is lossless and in BCNF, but dependency preservation needs its own check. Different choices of violation can give different decompositions.

For buyer_advice, splitting on adviser/style gives (advisor_id, tea_style) and (customer_id, advisor_id). Iris Lin, A1, and Oren Moss, A2, both advise green tea. Initially customer 1 has A1 and customer 2 has A2. Adding the assignment (1, A2) duplicates neither local key, yet customer 1 now has two advisers for green tea.

The original relation could reject two advisers for customer 1 and green tea. After the split, a key on adviser checks its style; a key on customer/adviser checks duplicate assignments. Neither relation contains customer and style together. The closure of (customer_id, tea_style) under the local FDs cannot reach advisor_id. That original dependency has not been preserved.

This does not contradict losslessness. Projection and reconstruction of a legal original are safe. Independently changing the resulting relations can admit a state that no legal original could have produced.

Keeping the 3NF assignment relation can be an intentional choice: it keeps the customer/style rule together while retaining some repetition of adviser/style. That repeated rule still needs enforcement too; declaring one candidate key alone does not implement every FD. Alternatively, keep the BCNF split and arrange a cross-table check. Constraints and data integrity and Transactions and isolation develop the enforcement mechanisms and their concurrent behaviour. A normal-form proof does not provide those mechanisms.

Synthesising a dependency-preserving 3NF design

BCNF decomposition starts with a wide schema and splits it. 3NF synthesis starts with a reduced set of FDs and builds relations around them. Under FDs it can always provide all three properties: 3NF, dependency preservation and a lossless join.

First find a minimal cover, an equivalent FD set with a single attribute on each right side, no unnecessary left-side attribute and no redundant dependency. “Minimal” does not promise a unique answer or the smallest possible number of characters.

Split every multiple-attribute right side into separate rules. For X → A, test whether a left-side attribute B is extraneous by computing (X − {B})⁺ under the current FD set. If it still contains A, remove B. Test a redundant rule by temporarily removing the whole rule and computing X⁺ under the others. If A is still reached, discard it. Repeat the reductions as needed, retaining equivalence at each step.

Take the flattened line’s three declared dependencies from the first table. Suppose the written set also includes (order_id, line_no) → customer_id and order_id → customer_name. In the first extra rule, the line number adds nothing: the order ID already supplies the customer. In the second, the name is already reachable through that customer. Removing these repeated rules leaves the original dependencies; splitting their right sides gives five single-attribute rules.

Group the remaining rules with the same determinant. For each group X → Y, create a schema X ∪ Y. Remove a schema contained in another, retaining one copy if they are equal. If no resulting schema contains a candidate key of the original relation, add a relation consisting of one such key.

For the line example, grouping by determinant creates (order_id, line_no, product_id, quantity, unit_price), (order_id, customer_id) and (customer_id, customer_name). None is contained in another. The first already contains the original candidate key, (order_id, line_no), so no extra key relation is needed.

The minimal cover makes the synthesis meet 3NF; putting each cover rule in a component preserves the FDs. The construction’s key condition ensures a lossless join. These are guarantees of the complete construction together: adding a key relation to an arbitrary decomposition does not by itself establish any of them. Different reduction choices can yield different minimal covers and designs.

Why a key relation may be needed

Consider (product_id, product_name, tag), with only product_id → product_name. P7 is the Blue mug and has the tags gift and ceramic. The candidate key is (product_id, tag). Synthesis from the FD alone makes (product_id, product_name). That schema preserves the name rule, but drops tag membership entirely.

Add the candidate-key relation (product_id, tag). Joining on product ID now recovers both named memberships. This also retains an attribute, tag, that appears in no non-trivial FD. A rule list is not a list of every fact that needs a home.

Multivalued dependencies and fourth normal form

FDs concern one answer for a determinant. They do not describe the shop’s two independent membership sets: P7 has tags gift and ceramic, and suppliers S1 and S2. In (product_id, tag, supplier_id), no proper subset is declared to determine the whole row. It passes BCNF under those rules, yet keeping independent lists together requires four combinations.

A multivalued dependency, or MVD, X ↠ Y describes that independence. Let Z be the remaining attributes outside X ∪ Y. For any two rows agreeing on X, the relation must also contain the row with the first row’s Y part and the second row’s Z part, keeping their common X. Reversing the two rows gives the other swapped combination.

For the memberships, product is X, tag is Y and supplier is Z. Take (P7, gift, S1) and (P7, ceramic, S2). Swapping their supplier parts requires (P7, gift, S2) and (P7, ceramic, S1) too. The independent lists require all four combinations.

product_id ↠ tag says that, within each product, its tags combine with all its suppliers. The complementary MVD product_id ↠ supplier_id describes the same condition. The right side can itself contain several attributes whose association must remain intact. Independence of a set of pairs would not mean independence of the individual columns within those pairs.

An MVD is trivial when Y is contained in X, or X ∪ Y is the whole schema. Otherwise fourth normal form, or 4NF, requires its determinant to be a superkey, for every implied MVD. Every FD also implies the corresponding MVD, so 4NF implies BCNF. The membership relation fails 4NF: product is not a superkey.

The MVD gives exactly the required binary decomposition: X ∪ Y and X ∪ Z, equivalently X ∪ Y and R − (Y − X). A row of their join chooses a Y part and a Z part for the same X. The swapping rule guarantees that combination was already present, proving losslessness. Splitting violating MVDs repeatedly gives 4NF components; it does not guarantee that every original dependency remains locally enforceable.

Having several values alone proves nothing. If a tag describes a particular supplier’s packaging rather than the product independently, a missing corner can be meaningful. The MVD would then be false, and the split could invent a tag–supplier association.

Join dependencies and fifth normal form

A join dependency, or JD, states that a relation is exactly the natural join of specified projections in every legal state. Write *(R₁, R₂, …, Rₙ) for those component attribute sets, whose union covers the original schema. It is trivial if a component is the whole schema. The MVD above is the two-component case.

Three components can express a rule that no binary split expresses. The modelling article’s actual supplier offers are (S1, P7, North), (S1, P3, South) and (S2, P7, South). Projecting supplier/product, supplier/region and product/region invents (S1, P7, South). A different rule could deliberately define eligibility by those three compatible pairs. Under that rule the fourth row would be intended, rather than an invented actual offer. The distinction is in the policy, not in the shape of the tables.

The actual-offer state disproves that proposed JD: one legal counterexample is enough. It does not by itself classify every other possible dependency of the schema. If the only declared constraints on actual offers are the full triple’s key, the schema meets the higher forms on that basis; accidental properties of those three rows add no rules.

The independent pairwise-approval policy is different. An offer is eligible if and only if supplier/product, supplier/region and product/region are all approved. Its eligibility relation contains four triples, and the three-projection JD is declared. Maintaining the three approval sets expresses the policy directly; eligibility can be reconstructed from them.

Under that policy, assume no further restrictions on the approval sets. There are no non-trivial FDs or MVDs on the ternary eligibility schema, so it is in 4NF. Its only candidate key is the whole triple. That key does not imply the three-way JD: the original three actual offers satisfy the key and violate the JD. This makes the eligibility schema fail fifth normal form, or 5NF, also called project-join normal form. 5NF requires every non-trivial implied JD to follow from the set of candidate-key dependencies.

Why can we not just split the eligibility relation twice? A first binary split of a three-attribute schema would express an MVD, such as supplier’s products being independent of its regions. The pairwise policy does not promise that: the product/region approval can forbid a combination. Its three-way reconstruction rule can hold without any such binary independence. All three projections are needed together. This is a property of the declared policy over all legal states; it is not established by counting the rows in the current example.

What higher normal forms can promise

Sixth normal form, or 6NF, takes decomposition further. In its ordinary, non-temporal reading, only trivial JDs may hold. A schema is then irreducible: it has no further lossless decomposition into proper projections. 5NF allows a non-trivial JD when keys imply it; 6NF excludes even that case.

For example, products(product_id, name, price) with only the product key is in 5NF. Its key nevertheless makes a split into product/name and product/price lossless, so it is not in 6NF. Keeping independently changing properties apart can be useful for histories. The temporal development of 6NF uses generalised relational operators; the procedures for dated prices and corrections belong in History, correction and deletion.

Domain-key normal form, or DK/NF, asks a different question: do the domain constraints and key constraints imply every constraint of the schema? A domain restricts an individual attribute’s allowed values; a key restricts which rows can agree on an identifying set. A rule that total payments may not exceed an order’s line value does not follow merely from positive amounts and unique payment IDs. Those local restrictions can all pass while the total is too large.

DK/NF is a demanding criterion, rather than a general recipe for translating every business rule into domains and keys. Likewise, 6NF does not mean that every useful relation has two columns: a ternary fact with no lossless proper decomposition remains irreducible. None of these labels establishes query speed, the cost of writes or complete application correctness. They state particular logical properties under particular constraints.

Choosing and checking a decomposition

A proposed decomposition should come with its assumptions and its argument. For the flattened line relation, the result is straightforward: numbered line facts, order/customer and customer/name. The closures derive the line key; the chase proves reconstruction; and the two smaller determinant rules stay local. Synthesis reaches that design without sacrificing any FD.

The adviser relation needs a decision. BCNF removes the repeated adviser/style fact but leaves the customer/style rule across tables. Keeping 3NF retains both rules within one relation and accepts that repetition. The tag/supplier relation needs a different dependency language altogether. The offer relation needs the meaning of an offer settled before any pairwise split is considered.

The last question goes beyond reconstructing projections. A product/name table can record a product before it has any tag. A supplier membership can exist before any tag membership does. Those independent tables are then deliberately capable of states that are not projections of one fully populated product/tag/supplier relation. Joining them may omit a product with an empty membership set; that does not erase its independent product row.

Decide that participation explicitly. Losslessness promises a round trip for legal original relations; it does not require every later state of independently maintained tables to be the projection of one original relation. Foreign keys, required memberships and lifecycle rules determine the intended wider design.

Use these proofs to establish what the design means. Then implement the constraints, plan a live schema change if existing data must move, and measure the queries in Query execution and performance. The logical argument is complete when every original fact can be recovered and every remaining enforcement responsibility has a clear owner.