Functional Dependency In DBMS

In database management systems (DBMS), functional dependency is a relationship between two sets of attributes (columns) in a database table. It defines how one attribute (or group of attributes) determines the value of another attribute. Simply put, if you know the value of one attribute, you can determine the value of another.

Functional dependencies are crucial in normalization and help in organizing data efficiently, eliminating redundancy, and improving data integrity.

Functional Dependency Syntax in DBMS

A Functional Dependency (FD) is written using the arrow symbol (→) to show dependency between attributes. The following diagram shows the syntax of FD

• Determinant: The attribute that determines another attribute.
• Dependent: The attribute whose value depends on the determinant.

Where:

• The left side (LHS) of the FD (attribute X) is known as a determinant,
• The right side (RHS) of the FD (attribute Y) is known as a dependent. 

Different Forms of FD Syntax

A Functional Dependency (FD) in DBMS is a relationship between attributes where one attribute (or set of attributes) determines another attribute. Here are 4 different forms of functional Dependency (FD) in DBMS are given below Note: FD Notation can represented as followings also

• {A} → {B}
• {A} → {B,C}
• {A<C} → {A,B}

Different ways to write FD Syntax

Here is the list of the top 6 ways to write DF, given below

Functional Dependency Concept in DBMS

Let A, B be two attributes in a Relation R. Then we say that A → B if and only if whenever all tuples (t) have the same A value, then those tuples also have the same B value

• t1.A = t2.A = t3.A = …. tn.A ⇒ t1.B = t2.B = t3.B = …. tm.B

for all tuples are t1, t2, t3, ……, tn where m,n ≥ 1

Formally Notation: For all tuples t1​,t2​∈R,t1​.A=t2​.A ⇒ t1​.B=t2​.B

Example with Relation 

Consider a relation R(A, B) that holds the functional dependency A → B A functional dependency A→ B is said to hold on schema R if every legal instance of R satisfies the dependency. We can see in the above table that whenever the values of “A” are similar, then the values of ” B will also be similar. i.e., In the above table,

• All 0s of “A” hold the same value “100”.
• All 1 of “A” holds the same value “500”.

Functional Dependency levels (Instance and Schema)

A functional dependency may hold in a specific instance of a relation but may not necessarily hold at the schema level, since schema-level dependencies must be satisfied by all legal instances.  Let expalin both functional and instance level functional dependencies with an example, consider the following table

i. Instance Level Functional Dependency

A functional dependency Name → Marks is satisfied in instance 1, but not satisfied in other instances. As in instance 1 whenver the Name comes similar, then their marks will also be similar. For example, In the above table, all names of “Ali” must hold the same numbers as “50” in instance 1

 ii. Schema Level Functional Dependency

A functional dependency District → State is said to hold on schema R if every legal instance of R satisfies the dependency. We can see in the above table that whenever the District name is similar, then the State will also be similar. i.e. In the above table, all districts with the name “Vehari” must hold the same name as “Punjab”.

Important:

• schema-level dependencies must be satisfied by all legal instances, but instance-level dependencies may or may not be satisfied by the schema (Relation)
• Functional Dependencies (FDs), Referential Constraints, Key Constraints, Domain Constraints, etc. are defined on the schema, not on a specific instance.

Function Dependencies Exercise

Question 1: Consider the relation instance and functional dependencies below, which of these Fd’s are on the instance and which do not?

1. A → B
2. A → C
3. B → C
4. B → A
5. C → A
6. C → B

Solution: Only the following two dependencies satisfy

• A → C
• C → A

Note: The above two dependencies may or may not hold in relation or schema (in the future). Question 02: The functional dependency A → C is satisfied, but C → A is not satisfied. Justify Solution:

• A → C Satisfied, Explain: There are two tuples that have an A value of a1, These tuples have the same C value name as “c1”. Similarly, the two tuples with an A value of a2 have the same C value, c2. There are no other pairs of distinct tuples that have the same A value.
• C → A  not Satisfied, Explain: There are two tuples that have an C value of c1, These tuples have the same A value name as “a1” Similarly, the three tuples with a C value of c2 have different A values, a2 and a3. So, the dependency condition is violated.

Question 03: The functional dependency AB → BC is satisfiedin the following Relation. Justify Solution:

• AB → BC Satisfied, Explain: There are two tuples that have combination of AB values of a1b1, These tuples have the same BC combination value name as “b1c1”. Similarly, the two tuples with an AB value of a2b2 have the same BC value, b2c2. There are no other pairs of distinct tuples that have the same AB value. So, AB → BC Satisfy the functional Dependency

Question 4: Consider the relation instance and functional dependencies below, which of these Fd’s are on the instance and which do not?

1. AB → C
2. AC → B
3. BC → A
4. ABC → A

Solution: Following three functional dependencies satisfied

1. AB → C
2. BC → A
3. ABC → A

Question 5: Consider the relation instance and functional dependencies below, which of these Fd’s are on the instance and which do not?

