550_4.6_Rationale_for_both_3NF_and_BCNF_default

Trade-offs Between 3rd Normal Form and Boyce-Codd Normal Form

Discussion of the trade-offs between 3rd Normal Form (3NF) and Boyce-Codd Normal Form (BCNF) highlights their relevance in the field of database normalization. Both normal forms are crucial in database design to effectively organize data, minimize redundancy, and prevent anomalies such as update, insertion, or deletion anomalies.

Goals of Decomposition

The context for decomposition arises when dealing with spreadsheet relations or any structured data format, aiming to streamline and optimize the database structure. The objective is to achieve decompositions into either:

  • 3rd Normal Form (3NF): This normal form addresses issues of redundancy and dependency by ensuring that every non-prime attribute is fully functionally dependent only on the primary key.

  • Boyce-Codd Normal Form (BCNF): A stricter version of 3NF that requires that for any functional dependency (X -> Y), X must be a super key, thus eliminating certain kinds of redundancy that can occur in 3NF.

Next Lesson

In the upcoming lesson, an algorithm will be introduced that specifically targets the process of achieving decomposition into 3NF, highlighting practical examples and potential pitfalls.

Good Decomposition Criteria

A good decomposition should satisfy two critical goals:

  1. Losslessness: This criterion mandates that the original relation can be perfectly reconstructed by joining the decomposed relations. Formally, it guarantees that the combination of the decomposed relations will yield the exact tuples of the original relation without any data loss.

  2. Dependency Preservation: This ensures that if the union of the functional dependencies holds across the decomposed relations, then all dependencies in the initial schema can still be derived. Essentially, decomposed relations must preserve the original functional dependencies to maintain the integrity of the data model.

Illustrative Example

An illustrative example discussing lossless versus lossy decompositions will showcase how different approaches to decomposition impact the completeness of data relationships.

Example: Pizza Shop Database

Dependency Issue

In analyzing a pizza shop database schema, an issue arises as the schema does not satisfy BCNF due to the functional dependency where "topping determines topping kind" and the left side is not a super key. This violation necessitates reconsideration of the schema design for normalization.

Decomposition Options

To rectify the BCNF violation, two decomposition options are presented:

  • First Option: Separate the attributes of topping and topping kind into relation R1 while retaining pizza and topping together in R2. This option is aimed at preserving functional dependencies effectively while maintaining a structured relationship.

  • Second Option: Separate pizza and topping kind into relation R1, while keeping pizza and topping attributes in R2. This option unfortunately results in loss of original relationships.

Achievements

Through the first decomposition, the functional dependency is preserved, and it achieves lossless decomposition. However, the second option demonstrates lossiness by creating additional tuples that did not exist in the original relation, indicating a loss of the inherent connections between attributes.

Goodness Criteria: Dependency Preservation

Definition

A functional dependency X determines Y is said to be preserved if every attribute in X and Y appears together in some relation R[i], or can be derived using reliable derivation methods such as Armstrong's axioms based on preserved dependencies.

Example in Pizza Shop Decomposition

In the context of the pizza shop decomposition:

  • R1: Successfully preserves the functional dependency (topping determines topping kind).

  • R2: Fails to preserve the relevant dependencies since the needed attributes do not exist in alignment with other preserved relations.

Conclusion

This absence of preservation characterizes the decomposition in R2 as non-dependency preserving, rendering it problematic.

Example: Student Information Schema

Input Dependencies

Consider a set of input dependencies, F, articulating the functional dependency "serial number determines subject."

Decomposed Relations

  • R1: Contains student grades and preserves dependency S_ID -> Grade.

  • R2: Comprises student information and preserves dependency S_ID -> Name.

  • R3: Highlights course offerings, maintaining dependency Serial Number -> Course ID.

  • R4: Contains course information that preserves Course ID -> Subject.

Dependency Evaluation

While "serial number determines subject" is not explicitly preserved in any single relation, it can be derived indirectly from preserved transitive relations through R3 and R4. By using transitive reasoning: if S_ID -> Course ID and Course ID -> Subject are both preserved, then Serial Number -> Subject can be inferred.

Conclusion

Thus, the decomposition is deemed dependency preserving due to inherent transitive relationships ensuring the integrity of the data.

Comparison of 3NF and BCNF

Essential Differences

  • Both normal forms require lossless decomposition, but the preservation of dependencies is optional in BCNF.

  • Every decomposition into BCNF can be achieved in a lossless manner; however, it may not always guarantee preserved dependencies.

  • In contrast, 3NF consistently ensures both losslessness and dependency preservation across all decompositions.

Overall Conclusion

A good decomposition effectively maintains losslessness while ideally preserving dependencies. However, in practice, the latter may not always be achievable, leading to the need for additional constraint checks to ensure the robustness of the database design.