Third Normal Form

Third Normal Form

  • Introduces Third Normal Form (3NF) as a relaxed version of BCNF that guarantees both lossless-join and dependency-preservation properties in a decomposition.
#1

read: Section 3.5: Third Normal Form (section)

model: pro
rules: bullet presentation short


Write a short motivating short intro on 3NF.  No technical details necessary.

While Boyce-Codd Normal Form (BCNF) represents a desirable design goal, its strict requirements can lead to decompositions where some functional dependencies are not preserved. This complicates the enforcement of data integrity constraints. Third Normal Form (3NF) offers a practical compromise to this problem.

  • A Relaxation of BCNF

    Third Normal Form is a slightly weaker condition than BCNF. It allows certain types of functional dependencies that would violate BCNF, thus providing more flexibility in the design process.

  • The Goal of 3NF

    The primary motivation for 3NF is to achieve a database design that has two critical properties simultaneously: a lossless-join and dependency preservation. This is not always possible with BCNF.

  • A Practical Standard

    By relaxing the BCNF constraints, we can use a synthesis algorithm to guarantee a decomposition of any relation into a set of 3NF relations that meets both of these essential design goals.

  • Version: 3
  • Model: gemini-2.5-pro
  • Created: 2025-09-08 12:21:48
  • Duration: 13.211544036865234
  • Cummulative cost: $4.63e-02

Definition of Third Normal Form

  • Defines a relation R to be in third normal form (3NF) if for every nontrivial functional dependency (FD) \(A_1 A_2 \dots A_n \rightarrow B_1 B_2 \dots B_m\), either {\(A_1, A_2, \dots, A_n\)} is a superkey, or the attributes on the right side, {\(B_1, B_2, \dots, B_m\)}, are each a member of some key (i.e., they are prime attributes).
  • Explains that an attribute is ‘prime’ if it is a member of any key.
  • Highlights the difference between the 3NF and BCNF conditions, noting that 3NF allows FDs where the left side is not a superkey, as long as the right side consists only of prime attributes.
#2