1. XY→ Z and Z→ Y
2. YZ → X and Y→ Z
3. YZ→ X and X→ Z
4. XZ→ Y and Y → X

Solution: Only the second dependency, which is YZ → X and Y→ Z, is satisfied.

Types of Functional Dependency

There are two major types of functional dependency Let’s explain

I. Trivial Functional Dependency

A functional dependency X → Y is trivial if Y is a subset of X.

• Mathematically: If Y ⊆ X, then X → Y is trivial.

That means the right-hand side attributes are already present in the left-hand side.

Example 1: Given Functional Dependency = A → A over Relation R(A, B)

Answer: Since A ⊆ A, it is trivial. In simple words, RHS (A) is already part of LHS (A). So, given that FD  is trivial.

Example 2: Given Functional Dependency = AB → A over Relation R(A, B)

Answer: Since A ⊆ AB, it is trivial. In simple words, RHS (A) is already part of LHS (AB). So, given that FD  is trivial.

 Important Point:

• Trivial functional dependencies always hold in every relation because the right-hand side is a subset of the left-hand side. Therefore, they do not provide meaningful design information.
• Non-trivial functional dependencies are useful because they represent actual data relationships and are important in normalization. In such FDs, we can decompose the RHS and remove trivial parts to obtain completely non-trivial functional dependencies.

II. Non-Trivial Functional Dependency

A functional dependency X → Y is non-trivial if Y is NOT a subset of X.

• Mathematically: If Y ⊄ X, then X → Y is non-trivial.

The right side contains at least one attribute that is not in X.

Example 1: Given Functional Dependency = A → B over Relation R(A, B)

Answer: Since B ⊄ A, it is non-trivial. In simple words, RHS (B) is not part of LHS (A). So, given FD is non-trivial.

Example 2: Given Functional Dependency = AB → C over Relation R(A, B)

Answer: Since C ⊄ AB, it is non-trivial. In simple words, RHS (C) is not part of LHS (AB). So, given FD  is non-trivial.

Completely Non-Trivial Functional Dependency It is a special type of non-trivial FD. A functional dependency X → Y is completely non-trivial if  X ∩ Y = ∅. That means there is no common attribute between left and right side. Example 1: Given Functional Dependency = A → B over Relation R(A, B) Answer: A ∩ B = ∅  In simple words, there is non common attribute between LHS and RHS. So it is completely non-trivial

 Quick Comparison Table

Other Notations of Functional Dependency

Here is another notation for representing functional dependency. Look at the following diagram Remember the Rule:

• Left Hand Side (LHS) of FD will be represented without arrow
• The right-hand side (RHS) of FD will be represented with an arrow

Functional Dependency Representation: Example 01

Functional Dependency Representation: Example 02

Functional Dependency Representation: Example 03

Functional Dependency Laws

Functional Dependency laws are inference rules used to derive new FDs from given FDs. They are called Armstrong’s Axioms. Armstrong’s Axioms consist of three fundamental rules: Reflexivity, Augmentation, and Transitivity. All other functional dependency rules, such as Union, Decomposition, and Pseudotransitivity, are derived from these three axioms. Let’s start one by one

1. Reflexivity Rule

A set of attributes always determines its subset. This rule always represents the trivial Functional Dependency

• Mathematically: If Y ⊆ X, then X→YX 

Examples:

• A → A
• AB → A
• ABC → AC
• ABCDE → DB

Proof: Consider the following relation R(A, B, C, D, E) that proves the reflexivity rule using the example ABCDE → DB. Solution: Consider an example ABCDE → DB that proves the reflexivity rule over the above R(A, B, C, D, E). If two tuples have the same ABCDE value, then those tuples will also have the same DE combinations.

• Look at the tuple 1,3 of the given relation, which has the same ABCDE value, which is 14222, then those tuples will also have the same DE combinations, having values 22

Hence, the reflexivity rule is satisfied.

2. Augmentation Rule

If a set of attributes determines another set of attributes, then adding the same attribute(s) to both sides of the dependency does not change the validity of the dependency.

Mathematically: If X → Y, then XZ → YZ

Examples:

• if A → B, then AC → BC
• if AB → C, then ABD → CD
• if X → Y, then XZ → YZ

Proof: Consider the following relation R(A, B, C, D) that proves the augmentation rule using the example

• if AB → C, then ABD → CD

Solution: Consider an example, if AB → C, then ABD → CD, which proves the augmentation rule over the above R(A, B, C, D). If two tuples have the same ABD value, then they will also have the same CD combinations.

• Look at the tuple 1,3 of the given relation, which has the same ABD value, which is 142, then those tuples will also have the same CD combinations, having values 22

Hence, the augmentation rule is satisfied.

3. Transitivity Rule

If one attribute set determines a second set, and that second set determines a third set, then the first set determines the third set.

Mathematically: If X → Y and Y → Z, then X → Z

Examples:

• if A → B and B → C,  then A → C
• if AB → C and C → D, then AB → D

