Database Systems: Normalization, Data Abstraction, and Database Design

Course Logistics & Assessment Updates

• Semester Schedule & Topics:

  • Week 6: Normalization.
  • Week 7: Introduction to SQL.
  • Week 8: Advanced SQL.
  • Previous Focus: Entity Relationship (ER) modeling.

• Quiz 3 Schedule Modification:

  • Original Schedule: Week 12, covering content from Weeks 7 through 11 (5 weeks of content).
  • Revised Schedule: Week 10, covering content from Weeks 7 through 9 (3 weeks of content) to reduce preparation burden.

• Quiz Attendance & Accommodation Procedures:

  • Attending an Alternate Class: Students unable to attend their registered class during a quiz week must send a Flow message requesting placement in an alternate session that same week.
  • Notice Period: Requires at least $48\,\text{hours}$ prior notice. If notice is given under $48\,\text{hours}$, the student must inform the tutor upon arrival at the alternate session to manually adjust availability.
  • Missed Quiz Policy (Additional Quiz): A single substitute quiz will run in Week 12 during the student's registered class time.
  • Eligibility: Automatically restricted to students who missed one of the regular quizzes (e.g., due to illness). Students who have completed all scheduled quizzes cannot take the additional quiz.
  • No prior absence notification is required for missing a quiz, as completion records are automatically tracked.

• Assignment 1 Guidance (ER and EER Modeling):

  • Core Requirements: Deconstruct many-to-many ($M:N$) relationships into binary one-to-many ($1:M$) relationships; eliminate fan traps and redundant relationships.
  • Assumptions Section: Students may include written assumptions to justify design decisions where project scenario specifications are ambiguous, unclear, or unstated.
  • Assumption Example: If an entity such as STUDENT lacks a explicit candidate key in the scenario description, assume and add a primary key named studentID.
  • Scoring Impact: Assumptions carry no direct marks, but serve to explain rationale to markers.
  • Scenario 2 Requirements: Can be completed using a standard Entity Relationship Diagram (ERD) or an Extended Entity Relationship Diagram (EERD). Submitting an EERD provides the structural depth required to attain High Distinction ($\text{HD}$) marks (e.g., modeling specialized entities like employee rovers versus using a simple boolean attribute).
  • Scenario 3 Requirements: Extended Entity Relationship Diagram (EERD) is strongly recommended/expected due to structural complexity.

Degrees of Data Abstraction

• Degrees of Abstraction Levels:

  • Abstraction increases moving from physical hardware implementation up to user views.
  • Supported Data Models across levels: Entity Relationship, Relational, Object-Oriented, Network, and Hierarchical models.

• External Model:

  • Definition: The end-user or application view of the database. Exposes only relevant slices of data required by specific user roles or interfaces, shielding rest of the database.
  • Diagrammatic Representation: Individual or task-specific Entity Relationship Diagrams (ERDs).
  • Examples:
    • Login Screen: Exposes only username and password fields.
    • Student Registration ERD: Displays entities and relationships for topic enrollment.
    • Class Scheduling ERD: Displays entities for timetable selection (e.g., selecting specific class times across days of the week).

• Conceptual Model:

  • Definition: The global, overall view of the entire database structure as designed. Integrates all external views into a single comprehensive layout without touching database management system (DBMS) software or physical hardware implementation details.
  • Diagrammatic Representation: Master Entity Relationship Diagram (ERD) incorporating all entities, attributes, primary keys, and relationships across the organization.

• Internal Model:

  • Definition: The DBMS-specific logical representation of the conceptual model. Translates conceptual diagrams into precise logical database constructs supported by the target DBMS.
  • Representation: SQL Data Definition Language (DDL) scripts, specifically CREATE TABLE statements establishing columns, data types, primary keys, and foreign key constraints.

