Subject :- Database Management System

Unit 3 : Functional Dependency & Normalization

Prepared By-

Ms. Rucha Agrawal

Assistant Professor
Department of AI & DS, MMIT, Pune

1
Features of Good database Design
• Data Integrity: Data integrity is fundamental. The database should maintain the accuracy, consistency, and

reliability of data. This is achieved through the use of constraints (e.g., primary keys, foreign keys, check

constraints) to prevent invalid or inconsistent data.

• Normalization: The database should be properly normalized to reduce data redundancy. This involves

organizing data into related tables and eliminating or minimizing duplicate data. Common normal forms

(e.g., 1NF, 2NF, 3NF, BCNF) should be followed.

• Efficiency: A well-designed database is efficient in terms of both storage and query performance. This is

achieved by minimizing data duplication, optimizing indexing, and carefully designing table structures to

reduce the need for complex joins.

• Scalability: The database design should accommodate future growth and scalability. It should be able to

handle increasing volumes of data and transactions without significant degradation in performance.
• Documentation: Comprehensive documentation of the database schema, data dictionaries, and usage
guidelines should be available to assist developers, administrators, and end-users.

• Data Consistency: The database should ensure consistent data representation, including the use of
standardized data types, naming conventions, and formatting rules.

• Performance Tuning: Regular performance tuning and optimization should be part of the database
management process. Indexes, query optimization, and caching strategies should be used to improve query
response times.

• Concurrency Control: Mechanisms for managing concurrent access to the database should be in place to
prevent data conflicts and maintain data consistency in multi-user environments.

• Maintainability: The database design should be easy to maintain and update. Changes to the schema should
not require significant effort or risk data integrity.
• Flexibility: The design should be flexible enough to accommodate changes in business requirements.

This includes the ability to add new data attributes, modify existing structures, and accommodate

evolving business logic.

• Data Relationships: Relationships between data entities (tables) should be clearly defined using

foreign keys. This ensures that data is logically connected and enforces referential integrity.

• Data Security: Access controls and authentication mechanisms should be in place to restrict access to

sensitive data. Security should be designed into the database structure and enforced at the application

level.

• Backup and Recovery: A robust backup and recovery strategy should be in place to safeguard against

data loss due to hardware failures, user errors, or other unforeseen events.
Functional Dependency
• Functional dependency is a fundamental concept in the field of database
management systems (DBMS) and plays a crucial role in database design
and normalization.

• It describes the relationship between attributes (columns) within a

relational database table.

• Specifically, a functional dependency indicates that the value of one or

more attributes uniquely determines the value of another attribute in the
same table.
• In the context of functional dependencies, we often use the notation X -> Y,
where X and Y represent sets of attributes.
• Determinant (X): The set of attributes that determines the values of another set
of attributes. In the notation X -> Y, X is the determinant.
• Dependent (Y): The set of attributes whose values are determined by the
determinant. In the notation X -> Y, Y is the dependent.
• Functional Dependency Rule: A functional dependency X -> Y implies that, for
any two rows in the table that have the same values for attributes in X, they must
also have the same values for attributes in Y.
Uses of Functional Dependency
• Normalization: Functional dependencies are crucial for normalizing a database to
eliminate redundancy and improve data integrity. The process of normalization
involves breaking down tables into smaller, related tables to achieve specific
normal forms (e.g., 1NF, 2NF, 3NF, BCNF).

• Data Integrity: By enforcing functional dependencies, a database can maintain

data integrity and prevent anomalies such as insertion, deletion, and update
anomalies. It ensures that data remains consistent and accurate.

• Query Optimization: Knowledge of functional dependencies can help query

optimizers generate more efficient execution plans for SQL queries. It allows for
better indexing and joins.
Example of Employee table
• EmployeeID (Primary Key) ,FirstName, LastName, Department, Salary

• In this table, we can observe functional dependencies:

• EmployeeID -> FirstName, LastName, Department, Salary: The employee's ID

uniquely determines their first name, last name, department, and salary.

• Department -> EmployeeID, FirstName, LastName, Salary: Knowing the

department uniquely determines the employee's details and salary within that
department.

• Functional dependencies can vary from one database schema to another, and
identifying them correctly is a crucial step in database design and optimization.
Types of functional dependency
• Functional dependencies in a relational database can be categorized into
several types, each representing a specific relationship between attributes
(columns) within a table.

