Functional dependencies in DBMS: definition, testing on a table and exam problems

0:00 Overview

This lesson introduces the basics of functional dependencies (FDs) in database management systems, covering formal definitions, the concept of keys as a generalization, the notation $X\to Y$ ("$X$ determines $Y$"), formal semantics based on tuple agreement, and evaluating validity using an example relation instance.

0:12 Definition of Functional Dependencies

• Functional Dependency (FD): A constraint between two sets of attributes in a relation from a database.
• Generalization of Keys: An FD is the generalization of the concept of keys.
• Notation: Represented as: $$\text{X}\to \text{Y}$$ Read as: "$\text{X}$ determines $\text{Y}$" (or: with the help of a unique value of $\text{X}$, you can determine every unique value of $\text{Y}$).

Example of Student Roll Number vs. Name

• Class with Students (Roll Number and Name):
  • Given a Roll Number, you can uniquely tell the Name of the student (one roll number uniquely determines the student's name).
  • Given a Name (e.g., "Himanshu"), if multiple students in the class share the same name, you cannot uniquely determine the Roll Number from the Name alone.
• Therefore, $\text{Roll Number}\to \text{Name}$ holds, but $\text{Name}\to \text{Roll Number}$ does not.

2:34 Formal Definition: Tuple Agreement

$$\text{X}\to \text{Y}\text{ says that if two tuples agree on the value of attribute }\text{X},\text{ then they must also agree on the value in attribute }\text{Y}.$$

3:24 Example Relation Instance and Evaluating FDs

Consider a relation with attributes $\text{A},\text{B},\text{C},\text{D}$ and the following instance:

Testing Candidate Functional Dependencies

1. Is $\text{A}\to \text{B}$ valid?

   • Check value $a_1$ of attribute $\text{A}$. It appears in two rows, paired with $\text{B}$ values $b_1$ and $b_2$.
   • Since the same $\text{A}$ value ($a_1$) maps to two different $\text{B}$ values ($b_1$ and $b_2$), $\text{A}$ cannot uniquely determine $\text{B}$.
   • Result: $\text{A}\to \text{B}$ does not hold (marked with $\times$).

2. Is $\text{A}\to \text{C}$ valid?

   • For $\text{A}=a_1$, $\text{C}$ has two different values ($c_1$ and $c_2$).
   • Result: $\text{A}\to \text{C}$ does not hold.

3. Is $\text{A}\to \text{D}$ valid?

   • For $\text{A}=a_1$, $\text{D}=d_1$ in both rows where $\text{A}=a_1$.
   • For $\text{A}=a_3$, $\text{D}=d_2$.
   • Every unique value of $\text{A}$ maps to a unique value of $\text{D}$.
   • Result: $\text{A}\to \text{D}$ holds (marked with $✓$).

4. Is $\text{B}\to \text{A}$ valid?

   • Two different $\text{B}$ values are associated with multiple or conflicting $\text{A}$ values.
   • Result: $\text{B}\to \text{A}$ does not hold.

5. Is $\text{B}\to \text{C}$ valid?

   • Result: $\text{B}\to \text{C}$ does not hold.

6. Is $\text{B}\to \text{D}$ valid?

   • Result: $\text{B}\to \text{D}$ does not hold.

7. Is $\text{C}\to \text{A}$ valid?

   • Result: $\text{C}\to \text{A}$ does not hold.

8:00 Checking Functional Dependencies with Counterexamples

• $C\to B$: Invalid. In the table, row 1 and row 2 both have $C=c_1$, but their $B$ values are $b_1$ and $b_2$ respectively ($b_1\ne b_2$). Since the same $C$ value points to different $B$ values, $C$ cannot uniquely determine $B$.
• $C\to D$: Invalid. Two rows with $C=c_1$ have different $D$ values ($d_1$ and $d_2$).
• $D\to A$: Invalid. $D$ values repeat, but their corresponding $A$ values are not unique.
• $D$ determining itself ($D\to D$): Always valid (trivial dependency). Every value of $D$ is associated with precisely one value of $D$.
• $D\to B$: Invalid. $D$ has repeating values with different $B$ values.
• $D\to C$: Invalid.

9:24 Combined Attribute Functional Dependencies

You are not limited to single-attribute left-hand sides; you can use combinations of attributes (e.g., $AB$).

• $AB\to C$: Valid.
  • Combinations of $AB$ in the table:
    • $a_1{b}_1$
    • $a_1{b}_2$
    • $a_2{b}_2$
    • $a_3{b}_3$
    • $a_4{b}_4$
    • $a_5{b}_3$
  • All these combinations are unique (none repeat). Since every combined $AB$ value is unique in the relation instance, it vacuously satisfies uniqueness and successfully determines $C$.
• $AB\to D$: Valid. Every value of $A$ is unique, so $AB$ determines $D$.
• $BC\to A$: Valid. All combinations of $BC$ are unique, so $BC$ determines $A$.
• $BC\to D$: Valid.

11:35 Formal Definition of Functional Dependency Satisfaction

Given a relation $R$, a set of attributes $X$ in $R$ is said to functionally determine another set of attributes $Y$ (also in $R$), denoted as $X\to Y$, if and only if:

Each $X$ value is associated with precisely one value of $Y$.

When this holds for all tuples in a relation instance, $R$ is said to satisfy the FD $X\to Y$.

Note that $X$ and $Y$ are sets of attributes (e.g., $X=\{A,B\}$ and $Y=\{C,D\}$).

13:51 Applications of Functional Dependencies

Using functional dependencies derived from a given relation, we can perform several database operations:

1. Additional FDs: Discover what other new functional dependencies hold on the relation.
2. Identifying Keys: Find candidate keys, primary keys, or super keys in the relation.
3. Equivalences in Functional Dependencies: Determine if two different sets of functional dependencies are equivalent to each other.
4. Minimal Functional Dependencies (Minimal Cover): Minimize a large set of functional dependencies so that it presents the same information using fewer FDs.

15:00 Exam Problem Example

Consider a relation $R(A,B,C)$ having the tuples given below:

R(A B C)
1 2 3
4 2 3
5 3 3
5 3 3

Question: Which of the following functional dependencies does not hold over $R$?

• Option A: $A\to B$
• Option B: $BC\to A$
• Option C: $B\to C$

16:00 ABC Relation Practice Problem

Consider a relation $R(A,B,C)$ having the tuples:

R(A, B, C)
---------
1  2  3
1  4  3
4  2  3
3  3  3

We want to determine which of the following functional dependencies does not hold:

• a) $A\to B$
• b) $BC\to A$
• c) $B\to C$
• d) $AC\to B$