• Physical Model:

  • Definition: The lowest level of abstraction representing how binary data ($0\text{s}$ and $1\text{s}$) is physically formatted, organized, and written to hardware storage media (e.g., Hard Drives, Solid State Drives).
  • Characteristics: Operates at the bit and byte level, managing hardware storage blocks, file structures, and low-level data encodings for numbers and characters. Does not use ER diagrams.

Fundamentals of Normalization & Denormalization

• Definition of Normalization:

  • A formal relational database technique for evaluating and modifying table structures to minimize data redundancy, reduce structural data anomalies, and assign attributes to relations based on functional determination.

• Normal Forms Sequence:

  • First Normal Form ($\text{1NF}$)
  • Second Normal Form ($\text{2NF}$)
  • Third Normal Form ($\text{3NF}$)
  • Boyce-Codd Normal Form ($\text{BCNF}$)
  • Fourth Normal Form ($\text{4NF}$)
  • Fifth Normal Form ($\text{5NF}$ / Domain-Key Normal Form $\text{DKNF}$)

• Target Level for Business Database Design:

  • Third Normal Form ($\text{3NF}$) serves as the default target standard for commercial database design. Forms above $\text{3NF}$ ($\text{BCNF}$, $\text{4NF}$, $\text{5NF}$) address specialized edge cases and are rarely mandated in standard business environments.

• Denormalization:

  • Definition: The intentional process of converting a relation from a higher normal form into a lower normal form.
  • Trade-Offs: Increases data redundancy and anomaly risks, but significantly improves read query execution speed and performance by reducing required table joins.
  • Use Cases: High-scale web applications (e.g., Facebook, YouTube) where global data replication across distributed servers prioritizes fast read access over data non-redundancy. Updating denormalized data requires simultaneously executing updates across all redundant storage locations to prevent inconsistencies.

• Primary Objectives of Normalization:

  • Designing new database table structures from raw requirements or forms.
  • Analyzing and refactoring existing relational entities.
  • Eliminating insertion, update, and deletion anomalies.
  • Eliminating unnecessary data redundancies.
  • Utilizing functional dependencies to assign attributes accurately.

Unnormalized Data & Functional Dependencies

• Structural Defects in Unnormalized Data Tables:

  • Multiple Subjects per Table: Failing the single-subject rule by combining separate entities into one structure (e.g., mixing project details, employee details, job classifications, and billing rates).
  • Repeating Groups / Multi-Valued Cells: Storing non-atomic cells containing multiple values within a single row-column intersection (e.g., listing multiple employee IDs within a single project row).
  • Data Redundancy: Duplicating identical descriptive data across multiple rows.
  • Improper Key Dependencies: Non-key attributes dependent on attributes other than the full primary key.
  • Anomalies:
    • Insertion Anomaly: Inability to add facts about one entity without artificially supplying facts for an unrelated entity.
    • Update Anomaly: Modifying a single attribute value requires updating multiple redundant rows; missing any row creates data inconsistency.
    • Deletion Anomaly: Deleting a record to remove one piece of information unintentionally destroys unrelated critical data (e.g., removing employee record $103$ simultaneously deletes the job class and charge rate history).

• Functional Dependencies Notation & Definitions:

  • Functional Dependency ($X \rightarrow Y$): Attribute $X$ functionally determines attribute $Y$ if each value of $X$ is associated with precisely one value of $Y$ at any given time.
  • Determinant: The attribute or set of attributes on the left side of the arrow ($X$) that determines the values of dependent attributes.
  • Candidate Key: A minimal superkey (an attribute or set of attributes) capable of uniquely identifying every tuple in a relation.
  • Primary Key: The selected candidate key used to uniquely identify records; underlined in theoretical notation.
  • Partial Dependency: Exists when an attribute $Y$ is functionally dependent on only a proper subset of a composite primary key $(X_1, X_2) \rightarrow Y$ where $X_1 \rightarrow Y$
  • Transitive Dependency: Exists when an attribute $Y$ is functionally dependent on attribute $Z$, where $Z$ is a non-prime attribute (an attribute not part of any candidate key): $PK \rightarrow Z$ and $Z \rightarrow Y$.

