Skip to content
Tutorials Center
My learning

Topics

Lesson 76 of 79 ยท Projects

Project: A Normalization Toolkit

Write a Python toolkit that reads functional dependencies, finds keys, tests 2NF, 3NF and BCNF, decomposes schemas and proves the result lossless.

The Database Design Theory chapter gave you a set of algorithms: attribute closure, candidate keys, minimal cover, normal-form tests, BCNF decomposition, 3NF synthesis and the chase. Each was a small program on its own. In this project you join them into one normalization toolkit: you feed it a list of attributes and functional dependencies, and it prints a complete design report, including a proof that the result can be joined back without losing or inventing rows.

A tool like this is how database designers double-check their reasoning. It will not find the dependencies for you (that needs a conversation with the people who know the business), but once the dependencies are written down, it never makes an arithmetic mistake.

What the toolkit does

Input Attributes and FDs like AB->C.
Analyze Keys, prime attributes, normal form.
Decompose BCNF split and 3NF synthesis.
Verify Lossless join and preserved FDs.
1 / 2

The design of the toolkit

The code is organized in three layers, and each layer only calls the one below it.

flowchart TB
  A["analyze() report"] --> B["Decomposition: bcnf_decompose, synthesize_3nf"]
  A --> C["Verification: chase_lossless, lost_fds"]
  B --> D["Normal-form tests: check_normal_form"]
  C --> E["closure()"]
  D --> E
  B --> E

Everything is built on a single function, closure, so a bug there would show up everywhere, which also makes it easy to test.

Attributes are single letters, and a dependency is a pair of frozen sets, so AB->C becomes (frozenset("AB"), frozenset("C")). That representation makes subset tests (left <= result) read almost like the mathematics in Functional Dependencies.

Layer 1: analysis

The first layer answers "what is wrong with this schema?" It reuses Attribute Closure, Keys and Minimal Cover for closure, candidate_keys and minimal_cover, and adds check_normal_form, which applies the definitions from 1NF, 2NF and 3NF and BCNF and Lossless Decomposition:

  • 2NF is violated when a proper subset of some candidate key determines a non-prime attribute (a partial dependency).
  • 3NF is violated when a non-trivial X -> A has X not a superkey and A not prime.
  • BCNF is violated when a non-trivial X -> A has X not a superkey.

The function reports the highest form that holds (1NF is assumed, since FDs cannot talk about atomic values) along with a message for every violation. It tests the single-attribute FDs of the minimal cover, which is enough to judge the whole relation.

Python Layer 1: keys, prime attributes and normal form

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 three reports in order. The enrollments schema has the single key CS (course plus student), but S -> N and C -> TIO depend on half of that key, so it fails 2NF, and the output lists the partial dependencies by name. The address schema is the famous 3NF-but-not-BCNF case: every attribute is prime, so 3NF accepts C -> B, while BCNF does not. The third schema, where a single attribute determines everything, passes all tests.

Layer 2: decomposition

Two algorithms, opposite trade-offs:

  1. bcnf_decompose repeatedly finds a violating X -> Y inside a piece and splits it into X+ and the rest plus X. It always ends in BCNF and is always lossless, but it may lose dependencies. To see FDs inside a piece, it uses project, which computes what each subset of the piece's attributes determines within that piece.
  2. synthesize_3nf builds the design from the minimal cover: one relation per group of FDs sharing a left side, plus a relation holding a candidate key if none is present, minus relations contained in others. It is always lossless and dependency preserving, but may stop at 3NF.

Layer 3: verification

The decomposition algorithms are proven correct on paper, but a tool that checks its own output is worth more than trust. Two checks run after every decomposition:

  • chase_lossless builds the tableau from BCNF and Lossless Decomposition: one row per piece, an a symbol where the piece has the attribute and a unique b otherwise. It applies the FDs to equate symbols and looks for a row of all a values.
  • lost_fds tests each original FD by growing a set from its left side through the pieces, one piece at a time. If the right side is never reached, enforcing that FD would need a join.

analyze ties them together, and the last lines of the output prove that the checker can say "no", using a split that really is lossy.

Python The full toolkit on three schemas

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.

