Chapter Three – The Relational Model and Normalization

Chapter Objectives

• Build foundational grasp of relational terminology, characteristics, and alternative vocabulary.

• Detect and describe functional dependencies (FDs), determinants, and dependent attributes.

• Recognise and select primary, candidate, composite, surrogate, and foreign keys.

• Spot insertion, deletion, and update (modification) anomalies.

• Transform relations into higher‐order normal forms, especially BCNF and 4NF, while appreciating the special position of Domain/Key Normal Form (DK/NF).

• Identify and eliminate multivalued dependencies (MVDs).

Chapter Premise & Starting Question

• Situation: One or more pre-existing tables are supplied for loading into a new database.

• Central issue: "Store data exactly as received, or transform it first?"
  → Leads to concerns about redundancy, anomalies, integrity, and long-term maintainability.

• Concrete teaser: Two separate tables could be combined into one—but would that create a "very strange" structure when new facts (e.g.
  Nancy Meyers manages SKU 101300) must be added?

The Relational Model – Historical Context

• Introduced by E. F. Codd (IBM) in 1970 via a seminal paper.

• Based on rigorous mathematics called relational algebra.

• Became the de-facto foundation for virtually every commercial DBMS.

Fundamental Terminology

• Entity: Any identifiable thing to track (Customers, Computers, Sales).

• Relation (aka Table): A two-dimensional structure holding entity data; meets strict conditions (see next section).

• Alternative equivalents:
  • Relation ≅ File ≅ Table
  • Tuple ≅ Row ≅ Record
  • Attribute ≅ Column ≅ Field

Characteristics of a Proper Relation

• Rows are unordered; order carries no meaning.

• Columns are unordered within design tools; referenced by name, not position.

• No duplicate rows—every tuple is unique.

• Every cell holds exactly one atomic (indivisible) data value → no repeating groups, no arrays.

• Each column has a single data type (enforced by domain integrity constraint).

• The table logically represents a set, enabling mathematical set operations.

Integrity Constraints (3-legged foundation of "Database Integrity")

• Domain Integrity Constraint
  • All values in a column come from the same domain. Example: FirstName values restricted to {Albert, Bruce, …}.
  • Distinct relations may legally reuse the same attribute name if domains coincide.

• Entity Integrity Constraint
  • Primary Key (PK) must be unique and NOT NULL for every row.

• Referential Integrity Constraint
  • Foreign Key (FK) values must already exist as PK values in the referenced relation.
  • Formal statement: $ORDER_ITEM.SKU$ must exist in $SKU_DATA.SKU$.

Keys and Key Types

• Key: One or more columns that uniquely identify a row.

• Composite Key: Key involving ≥2 attributes.

• Candidate Key: Any key that determines all other columns; potential choice for PK.

• Primary Key: Chosen candidate used operationally; exactly one per relation.
  • Desirable traits: short, numeric, immutable.

• Surrogate Key: DBMS-supplied artificial identifier (e.g., auto-increment integer).
  • Ideal PK characteristics; meaningless to users; often hidden. Example transformation:
  RENTAL_PROPERTY before → $RENTAL_PROPERTY(Street,City,State,Zip,Country,Rental_Rate)$
  after → $RENTAL_PROPERTY(PropertyID,Street,City,State,Zip,Country,Rental_Rate)$

• Foreign Key: PK of one relation stored in another to create a link; can also be composite.

Functional Dependencies (FDs)

• Definition: An FD exists when one attribute (or set) determines another attribute (or set).
  Notation: $A \rightarrow B$.

• Examples:
  • $StudentID \rightarrow StudentName$
  • $StudentID \rightarrow (DormName, DormRoom, Fee)$

• Determinant: Attribute(s) on left side of the arrow.

• Composite Determinant: Multi-attribute determinant, e.g. $(StudentName, ClassName, Semester) \rightarrow Grade$.

• Equation-style derivations appear (e.g. $ExtendedPrice = Quantity \times UnitPrice$ ) but FDs are not mathematical equations; they represent consistency rules in stored data.