The Normalization Process: 1NF to 3NF

• Sample Unnormalized Dataset (Construction Project Context):

  • Unnormalized Attributes: Project Number, Project Name, Employee Number, Employee Name, Job Class, Charge Per Hour, Hours (where Employee Number, Employee Name, Job Class, Charge Per Hour, and Hours exist as repeating groups inside individual project records).

• Step 1: First Normal Form ($\text{1NF}$):

  • Rules: Eliminate all repeating groups / multi-valued attributes so every row-column intersection contains a single atomic value; define a primary key.
  • Action: Transform repeating groups into individual atomic rows. Identify candidate keys: Project Number determines Project Name; Employee Number determines Employee Name, Job Class, and Charge Per Hour.
  • Primary Key: Composite key composed of ($\mathbf{\text{Project Number}}$, $\mathbf{\text{Employee Number}}$).
  • $\text{1NF}$ Table Definition:         $\text{PROJECT\_ASSIGNMENT}(\mathbf{\text{Project Number}}, \mathbf{\text{Employee Number}}, \text{Project Name}, \text{Employee Name}, \text{Job Class}, \text{Charge Per Hour}, \text{Hours})$
  • Identified Dependencies in $\text{1NF}$:
    • $\text{Project Number} \rightarrow \text{Project Name}$ (Partial Dependency)
    • $\text{Employee Number} \rightarrow \text{Employee Name}, \text{Job Class}, \text{Charge Per Hour}$ (Partial Dependency)
    • $\text{Job Class} \rightarrow \text{Charge Per Hour}$ (Transitive Dependency)
    • $(\text{Project Number}, \text{Employee Number}) \rightarrow \text{Hours}$ (Full Functional Dependency)

• Step 2: Second Normal Form ($\text{2NF}$):

  • Rules: Must be in $\text{1NF}$, and all partial dependencies must be eliminated by placing partially dependent attributes into separate relations alongside their determinant.
  • Action: Break up $\text{1NF}$ table into three separate relations based on partial dependency determinants.
  • Resulting $\text{2NF}$ Relations:
    • $\text{PROJECT}(\mathbf{\text{Project Number}}, \text{Project Name})$
    • $\text{EMPLOYEE}(\mathbf{\text{Employee Number}}, \text{Employee Name}, \text{Job Class}, \text{Charge Per Hour})$
    • $\text{ASSIGNMENT}(\mathbf{\text{Project Number}}, \mathbf{\text{Employee Number}}, \text{Hours})$
  • Status: Partial dependencies removed. The EMPLOYEE relation retains a transitive dependency ($\text{Job Class} \rightarrow \text{Charge Per Hour}$).

• Step 3: Third Normal Form ($\text{3NF}$):

  • Rules: Must be in $\text{2NF}$, and all transitive dependencies must be eliminated by placing transitively dependent attributes into separate relations alongside their non-prime determinant.
  • Action: Remove $\text{Job Class} \rightarrow \text{Charge Per Hour}$ from EMPLOYEE and create a dedicated JOB_CLASS table.
  • Final $\text{3NF}$ Relations:
    • $\text{PROJECT}(\mathbf{\text{Project Number}}, \text{Project Name})$
    • $\text{JOB\_CLASS}(\mathbf{\text{Job Class}}, \text{Charge Per Hour})$
    • $\text{EMPLOYEE}(\mathbf{\text{Employee Number}}, \text{Employee Name}, \text{Job Class})$ (where Job Class serves as a Foreign Key referencing JOB_CLASS)
    • $\text{ASSIGNMENT}(\mathbf{\text{Project Number}}, \mathbf{\text{Employee Number}}, \text{Hours})$ (where Project Number and Employee Number serve as Foreign Keys referencing PROJECT and EMPLOYEE respectively)

Advanced Normal Forms: BCNF, 4NF, and 5NF

