Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 79 ยท Database Design Theory

Finding the Highest Normal Form, FD Equivalence and DKNF

Find the highest normal form of a relation step by step, test whether two FD sets are equivalent, and learn what domain-key normal form (DKNF) promises.

Exams and design reviews keep asking the same question in different words: "What is the highest normal form of this relation?" The answer is not a guess. It is a short procedure that you can run on paper or in code, and it uses only tools you already have: attribute closure and candidate keys and the definitions of 2NF and 3NF and BCNF.

This lesson turns that procedure into a checklist, applies it to several schemas, and then answers a related question: when are two different-looking FD sets really the same set of rules? It closes with domain-key normal form (DKNF), the theoretical end of the normal-form ladder.

The procedure

Given a relation R and a set of FDs F, work through these steps in order.

  1. Find every candidate key. Compute closures of attribute subsets, smallest first, and keep the minimal ones whose closure is all of R.
  2. List the prime attributes. An attribute is prime if it belongs to at least one candidate key. Everything else is non-prime.
  3. Test BCNF. For each non-trivial FD X -> A, X must be a superkey. If every FD passes, the answer is BCNF, and you stop.
  4. Test 3NF. Each violation X -> A from step 3 is tolerated if A is prime. If every violation is tolerated, the answer is 3NF.
  5. Test 2NF. Look for a partial dependency: a non-prime attribute determined by a proper subset of a candidate key. If there is none, the answer is 2NF.
  6. Otherwise the relation is only in 1NF (we assume the columns are atomic, as in the relational model).

Test the FDs that follow from F, not only the ones you were given. If A -> B and B -> C are given, then A -> C also holds, and it can create a violation that no single listed FD shows. Computing closures of subsets, as the code below does, catches these hidden cases automatically.

Two shortcuts are worth remembering. A relation whose every attribute is prime is always in 3NF, because the "is the right side prime?" escape hatch always applies. And a relation with a single-attribute candidate key and no composite key cannot have a partial dependency, so it is at least in 2NF.

Running the procedure in code

The program below finds the keys, the prime attributes and every violation, and then reports the highest normal form. For each right-hand attribute it prints the smallest left side that causes the violation.

Python Highest normal form of a relation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the four results like an examiner would.

  • AB -> C, B -> D, C -> E has the single key {A,B}. B -> D determines a non-prime attribute from half of the key, a partial dependency, so the relation is only in 1NF. Fixing it is the job of normalization.
  • AB -> C, C -> B has two keys, {A,B} and {A,C}, so every attribute is prime. C -> B breaks BCNF, because C is not a superkey, but B is prime, so 3NF tolerates it. The answer is 3NF, and this is the classic case of a 3NF relation that is not in BCNF.
  • A -> B, B -> C, C -> D has the key . A chain of non-key dependencies is a transitive dependency. There are no partial dependencies, because the key has only one attribute, so the answer is 2NF. Notice that the program also reports B -> D, which is not in the list but is implied by it. This is what the note above warned about.
  • A -> BC has the key and nothing else to complain about: BCNF.

Equivalence of two FD sets

Different people write down the same business rules in different ways. One designer lists A -> B, B -> C, A -> C, another lists only A -> B, B -> C. Are they describing the same constraints?

Two FD sets F and G over the same attributes are equivalent when F+ = G+, which means each one implies every FD of the other. The test has two halves:

  1. F covers G: for every X -> Y in G, compute X+ using F and check that Y is inside it.
  2. G covers F: the same check in the other direction.

If both halves pass, the sets are equivalent. If only one passes, the sets are different, and the failing half tells you which direction is the problem: that FD is a rule one designer enforces and the other does not.

Python Are two FD sets equivalent?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second pair is the interesting one. AB -> C has an extraneous attribute: because A -> B already holds, A alone determines C. The two sets look different but say the same thing. The third pair fails in one direction only: G is implied by F (since A -> B -> C gives A -> C), but F is not implied by G, because G never says that B determines C. This is also why we reduce a set to its minimal cover before running a decomposition algorithm: equivalent sets give the same guarantees, and the minimal one is the least work.

Beyond BCNF: domain-key normal form

The ladder from 1NF to BCNF removes redundancy caused by FDs. 4NF and 5NF, covered in Multivalued Dependencies, 4NF and Denormalization, remove redundancy caused by multivalued and join dependencies. Domain-key normal form (DKNF), defined by Ronald Fagin in 1981, tries to say it all at once.

A relation is in DKNF when every constraint on it is a logical consequence of its domain constraints and its key constraints.

  • A domain constraint restricts the values one attribute may take: a type, a range, or a list of allowed values.
  • A key constraint says that some attributes uniquely identify a row.
  • A constraint here means any rule about which states of the relation are legal, not only FDs.

If a relation is in DKNF, the DBMS can enforce every business rule with nothing but column types, CHECK conditions on single columns, and PRIMARY KEY or UNIQUE. No anomaly can arise, because no rule depends on a combination of columns in some other way. Fagin proved that DKNF relations are free of all insertion, deletion and modification anomalies, and that a DKNF relation is automatically in BCNF, 4NF and 5NF.

A rule that breaks DKNF is one that links the values of several columns without being a key. Here is a typical example. A shop sells books and gadgets. Books have a page count, gadgets have a battery size, and a book must never have a battery. The first table below has columns for both, so it relies on an unwritten rule.

SQL A rule that is neither a key nor a domain constraint

Press Run (or Ctrl + Enter) to see the result here.

In the redesign, a book row simply has no battery_wh column to misuse, so the rule is built into the structure. Everything that remains is a key (sku) or a domain check (pages > 0). That is the spirit of DKNF.

DKNF is mostly a design ideal, not a procedure. No general algorithm is known that takes any schema and produces a DKNF one, and deciding whether a given relation is in DKNF requires knowing all of its constraints, which cannot be done from FDs alone. Practitioners therefore aim for BCNF or 4NF and use DKNF as a way of thinking: "can I push this rule into a key or a column domain?"

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A relation has attributes ABC and FDs AB -> C and C -> B. What is its highest normal form?

    The candidate keys are AB and AC, so every attribute is prime. C -> B has a non-superkey left side, which breaks BCNF, but B is prime, so 3NF allows it.
  2. 2. In the procedure for finding the highest normal form, why do we compute closures of attribute subsets instead of only checking the FDs that were listed?

    With A -> B and B -> C, the FD A -> C is implied. A partial or transitive dependency can be hidden behind a chain of listed FDs.
  3. 3. F = {A -> B, B -> C} and G = {A -> B, A -> C}. Which statement is true?

    F gives A -> C by transitivity, so F implies G. G never states B -> C, so F is not implied by G.
  4. 4. What must be true of every constraint in a relation that is in DKNF?

    That is the definition. If every rule is a consequence of column domains and keys, no anomaly can appear.
  5. 5. A relation where every attribute is prime is always at least in which normal form?

    3NF tolerates a violating FD whenever its right side is prime. If every attribute is prime, every violation is tolerated, but BCNF can still fail.

Summary

  • To find the highest normal form: find all candidate keys, mark the prime attributes, then test BCNF, 3NF and 2NF in that order.
  • Test the FDs implied by F, not only the listed ones; closures of attribute subsets do this for you.
  • A relation with only prime attributes is in 3NF; the example AB -> C, C -> B shows 3NF without BCNF.
  • Two FD sets are equivalent when each implies every FD of the other; test both directions with attribute closure.
  • DKNF requires every constraint to follow from domain and key constraints; it is a design ideal rather than an algorithm.

Next: Schema Design Strategies and Schema Integration.