• Core inference rules (Armstrong):
  • Decomposition: If $A \rightarrow (B,C)$ then $A \rightarrow B$ and $A \rightarrow C$.
  • Union: If $A \rightarrow B$ and $A \rightarrow C$ then $A \rightarrow (B,C)$.
  • Non-simplification: From $(A,B) \rightarrow C$ one cannot infer $A \rightarrow C$ nor $B \rightarrow C$.

• Detecting determinants only via scanning for uniqueness can mislead (sampling limitations, logical vs. accidental uniqueness).

Real-table FD illustrations

1. SKU_DATA
   • $SKU \rightarrow (SKU_Description, Department, Buyer)$
   • $SKU_Description \rightarrow (SKU, Department, Buyer)$
   • $Buyer \rightarrow Department$

2. ORDER_ITEM
   • $(OrderNumber, SKU) \rightarrow (Quantity, Price, ExtendedPrice)$
   • $(Quantity, Price) \rightarrow ExtendedPrice$

Modification Anomalies & Data Integrity Problems

• Occur whenever duplicated data exist.

• Insertion anomaly: Cannot add data about one entity unless accompanied by unrelated data (e.g. new piece of equipment without repair info).

• Deletion anomaly: Removing a row also unintentionally deletes facts about a different entity.

• Update anomaly: Same fact stored multiple times; updating one instance creates inconsistencies (demonstrated by incorrect AcquisitionCost change in EQUIPMENT_REPAIR).

• Any table suffering anomalies is branded "unsatisfactory" or "bad"—prime target for normalization.

Normalization & Normal Forms

• Normalization: Systematic decomposition of "bad" relations into smaller, well-structured relations.

• Book’s stance on 1NF: A relation must both meet table rules and possess a defined primary key.

• Formal normal forms:
  • 1NF – Relation with atomic values, unique rows, PK defined.
  • 2NF – In 1NF and every non-key attribute fully dependent on the whole PK (eliminates partial dependencies on composite PK parts).
  • 3NF – In 2NF and no non-key attribute is transitively dependent (i.e., determined by another non-key determinant).
  • BCNF (Boyce-Codd NF) – Every determinant in the relation is a candidate key. Mnemonic: “Non-key columns depend on the key, the whole key, and nothing but the key, so help me Codd.”
  • 4NF – In BCNF and free of multivalued dependencies (MVDs).
  • Domain/Key NF (DK/NF) – Every constraint arises solely from domains and keys (ideal but rarely achieved in practice).

Worked Example – Normalising SKU_DATA to BCNF

1. Starting 1NF relation
   $SKU_DATA(SKU, SKU_Description, Department, Buyer)$

2. 2NF evaluation
   • Candidate keys: SKU (single) and SKU_Description (single).
   • Because PK is single-column, all non-key attributes depend on it → relation already in 2NF.

3. 3NF evaluation
   • FD present: $Buyer \rightarrow Department$ (non-key → non-key).
   • Violates 3NF, therefore not in 3NF nor BCNF.

4. Decomposition
   • Break out the offending FD:
   a) $SKU_DATA_2(SKU, SKU_Description, Buyer)$
   b) $BUYER(Buyer, Department)$
   • Enforce FK: $SKU_DATA_2.Buyer$ must exist in $BUYER.Buyer$.

5. Result
   • Both new relations satisfy 3NF; determinants are candidate keys → BCNF achieved.

Additional Concepts & Connections

• How many tables?
  • Original design question re-emerges after learning FDs and normal forms. Rules of thumb: prefer multiple focused relations over a single wide relation when FDs indicate separable themes.

• When to declare PKs?
  • Although Codd’s abstract model only requires unique rows, practical design sets a PK early to clarify dependencies and support integrity constraints.

• Mathematical notations used in FDs resemble logic implications, not algebraic equalities; avoid treating arrows as equations.

• Real-world relevance: Normalization reduces storage costs, supports concurrency, prevents inconsistent reports, and aligns with regulatory requirements (e.g. SOX, GDPR data accuracy clauses).

• Ethical/Practical implications: Poorly controlled data (null PKs, orphaned FKs) leads to erroneous decision-making, financial loss, or privacy breaches. Proper normalization coupled with integrity constraints safeguards stakeholder trust.

