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 eight major types of functional dependencies commonly discussed in DBMS, which is shown in the following diagram

  Let’s explain

1. Trivial Functional Dependency

A Trivial Functional Dependency exists when the RHS (dependent attribute) is a subset of the LHS (determinant).

• Rule: If X → Y and Y ⊆ X then X → Y is called a Trivial Functional Dependency.

Example 1:

Suppose a Relation R(A, B, C) contains the following Functional Dependencies:

• ABC → AB
• ABC → A

Since AB ⊆ ABC and A ⊆ ABC, both are trivial functional dependencies.

Example 2:

Suppose the relation R(A, B, C, D, E) contains the following functional dependencies:

• ABCDE → ACE
• ABCDE → E

Since ACE ⊆ ABCDE and E ⊆ ABCDE, both are trivial functional dependencies.

2. Non-Trivial Functional Dependency

A Non-Trivial Functional Dependency exists when the RHS (dependent attribute) is not a subset of the LHS (determinant).

• Rule: If X → Y and Y ⊄ X, then X → Y is called a Non-Trivial Functional Dependency.

Example 1:

Suppose a Relation R(A, B, C) contains the following Functional Dependencies:

• A → AB
• AB → ABC

Since AB ⊄ A and ABC ⊄ AB, both are non-trivial functional dependencies.

Example 2:

Suppose the relation R(A, B, C, D) contains the following functional dependencies:

• AB → ABCD
• C → AB

Since ABCD ⊄ AB and AB ⊄ C, both are non-trivial functional dependencies.

3. Completely Non-Trivial Functional Dependency

A Completely Non-Trivial Functional Dependency exists when no attribute of the RHS (dependent attributes) appears in the LHS (determinant). In other words, the LHS and RHS are disjoint sets.

• Rule: If X → Y and X ∩ Y = ∅, then X → Y is called a Completely Non-Trivial Functional Dependency.

Example 1:

Suppose a Relation R(A, B, C) contains the following Functional Dependencies: A → BC B → AC Since A ∩ BC = ∅ and B ∩ AC = ∅, both are completely non-trivial functional dependencies.

Example 2:

Suppose the relation R(A, B, C, D) contains the following functional dependencies:

• AB → CD
• C → AD

Since AB ∩ CD = ∅ and C ∩ AD = ∅, both are completely non-trivial functional dependencies. Here is the content in the same wording and formatting for Semi Non-Trivial Functional Dependency.

4. Semi Non-Trivial Functional Dependency

A Semi Non-Trivial Functional Dependency exists when some attributes of the RHS (dependent attributes) are present in the LHS (determinant), while the remaining attributes are not. In other words, the RHS is neither a subset of the LHS nor completely disjoint from it. Rule: If X → Y, X ∩ Y ≠ ∅, and Y ⊄ X, then X → Y is called a Semi Non-Trivial Functional Dependency.

Example 1:

Suppose a Relation R(A, B, C) contains the following Functional Dependencies:

• A → AB
• B → BC

Since A ∩ AB = A, B ∩ BC = B, and AB ⊄ A, BC ⊄ B, both are semi-non-trivial functional dependencies.

Example 2:

Suppose the relation R(A, B, C, D, E) contains the following functional dependencies:

• ABC → ABCD
• DE → DEA

Since ABC ∩ ABCD = ABC, DE ∩ DEA = DE, and ABCD ⊄ ABC, DEA ⊄ DE, both are semi-non-trivial functional dependencies.

5. Multivalued Dependency (MVD)

A Multivalued Dependency (MVD) exists when one attribute determines multiple independent values. The attributes on the RHS (dependent set) are not functionally dependent on each other. That is, if A →→ {B, C} and B does not determine C, and C does not determine B, then A →→ {B, C} is called a Multivalued Dependency. It is represented by the symbol ↠.

• Rule: If X ↠ Y, then for each value of X, there can be multiple independent values of Y, regardless of the values of the remaining attributes.

Example 1:

Suppose a Relation R(Student, Course, Hobby) contains the following Multivalued Dependencies:

• Student ↠ Course
• Student ↠ Hobby

Since a student can enroll in multiple courses and also have multiple hobbies independently, both are multivalued dependencies.

Example 2:

Suppose the relation R(Employee, Skill, Language) contains the following Multivalued Dependencies:

• Employee ↠ Skill
• Employee ↠ Language

Since an employee can have multiple skills and know multiple languages independently, both are multivalued dependencies.

6. Transitive Functional Dependency

A Transitive Functional Dependency exists when one attribute determines another attribute through an intermediate attribute. In other words, if X determines Y and Y determines Z, then X transitively determines Z, provided Y is not a candidate key.

• Rule: If X → Y and Y → Z, then X → Z is called a Transitive Functional Dependency.

Example 1:

Suppose a Relation R(A, B, C) contains the following Functional Dependencies:

• A → B
• B → C

Since A → B and B → C, therefore A → C is a transitive functional dependency.

Example 2:

Suppose the relation R(A, B, C, D, E) contains the following functional dependencies:

• AB → C
• C → E

Since AB → C and C → E, therefore AB → E is a transitive functional dependency. Here is the content in the same wording and formatting for Full Functional Dependency.

7. Full Functional Dependency

A Full Functional Dependency exists when an attribute (or set of attributes) is functionally dependent on the entire LHS (determinant) and not on any proper subset of the LHS. Rule: If X → Y, and Y is not functionally dependent on any proper subset of X, then X → Y is called a Full Functional Dependency.

Example 1:

Suppose a Relation R(A, B, C) contains the following Functional Dependency: AB → C Since C is dependent on the entire determinant AB, and neither A → C nor B → C holds, AB → C is a full functional dependency.

Example 2:

Suppose the relation R(A, B, C, D) contains the following Functional Dependency: ABC → D Since D is dependent on the entire determinant ABC, and none of the proper subsets (A, B, C, AB, AC, or BC) determines D, ABC → D is a full functional dependency.

8. Partial Functional Dependency

A Partial Functional Dependency exists when an attribute (or set of attributes) is functionally dependent on a proper subset of the LHS (determinant) instead of the entire LHS. Rule: If X → Y, and Y is functionally dependent on a proper subset of X, then X → Y is called a Partial Functional Dependency.

Example 1:

Suppose a Relation R(A, B, C) contains the following Functional Dependency AB → C then  A → C is a partial functional dependency because C is dependent on the proper subset A of AB. So, AB → C is a partial functional dependency.

Example 2:

Suppose the relation R(A, B, C, D) contains the following Functional Dependencies:

• ABC → D
• AB → D

Since D is dependent on the proper subset AB of ABC, ABC → D is a partial functional dependency.

Quick Comparison of Types of Functional Dependencies

Functional Dependency Type	Rule	LHS–RHS Relationship	Example
Trivial Functional Dependency	Y ⊆ X	RHS is a subset of the LHS.	ABC → AB
Non-Trivial Functional Dependency	Y ⊄ X	RHS is not a subset of the LHS.	A → AB
Completely Non-Trivial Functional Dependency	X ∩ Y = ∅	LHS and RHS have no common attributes (disjoint sets).	AB → CD
Semi Non-Trivial Functional Dependency	X ∩ Y ≠ ∅ and Y ⊄ X	LHS and RHS share some common attributes, but RHS is not a subset of LHS.	AB → BC
Multivalued Dependency (MVD)	X ↠ Y	One value of LHS determines multiple independent values of RHS.	Student ↠ Course
Transitive Functional Dependency	X → Y and Y → Z ⇒ X → Z	RHS depends on LHS indirectly through another attribute.	A → B, B → C ⇒ A → C
Full Functional Dependency	X → Y and no proper subset of X determines Y	RHS depends on the entire LHS.	AB → C
Partial Functional Dependency	A proper subset of X determines Y	RHS depends on only a proper subset of the LHS.	AB → C and A → C

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.