• Full Functional Dependency (FD):

• A full functional dependency occurs when the value of one attribute (column) in a
table uniquely determines the value of another attribute, and this dependency
cannot be further restricted by removing any attribute from the determining set.
• For example, if "A" and "B" are attributes in a table, "A -> B" represents a full
functional dependency.
Partial Functional Dependency (PFD)
• A partial functional dependency occurs when an attribute's value
depends on only a part of the candidate key (the primary key).

• In a well-normalized table (typically in 2NF or higher), partial

functional dependencies should be eliminated.

• For example, if "AB" is the candidate key, and "A -> B" represents a
partial functional dependency.
Transitive Dependency (TD):
• A transitive dependency occurs when the value of one attribute
depends on another attribute through a third attribute.

• In other words, if "A -> B" and "B -> C," then "A -> C" represents a
transitive dependency.

• Transitive dependencies are often eliminated to achieve 3NF or BCNF.

Multi-valued Dependency (MVD):
• A multi-valued dependency exists when an attribute depends on
another attribute, but both attributes are part of the same candidate
key.

• MVDs are often addressed when dealing with non-first normal form
tables.

• For example, if "A ->> B" represents a multi-valued dependency, it

means that for each value of "A," there can be multiple values of "B."
Derived Dependency:
• A derived dependency is one where the value of an attribute can be derived from other
attributes using some functional dependency rules.
• For example, if "A" and "B" are attributes, and "A -> B" holds, then "B" can be considered a
derived attribute.

• These types of functional dependencies are critical when designing and

normalizing a relational database. The goal of normalization is to eliminate or
minimize certain types of dependencies, such as partial and transitive
dependencies, to ensure data integrity and reduce redundancy in the database
schema. Properly normalized databases are typically easier to maintain and
query, leading to better performance and data consistency.
Inference Rules (Armstrong’s Axioms)
• Armstrong's axioms, also known as Armstrong's inference rules, are a set of
logical rules used in the field of database management systems (DBMS) to derive
functional dependencies and ensure data integrity within a relational database.

• These axioms were formulated by William W. Armstrong and are fundamental to

the process of normalizing a database schema.

• They help in identifying and eliminating redundancy in the database design.

• Armstrong's axioms are used to infer new functional dependencies from a given
set of known functional dependencies.
Reflexivity Axiom (Reflexive Rule):
• If you have a set of attributes (X), then X -> X is true.

• This axiom represents the idea that an attribute (or a set of

attributes) is functionally dependent on itself.
Augmentation Axiom (Augmentation Rule):
• If you have a functional dependency X -> Y, then you can augment
both sides of the dependency with additional attributes. For example,
if X -> Y, then XZ -> YZ is also true, where Z is a set of attributes.

• This axiom allows you to add attributes to both the determinant (X)
and the dependent (Y) while preserving the functional dependency.
Transitivity Axiom (Transitive Rule):
• If you have two functional dependencies X -> Y and Y -> Z, then you can infer a
third functional dependency X -> Z.

• This axiom represents the transitive property of functional dependencies. If you

can reach Z from X through an intermediate step (Y), then X directly determines Z.

• These axioms are used iteratively during the process of normalization to discover
new functional dependencies and to ensure that the database schema is in a
suitable normal form (e.g., 1NF, 2NF, 3NF, BCNF) to minimize data redundancy
and maintain data integrity.
Additional Inference Rules
• Union Rule (Additivity Rule):
• If you have two functional dependencies X -> Y and X -> Z, you can infer X -> YZ.

• This rule allows you to combine two separate dependencies into a single
dependency.

• Decomposition Rule (Projectivity Rule):

• If you have a functional dependency X -> YZ, you can infer both X -> Y and X -> Z.

• This rule allows you to break down a single dependency into multiple dependencies.
• Pseudotransitivity Rule:
• If you have two functional dependencies X -> Y and WY -> Z, you can infer WX -> Z.

• This rule allows you to connect dependencies through a common attribute (Y) to
infer a new dependency.

• Combining Augmentation and Transitivity:

• If you have a functional dependency X -> Y and X -> Z, you can infer X -> YZ using
augmentation and transitivity together.

• This combines the Augmentation and Transitivity axioms.