Quick Reference – Integrity & Normal Forms Cheat-Sheet

• $\text{Domain Integrity} + \text{Entity Integrity} + \text{Referential Integrity} \Rightarrow \text{Database Integrity}$

• Normalization ladder: $1NF \subset 2NF \subset 3NF \subset BCNF \subset 4NF \subset DK/NF$

• Common FD rules:
  • Decomposition (Project)
  • Union (Join)
  • Pseudotransitivity (not covered but useful in proofs)

• Surrogate vs. Natural PK debate: Surrogates minimise update churn; natural keys enhance interpretability—choose case-by-case.

End-of-Chapter Takeaways

• Understanding FDs is foundational; normalization is an algorithmic application of FDs toward anomaly-free design.

• Keys (PK, FK, surrogate) are the skeletal system; integrity constraints are the ligaments; together they uphold a healthy database organism.

• Achieving BCNF is often sufficient for operational systems; move to 4NF when MVDs (e.g., employees with multiple independ­ent skills and languages) appear.

• Always revisit initial "very strange tables" after mastering these concepts—the rationale for transforming data becomes self-evident.

Chapter Objectives

To effectively design and manage robust relational databases, it is crucial to:

• Build a foundational grasp of relational terminology, including the precise definitions of terms like relation, tuple, and attribute, along with their common alternative vocabulary (e.g., table, row, column), to ensure clear communication and understanding within the database domain.

• Detect and accurately describe functional dependencies (FDs), which are fundamental rules specifying how one attribute or a set of attributes determines another. This includes identifying determinants (the attributes on the left side of an FD) and dependent attributes (those on the right side).

• Recognise and select appropriate primary, candidate, composite, surrogate, and foreign keys. Understanding the role and characteristics of each key type is essential for enforcing data integrity and establishing correct relationships between tables.

• Spot insertion, deletion, and update (modification) anomalies, which are data inconsistencies arising from poor database design. Learning to identify these problems is the first step toward rectifying them through normalization.

• Transform relations into higher-order normal forms, especially Boyce-Codd Normal Form (BCNF) and Fourth Normal Form (4NF), by systematically decomposing problematic tables. This process aims to eliminate data redundancy and anomalies, while appreciating the special theoretical position of Domain/Key Normal Form (DK/NF) as an ideal but often unattainable goal.

• Identify and eliminate multivalued dependencies (MVDs), which represent a more complex type of dependency that can lead to redundancy and anomalies, requiring normalization to 4NF for their resolution.

Chapter Premise & Starting Question

• Situation: Database design often begins with existing, sometimes ill-structured, data. This typically involves one or more pre-existing tables or flat files that need to be loaded into a new, properly designed database system.

• Central issue: A critical decision arises: "Store data exactly as received, or transform it first?" This question highlights the core challenge of database design: whether to directly import potentially flawed data structures or to refine them to adhere to relational principles.

  → This fundamental question inevitably leads to significant concerns about:

  • Redundancy: Duplication of data, wasting storage space and posing risks for inconsistencies.

  • Anomalies: Problems that occur when inserting, deleting, or updating data, leading to integrity violations.

  • Integrity: The overall correctness, consistency, and reliability of data. Poor design compromises integrity.

  • Long-term maintainability: A poorly designed database becomes increasingly difficult and costly to manage, debug, and extend over time.

• Concrete teaser: Consider a scenario where two separate tables (e.g., Products and Product_Managers) could seemingly be combined into one table. However, doing so might create a "very strange" or problematic structure, especially when new facts, such as "Nancy Meyers manages SKU 101300," must be added. This foreshadows the need for normalization to avoid such design pitfalls.

The Relational Model – Historical Context

• Introduced by E. F. Codd (IBM) in 1970 via a seminal paper titled "A Relational Model of Data for Large Shared Data Banks." Codd's significant contribution was to propose a new, mathematically grounded approach to data management, moving beyond the hierarchical and network models prevalent at the time.

• Based on rigorous mathematics called relational algebra. This mathematical foundation provides a powerful, formal system for manipulating data, allowing for precise definition of operations (like select, project, join) and ensuring data consistency and integrity.

