Functional Dependency
A functional dependency A->B in a relation holds if two tuples having same value of attribute A
also have same value for attribute B. For Example, in relation STUDENT shown in table 1,
Functional Dependencies
STUD_NO->STUD_NAME, STUD_NO->STUD_PHONE hold
but
STUD_NAME->STUD_ADDR do not hold
How to find functional dependencies for a relation?
Functional Dependencies in a relation are dependent on the domain of the relation. Consider the
STUDENT relation given in Table 1.
We know that STUD_NO is unique for each student. So STUD_NO->STUD_NAME,
STUD_NO->STUD_PHONE, STUD_NO->STUD_STATE, STUD_NO->STUD_COUNTRY
and STUD_NO -> STUD_AGE all will be true.
Similarly, STUD_STATE->STUD_COUNTRY will be true as if two records have same
STUD_STATE, they will have same STUD_COUNTRY as well.
For relation STUDENT_COURSE, COURSE_NO->COURSE_NAME will be true as two
records with same COURSE_NO will have same COURSE_NAME.
Functional Dependency Set: Functional Dependency set or FD set of a relation is the set of all
FDs present in the relation. For Example, FD set for relation STUDENT shown in table 1 is:
{ STUD_NO->STUD_NAME, STUD_NO->STUD_PHONE, STUD_NO->STUD_STATE, STUD_NO-
>STUD_COUNTRY,
STUD_NO -> STUD_AGE, STUD_STATE->STUD_COUNTRY }
Attribute Closure: Attribute closure of an attribute set can be defined as set of attributes which
can be functionally determined from it.
How to find attribute closure of an attribute set?
To find attribute closure of an attribute set:
Add elements of attribute set to the result set.
Recursively add elements to the result set which can be functionally determined from the
elements of the result set.
Using FD set of table 1, attribute closure can be determined as:
(STUD_NO)+ = {STUD_NO, STUD_NAME, STUD_PHONE, STUD_STATE, STUD_COUNTRY, STUD_AGE}
(STUD_STATE)+ = {STUD_STATE, STUD_COUNTRY}
How to find Candidate Keys and Super Keys using Attribute Closure?
If attribute closure of an attribute set contains all attributes of relation, the attribute set will be
super key of the relation.
If no subset of this attribute set can functionally determine all attributes of the relation, the set
will be candidate key as well. For Example, using FD set of table 1,
(STUD_NO, STUD_NAME)+ = {STUD_NO, STUD_NAME, STUD_PHONE, STUD_STATE,
STUD_COUNTRY, STUD_AGE}
(STUD_NO)+ = {STUD_NO, STUD_NAME, STUD_PHONE, STUD_STATE, STUD_COUNTRY,
STUD_AGE}
(STUD_NO, STUD_NAME) will be super key but not candidate key because its subset
(STUD_NO)+ is equal to all attributes of the relation. So, STUD_NO will be a candidate key.
Question: Consider the relation scheme R = {E, F, G, H, I, J, K, L, M, M} and the set of
functional dependencies {{E, F} -> {G}, {F} -> {I, J}, {E, H} -> {K, L}, K -> {M}, L -> {N} on R.
What is the key for R? (GATE-CS-2014)
A. {E, F}
B. {E, F, H}
C. {E, F, H, K, L}
D. {E}
Answer: Finding attribute closure of all given options, we get:
{E,F}+ = {EFGIJ}
{E,F,H}+ = {EFHGIJKLMN}
{E,F,H,K,L}+ = {{EFHGIJKLMN}
{E}+ = {E}
{EFH}+ and {EFHKL}+ results in set of all attributes, but EFH is minimal. So it will be candidate
key. So correct option is (B).
How to check whether an FD can be derived from a given FD set?
To check whether an FD A->B can be derived from an FD set F,
1. Find (A)+ using FD set F.
2. If B is subset of (A)+, then A->B is true else not true.
Question: In a schema with attributes A, B, C, D and E following set of functional
dependencies are given
{A -> B, A -> C, CD -> E, B -> D, E -> A}
Which of the following functional dependencies is NOT implied by the above set? (GATE IT
2005)
A. CD -> AC
B. BD -> CD
C. BC -> CD
D. AC -> BC
Answer: Using FD set given in question,
(CD)+ = {CDEAB} which means CD -> AC also holds true.
(BD)+ = {BD} which means BD -> CD can’t hold true. So this FD is no implied in FD set. So (B) is
the required option.
Others can be checked in the same way.
Prime and non-prime attributes
Attributes which are parts of any candidate key of relation are called as prime attribute, others are
non-prime attributes. For Example, STUD_NO in STUDENT relation is prime attribute, others are
non-prime attribute.
Question: Consider a relation scheme R = (A, B, C, D, E, H) on which the following
functional dependencies hold: {A–>B, BC–> D, E–>C, D–>A}. What are the candidate keys
of R?
(a) AE, BE
(b) AE, BE, DE
(c) AEH, BEH, BCH
(d) AEH, BEH, DEH
Answer: (AE)+ = {ABECD} which is not set of all attributes. So AE is not a candidate key. Hence
option A and B are wrong.
(AEH)+ = {ABCDEH}
(BEH)+ = {BEHCDA}
(BCH)+ = {BCHDA} which is not set of all attributes. So BCH is not a candidate key. Hence option
C is wrong.
So correct answer is D.
Dependencies in DBMS are a relation between two or more attributes. It has the following types in
DBMS −
Functional Dependency
Fully-Functional Dependency
Transitive Dependency
Multivalued Dependency
Partial Dependency
What is Fully-functional dependency?
An attribute is fully functional dependent on another attribute, if it is Functionally Dependent on
that attribute and not on any of its proper subset.
For example, an attribute Q is fully functional dependent on another attribute P, if it is Functionally
Dependent on P and not on any of the proper subset of P.
Let us see an example −
<ProjectCost>
ProjectID ProjectCost
001 1000
001 5000
<EmployeeProject>
EmpID ProjectID Days
E099 001 320
E056 002 190
The above relations states that −
Days are the number of days spent on the project.
EmpID, ProjectID, ProjectCost -> Days
However, it is not fully functional dependent.
Whereas the subset {EmpID, ProjectID} can easily determine the {Days} spent on the project by
the employee.
This summarizes and gives our fully functional dependency −
{EmpID, ProjectID} -> (Days)
What is Partial Dependency?
Partial Dependency occurs when a non-prime attribute is functionally dependent on part of a
candidate key.
The 2nd Normal Form (2NF) eliminates the Partial Dependency.
Let us see an example −
Example
<StudentProject>
StudentID ProjectNo StudentName ProjectName
S01 199 Katie Geo Location
S02 120 Ollie Cluster Exploration
In the above table, we have partial dependency; let us see how −
The prime key attributes are StudentID and ProjectNo, and
StudentID = Unique ID of the student
StudentName = Name of the student
ProjectNo = Unique ID of the project
ProjectName = Name of the project
As stated, the non-prime attributes i.e. StudentName and ProjectName should be functionally
dependent on part of a candidate key, to be Partial Dependent.
The StudentName can be determined by StudentID, which makes the relation Partial Dependent.
The ProjectName can be determined by ProjectNo, which makes the relation Partial Dependent.
Therefore, the <StudentProject> relation violates the 2NF in Normalization and is considered a
bad database design.
To remove Partial Dependency and violation on 2NF, decompose the tables −
<StudentInfo>
StudentID ProjectNo StudentName
S01 199 Katie
S02 120 Ollie
<ProjectInfo>
ProjectNo ProjectName
199 Geo Location
120 Cluster Exploration
Now the relation is in 2nd Normal form of Database Normalization.
Differentiate between Full Functional Dependency and Partial Dependency:
Full Functional Dependency : In a relation , there exists Full Functional Dependency
between any two attributes X and Y, when X is functionally dependent on Y and is not
functionally dependent on any proper subset of Y.
Partial Functional Dependency : In a relation, there exists Partial Dependency, when
a non-prime attribute (the attributes which are not a part of any candidate key ) is
functionally dependent on a proper subset of Candidate Key.
For example : Let there be a relation R ( Course, Sid , Sname , fid, schedule , room ,
marks )
Full Functional Dependencies : {Course , Sid) -> Sname , {Course , Sid} -> Marks, etc.
Partial Functional Dependencies : Course -> Schedule , Course -> Room
What is Transitive Dependency?
When an indirect relationship causes functional dependency it is called Transitive Dependency.
If P -> Q and Q -> R is true, then P-> R is a transitive dependency.
To achieve 3NF, eliminate the Transitive Dependency.
Example
<MovieListing>
Movie_ID Listing_ID Listing_Type DVD_Price ($)
M08 L09 Crime 180
M03 L05 Drama 250
M05 L09 Crime 180
The above table is not in 3NF because it has a transitive functional dependency −
Movie_ID -> Listing_ID
Listing_ID -> Listing_Type
Therefore, the following has transitive functional dependency.
Movie_ID -> Listing_Type
The above states the relation <MovieListing> violates the 3rd Normal Form (3NF).
To remove the violation, you need to split the tables and remove the transitive functional
dependency.
<Movie>
Movie_ID Listing_ID DVD_Price ($)
M08 L09 180
M03 L05 250
M05 L09 180
<Listing>
Listing_ID
Listing_Type
L09 Crime
L05 Drama
L09 Crime
Now the above relation is in Third Normal Form (3NF) of Normalization.
What is Multi-valued dependency?
When existence of one or more rows in a table implies one or more other rows in the same table,
then the Multi-valued dependencies occur.
If a table has attributes P, Q and R, then Q and R are multi-valued facts of P.
It is represented by double arrow −
->->
For our example:
P->->Q
P->->R
In the above case, Multivalued Dependency exists only if Q and R are independent attributes.
A table with multivalued dependency violates the 4NF.
Example
Let us see an example &mins;
<Student>
StudentName CourseDiscipline Activities
Amit Mathematics Singing
Amit Mathematics Dancing
Yuvraj Computers Cricket
Akash Literature Dancing
Akash Literature Cricket
Akash Literature Singing
In the above table, we can see Students Amit and Akash have interest in more than one activity.
This is multivalued dependency because CourseDiscipline of a student are independent of
Activities, but are dependent on the student.
Therefore, multivalued dependency −
StudentName ->-> CourseDiscipline
StudentName ->-> Activities
The above relation violates Fourth Normal Form in Normalization.
To correct it, divide the table into two separate tables and break Multivalued Dependency −
<StudentCourse>
StudentName CourseDiscipline
Amit Mathematics
Amit Mathematics
Yuvraj Computers
Akash Literature
Akash Literature
Akash Literature
<StudentActivities>
StudentName Activities
Amit Singing
Amit Dancing
Yuvraj Cricket
Akash Dancing
Akash Cricket
Akash Singing
This breaks the multivalued dependency and now we have two functional dependencies −
StudentName -> CourseDiscipline
StudentName - > Activities
What is Join Dependency?
If a table can be recreated by joining multiple tables and each of this table have a subset of the
attributes of the table, then the table is in Join Dependency. It is a generalization of Multivalued
Dependency
Join Dependency can be related to 5NF, wherein a relation is in 5NF, only if it is already in 4NF
and it cannot be decomposed further.
Example
<Employee>
EmpName EmpSkills EmpJob (Assigned
Work)
Tom Networking EJ001
Harry Web Development EJ002
Katie Programming EJ002
The above table can be decomposed into the following three tables; therefore it is not in 5NF:
<EmployeeSkills>
EmpName EmpSkills
Tom Networking
Harry Web Development
Katie Programming
<EmployeeJob>
EmpName EmpJob
Tom EJ001
Harry EJ002
Katie EJ002
<JobSkills>
EmpSkills EmpJob
Networking EJ001
Web Development EJ002
Programming EJ002
Our Join Dependency −
{(EmpName, EmpSkills ), ( EmpName, EmpJob), (EmpSkills, EmpJob)}
The above relations have join dependency, so they are not in 5NF. That would mean that a join
relation of the above three relations is equal to our original relation <Employee>.