Evaluating Each Option:

• a) $A\to B$: With the help of a unique value of $A$, can you determine $B$? Yes, you can do it. Why? Because all these values of $A$ are unique; there is no value repeating itself. Therefore, this holds.
• b) $BC\to A$: First of all, check with $B$ and $C$. Is every value unique? No, it is not unique because 2 3 is repeating two times. If 2 3 is repeating two times, then check whether $A$ is having a unique value in both the cases. Here you can clearly see $A$ is not having a unique value; $A$ is having value $1$ and $4$, which are not unique. Therefore, given $BC$, you cannot uniquely tell what is the value of $A$. Therefore, this does not hold.
• c) $B\to C$: Can you say $B\to C$? Yes, I can say that. Why? Because if the values of $B$ are repeating, in both the cases $C$ is containing a unique value, that is $3$. So this does hold.
• d) $AC\to B$: Yes, $AC$ does determine $B$ because all these combinations are unique (1 3, 4 3, and 5 3 — note: the last tuple has $A=3,B=3,C=3$, so combinations are 1 3, 4 3, 3 3). All these combinations are unique. Therefore, this does hold.

So the functional dependency which is represented by option b (BC -> A) does not hold.

17:20 XYZ Relation Practice Problem

Consider the following relation instance where we have the attributes $X,Y$, and $Z$:

