Functional Dependency & Normalization

FUNCTIONAL DEPENDENCY &
NORMALIZATION
DEPENDENCY
A functional dependency is a constraint that specifies the relationship

between two sets of attributes where one set can accurately determine the
value of other sets
It is denoted as X → Y, where X is a set of attributes that is capable of
determining the value of Y. The attribute set on the left side of the
arrow, X is called Determinant, while on the right side, Y is called
the Dependent
Given a relation R, a set of attributes X in R is said to
functionally determine another attribute Y, also in R,
(written X → Y) if and only if each X value is associated
with at most one Y value.
CONSIDER THE GIVEN TABLE:
Consider any two tuples in this table ie, t1 and t2
If t1.x=t2.x
Then check for t1.y=t2.y(this condition must be true)
CHECK FOR FUNCTIONAL DEPENDENCIES
X -> Y
R_No -> Name(Here t1.x≠t12.x, so need to check for t1.y and t2.y)
This is functional dependency
Name ->R_No. (Not FD)
R_No ->Marks (FD)
Dept. ->Course (Not FD)
Course ->Dept. (Not F.D)
Name ->Marks (FD)
X and Y can be a set of attributes
(R_No., Name)->Marks (FD)

TYPES OF FUNCTIONAL DEPENDENCIES
Trivial: In Trivial Functional Dependency, a dependent is always a subset of the determinant.
i.e. If X → Y and Y is the subset of X, then it is called trivial functional dependency.

Eg: (R_No, Name) → Name
X → X(means X determines X . This is also trivial functional dependency)
Eg:If I tell you the R_No. of student and asking about the R_No of a student. R_No. can determine itself.
Every attribute in a relation determines itself . This is also a Trivial functional dependency
NOTE:Trivial FDs always hold.

Non-Trivial: In Non-trivial functional dependency, the dependent is strictly
not a subset of the determinant.
i.e. If X → Y and Y is not a subset of X, then it is called Non-trivial
functional dependency.
If x → y and x ∩ y= ϕ(fully trivial FD)
Eg: R_No → Name
This is FD as Nothing is common between R_No and Name
Y is not a subset of x(semi- trivial FD)
Eg: R_No, Name →Name, Marks
In this Example, Y is not a subset of x , condition apply , But intersection
is there as name is common in both x and y.
Multi-valued:In Multivalued functional dependency, entities of the
dependent set are not dependent on each other.
i.e. If a → {b, c} and there exists no functional dependency
between b and c, then it is called a multivalued functional
dependency.
Transitive
roll_no name age
42 abc 17
43 pqr 18
44 xyz 18
45 abc 19
Here, roll_no → {name, age} is a multivalued functional dependency, since the

dependents name & age are not dependent on each other(i.e. name → age or
age → name doesn’t exist !)
FULLY FUNCTIONAL DEPENDENCY :
If X and Y are an attribute set of a relation, Y is fully functional dependent on X, if

Y is functionally dependent on X but not on any proper subset of X.
Example –
In the relation ABC->D, attribute D is fully functionally dependent on ABC and not
on any proper subset of ABC. That means that subsets of ABC like AB, BC, A, B,
etc cannot determine D.
supplier_id item_id price
1 1 540
2 1 545
1 2 200
2 2 201
1 1 540
2 2 201
3 1 542
From the table, we can clearly see that neither supplier_id nor item_id
can uniquely determine the price
but both supplier_id and item_id together can do so.
So we can say that price is fully functionally dependent on
{ supplier_id, item_id }.
This summarizes and gives our fully functional dependency −
{ supplier_id , item_id } -> price
PARTIAL FUNCTIONAL DEPENDENCY :
A functional dependency X->Y is a partial dependency if Y is functionally dependent on X

and Y can be determined by any proper subset of X.
name roll_no course

Ravi 2 DBMS
Tim 3 OS
John 5 Java
In the above Example, we can see that both the attributes name
and roll_no alone are able to uniquely identify a course. Hence
we can say that the relationship is partially dependent.
INFERENCE RULE (IR)/ ARMSTRONG AXIOMS
1. Reflexivity Rule --- If X is a set of attributes and Y is a subset of X, then X →Y holds.

each subset of X is functionally dependent on X
2. Transitivity Rule --- If X → Y and Y → Z holds, then X → Z holds.
Eg : Ram is a sibling of Sham and Sham is a sibling of Mohan then Ram and Mohan are siblings
In the given table
If Name →Marks (FD)and