• Closure of Attributes:
• The closure of attributes for a given set of attributes X, denoted as X⁺, is the set of all attributes
that can be functionally determined by X using the given set of functional dependencies.

• Complement Rule:
• If you have a functional dependency X -> Y, you can infer X -> (R - Y), where R represents the set of
all attributes in the relation.
• This rule allows you to derive a complementary functional dependency.

• Trivial Dependency Rule:

• If you have a functional dependency X -> Y, you can infer XY -> Z for any set of attributes Z,
including an empty set.
• This rule accounts for the possibility of including additional attributes.
• These additional inference rules, when used in combination with the
primary axioms, provide a comprehensive toolkit for analyzing functional
dependencies in a database schema.

• They help in the process of normalization, where the goal is to eliminate

data redundancy and ensure data integrity by identifying and applying the
appropriate functional dependencies to tables in the database design.
Normalization
• A large database defined as a single relation may result in data duplication. This repetition of data
may result in:
• Making relations very large.
• It isn't easy to maintain and update data as it would involve searching many records in
relation.
• Wastage and poor utilization of disk space and resources.
• The likelihood of errors and inconsistencies increases.

• So to handle these problems, we should analyze and decompose the relations with redundant
data into smaller, simpler, and well-structured relations that are satisfy desirable properties.
Normalization is a process of decomposing the relations into relations with fewer attributes.
What is Normalization?
• Normalization is the process of organizing the data in the database.

• Normalization is used to minimize the redundancy from a relation or set of

relations. It is also used to eliminate undesirable characteristics like
Insertion, Update, and Deletion Anomalies.

• Normalization divides the larger table into smaller and links them using
relationships.

• The normal form is used to reduce redundancy from the database table.
Why do we need Normalization?
• The main reason for normalizing the relations is removing these
anomalies (insert anomaly, update anomaly, delete anomaly). Failure
to eliminate anomalies leads to data redundancy and can cause data
integrity and other problems as the database grows. Normalization
consists of a series of guidelines that helps to guide you in creating a
good database structure.
Advantages of Normalization
• Normalization helps to minimize data redundancy.

• Greater overall database organization.

• Data consistency within the database.

• Much more flexible database design.

• Enforces the concept of relational integrity.

Disadvantages of Normalization
• You cannot start building the database before knowing what the user
needs.
• The performance degrades when normalizing the relations to higher
normal forms, i.e., 4NF, 5NF.
• It is very time-consuming and difficult to normalize relations of a higher
degree.
• Careless decomposition may lead to a bad database design, leading to
serious problems.
First Normal Form (1NF)
• A relation will be 1NF if it contains an atomic value.

• It states that an attribute of a table cannot hold multiple values. It

must hold only single-valued attribute.

• First normal form disallows the multi-valued attribute, composite

attribute, and their combinations.
Relation EMPLOYEE is not in 1NF because of multi-valued attribute EMP_PHONE.
Second Normal Form (2NF)
• The Second Normal Form (2NF) is a database normalization rule that
builds upon the First Normal Form (1NF). It addresses the issue of
partial dependencies within a relational database table. To achieve
2NF, the table must meet the following two conditions:

• It must be in First Normal Form (1NF).

• It must not have partial dependencies on a candidate key.

• Candidate Key: A candidate key is a set of one or more columns that uniquely identifies each row in a

table. In a well-designed table, there can be multiple candidate keys.

• Functional Dependency: A functional dependency occurs when the value of one or more columns in a

table uniquely determines the value of another column. For example, if column A determines column

B, we write it as A → B.

• Partial Dependency: A partial dependency exists when a non-prime attribute (a column that is not part

of any candidate key) depends on only a part of the candidate key, rather than the entire candidate key.

• To achieve 2NF, we need to remove partial dependencies by breaking the table into smaller tables. This

is done by creating new tables for non-prime attributes that depend on only part of a candidate key.

The non-prime attributes are then moved to the new table, along with a copy of the candidate key on

which they depend.

• Consider the following table "Students" with columns: StudentID (Primary Key), CourseID
(Primary Key), StudentName, CourseName, and CourseInstructor.
StudentID | CourseID | StudentName | CourseName | CourseInstructor

-------------------------------------------------------------------

1 | 101 | Alice | Math | Prof. Smith

1 | 102 | Alice | Physics | Prof. Johnson

2 | 101 | Bob | Math | Prof. Smith