X  Y  Z
-------
1  4  3
1  5  3
4  6  3
3  2  2

We are asked: Which of the following functional dependencies are satisfied by the above instance? That means what are the functional dependencies which are satisfied here?

• a) $XY\to Z,Z\to Y$
• b) $XZ\to X,Y\to Z$
• c) $XY\to Z,Z\to X$
• d) $XZ\to Y,Y\to Z$

We have to tell which of the following functional dependencies does not hold.

Evaluating Option by Option:

• Case 1: $XY\to Z$

  • If you take every value of every combination of $XY$, are all these combinations unique? Yes, all the combinations are unique. That is why $XY\to Z$.
  • Can I say $Z\to Y$? I cannot say $Y$ because $Z$ is repeating three times. These values are repeating three times and they are associated with different values of $Y$. Therefore, $Z$ cannot determine $Y$.

• Case 2: $XZ\to X$

  • If you take all these combinations of $X$ and $Z$, then is there any combination which is repeating itself? Yes, there is one combination, that is 1, 3 is here as well as 1, 3 is here. That means if you take a combination of $X$ and $Z$, there are two combinations which are repeating itself.
  • But it is determining $X$ itself, right? Because for this combination $X$ is containing a unique value. By the way, this kind of functional dependency is also called as trivial functional dependencies.
  • A trivial functional dependency is if we have some $X\to Y$ where $X$ and $Y$ both are set of functional dependencies and $Y$ is a subset of $X$, then you can say this is a trivial functional dependency (I'll cover this in later videos).
  • Just giving you a hint: if we have $ABC\to AB$, you can see this part is a subset of this part. So this kind of functional dependency is trivial, and it does—it always does hold. So this one is also true.

• Can I say $Y\to Z$? Yes, I can say $Y\to Z$ because $Y$ is containing all the unique values. There is no value in $Y$ which is repeating itself.

• Therefore, option b is correct.

• Option c ($XY\to Z$ and $Z\to X$):

  • $XY\to Z$ is true.
  • Is $Z\to X$ true? No. Why? Because $3$ is repeating (containing a value $1$, as well as $3$ is containing value of $4$). So it is not valid.

• Option d ($XZ\to Y$ and $Y\to Z$):

  • If I take $XZ\to Y$, it does not hold $Y$ because $XZ$ is having 1, 3 and 1, 3. For these combinations $Y$ is having two different values ($4$ and $5$). Therefore, this does not hold.

So you can see only the option number b holds; other options are wrong because there is at least one value, at least one functional dependency which are given in those options which does not hold.

In case of functional dependencies, there are some axioms which hold, like they are also called as Armstrong's axioms. Let us look at those axioms. Axioms are kind of inference rules, or you can say a set of formulas.

Key Takeaways

• Definition: A Functional Dependency (FD), denoted as $X\to Y$ ("$X$ determines $Y$"), is a database constraint stating that a unique value of attribute set $X$ uniquely determines the value of attribute set $Y$.
• Tuple Agreement Semantics: An FD $X\to Y$ holds if any two tuples that agree on their $X$ values must also agree on their $Y$ values.
• Evaluating Validity: To test an FD in a relation instance, check if repeating values in the left-hand side ($X$) always point to the exact same value in the right-hand side ($Y$). If a single $X$ value maps to multiple $Y$ values, the FD is invalid.
• Combined Attributes: Left-hand sides are not restricted to single attributes; combinations of attributes (e.g., $AB\to C$) can also functionally determine other attributes.
• Trivial FDs: A functional dependency $X\to Y$ is always valid (trivial) if $Y$ is a subset of $X$ (e.g., $D\to D$ or $ABC\to AB$).
• Applications: FDs are used to discover new dependencies, identify keys (candidate, primary, super keys), determine FD equivalences, and compute minimal covers.