read: Section 3.5.1: Definition of Third Normal Form (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- Defines a relation R to be in third normal form (3NF) if for every nontrivial functional dependency (FD) $A_1 A_2 \dots A_n \rightarrow B_1 B_2 \dots B_m$, either {$A_1, A_2, \dots, A_n$} is a superkey, or the attributes on the right side, {$B_1, B_2, \dots, B_m$}, are each a member of some key (i.e., they are prime attributes).
- Explains that an attribute is 'prime' if it is a member of any key.
- Highlights the difference between the 3NF and BCNF conditions, noting that 3NF allows FDs where the left side is not a superkey, as long as the right side consists only of prime attributes.

Definition: Third Normal Form (3NF)

A relation schema \(R\) is in Third Normal Form (3NF) if for every nontrivial functional dependency (FD) \(X \rightarrow Y\) that holds on \(R\), one of the following conditions is true: 1. \(X\) is a superkey for \(R\). 2. Each attribute \(A\) in the set \(Y - X\) is a prime attribute.

  • A prime attribute is defined as an attribute that is part of any candidate key.

    An attribute that is not a member of any candidate key is termed a nonprime attribute. The 3NF condition can be stated as: for each nontrivial FD, either the left side is a superkey, or the right side consists of only prime attributes.

  • The 3NF condition is a relaxation of the BCNF condition.

    BCNF requires that for any nontrivial FD \(X \rightarrow Y\), \(X\) must be a superkey. 3NF relaxes this constraint by permitting the FD even if \(X\) is not a superkey, provided that every attribute in \(Y - X\) is prime. This additional clause allows certain dependencies that would violate BCNF, thereby enabling decompositions that are both lossless and dependency-preserving, which is not always possible with BCNF.

  • Version: 1
  • Model: gemini-2.5-pro
  • Created: 2025-09-08 12:17:32
  • Duration: 19.113168954849243
  • Cummulative cost: $1.69e-02

The Synthesis Algorithm for 3NF Schemas

  • Presents an algorithm to decompose a relation R into a set of relations that are all in 3NF, have a lossless join, and preserve dependencies.
#3

read: Section 3.5.2: The Synthesis Algorithm for 3NF Schemas (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- Presents an algorithm to decompose a relation R into a set of relations that are all in 3NF, have a lossless join, and preserve dependencies.

The Synthesis Algorithm for 3NF

The synthesis algorithm decomposes a relation R into a set of relations that are all in 3NF, have a lossless join, and preserve dependencies.

Algorithm 3.26: Synthesis of Third-Normal-Form Relations With a Lossless Join and Dependency Preservation

INPUT: A relation R and a set F of functional dependencies that hold for R.

OUTPUT: A decomposition of R into a collection of relations, each of which is in 3NF. The decomposition has the lossless-join and dependency-preservation properties.

METHOD:

  • Find a minimal basis for F, say G.

    A minimal basis is a set of FDs that is equivalent to F but contains no redundant dependencies or extraneous attributes in the left-hand sides of its dependencies.

  • For each functional dependency \(X \rightarrow A\) in G, use \(XA\) as the schema of one of the relations in the decomposition.

    This step ensures that every dependency in the minimal basis is preserved, as all attributes involved in the FD X → A are contained within a single relation schema, XA.

  • If none of the relation schemas from the previous step is a superkey for R, add another relation whose schema is a key for R.

    This step is crucial for guaranteeing the lossless-join property. The presence of a relation schema that is a superkey of the original relation R is a sufficient condition for the decomposition to be lossless.

  • Version: 1
  • Model: gemini-2.5-pro
  • Created: 2025-09-08 12:17:52
  • Duration: 20.22602891921997
  • Cummulative cost: $1.83e-02

Why the 3NF Synthesis Algorithm Works

  • Justifies the correctness of the 3NF synthesis algorithm by showing it satisfies three key properties.
  • Lossless Join: The algorithm ensures that at least one of the resulting relation schemas is a superkey, which guarantees a lossless join according to the chase test.
  • Dependency Preservation: Each FD in the minimal basis is fully contained within one of the decomposed relations, ensuring all original dependencies can be checked.
  • Third Normal Form: Explains that any relation schema added because it’s a key is inherently in 3NF. For relations derived from FDs in a minimal basis, it asserts they are also in 3NF, stating that a violation would contradict the minimality of the basis.
#4

read: Section 3.5.3: Why the 3NF Synthesis Algorithm Works (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- Justifies the correctness of the 3NF synthesis algorithm by showing it satisfies three key properties.
- **Lossless Join**: The algorithm ensures that at least one of the resulting relation schemas is a superkey, which guarantees a lossless join according to the chase test.
- **Dependency Preservation**: Each FD in the minimal basis is fully contained within one of the decomposed relations, ensuring all original dependencies can be checked.
- **Third Normal Form**: Explains that any relation schema added because it's a key is inherently in 3NF. For relations derived from FDs in a minimal basis, it asserts they are also in 3NF, stating that a violation would contradict the minimality of the basis.

The synthesis algorithm for Third Normal Form (Algorithm 3.26) produces a decomposition that is correct, satisfying three essential properties.

  • Lossless Join

    The algorithm ensures that the decomposition has a lossless join. By construction, if no relation schema produced from the functional dependencies is a superkey, a relation whose schema is a key for the original relation \(R\) is explicitly added. The presence of a relation schema that is a superkey for \(R\) is a sufficient condition to guarantee that the natural join of the projections is lossless. This can be formally verified using the chase test.

  • Dependency Preservation

    The decomposition preserves all original dependencies. The algorithm begins with a minimal basis \(G\) for the set of functional dependencies \(F\). For each functional dependency \(X \rightarrow A\) in \(G\), a relation schema \(XA\) is created. This construction ensures that all attributes of every dependency in the minimal basis appear together in at least one relation schema, allowing each dependency to be enforced by checking a single relation.

  • Third Normal Form

    All relations in the resulting decomposition are in Third Normal Form. Any relation schema added because it is a key for \(R\) is necessarily in 3NF, as all its attributes are prime. For the relation schemas derived from the functional dependencies of the minimal basis, it can be shown that they are also in 3NF. A formal proof demonstrates that a violation of 3NF in one of these relations would imply that the basis was not minimal, which is a contradiction.

  • Version: 1
  • Model: gemini-2.5-pro
  • Created: 2025-09-08 12:18:09
  • Duration: 16.3625910282135
  • Cummulative cost: $1.58e-02