Compare the two strategies on each input.

  • Enrollments. Both algorithms return the same four relations: NS (student names), CIT (course, instructor, title), IO (instructor, office) and CGS (grades). All are in BCNF, the join is lossless and no FD is lost: the happy case.
  • Addresses. BCNF splits into AC and BC and loses AB -> C, as the lesson on BCNF predicted. 3NF synthesis returns the original relation unchanged: it is already in 3NF, so the toolkit leaves it alone and keeps every dependency.
  • Scheduling. BCNF produces four relations and loses HT -> R. Synthesis returns five relations and loses nothing, with HRS and HRT as the extra relations that keep HS -> R and HT -> R enforceable inside a single table.

This is the rule of thumb to carry away: if BCNF preserves everything, take it; if it does not, decide whether the lost rule can be enforced another way (a trigger, an assertion, an application check) or fall back to the 3NF design.

From the report to real tables

The final step is to turn the answer into tables and see that nothing was lost. The SQL below creates the flat enrollment table, builds the four tables from the toolkit's answer with each key declared, rebuilds the original through a view, and compares both directions with EXCEPT. A decomposition is lossless exactly when both differences are empty. The query then shows the payoff of the new design: one UPDATE changes an office in a single place.

SQL Check the decomposition on real data

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

Both counts are zero, so the four tables together carry exactly the original information. A data check like this can only demonstrate losslessness for the rows you tried; the chase proves it for every possible instance that satisfies the dependencies. Use both: the proof tells you the design is right, and the data check tells you the code that moves the data is right.

The toolkit trusts the dependencies you type. If a real rule is missing from the input, every report will cheerfully call the design fine. Always validate FDs against real data (for example with a GROUP BY ... HAVING COUNT(DISTINCT ...) > 1 query from Functional Dependencies) and with the people who own the data.

Extensions

  • Input parsing. Accept multi-letter attribute names such as StudentID -> Name, splitting on commas instead of single characters.
  • Pretty output. Print each resulting relation with its keys and generate CREATE TABLE statements, including foreign keys from shared attributes.
  • Higher forms. Add multivalued dependencies and a 4NF check, as in Multivalued Dependencies, 4NF and Denormalization.
  • Dependency discovery. Given rows, test every candidate X -> A by grouping, and print the FDs that hold in the data. Treat the output as hints, since data can satisfy a rule by accident.
  • Performance. The key search and project try every subset of attributes. That is fine for a dozen attributes and hopeless for fifty, so try pruning with the "never on a right side" rule or using the closure of single attributes first.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the toolkit run a chase after every decomposition?

    The chase decides whether the decomposition is lossless. A lossy design would produce spurious rows when the pieces are joined.
  2. 2. For R(A, B, C) with AB -> C and C -> B, why do BCNF decomposition and 3NF synthesis give different results?

    Every attribute is prime, so 3NF accepts C -> B. BCNF does not, so it splits the table into AC and BC, and AB -> C can no longer be checked inside one table.
  3. 3. What does a partial dependency mean in check_normal_form?

    Partial dependencies (a proper subset of a key determining a non-prime attribute) are what 2NF forbids.
  4. 4. In the SQL check, what result shows that the decomposition is lossless for the sample data?

    If flat EXCEPT rebuilt and rebuilt EXCEPT flat are both empty, the two row sets are identical, so the join recreated exactly the original rows.
  5. 5. Which input can the toolkit never get right on its own?

    All algorithms reason only about the FDs they are given. Discovering the true business rules is a human task.

Summary

  • The toolkit stacks three layers on one function, closure: analysis (keys, prime attributes, normal form), decomposition (BCNF split, 3NF synthesis) and verification (chase and preservation tests).
  • 2NF, 3NF and BCNF are three small tests over the same data: partial dependencies, non-superkey determinants and prime right sides.
  • BCNF decomposition is always lossless but may lose a dependency; 3NF synthesis is always lossless and preserving but may stop at 3NF.
  • Verify every result twice: with the chase for all legal instances, and with real data through EXCEPT queries.
  • The quality of the report depends entirely on the quality of the dependencies you feed in.

Next: Exercises with Solutions.