Functional Dependency and its types in SQL
Abstract:
“Normalization” is a very critical yet essential aspect in Database Management Systems. Generally, people directly start learning normalization but they miss this very base i.e., Functional Dependency and its types. After this topic, normalization is hardly a matter of half an hour. Functional Dependency (FD) is a constraint that determines the relation of one attribute to another attribute in a Database Management System (DBMS). This article will focus on firstly what actually a functional dependency is and will explain all the types of dependencies with real table illustrations to each. Armstrong’s Axioms are also explained very well which gives the added power to this concept in terms of logical implementation. This article will help you master this topic and will make your understanding in Normalization better.
What is Functional Dependency??
Let’s understand with an example: -
Let us consider 2 attributes α and β from a table. Now if we are saying that there exists a functional dependency from f:(α) à β, then it doesn’t mean that we will get the value of β if we are given α. Instead, it means that if we can search the values of β with the help of α in the table.
Rule: There cannot be any value of α pointing to the more than 1 value of β.
Here, α is known as “Determinant attribute” and β is known as “Dependent attribute” and is said as “α determines β” or “β is determined by α”.
Now in the below table let’s say there is a dependency between Roll_No à Name. But as one value of Roll_No (i.e 1) is associated with 2 different values of Name (i.e., Anoop and Anurag), thus is not an example of functional Dependency.
Example: — Which of the following functional dependencies does not hold true?
Explanation: -
Option 1- [ A à BC ] For all {a} à {2,3}, and {2} à {a,3}, thus it holds the rules.
Option 2- [ DE à C ] For all {4,5} à {3}, {6,5} à {3} and {6,6} à {3} thus it holds the rules.
Option 3- [ C à DE ] {3} à {4,5}, {6,5} and {6,6} thus it doesn’t hold the rules.
Option 4- [ BC à A ] For all {2,3} à {a}, and {a,3} à {2}, thus it holds the rules.
In Option 3 the property of “In any functional dependency f:(α) à β. There cannot be any value of α pointing to the more than 1 unique value of β.” does not hold, so Option 3 does not hold the dependency.
Types of Functional Dependency: -
There are 4 types of dependencies:
1. Trivial Dependency: In this type, if X à Y then Y is a subset of X, i.e Y ⊆ X.
Example: Let there be a student table, now a typical trivial dependency would be {STUD_NO, STUD_NAME} à {STUD_NAME}. Where STUD_NAME is a subset of {STUD_NO, STUD_NAME}.
2. Non-Trivial Dependency: In this type, if X à Y then Y is not a subset of X, i.e Y ⊄ X.
Example: In the above student table 1, now a typical non trivial dependency would be {STUD_NO, STUD_NAME} à {STUD_AG}. Where STUD_AG is not a subset of {STUD_NO, STUD_NAME}.
3. Multivalued dependency: In this type, if there is a FD as X à YZ, then Y à Z and Z à Y does not exist.
Example: In the above student table 1, now a typical Multivalued dependency would be {STUD_NO} à {STUD_NAME, STUD_STATE}. Because there exists no dependency between STUD_NAME and STUD_STATE as the dependency between them would not satisfy the rule of “In any functional dependency f:(α) à β. There cannot be any value of α pointing to the more than 1 unique value of β.”
4. Transitive Dependency: In this type, if X à Y and Y à Z exists, then X à Z is also a valid functional dependency.
Example: In the above student table 1, X = {STUD_NO, STUD_NAME} and Y = {STUD_AG}. Thus X à Y is valid functional dependency. Now let Z = {STUD_STATE } then, Y à Z and according to the rule now X à Z, making {STUD_NO, STUD_NAME} à {STUD_STATE} a valid functional dependency.
Armstrong axioms: -
The word “Armstrong axioms” applies to William W. Armstrong’s sound and detailed set of inference rules or axioms for checking the logical implication of functional dependencies.
There are 3 Primary rules and 3 Secondary / Derived rules.
Primary Rules: -
1. Reflexive Rule: — In the reflexive rule, if Y is a subset of X, then X determines Y.
v If X ⊇ Y then X à Y.
Example: In the Table 1, X = {STUD_NO, STUD_NAME, STUD_AG} and Y = {STUD_NAME, STUD_AG}. Thus Y ⊆ X and hence X à Y is valid functional dependency.
2. Augmentation Rule: — The augmentation rule is also known as a partial dependency. In partial dependency, if X determines Y, then XZ determines YZ for any Z attribute/set of attributes in the table R.
v If X à Y then XZ à YZ.
Example: In the Table 1, X = {STUD_NO, STUD_NAME} and Y = {STUD_STATE}. Thus X à Y is valid functional dependency. Now let Z = { STUD_AG } then, XZ à YZ making {STUD_NO, STUD_NAME, STUD_AG } à {STUD_STATE, STUD_AG } a valid functional dependency.
3. Transitive Rule: — In the transitive rule, if X determines Y and Y determine Z, then X must also determine Z.
v If X à Y and Y à Z then X à Z
Example: In the Table 1, X = {STUD_NO, STUD_NAME} and Y = {STUD_AG}. Thus X à Y is valid functional dependency. Now let Z = {STUD_STATE } then, Y à Z and according to the rule now X à Z, making {STUD_NO, STUD_NAME} à {STUD_STATE} a valid functional dependency.
Secondary / Derived Rules: -
1. Union: — If X determines Y and X determines Z, then X must also determine Y and Z.
v If X à Y and X à Z then X à YZ.
Proof:
1. X → Y (given)
2. X → Z (given)
3. X → XY (using Partial dependency rule on 1 by augmentation with X)
4. XY → YZ (using 2nd primary Rule on 2 by augmentation with Y)
5. X → YZ (using 3rd primary rule on 3 and 4)
Example: In the Table 1, X = {STUD_NO} and Y = {STUD_STATE}. Thus X à Y is valid functional dependency. Now let Z = {STUD_AG} then, X à Z, thus making {STUD_NO} à {STUD_STATE, STUD_AG} a valid functional dependency i.e., X à YZ.
2. Decomposition Rule: — if X determines Y and Z, then X determines Y and X determines Z separately.
v If X à YZ then X à Y and X à Z.
Proof:
1. X → YZ (given)
2. YZ → Y (using 1st Primary Rule)
3. X → Y (using 3rd Primary Rule on 1 and 2)
Example: In the Table 1, X = {STUD_NO}, Y = {STUD_STATE} and Z = {STUD_AG}. Thus X à YZ i.e., {STUD_NO} à {STUD_STATE, STUD_AG} is valid functional dependency. Thus X à Y and X à Z as {STUD_NO} à {STUD_STATE} and {STUD_NO} à {STUD_AG} are valid functional dependencies.
3. Pseudo transitive Rule: — If X determines Y and YZ determines W, then XZ determines W. Where W is any attribute in table R.
v If X à Y and YZ à W then XZ à W.
Proof:
1. X → Y (given)
2. WY → Z (given)
3. WX → WY (using 2nd primary rule on 1 by augmenting with W)
4. WX → Z (using 3rd primary rule on 3 and 2)
Example: In the Table 1, X = {STUD_NO}, Y = {STUD_STATE}, Z = {STUD_AG} and W = {STUD_NAME}. Thus X à Y and YZ à W i.e., {STUD_NO} à {STUD_STATE} and {STUD_STATE, STUD_AG} à {STUD_NAME} are valid functional dependencies. Thus XZ à W as {STUD_NO, STUD_AG} à {STUD_NAME} is a valid functional dependency.