• Boyce-Codd Normal Form ($\text{BCNF}$):

  • Rule: A relation is in $\text{BCNF}$ if it is in $\text{3NF}$ and every determinant in the table is a candidate key.
  • Relationship to $\text{3NF}$: If a table contains only one single candidate key, $\text{3NF}$ and $\text{BCNF}$ are functionally equivalent. $\text{BCNF}$ addresses rare situations where non-key attributes determine components of a composite candidate key or where overlapping candidate keys exist.

• Fourth Normal Form ($\text{4NF}$):

  • Focus: Elimination of Multi-Valued Dependencies ($\text{MVD}$).
  • Multi-Valued Dependency Definition: Occurs when one attribute determines a set of independent values for another attribute, leading to combinatorial row expansion.
  • Scenario Example: An ANIMAL entity containing independent multi-valued attributes for Owner and Payment Method.
    • Animal Frank has owners Susan and Simon, and has recorded payments via Cash and Card.
    • In $\text{3NF}$, storing these independent attributes in a single table requires multi-row cross-product combinations (Frank-Susan-Cash, Frank-Susan-Card, Frank-Simon-Cash, Frank-Simon-Card) to maintain integrity, introducing severe redundancy.
  • $\text{4NF}$ Decomposition Solution: Split independent multi-valued attributes into separate binary tables:
    • $\text{ANIMAL\_OWNER}(\mathbf{\text{Animal}}, \mathbf{\text{Owner}})$
    • $\text{ANIMAL\_PAYMENT}(\mathbf{\text{Animal}}, \mathbf{\text{Payment Method}})$

• Fifth Normal Form ($\text{5NF}$ / Join-Dependency / Project-Join Normal Form $PJNF$):

  • Focus: Reconstructing complex datasets from decomposed tables without introducing join-loss or false tuple combinations.
  • Scenario Example: If constraints exist between specific pairings (e.g., owner Simon pays strictly via Card, while owner Susan uses Cash and Card), standard $\text{4NF}$ decomposition loses the owner-to-payment mapping context.
  • $\text{5NF}$ Decomposition Solution: Decompose into three pairwise binary relations to preserve exact logical relationships:
    • $\text{ANIMAL\_OWNER}(\mathbf{\text{Animal}}, \mathbf{\text{Owner}})$
    • $\text{ANIMAL\_PAYMENT}(\mathbf{\text{Animal}}, \mathbf{\text{Payment Method}})$
    • $\text{OWNER\_PAYMENT}(\mathbf{\text{Owner}}, \mathbf{\text{Payment Method}})$
  • Reconstruction: Executing relational SQL queries/views joining all three tables allows complete, accurate reconstruction of original real-world relationships without data anomalies.

Database Design Guidelines & Best Practices

• Database Refinement Best Practices:

  • Entity Naming Conventions: Entity names must be singular nouns (e.g., STUDENT, EMPLOYEE, PROJECT, not plural STUDENTS).
  • Attribute Atomicity: Attributes must represent atomic, indivisible data units. Multi-valued or composite values (e.g., full names, unparsed address fields, combined arrays) must be subdivided into distinct attributes.
  • Primary Key Granularity: Ensure primary keys accurately match the intended level of detail (granularity) represented by each table row.
  • Surrogate Keys: System-generated unique values introduced as primary keys when natural attributes fail to yield a reliable candidate key.
  • Historical Accuracy: Retaining point-in-time data values (e.g., storing historic wage rates or transaction prices directly within transaction lines) rather than relying on dynamic lookup tables that update over time.
  • Derived Attributes: Evaluate storing computed values versus calculating them dynamically on demand via SQL queries to avoid sync errors.

• Data Modeling Quality Assurance Checklist:

  • Verify singular entity names across all models.
  • Verify attribute atomic values across all cells.
  • Confirm relationship names and cardinalities in ER/EER models.
  • Ensure all relations meet minimum $\text{3NF}$ criteria for production database implementations.