3 | 102 | Charlie | Physics | Prof. Johnson

• In this example, the table is in 1NF because each cell contains a single value, and there are no
repeating groups. However, there is a partial dependency on the StudentID column (non-prime
attribute) with respect to CourseName and CourseInstructor. The attributes CourseName and
CourseInstructor depend on only part of the candidate key (StudentID, CourseID).
• To achieve 2NF, we split the table into two separate tables: "Students" and
"Courses."
• Table: Students
StudentID | StudentName
-----------------------
1 | Alice
2 | Bob
3 | Charlie

Table: Courses
StudentID | CourseID | CourseName | CourseInstructor
-----------------------------------------------------
1 | 101 | Math | Prof. Smith
1 | 102 | Physics | Prof. Johnson
2 | 101 | Math | Prof. Smith
3 | 102 | Physics | Prof. Johnson
• Now, the table "Students" contains only unique student information,
and the table "Courses" contains the course-related information
without any partial dependencies. The StudentID column in the
"Courses" table is still part of the candidate key but is no longer part
of a partial dependency.

• By applying the Second Normal Form, we have eliminated partial

dependencies and achieved a more well-structured database design,
leading to better data organization and maintainability.
Third Normal Form (3NF)
• The Third Normal Form (3NF) is a database normalization rule that
builds upon the Second Normal Form (2NF). It aims to eliminate
transitive dependencies from a relational database table. To achieve
3NF, the table must meet the following two conditions:

• It must be in Second Normal Form (2NF).

• It must not have transitive dependencies on non-prime attributes.

• To understand transitive dependencies, let's first discuss non-prime attributes and functional
dependencies:

• Non-Prime Attribute: A non-prime attribute is a column that is not part of any candidate key. In
other words, it is not part of the primary key or any alternate keys.

• Functional Dependency: A functional dependency occurs when the value of one or more columns
in a table uniquely determines the value of another column. For example, if column A determines
column B, we write it as A → B.

• Transitive Dependency: A transitive dependency exists when a non-prime attribute depends on

another non-prime attribute through a prime attribute (part of the candidate key).
• To achieve 3NF, we need to remove transitive dependencies by
further breaking down the table into smaller tables. This is done by
creating new tables for non-prime attributes that depend on other
non-prime attributes through a prime attribute. The non-prime
attributes are then moved to the new table along with the prime
attribute on which they depend.
• Consider the following table "Students" with columns: StudentID (Primary Key), CourseID
(Primary Key), StudentName, CourseName, and CourseInstructor.
StudentID | CourseID | StudentName | CourseName | CourseInstructor

-------------------------------------------------------------------

1 | 101 | Alice | Math | Prof. Smith

1 | 102 | Alice | Physics | Prof. Johnson

2 | 101 | Bob | Math | Prof. Smith

3 | 102 | Charlie | Physics | Prof. Johnson

• In this example, the table is already in 2NF as we have eliminated partial dependencies by
creating separate tables for Students and Courses. However, there is a transitive dependency on
the CourseID with respect to CourseName and CourseInstructor. The attributes CourseName and
CourseInstructor depend on CourseID through the StudentID.
• To achieve 3NF, we further split the table into three separate tables: "Students,"
"Courses," and "Instructors.“
Table: Students
StudentID | StudentName
-----------------------
1 | Alice
2 | Bob
3 | Charlie

Table: Courses
CourseID | CourseName
---------------------
101 | Math
102 | Physics

Table: Instructors
CourseID | CourseInstructor
--------------------------
101 | Prof. Smith
102 | Prof. Johnson
• Now, the table "Students" contains only unique student information, the
table "Courses" contains unique course information, and the table
"Instructors" contains unique instructor information. The CourseID in the
"Courses" table serves as the primary key for that table, and the transitive
dependency on the CourseID has been eliminated.
• By applying the Third Normal Form, we have eliminated both partial and
transitive dependencies, resulting in a well-structured and normalized
database design. This ensures better data integrity, reduced data
redundancy, and improved data management.
Boyce-Codd Normal Form (BCNF)
• Boyce-Codd Normal Form (BCNF) is a higher level of database
normalization than the Third Normal Form (3NF). BCNF is designed to
eliminate certain types of anomalies that can occur in a database,
particularly those related to functional dependencies. A table is in
BCNF if, for every non-trivial functional dependency X -> Y, X is a
superkey. In simpler terms, a table is in BCNF if there are no partial
dependencies, where a part of the candidate key determines a non-
prime attribute.
• Suppose we have a table called "Student_Course" that tracks which
students are enrolled in which courses. It has the following columns:
Student_ID Course_ID Student_Name Course_Name Professor
1 101 Alice Math 101 Dr. Smith
2 101 Bob Math 101 Dr. Smith
3 102 Carol History 101 Dr. Johnson
4 103 David Physics 101 Dr. Lee

