Functional Dependencies and Normalization - CSU357 - Shoolini University

Functional Dependencies and Normalization

April, 2024

1. Overview of Normalization

Normalization involves dividing a database into two or more tables and defining relationships between the tables. The objective is to isolate data so that additions, deletions, and modifications of a field can be made in just one table and then propagated through the rest of the database via the defined relationships.

1.1 Functional Dependencies

Functional dependencies are constraints between two sets of attributes in a relation from a database. They are used to ensure that the database is normalized to a certain level. A functional dependency is denoted by X → Y, where X and Y are sets of attributes in a relation. The dependency states that the values of X uniquely determine the values of Y.

1.2 Benefits of Normalization

Normalization offers several advantages, including:

1.3 Levels of Normalization

Normalization is divided into several normal forms, each representing a level of organization that is free of certain types of anomalies. The most common normal forms include:

Purpose of Normalization

The primary purpose of normalization is to reduce redundancy and eliminate undesirable characteristics in a database.

By systematically organizing data in a database, normalization helps in ensuring data integrity, reducing update anomalies, and making the database more efficient for querying. It simplifies the schema design, making it easier to maintain and less prone to errors, thereby enhancing the reliability and performance of the database system.

Purpose of Normalization and Characteristics of Suitable Relations

The purpose of normalization extends beyond organizing data—it aims to produce a set of suitable relations that effectively support the data requirements of an enterprise. Characteristics of these relations include minimal attributes necessary to support these requirements, logical grouping of closely related attributes, and minimal redundancy. Notably, attributes that form all or part of foreign keys may be an exception to this redundancy rule. The result is a database that is not only easier for users to access and maintain but also occupies minimal storage space, enhancing overall efficiency.

2. Normal Forms

Normal Forms are standards for determining how far a database is on the normalization path. Each normal form represents a level of database normalization that is free of certain types of anomalies and redundancy. Achieving higher normal forms typically involves splitting tables into smaller ones, which can lead to more complex but also more efficient and cleaner database designs.

Redundant Data and its Problems

Redundant data in a database can lead to several problems, including:

  • Data inconsistency: Different copies of the same data may have different values, leading to inconsistencies.
  • Update anomalies: Inserting data into one place may require adding the same data in multiple locations, leading to inconsistencies.
  • Deletion anomalies: Removing data from one place may result in the loss of related data stored elsewhere.
  • Insert anamolies: Inability to add data to the database due to missing related data.

Redundant data in base relations can lead to various problems, including increased storage costs, difficulty in data management, and potential inconsistencies. Update anomalies can arise where changes in one instance of data require multiple updates across the database. Similarly, insert and delete anomalies can result in the loss of valuable information or the creation of incomplete records. Normalization addresses these issues by ensuring that each piece of information is stored only once.

Data Redundancy and Update Anomalies

The primary goal of relational database design is to organize attributes into relations to minimize data redundancy. This approach brings several benefits, including fewer operations required for updates—thereby reducing the chances for data inconsistencies—and a reduction in the storage space needed. Illustratively, comparing Staff and Branch relations with a StaffBranch relation highlights the redundancy issue: in StaffBranch, branch details are repeated for each staff member, while in a normalized design, branch information is stored once, with only the branch number repeated in the Staff relation. This design minimizes update anomalies, which include problems related to insertion, deletion, and modification of data.

Functional Dependencies and Normalization

A functional dependency exists when one attribute uniquely determines another attribute within a relation. This concept is fundamental to normalization as it helps in identifying relationships among attributes, which in turn informs the division of data into tables. Functional dependencies are used to identify the primary key of a relation, as they indicate attributes that can uniquely identify records in a table. Understanding functional dependencies is crucial for the process of normalization, as they guide the organization of attributes into relations that meet the criteria of known normal forms.

Identifying Functional Dependencies

To identify functional dependencies for a given relation, one must analyze the relationships between attributes, determining which attributes or combinations thereof can uniquely determine other attributes. This process involves examining the data usage and constraints inherent to the domain of the database. Identifying functional dependencies is a critical step in normalization, as it helps in understanding how attributes are related and lays the groundwork for structuring tables.

2.1 First Normal Form (1NF)

A table is in 1NF if it satisfies the following conditions:

2.2 Second Normal Form (2NF)

A table is in 2NF if it is in 1NF and all non-key attributes are fully functional dependent on the primary key. This means:

2.3 Third Normal Form (3NF)

A table is in 3NF if it is in 2NF and no transitive dependency exists. Conditions include:

2.4 Boyce-Codd Normal Form (BCNF)

A refinement of 3NF, a table is in BCNF if, and only if, it is in 3NF and every determinant is a candidate key. This level deals with certain types of anomaly not handled by 3NF.

2.5 Fourth Normal Form (4NF)

A table is in 4NF if it is in BCNF and has no multi-valued dependencies, except possibly those involving candidate keys. Multi-valued dependency occurs when two attributes in a table are independent of each other, but both depend on a third attribute. 4NF is useful for handling complex relationships where one key determines multiple sets of values that are themselves independent. This normalization form helps in further reducing redundancy that is not addressed by BCNF.

2.6 Fifth Normal Form (5NF) or Project-Join Normal Form (PJNF)

A table is in 5NF, also known as Project-Join Normal Form (PJNF), if it is in 4NF and every join dependency in it is implied by its candidate keys. A join dependency is a generalization of a functional dependency in a relation that involves three or more attributes. 5NF addresses situations where information can be reconstructed from smaller pieces of data (projections) that can be recombined (joined) without loss of information or introduction of redundancy. Tables in 5NF are free from all update anomalies associated with multi-valued facts.

