Functional Dependencies in Database

Functional dependencies are the result of interrelationship between attributes or in between tuples in  any  relation.

Definition : In relation R, X and Y are the two subsets of the set of attributes, Y is said to be functionally dependent on X if a given value of X (all attributes in X) uniquely determines the value of Y (all attributes in Y).

It is denoted by X → Y(Y depends upon X).

Determinant : Here X is known as determinant of functional dependency. Consider the  example  of  Employee  relation:

In Employee relation, EID is primary key. Suppose you want to know the name and salary of any employee. If you have EID of that employee, then you can easily find information of that employee. So, Name and Salary attributes depend upon EID attribute.

Here, X  is (EID)  and Y is (Name,  Salary)

X (EID) : Y (Name, Salary)

The determinant is EID

Suppose X has value 5 then Y has value (Manoj, 9,000)

1. Functional Dependency Chart/Diagram

It is the graphical representation of function dependencies among attributes in any relation. The following  four  steps  are  followed  to  draw  FD  chart.

1. Find out the primary key
2. Make a rectangle and  write  all primary  key attributes  inside
3. Write all non-prime key attributes outside the
4. Use arrows to show functional  dependency among

Consider the example of Figure 6.1. Its functional dependency chart is shown   in Figure 6.2.

It is  easier to  remember  all dependencies  by making  FD  charts.

Example. Consider the  following relation:

Professor (Pfcode, Dept, Head, Time) It is assumed that

1. A professor can work in more than one
2. The time he spends in each dept is
3. Each dept has only one

Draw the  dependency diagram  for  the given  relation  by identifying  the  dependencies.

Sol. The Figure 6.3 shows the corresponding dependency diagram.

2. Types of Functional Dependencies

There are four major types of FD’s.

1.   Partial Dependency and Fully Functional Dependency

• Partial dependency : Suppose you have more than one attributes in primary Let A be the non-prime key attribute. If A is not dependent upon all prime key attributes then partial dependency exists.
• Fully functional dependency : Let A be the non-prime key attribute and value of A is dependent upon all prime key Then A is said to be fully functional dependent. Consider a relation student having prime key attributes (RollNo and Game) and non-prime key attributes (Grade, Name and Fee).

As shown in Figure 6.4, Name and Fee are partially dependent because you can find the name of student by his RollNo. and fee of any game by name of the game.

Grade is fully functionally dependent because you can find the grade of any student in a particular game if you know RollNo. and Game of that student. Partial dependency is due to  more  than  one  prime  key  attribute.

2.   Transitive Dependency and Non-transitive Dependency

• Transitive dependency :Transitive dependency is due to dependency between non-prime key attributes. Suppose in a relation R, X → Y (Y depen upon X), Y → Z (Z depends upon Y), then X → Z (Z depends upon X). Therefore, Z is said to be transitively dependent upon X.
• Non-transitive dependency : Any functional dependency which is not transitive is known as Non-transitive dependency.

Non-transitive dependency exists if there is no dependency between non-prime key attributes.

Consider a relation student (whose functional dependency chart is shown in Figure 6.5) having prime key attribute (RollNo) and non-prime key attributes (Name, Semester, Hostel).

For each semester there is different hostel

Here Hostel is transitively dependent upon RollNo. Semester of any student can be find by  his  RollNo. Hostel  can  be  find out  by  semester  of student.

Here, Name is  non-transitively dependent upon RollNo.

3.   Single Valued Dependency and Multivalued Dependency

• Single valued dependency : In any relation R, if for a particular value of X, Y has single value then it is known as single valued  dependency.
• Multivalued dependency (MVD) : In any relation R, if for a particular value of X, Y has more then one value, then it is known as multivalued It is denoted by X →→ Y.

Consider the relation Teacher shown in Figure 6.6(a) and its FD chart shown in Figure 6.6(b).

There is MVD between Teacher and Class because a teacher can take more than one class. There is another MVD between Class and Days because a class can be on more than one day.

There is single valued dependency between ID and Teacher because each teacher has a unique ID.

4.   Trival Dependency and Non-trival Dependency

• Trival FD : In any relation R, X ® Y is trival if Y Í X (Y is the subset of X).
• Non-trival FD : In any relation R, X ®Y is non-trival if Y  X (Y is not the subset of X)

Consider the Supplier-Product relation shown in Figure 6.7.

Here,                                          (S#, P#) : S# is  trival FD

S# : Supplier ID

P# :   Product ID

Example. Consider the  given relation  R:

Write all non-trivial functional dependencies satisfied by R. Also give an example of an FD that does not hold on R.

Sol. For functional dependencies look at the data given in the table.

• The FD O → P holds on R, since for each value of O there is a single value of P.
• The FD O → Q does not hold on R, since in the 2nd and 3rd row, O has the same value, but Q  has  different  values.

The non-trivial functional  dependencies are  as follows:

O → P, Q → O, Q → P, OQ → P, PQ → O, Q → OP, O → OP, OQ → PQ, OQ → OPQ, Q → OQ, PQ → OPQ, Q → OPQ, P → O, P → OP

Source: Gupta Satinder Bal, Mittal Aditya (2017), Introduction to Basic Database Management System, 2nd Edition-University Science Press (2017)