• Became the de-facto foundation for virtually every commercial Database Management System (DBMS) that followed. Its simplicity, logical clarity, and strong theoretical basis made it widely adopted and remains the dominant paradigm for structured data management.

Fundamental Terminology

• Entity: Any identifiable thing (person, place, event, concept) about which an organization chooses to store data. Examples include Customers, Computers, Sales, or Courses. Entities become tables in a relational database.

• Relation (aka Table): A two-dimensional structure designed to hold data about a single entity. It must meet a set of strict conditions (detailed in the next section) to qualify as a

Chapter Objectives

To effectively design and manage robust relational databases, it is crucial to:

• Build a foundational grasp of relational terminology, including the precise definitions of terms like relation, tuple, and attribute, along with their common alternative vocabulary (e.g., table, row, column), to ensure clear communication and understanding within the database domain.

• Detect and accurately describe functional dependencies (FDs), which are fundamental rules specifying how one attribute or a set of attributes determines another. This includes identifying determinants (the attributes on the left side of an FD) and dependent attributes (those on the right side).

• Recognise and select appropriate primary, candidate, composite, surrogate, and foreign keys. Understanding the role and characteristics of each key type is essential for enforcing data integrity and establishing correct relationships between tables.

• Spot insertion, deletion, and update (modification) anomalies, which are data inconsistencies arising from poor database design. Learning to identify these problems is the first step toward rectifying them through normalization.

• Transform relations into higher-order normal forms, especially Boyce-Codd Normal Form (BCNF) and Fourth Normal Form (4NF), by systematically decomposing problematic tables. This process aims to eliminate data redundancy and anomalies, while appreciating the special theoretical position of Domain/Key Normal Form (DK/NF) as an ideal but often unattainable goal.

• Identify and eliminate multivalued dependencies (MVDs), which represent a more complex type of dependency that can lead to redundancy and anomalies, requiring normalization to 4NF for their resolution.

Chapter Premise & Starting Question

• Situation: Database design often begins with existing, sometimes ill-structured, data. This typically involves one or more pre-existing tables or flat files that need to be loaded into a new, properly designed database system.

• Central issue: A critical decision arises: "Store data exactly as received, or transform it first?" This question highlights the core challenge of database design: whether to directly import potentially flawed data structures or to refine them to adhere to relational principles.

  → This fundamental question inevitably leads to significant concerns about:

  • Redundancy: Duplication of data, wasting storage space and posing risks for inconsistencies.

  • Anomalies: Problems that occur when inserting, deleting, or updating data, leading to integrity violations.

  • Integrity: The overall correctness, consistency, and reliability of data. Poor design compromises integrity.

  • Long-term maintainability: A poorly designed database becomes increasingly difficult and costly to manage, debug, and extend over time.

• Concrete teaser: Consider a scenario where two separate tables (e.g., Products and Product_Managers) could seemingly be combined into one table. However, doing so might create a "very strange" or problematic structure, especially when new facts, such as "Nancy Meyers manages SKU 101300," must be added. This foreshadows the need for normalization to avoid such design pitfalls.

The Relational Model – Historical Context

• Introduced by E. F. Codd (IBM) in 1970 via a seminal paper titled "A Relational Model of Data for Large Shared Data Banks." Codd's significant contribution was to propose a new, mathematically grounded approach to data management, moving beyond the hierarchical and network models prevalent at the time.

• Based on rigorous mathematics called relational algebra. This mathematical foundation provides a powerful, formal system for manipulating data, allowing for precise definition of operations (like select, project, join) and ensuring data consistency and integrity.

• Became the de-facto foundation for virtually every commercial Database Management System (DBMS) that followed. Its simplicity, logical clarity, and strong theoretical basis made it widely adopted and remains the dominant paradigm for structured data management.

Fundamental Terminology

• Entity: Any identifiable thing (person, place, event, concept) about which an organization chooses to store data. Examples include Customers, Computers, Sales, or Courses. Entities become tables in a relational database.

• Relation (aka Table): A two-dimensional structure designed to hold data about a single entity. It must meet a set of strict conditions (detailed in the next section) to qualify as a