Marks →Dept.(NOT FD)
Then Name →Dept.(may or may not true we can not say anything about it.) but according
to the given table it holds transitive rule
3. Augmentation Rule --- If X → Y holds and W is a set of attributes,
then WX → WY holds.
As per above table:
R_No. →Name or name →marks(but name is not a primary key )
Then (R_No,Marks) →(Name, Marks) (is also true)
*note : there is no condition exist that the x should be a primary key
Above mentioned rules are primary rules
We have secondary rules also
1. Union:Union rule says, if X determines Y and X determines Z, then X must also
determine Y and Z.
If X → Y and X → Z then X → YZ
Eg: R_No → Name & R_No → Marks
Then R_No → Name,Marks
DECOMPOSITION RULE
2. Decompositionrule is also known as project rule. It is the reverse of union rule.This Rule says, if X
determines Y and Z, then X determines Y and X determines Z separately.
If X → YZ then X → Y and X → Z (splitting of right side is possible) but vice-versa is not
true
Eg: If X → Y Z
(Name, Marks) → Dept, Course
Then Name, Marks → Dept and Name, Marks → Course
PSEUDO TRANSITIVE RULE
In Pseudo transitive Rule, if X determines Y and YZ determines

W, then XZ determines W.
If X → Y and YZ → W then XZ → W
Eg: R_No → Name and Name, Marks → Dept
Then R_No,Marks → Dept
INTEGRITY CONSTRAINTS
• Integrity constraints are a set of rules. It is used to maintain the quality of

information.
• Integrity constraints ensure that the data insertion, updating, and other
processes have to be performed in such a way that data integrity is not affected.
• Thus, integrity constraint is used to guard against accidental damage to the
database.
TYPES OF INTEGRITY CONSTRAINT
DOMAIN CONSTRAINTS
• Domain constraints can be defined as the definition of a valid set of

values for an attribute.
• The data type of domain includes string, character, integer, time, date,
currency, etc. The value of the attribute must be available in the
corresponding domain.
EXAMPLE:
ENTITY INTEGRITY CONSTRAINTS
• The entity integrity constraint states that primary key value can't be
null.
• This is because the primary key value is used to identify individual
rows in relation and if the primary key has a null value, then we can't
identify those rows.
• A table can contain a null value other than the primary key field.
EXAMPLE:
REFERENTIAL INTEGRITY CONSTRAINTS
• A referential integrity constraint is specified between two tables.

• In the Referential integrity constraints, if a foreign key in Table 1 refers to the
Primary Key of Table 2, then every value of the Foreign Key in Table 1 must be
null or be available in Table 2.
EXAMPLE:
KEY CONSTRAINTS
• Keys are the entity set that is used to identify an entity within its entity
set uniquely.
• An entity set can have multiple keys, but out of which one key will be
the primary key. A primary key can contain a unique and null value in
the relational table.
ATTRIBUTE CLOSURE
The set of attributes that are functionally dependent on

the attribute A is called Attribute Closure of A and it can
be represented as A+.
Super Key: set of attributes whose closure contains all attributes of a
given relation.
Because A is a super Key , we can combine A with any other attribute
, that will also be super key
A , AD, AB, AC, AB, ABC, ABCDE are Super keys
No. of super keys possible 2ⁿ=16, where n=4

Candidate key- Minimal superkey
Consider A, No proper subset(Proper subset contains less
attribute than the attribute itself) of A is a super key.
Proper subset of A- ϕ
So A is super key as well as candidate key
Consider AD- which is a super key
Now consider the Proper subset of AD ie, {A, D}
But A is a super Key
So AD is not a Candidate Key
Prime Attributes: Are those attributes that are a part of Candidate key
In the previous Example, Prime ACD is a Candidate key
So we can say that A, C, D are the Prime attributes
ii. If the prime attributes are on the right side of a functional dependency
then we can say that there is no more candidate key in this relation

Functional Dependency & Normalization

Uploaded by

Copyright:

Available Formats

Functional Dependency & Normalization

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Functional Dependency & Normalization

Uploaded by

Copyright:

Available Formats

FUNCTIONAL DEPENDENCY &

A functional dependency is a constraint that specifies the relationship

(R_No., Name)->Marks (FD)

Trivial: In Trivial Functional Dependency, a dependent is always a subset of the determinant.

i.e. If X → Y and Y is the subset of X, then it is called trivial functional dependency.

NOTE:Trivial FDs always hold.

Here, roll_no → {name, age} is a multivalued functional dependency, since the

If X and Y are an attribute set of a relation, Y is fully functional dependent on X, if

A functional dependency X->Y is a partial dependency if Y is functionally dependent on X

name roll_no course

1. Reflexivity Rule --- If X is a set of attributes and Y is a subset of X, then X →Y holds.

If Name →Marks (FD)and

In Pseudo transitive Rule, if X determines Y and YZ determines

• Integrity constraints are a set of rules. It is used to maintain the quality of

• Domain constraints can be defined as the definition of a valid set of

• A referential integrity constraint is specified between two tables.

The set of attributes that are functionally dependent on

No. of super keys possible 2ⁿ=16, where n=4

You might also like