Here is the diagram that proves the transitivity rule. Proof: Consider the following relation R(A, B, C, D) that proves the transitivity rule using the example

• if AB → C and C → D, then AB → D

Solution: Consider an example, if AB → C and C → D, then AB → D, which proves the transitivity rule over the above R(A, B, C, D). If two tuples have the same AB value, then they will also have the same D Value.

• Look at the tuple 1,2,3 of the given relation, which has the same AB value, which is 14, then those tuples will also have the same D combinations, having values 5

Hence, the transitivity rule is satisfied.

4. Union Rule (Combine FD on RHS)

If a set of attributes determines two attribute sets separately, then it determines their union.

Mathematically: If X → Y and X → Z, then X → YZ

Examples:

• if A → B and  A → C, then A → BC
• if AB → C and AB → D, then AB → CD

Proof: Consider the following relation R(A, B, C, D) that proves the union rule (Combine FD on RHS) rule using the example

• if AB → C and AB → D, then AB → CD

Solution: Consider an example, if AB → C and AB → D, then AB → CD, which proves the union rule over the above R(A, B, C, D). If two tuples have the same AB value, then they will also have the same CD Value.

• Look at the tuple 1,2,3 of the given relation, which has the same AB value, which is 14, then those tuples will also have the same CD combinations, having values 25

Hence, the union rule is satisfied.

5. Decomposition Rule (Split FD on RHS)

If a set of attributes determines a combined set of attributes, then it determines each attribute separately.

Mathematically: If X → YZ, then X → Y and X → Z

Examples:

• If A → BC, then A → B and A → C
• if AB → CD, then AB → C and AB → D

Here is the diagram that proves the decomposition rule (Split FD on RHS). Proof: Consider the following relation R(A, B, C, D) that proves the decomposition rule (Split FD on RHS) using the example

• If A → BC, then A → B and A → C

Solution: Consider an example, if A → BC, then A → B and A → C, which proves the decomposition rule over the above R(A, B, C). If two tuples have the same A value, then they will also have the same B Value. Similarly, if two tuples have the same A value, then they will also have the same C value.

• Look at the tuple 1,3 of the given relation, which has the same A value, which is 1, then those tuples will also have the same B value, having values 4
• Look at the tuple 1,3 of the given relation, which has the same A value, which is 1, then those tuples will also have the same C value, having values 2

Hence, the decomposition rule is satisfied.

6. Pseudotransitivity Rule

If a set determines another set, and combining that determined set with another attribute determines a third set, then combining the first set with that attribute determines the third set.

Mathematically: If X → Y and WY → Z, then WX → Z

Examples:

• if A → B and CB → D then CA → D
• if AB → C and DC → E then, DAB → E

Proof: Consider the following relation R(A, B, C, D) that proves the pseudotransitivity rule using the example

• if A → B and CB → D then CA → D

Solution: Consider an example, if A → B and CB → D, then CA → D, which proves the pseudotransitivity rule over the above R(A, B, C, D). If two tuples have the same CA value, then they will also have the same D Value.

• Look at the tuple 1,3, of the given relation, which has the same CA value, which is 21, then those tuples will also have the same D value, having values 8

Hence, the pseudotransitivity rule is satisfied.

7. Composition (Combine FD on LHS)

If two functional dependencies hold separately, then their left-hand sides and right-hand sides can be combined.

Mathematically:  If X→Y  and Z→W Then XZ→YW

Examples:

• If A→B  and C→D Then AC→BD
• If AB→CD  and EF→GH, then ABEF→CDGH

Proof: Consider the following relation R(A, B, C, D) that proves the composition rule using the example

• If A→B  and C→D Then AC→BD

Solution: Consider an example, A→B, and C→D, then AC→ BD. , which proves the composition  rule over the above R(A, B, C, D). If two tuples have the same AC value, then they will also have the same BD Value.

• Look at the tuple 1,2,3 of the given relation, which has the same AC value, which is 12, then those tuples will also have the same BD value, having values 42

Hence, the composition rule is satisfied.

Important: Becarefull, here is the common mistake in functional dependency If XY → Z, then does it not imply that X → Z and Y → Z. The following diagram explains it Note in the above diagram, XY → Z hold, but Y→ Z and Y→ Z are not held.

Why is Functional Dependency Important?

• Normalization: Understanding functional dependencies is crucial in the normalization process, where they help organize data and reduce redundancy in a database.

• Data Integrity: Functional dependencies help maintain the consistency and integrity of data by ensuring that updates are made consistently across the database.

• Efficient Queries: When the data is organized based on functional dependencies, queries can be processed more efficiently, improving performance.

• Designing Tables: Functional dependencies help in defining keys, especially candidate keys and foreign keys, which are vital in relational database design.

Conclusion

Functional dependency is a fundamental concept in database design that helps organize data efficiently and maintain data integrity. By understanding functional dependencies, database designers can ensure that data is stored in the most logical and effective way, leading to faster queries, fewer data anomalies, and a well-structured database.