Introduction

Functional Dependencies (FDs) are essential in relational database schema design, ensuring data consistency and normalization. An FD represents a constraint between two attribute sets in a table. If an attribute set X determines another set Y, it is written as X → Y.

This post explains Functional Dependencies using five examples with tables. Each table demonstrates specific dependencies and whether they hold or not.

Example 1

Table:

Functional Dependency Analysis:

• A → B: Does not hold because for \( A = 1 \), \( B \) has two values (1 and 2).
• B → A: Holds because:
  • \( B = 1 \) implies \( A = 1 \)
  • \( B = 2 \) implies \( A = 2 \)

Example 2

Table:

Functional Dependency Analysis:

• A → C: Holds. When \( A = 1 \), \( C = 4 \); when \( A = 2 \), \( C = 3 \).
• C → A: Holds. \( C = 4 \implies A = 1 \), and \( C = 3 \implies A = 2 \).

Example 3

Table:

Functional Dependency Analysis:

• A → B: Holds. \( A = 1 \implies B = 1 \) and \( A = 2 \implies B = 3 \).
• B → C: Does not hold. \( B = 1 \) maps to multiple values of \( C \) (1 and 0).

Example 4

Table:

Functional Dependency Analysis:

• XY → Z: Holds. Each combination of \( X \) and \( Y \) determines \( Z \).
• Y → Z: Holds. For \( Y = 4 \) and \( Y = 5 \), \( Z = 3 \).

Example 5

Table:

Functional Dependency Analysis:

• B → C: Holds. For \( B = 2 \), \( C = 3 \); for \( B = 3 \), \( C = 3 \).
• C → B: Does not hold. \( C = 3 \) maps to multiple \( B \) values (2 and 3).

Summary

Functional dependencies help us understand attribute relationships in a database table. By analyzing tables with Armstrong’s rules, we determine which dependencies hold and simplify schema design. These examples illustrate the importance of FDs in normalization, integrity, and query optimization.

1. What is Closure of Attributes?

The Closure of Attributes is the set of all attributes that can be functionally determined by a given set of attributes, based on a set of functional dependencies (FDs).

It is denoted as X⁺, where X is the attribute set.

Steps to Find Closure:

1. Start with the given attribute set X.
2. Iteratively add attributes to the closure that can be functionally determined from FDs.
3. Repeat until no more attributes can be added.

Example:

Given FDs: A → B, B → C, and the set X = {A}.

• Start with X = {A}.
• From A → B, add B to the closure: {A, B}.
• From B → C, add C: {A, B, C}.
• Final closure: A⁺ = {A, B, C}.

2. Keys in DBMS

2.1 Super Key

A Super Key is a set of attributes that uniquely identifies each tuple (row) in a relation.

Example: In a relation (A, B, C) with FDs A → B, C, the set {A} is a super key.

2.2 Candidate Key

A Candidate Key is a minimal super key. It uniquely identifies tuples, but no attribute can be removed from it without losing its uniqueness property.

Example: In (A, B, C), if A → B, C, then {A} is a candidate key.

2.3 Prime Key

A Prime Key is any attribute that is part of a candidate key.

Example: If {A, B} is a candidate key, then A and B are prime attributes.

2.4 Primary Key

A Primary Key is a chosen candidate key that uniquely identifies each tuple in a relation.

3. Checking Additional Functional Dependencies

To check if a new functional dependency (FD) \( X → Y \) holds:

Algorithm to Check Additional FDs:

1. Compute the closure of \( X \) using the given set of FDs.
2. If \( Y \) is a subset of \( X⁺ \), then \( X → Y \) holds; otherwise, it does not hold.

Example:

Given FDs: A → B, B → C. Check if A → C.

• Find \( A⁺ \): Start with \( A \), add \( B \) (from \( A → B \)), then add \( C \) (from \( B → C \)).
• \( A⁺ = {A, B, C} \).
• Since \( C \subseteq A⁺ \), \( A → C \) holds.

4. Equivalence of Functional Dependencies

Two sets of FDs \( F \) and \( G \) are equivalent if they generate the same closure for all attribute sets.

Algorithm for Equivalence:

1. For each FD in \( F \), check if it can be derived from \( G \).
2. For each FD in \( G \), check if it can be derived from \( F \).
3. If both conditions hold, \( F \) and \( G \) are equivalent.

5. Minimization of Functional Dependencies

The goal is to reduce a set of FDs to a minimal cover while preserving equivalence.

Steps to Minimize FDs:

1. Split FDs so that each FD has a single attribute on the right-hand side.
2. Remove redundant attributes from the left-hand side.
3. Eliminate redundant FDs by checking if they can be derived from others.

Example:

Given FDs: A → BC, B → C.

• Split: A → B, A → C, B → C.
• Check redundancy: \( A → C \) is already implied by \( A → B \) and \( B → C \).
• Minimal cover: A → B, B → C.

Conclusion

Understanding closure of attributes, keys, and functional dependencies is crucial for database design. Algorithms for checking additional FDs, FD equivalence, and FD minimization help ensure efficient and normalized schemas. These concepts form the foundation of relational database theory and normalization processes.

1. What is Decomposition in DBMS?

Decomposition in DBMS is the process of dividing a large table (relation) into smaller tables to eliminate redundancy, anomalies, and ensure normalization. Decomposition must maintain two properties:

• Lossless Join Property: Ensures no data is lost when smaller tables are joined.
• Dependency Preservation: Ensures functional dependencies are not lost.

2. Lossless vs Lossy Decomposition

Lossless Decomposition

A decomposition is lossless if the original relation can be reconstructed without any loss of data by performing a natural join on the smaller tables.

Lossy Decomposition

A decomposition is lossy if some data is lost when the smaller tables are joined back together.

Example of Lossless and Lossy Decomposition

Original Table: R(A, B, C)

Lossless Decomposition:

Decompose R(A, B, C) into R1(A, B) and R2(B, C).

Natural Join: R1 ⋈ R2 gives back the original relation R(A, B, C). Hence, the decomposition is lossless.

Lossy Decomposition:

Decompose R(A, B, C) into R1(A, B) and R2(A, C).

Performing a natural join does not reconstruct the original table accurately. Hence, this decomposition is lossy.

3. What is Function-Preserving Decomposition?

A decomposition is function-preserving if all functional dependencies (FDs) in the original table are preserved in the smaller tables.

Example:

Original FDs: A → B and B → C.

Decompose R(A, B, C) into R1(A, B) and R2(B, C). Both FDs are preserved:

• A → B in R1.
• B → C in R2.

Hence, the decomposition is function-preserving.

4. Examples of Lossless, Lossy, and Function-Preserving Decomposition

Example 1: Lossless Decomposition

Given Relation: R(A, B, C) with FD A → B.

• Decompose into R1(A, B) and R2(A, C).
• Join R1 and R2 using A: Lossless.

Example 2: Lossy Decomposition

Given Relation: R(A, B, C) without any functional dependencies.

• Decompose into R1(A, B) and R2(B, C).
• Natural join loses information: Lossy.

Example 3: Function-Preserving Decomposition

Given Relation: R(A, B, C) with FDs A → B and B → C.

• Decompose into R1(A, B) and R2(B, C).
• All FDs are preserved.

5. Conclusion

Lossless decomposition ensures no data is lost during the join operation, while function-preserving decomposition ensures all functional dependencies are retained. Lossy decompositions should