2.7 Domain-Key Normal Form (DKNF)

A table is in Domain-Key Normal Form (DKNF) if every constraint on the table is a logical consequence of the domain constraints and key constraints. It goes beyond 5NF in ensuring that there are no constraints other than domain constraints and key constraints that can determine data validity. DKNF is considered the ultimate form of normalization, where all types of possible anomalies are eliminated. However, achieving DKNF can be difficult in practice, and it is rarely necessary or practical to normalize databases to this level.

3. Denormalization

Denormalization is the process of trying to improve the read performance of a database by adding redundant data or by grouping data. It is the reverse process of normalization. In some cases, denormalization helps by reducing the number of joins.

3.1 Purpose of Denormalization

Denormalization is used to improve the performance of a database system, especially for read-heavy operations. By reducing the number of joins required to retrieve data, denormalization can speed up query processing and enhance the overall performance of the database.

3.2 Advantages of Denormalization

Denormalization offers several benefits, including:

3.3 Implementing Denormalization

Denormalization can be implemented by adding redundant data to tables, creating summary tables, or using materialized views. By strategically introducing redundancy, denormalization aims to optimize read performance without compromising data integrity.

3.4 Considerations for Denormalization

While denormalization can enhance query performance, it also introduces the risk of data inconsistency due to redundant data. Careful planning and monitoring are essential to ensure that denormalization does not compromise data integrity and that the benefits of improved performance outweigh the potential drawbacks.

3.5 Designing a Relational Database with Normalization

When designing a relational database, normalization plays a crucial role in structuring data. By applying normalization principles from the outset, database designers can create a logical and efficient schema that supports robust data integrity and facilitates easy data manipulation and retrieval. It involves analyzing the relationships between data entities and systematically organizing data into tables that minimize redundancy and dependency anomalies.

4. Implementation in SQL

To implement normalization, database designers need to understand the data usage patterns and structure the database accordingly. Here’s how a simple normalization process might look like in SQL for a hypothetical Employee Management System.

Normalization Process

The process of normalization involves applying a series of rules or 'normal forms' to ensure that databases are structured optimally. Starting with the identification of functional dependencies, the process sequentially applies the criteria for each normal form, from 1NF to 3NF and beyond, as necessary. This methodical approach helps in grouping attributes into relations that minimize redundancy and dependency anomalies. By following these steps, database designers can achieve a well-structured database schema that facilitates data integrity and efficient data manipulation.

4.1 Implementing 1NF

Assuming an 'Employees' table that violates 1NF because it contains a list of phone numbers for some employees:

CREATE TABLE Employees (
    EmployeeID INT PRIMARY KEY,
    Name VARCHAR(100),
    PhoneNumber VARCHAR(100)
);

To conform to 1NF, we create a separate table for phone numbers:

CREATE TABLE PhoneNumbers (
    EmployeeID INT,
    PhoneNumber VARCHAR(100),
    FOREIGN KEY (EmployeeID) REFERENCES Employees(EmployeeID)
);

4.2 Achieving 2NF and 3NF

To achieve 2NF and 3NF, ensure that all non-key attributes are fully dependent on the primary key and that there are no transitive dependencies. If an 'EmployeeAddresses' table has an 'Address' column that depends on 'EmployeeID' but also on 'DepartmentID', we split the table to remove the transitive dependency:

CREATE TABLE Departments (
    DepartmentID INT PRIMARY KEY,
    Name VARCHAR(100)
);
CREATE TABLE EmployeeAddresses (
EmployeeID INT,
Address VARCHAR(255),
DepartmentID INT,
FOREIGN KEY (EmployeeID) REFERENCES Employees(EmployeeID),
FOREIGN KEY (DepartmentID) REFERENCES Departments(DepartmentID)
);

4.3 Implementing BCNF

Implementing BCNF typically involves more complex restructuring to ensure that every determinant is a candidate key. For a detailed example, one would need to look at specific cases where anomalies occur despite the table being in 3NF, then restructuring the database to eliminate these issues.

4.4 Problems with Non-normalized Relations

Relations that do not comply with the rules of 1NF, 2NF, or 3NF are prone to various issues. These include redundancy, which leads to unnecessary duplication of data; update anomalies, where changes to data in one place require changes to data in multiple places; insert anomalies, which can prevent the addition of new data without other required data; and delete anomalies, where the deletion of data in one place can unintentionally affect data in another. By adhering to normalization rules, these problems can be systematically avoided, ensuring a robust and efficient database design.

4.5 Lossless Joins and Dependency Preservation

Two important properties in the decomposition process of normalization are lossless joins and dependency preservation. The lossless-join property ensures that we can reconstruct the original relation from the decomposed smaller relations without losing information. This is crucial for maintaining the integrity and completeness of the database. On the other hand, the dependency preservation property ensures that constraints on the original relation can be enforced by applying constraints on each of the decomposed relations. This is essential for maintaining consistent data validation rules across the database, ensuring that all data adheres to the original constraints and business logic.

Representing Form Attributes as 3NF Relations

Converting attributes displayed on a form into 3NF relations involves analyzing the form to identify its entities, attributes, and the functional dependencies among them. This analysis helps in determining how to best structure the database tables to reflect the form's data while adhering to the principles of 3NF. By ensuring that each table represents a single concept without redundancy, and that there is no transitive dependency in any table, the data structure can efficiently support form processing and data integrity.