💾Intro to Database Systems Unit 9 – Functional Dependencies & Normalization

Key Concepts

• Functional dependencies (FDs) define relationships between attributes in a database schema
• An FD $X \rightarrow Y$ means the value of attribute set $X$ uniquely determines the value of attribute set $Y$
  • Example: In a student table,

    student_id

    uniquely determines

    student_name

• Normalization is the process of organizing data in a database to minimize redundancy and dependency
• Normal forms are guidelines for designing well-structured database schemas
  • Includes 1NF, 2NF, 3NF, BCNF, 4NF, and 5NF
• Candidate keys are attribute sets that uniquely identify a tuple in a relation
• Prime attributes are part of any candidate key, while non-prime attributes are not

Types of Functional Dependencies

• Trivial FDs occur when the right-hand side (RHS) is a subset of the left-hand side (LHS)
  • Example: $\{A, B\} \rightarrow A$
• Non-trivial FDs have at least one attribute on the RHS that is not present in the LHS
  • Example: $A \rightarrow B$
• Partial FDs occur when a non-prime attribute depends on only a part of a composite key
  • Example: In a table with candidate key

    {student_id, course_id}

    ,

    student_id \rightarrow student_name

    is a partial FD
• Transitive FDs involve three attributes, where $A \rightarrow B$ and $B \rightarrow C$, but $A$ is not functionally dependent on $C$
• Multivalued dependencies (MVDs) occur when the presence of one attribute value determines a set of values for another attribute, regardless of other attributes
  • Example: If a student can have multiple phone numbers,

    student_id \twoheadrightarrow phone_number

Normalization Basics

• Normalization is a step-by-step process to eliminate data redundancy and anomalies
• It involves breaking down a database schema into smaller, more manageable parts
• The goal is to ensure data integrity, reduce data redundancy, and improve data consistency
• Normalization is based on functional dependencies and normal forms
• The process starts with the lowest normal form (1NF) and progresses to higher normal forms (2NF, 3NF, BCNF, etc.)
  • Each higher normal form builds upon the requirements of the previous one
• Denormalization is the intentional introduction of redundancy to improve query performance, but it should be used sparingly

Normal Forms Explained

• First Normal Form (1NF): Eliminates repeating groups and ensures atomic values
  • Each attribute must contain only a single value from its domain
• Second Normal Form (2NF): Eliminates partial dependencies
  • No non-prime attribute should depend on only a part of a composite key
• Third Normal Form (3NF): Eliminates transitive dependencies
  • No non-prime attribute should depend on another non-prime attribute
• Boyce-Codd Normal Form (BCNF): Stricter version of 3NF
  • For any dependency $A \rightarrow B$, $A$ must be a superkey
• Fourth Normal Form (4NF): Eliminates multivalued dependencies
• Fifth Normal Form (5NF) or Project-Join Normal Form (PJNF): Ensures lossless join decomposition

Normalization Process

• Identify the functional dependencies in the database schema
• Determine the current normal form of the schema
• If the schema is not in the desired normal form, decompose it into smaller relations
  • This involves splitting the attributes into new relations based on the functional dependencies
• Ensure that the decomposition is lossless and dependency-preserving
  • Lossless join property guarantees that no information is lost during decomposition
  • Dependency preservation ensures that all functional dependencies are still enforced
• Repeat the process until the desired normal form is achieved
• Verify that the normalized schema meets the requirements of the application and performs efficiently

Benefits and Drawbacks

• Benefits of normalization:
  • Reduces data redundancy and anomalies (insertion, deletion, update)
  • Ensures data integrity and consistency
  • Simplifies data maintenance and updates
  • Facilitates schema extension and modification
• Drawbacks of normalization:
  • May result in a larger number of tables and complex joins
  • Can impact query performance due to the need for multiple joins
  • Requires more storage space for additional tables and indexes
  • May make the schema harder to understand for non-technical users

Real-World Applications

• E-commerce platforms use normalization to manage product catalogs, customer information, and order details
  • Ensures data consistency across multiple tables and reduces redundancy
• Healthcare systems employ normalization to store patient records, medical history, and treatment plans
  • Helps maintain data integrity and facilitates data sharing among healthcare providers
• Financial institutions rely on normalized schemas to manage customer accounts, transactions, and financial products
  • Ensures data accuracy and facilitates regulatory compliance
• Educational institutions use normalization to manage student records, course offerings, and faculty information
  • Helps maintain data consistency and facilitates data analysis and reporting

Common Pitfalls and Tips

• Over-normalization can lead to performance issues due to excessive joins
  • Denormalize selectively to improve query performance when necessary
• Under-normalization can result in data redundancy and anomalies
  • Regularly review the schema and functional dependencies to identify normalization opportunities
• Ensure that the normalization process preserves all functional dependencies
  • Use dependency diagrams or matrices to visualize and verify dependencies
• Consider the application's requirements and access patterns when deciding on the appropriate level of normalization
  • Balance data integrity and performance based on the system's needs
• Document the normalization process and the resulting schema
  • Helps maintain the schema over time and facilitates communication with developers and stakeholders