• In this table, the candidate key is {Student_ID, Course_ID}, which

uniquely identifies each row. However, we have a partial dependency on
the candidate key. The "Professor" column depends only on the
"Course_ID" and not on the full candidate key.
To bring this table to BCNF, we'll perform the following steps:

• Step 1: Create a new table called "Course_Info" to store information about courses and professors.
CREATE TABLE Course_Info (

Course_ID VARCHAR(5) PRIMARY KEY,

Course_Name VARCHAR(50),

Professor VARCHAR(50)

);

Step 2: Update the "Student_Course" table to reference the "Course_Info" table using a foreign key constraint.
ALTER TABLE Student_Course

ADD CONSTRAINT FK_Course_Info

FOREIGN KEY (Course_ID)

REFERENCES Course_Info (Course_ID);

• Now, our tables are structured as follows:
• Student_Course:
Student_ID Course_ID
1 101
2 101
3 102
4 103

• Course_Info:
Course_ID Course_Name Professor
101 Math 101 Dr. Smith
102 History 101 Dr. Johnson
103 Physics 101 Dr. Lee

• By separating the course information into a dedicated table ("Course_Info") and creating a foreign key
relationship, we have removed the partial dependency in the "Student_Course" table. Now, the
"Student_Course" table is in BCNF because all non-trivial functional dependencies satisfy the condition that
the left side of the dependency is a superkey (in this case, {Student_ID, Course_ID} is a superkey). BCNF
ensures that there are no partial dependencies, which can lead to anomalies in the database.
Decomposition
• Decomposition involves breaking down a larger table into smaller,
more manageable tables to reduce data redundancy and improve
data organization.
• The algorithms of decomposition refer to the systematic steps and
rules for performing this process while ensuring data integrity.
• The most commonly used algorithm is based on the principles of
normalization.
Problems related to decomposition
• Some queries become more expensive
• Given instances of decomposed relations we may not be able to
reconstruct the corresponding instance of the original relation.
• Checking some dependencies may require joining the instances of the
decomposed relations.
• There may be loss of information during decomposition.
Lossless Decomposition
• Lossless decomposition, also known as lossless-join decomposition,
ensures that when a relation is decomposed into smaller relations, the
original data can be reconstructed without loss of information by joining
the smaller relations.
• In other words, it guarantees that no data is missing when you recombine
the decomposed tables through a natural join operation.
• Given a relation R, if it is decomposed into two smaller relations R1 and R2,
the natural join (usually on the common attributes) of R1 and R2 should
produce the original relation R.
• Achieving lossless decomposition is essential because it ensures that no
data is accidentally omitted or lost during the decomposition process. It
guarantees the ability to reconstruct the original data if needed.
Dependency Preservation
• Dependency preservation, also known as preservation of functional dependencies,
ensures that the functional dependencies that held in the original relation (table) still
hold true in the decomposed relations. Functional dependencies are relationships
between attributes in a relation, such as X → Y, which means that knowing the values of
X uniquely determines the values of Y.
• To achieve dependency preservation, the following conditions must be met:
• All functional dependencies that held in the original relation R should still hold in the
decomposed relations R1 and R2.
• If a functional dependency X → Y exists in R, then it should exist in either R1 or R2 or
both.
• Dependency preservation is crucial for maintaining data integrity and consistency. If
functional dependencies are not preserved during decomposition, it can lead to incorrect
query results and data anomalies.
University Questions
1. Justify the impact of normalization on database? Explain 2ndnormal
form, 3rd normal form and BCNF with example. [8]
2. Elaborate the significance of codd’s rule. Explain 12 rules proposed
by codd’s. [9]
3. What is the impact of insert, update and delete anomaly on overall
design of database? How is normalization used to remove these
anomalies? [9]
4. Explain 3NF and BCNF and give its example. Also enlist their
differences.[8]