Rules About Functional Dependencies

Rules About Functional Dependencies

Section outline

• Introduction to reasoning about Functional Dependencies (FDs) by deducing additional FDs from a given set.
• Definition of equivalent sets of FDs and when one set of FDs follows from another.

#1

read: Section 3.2: Rules About Functional Dependencies (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- Introduction to reasoning about Functional Dependencies (FDs) by deducing additional FDs from a given set.
- Definition of equivalent sets of FDs and when one set of FDs follows from another.

Tip

Suppose \(R(A, B, \dots)\in\textbf{Relation}\) is a relation instance, and \(F = X\to Y\in\mathbf{FD}\) is a functional dependency. We will write: \[ R \models_\mathrm{sat} S \] if \(R\) satisfies \(F\).

More generally, if \(S\) is a set of FD, we can write: \[ R \models_\mathrm{sat}S \] if \(R\) satisfies all \(F\in S\).

• Given a set of functional dependencies (FDs) that a relation is known to satisfy, we can often reason that the relation must satisfy certain other FDs. This process of discovering additional FDs is essential for database schema design.

  For instance, if a relation \(R(A, B, C) \models_\mathrm{sat} \{A \rightarrow B, B \rightarrow C\}\), we can deduce that \(R \models_\mathrm{sat} A \rightarrow C\). To prove this, one must consider any two tuples in \(R\) that agree on attribute \(A\) and show they must also agree on attribute \(C\).

Note

Definition: Equivalent Sets of FDs

Two sets of FDs, \(S\) and \(T\), are equivalent if the set of relation instances satisfying all FDs in \(S\) is exactly the same as the set of relation instances satisfying all FDs in \(T\).

\[ \forall R\in\mathbf{Relation},\ R\models_\mathrm{sat} S \iff R\models_\mathrm{sat} T \]

In this case, we write:

\[ S \iff T \]

Note

Definition: Follows From

A set of FDs \(S\) follows from a set of FDs \(T\) if every relation instance that satisfies all the FDs in \(T\) also satisfies all the FDs in \(S\). Namely,

\[ \forall R\in\mathbf{Relation},\ R\models_\mathrm{sat} T \implies R\models_\mathrm{sat} S \]

This means that \(T\) is a stronger set of constraints than \(S\).

We can write:

\[ T \implies S \]

• The concepts of equivalence and following from are directly related.

  Two sets of FDs, \(S\) and \(T\), are equivalent if and only if \(S\) follows from \(T\), and \(T\) follows from \(S\).

  This can be stated as:

  Claim:

  If \(T\implies S\) and \(S\implies T\), then \(S \iff T\).

gemini-2.5-pro

• Version: 1
• Model: gemini-2.5-pro
• Created: 2025-09-03 20:47:05
• Duration: 16.588371992111206
• Cummulative cost: $1.97e-02

The Splitting/Combining Rule

Section outline

• Describes the rule that an FD with multiple attributes on the right side, such as \(A_1 A_2 \cdots A_n \rightarrow B_1 B_2 \cdots B_m\), is equivalent to a set of FDs with single attributes on the right side: \(A_1 A_2 \cdots A_n \rightarrow B_i\) for each \(i\).
• The splitting rule breaks a multi-attribute right side into individual FDs.
• The combining rule merges multiple FDs with the same left side into a single FD.
• Clarifies that splitting cannot be applied to the left sides of FDs.

#3

read: Section 3.2.2: The Splitting/Combining Rule (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- Describes the rule that an FD with multiple attributes on the right side, such as $A_1 A_2 \cdots A_n \rightarrow B_1 B_2 \cdots B_m$, is equivalent to a set of FDs with single attributes on the right side: $A_1 A_2 \cdots A_n \rightarrow B_i$ for each $i$.
- The splitting rule breaks a multi-attribute right side into individual FDs.
- The combining rule merges multiple FDs with the same left side into a single FD.
- Clarifies that splitting cannot be applied to the left sides of FDs.

Definition: The Splitting/Combining Rule

A functional dependency of the form \(A_1 A_2 \cdots A_n \rightarrow B_1 B_2 \cdots B_m\) holds if and only if the set of functional dependencies \(\{ A_1 A_2 \cdots A_n \rightarrow B_i \mid i = 1, 2, \ldots, m \}\) holds.

• The Splitting Rule

  This rule states that a functional dependency with multiple attributes on its right side may be replaced by an equivalent set of functional dependencies, each having a single attribute on its right side. Specifically, \(X \rightarrow YZ\) can be replaced by the set \(\{X \rightarrow Y, X \rightarrow Z\}\).

• The Combining Rule

  Conversely, a set of functional dependencies with the same left side can be replaced by a single functional dependency whose right side is the union of the original right sides. For example, the set \(\{X \rightarrow Y, X \rightarrow Z\}\) can be replaced by the single functional dependency \(X \rightarrow YZ\).

  \[ \{X\to YZ\} \iff \{X\to Y, X\to Z\} \tag{Split and combine} \]

• Limitation on Left-Side Splitting

  This principle of splitting and combining applies only to the attributes on the right side (the determined attributes) of a functional dependency. A similar rule does not exist for the left side. The functional dependency \(XY \rightarrow Z\) does not imply that either \(X \rightarrow Z\) or \(Y \rightarrow Z\) must hold.

  \[ \{XY\to Z\} \not\Leftrightarrow \{X\to Z, Y\to Z\} \tag{Don't make this mistake} \]

gemini-2.5-pro

• Version: 1
• Model: gemini-2.5-pro
• Created: 2025-09-03 20:47:41
• Duration: 15.835576057434082
• Cummulative cost: $1.69e-02

Trivial Functional Dependencies

Section outline

• Defines a trivial FD as one where the right side is a subset of its left side, i.e., for \(A_1 A_2 \cdots A_n \rightarrow B_1 B_2 \cdots B_m\), it holds that \(\{B_1, B_2, \dots, B_m\} \subseteq \{A_1, A_2, \dots, A_n\}\).
• Introduces the trivial-dependency rule, which simplifies an FD by removing attributes from the right side that also appear on the left.

#4

read: Section 3.2.3: Trivial Functional Dependencies (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- Defines a trivial FD as one where the right side is a subset of its left side, i.e., for $A_1 A_2 \cdots A_n \rightarrow B_1 B_2 \cdots B_m$, it holds that $\{B_1, B_2, \dots, B_m\} \subseteq \{A_1, A_2, \dots, A_n\}$.
- Introduces the trivial-dependency rule, which simplifies an FD by removing attributes from the right side that also appear on the left.

Definition: Trivial Functional Dependency

An FD of the form \(A_1 A_2 \cdots A_n \rightarrow B_1 B_2 \cdots B_m\) is said to be trivial if the set of attributes on the right-hand side is a subset of the set of attributes on the left-hand side. Formally, this condition is: \[ \{B_1, B_2, \dots, B_m\} \subseteq \{A_1, A_2, \dots, A_n\} \]

• Nature of Trivial FDs

A trivial FD is a constraint that holds for every possible instance of a relation, irrespective of any other constraints. Such a dependency follows directly from the definition of a functional dependency. If two tuples agree on a set of attributes, they must necessarily agree on any subset thereof. For example, title year \(\rightarrow\) title is a trivial FD.

• The Trivial-Dependency Rule

We can delete attributes on the right that appears in the left because:

For example: \[ ABC\to BCDE \iff ABC \to DE \] This can be generally stated as: \[ X\to Y \iff X\to (Y-X) \]

gemini-2.5-pro

• Version: 1
• Model: gemini-2.5-pro
• Created: 2025-09-03 20:50:45
• Duration: 16.379074096679688
• Cummulative cost: $1.84e-02

Computing the Closure of Attributes

Section outline

• Defines the closure of a set of attributes \(\{A_1, A_2, \dots, A_n\}^+\) as the set of attributes \(B\) such that the FD \(A_1 A_2 \cdots A_n \rightarrow B\) follows from the given set of FDs.
• Presents Algorithm 3.7 for computing the closure of a set of attributes.
• Explains how to use the closure to test if a given FD follows from a set of FDs.

#5

read: Section 3.2.4: Computing the Closure of Attributes (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- Defines the closure of a set of attributes $\{A_1, A_2, \dots, A_n\}^+$ as the set of attributes $B$ such that the FD $A_1 A_2 \cdots A_n \rightarrow B$ follows from the given set of FDs.
- Presents Algorithm 3.7 for computing the closure of a set of attributes.
- Explains how to use the closure to test if a given FD follows from a set of FDs.

Computing the Closure of Attributes

• The closure of a set of attributes is a fundamental concept for reasoning about functional dependencies. It consists of all attributes that are functionally determined by a given set of attributes.

  Definition: Closure of a Set of Attributes

  Let \(S\) be a set of functional dependencies (FDs) over a set of attributes \(U\). For any subset of attributes \(X \subseteq U\), the closure of \(X\) under \(S\), denoted \(X^+\), is the set of all attributes \(A\) such that the functional dependency \(X \rightarrow A\) is logically implied by the FDs in \(S\).

  Formally: \[ X^+ = \{ A \in U \mid S \implies (X \rightarrow A) \} \]

• We may compute the closure of a set of attributes \(X\) by starting with the attributes in \(X\) and repeatedly adding attributes that are functionally determined by attributes already collected. This iterative procedure is formalized in Algorithm 3.7.

Algorithm 3.7: Closure of a Set of Attributes

INPUT: A set of attributes \(X\) and a set of FDs \(S\).
OUTPUT: The closure \(X^+\).

result := \(X\)

Loop:

For each \((Y\to Z) \in S\):

If \(Y\subseteq\)result:

\(\text{result} := \text{result} \cup Z\)

End if

End for

If no change to result:

Exit

End

return result

• The closure algorithm provides a direct test for whether a given FD follows from a set of FDs.

  An FD \(X \rightarrow Y\) is logically implied by a set of FDs \(S\) if and only if \(Y \subseteq X^+\), where \(X^+\) is computed with respect to \(S\).

  To test if \(X \rightarrow Y\) follows from \(S\):

  1. Compute \(X^+\) using the closure algorithm with the set of FDs \(S\).
  2. Check if every attribute in \(Y\) is also in \(X^+\). If this condition holds, the dependency follows. Otherwise, it does not.

gemini-2.5-pro

• Version: 1
• Model: gemini-2.5-pro
• Created: 2025-09-03 20:51:11
• Duration: 26.370187997817993
• Cummulative cost: $3.00e-02

The Transitive Rule

Section outline

• Generalizes the observation from Example 3.4 into the transitive rule: If \(A_1 \cdots A_n \rightarrow B_1 \cdots B_m\) and \(B_1 \cdots B_m \rightarrow C_1 \cdots C_k\) hold, then \(A_1 \cdots A_n \rightarrow C_1 \cdots C_k\) also holds.
• Demonstrates the validity of the rule using the attribute closure test.

#7

read: Section 3.2.6: The Transitive Rule (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- Generalizes the observation from Example 3.4 into the transitive rule: If $A_1 \cdots A_n \rightarrow B_1 \cdots B_m$ and $B_1 \cdots B_m \rightarrow C_1 \cdots C_k$ hold, then $A_1 \cdots A_n \rightarrow C_1 \cdots C_k$ also holds.
- Demonstrates the validity of the rule using the attribute closure test.

Let’s is demonstrate how the closure set can be used to prove some result:

Claim:

If a relation \(R\) satisfies the functional dependencies (FDs) \(A_1 A_2 \cdots A_n \rightarrow B_1 B_2 \cdots B_m\) and \(B_1 B_2 \cdots B_m \rightarrow C_1 C_2 \cdots C_k\), then \(R\) must also satisfy the FD \(A_1 A_2 \cdots A_n \rightarrow C_1 C_2 \cdots C_k\).

Proof:

The validity of the transitive rule is demonstrated by applying the attribute closure test.

To test if the FD \(A_1 \cdots A_n \rightarrow C_1 \cdots C_k\) holds, we compute the closure \(\{A_1, \ldots, A_n\}^+\) using the two given FDs.

The first FD, \(A_1 \cdots A_n \rightarrow B_1 \cdots B_m\), implies that all attributes \(B_1, \ldots, B_m\) are in the closure \(\{A_1, \ldots, A_n\}^+\).

Since the closure now contains all attributes from the set \(\{B_1, \ldots, B_m\}\), we can use the second FD, \(B_1 \cdots B_m \rightarrow C_1 \cdots C_k\), to add the attributes \(C_1, \ldots, C_k\) to the closure.

As all attributes \(C_1, \ldots, C_k\) are now in \(\{A_1, \ldots, A_n\}^+\), we conclude that the FD \(A_1 \cdots A_n \rightarrow C_1 \cdots C_k\) holds for any relation that satisfies the initial two FDs.

gemini-2.5-pro

• Version: 1
• Model: gemini-2.5-pro
• Created: 2025-09-03 20:52:07
• Duration: 23.02730083465576
• Cummulative cost: $2.63e-02

Closing Sets of Functional Dependencies

Section outline

• Introduces the concept of a basis, which is any set of FDs equivalent to a given set S.
• Defines a minimal basis as a basis B that satisfies three conditions: all FDs in B have singleton right sides, no FD in B can be removed, and no attribute can be removed from the left side of any FD in B.

#8

read: Section 3.2.7: Closing Sets of Functional Dependencies (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- Introduces the concept of a basis, which is any set of FDs equivalent to a given set S.
- Defines a minimal basis as a basis B that satisfies three conditions: all FDs in B have singleton right sides, no FD in B can be removed, and no attribute can be removed from the left side of any FD in B.

• Basis for a Set of Functional Dependencies

  Given a set of FDs \(S\) that hold for a relation, there may be many other sets of FDs that logically imply the same set of constraints. Any such equivalent set is called a basis.

Definition: Basis

Let \(S\) be a set of functional dependencies. A basis is another set of FD, \(B\) such that \[ B \iff S \] and each FD in \(B\) only has one attribute on the right hand side.

• Minimal Basis

  To avoid an explosion of possible bases, it is useful to define a canonical, or minimal, form for a basis. This form ensures that each FD is as simple as possible and that the set itself contains no redundant information.

Definition: Minimal Basis

A basis \(B\) for a set of FDs is a minimal basis if it satisfies the following three conditions:

1. Singleton Right Sides: Every functional dependency in \(B\) has exactly one attribute on its right side.
2. No Redundant FDs: If any FD is removed from \(B\), the resulting set of FDs is no longer a basis.
3. No Extraneous Attributes in Left Sides: For any FD in \(B\), if one or more attributes are removed from the left side of that FD, the resulting set of FDs is no longer a basis.

Minimal basis of \(S\) can be computed.

gemini-2.5-pro

• Version: 1
• Model: gemini-2.5-pro
• Created: 2025-09-03 20:52:25
• Duration: 17.790035009384155
• Cummulative cost: $1.85e-02

Projecting Functional Dependencies

Section outline

• Addresses the problem of finding the set of FDs that hold in a relation resulting from a projection operation.
• Presents Algorithm 3.12 for calculating the projection of a set of functional dependencies.

#9

read: Section 3.2.8: Projecting Functional Dependencies (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- Addresses the problem of finding the set of FDs that hold in a relation resulting from a projection operation.
- Presents Algorithm 3.12 for calculating the projection of a set of functional dependencies.

When designing relation schemas, one must often consider projections of a relation. Suppose we are given a relation \(R\) with a set of functional dependencies \(S\), and we compute a new relation \(R_1\) by projecting \(R\) onto a subset of its attributes, \(L\). The question then arises: what set of functional dependencies holds for this new relation \(R_1\)?

Definition: Projection of Functional Dependencies

Let \(R\) be a relation schema, \(S\) be a set of functional dependencies on \(R\), and \(L\) be a subset of the attributes of \(R\). The projection of \(S\) onto \(L\), denoted \(\pi_L(S)\), is the set of all functional dependencies \(X \to Y\) such that:

1. \(X \to Y\) is implied by the FDs in \(S\).
2. The attributes in \(X\) and \(Y\) are all contained in \(L\).

A direct computation of all such FDs is often intractable. We present an algorithm to compute a basis for the FDs that hold in the projected relation.

• Algorithm 3.12: Projecting a Set of Functional Dependencies

  This algorithm computes the set of functional dependencies that hold in a projected relation \(R_1 = \pi_L(R)\).

  1. Initialize an empty set, \(T\), which will hold the FDs for \(R_1\).

  2. For each subset of attributes \(X \subseteq L\), compute its closure \(X^+\) using the original set of FDs, \(S\). This closure may include attributes not in \(L\).

  3. For each attribute \(A\) such that \(A \in X^+\) and \(A \in L\), add the nontrivial functional dependency \(X \to A\) to the set \(T\).

  4. The set \(T\) is now a basis for the FDs of \(R_1\). This basis may be reduced to a minimal basis by systematically removing redundant dependencies and redundant attributes from the left-hand sides of dependencies.

     • Remove any FD \(F \in T\) that is implied by the other FDs in \(T\).
     • For each FD \(Y \to B \in T\), if an attribute can be removed from \(Y\) to form a smaller set \(Z\) such that \(Z \to B\) is still implied by \(T\), replace \(Y \to B\) with \(Z \to B\).
     • Repeat until no further reductions are possible.

gemini-2.5-pro

• Version: 1
• Model: gemini-2.5-pro
• Created: 2025-09-03 20:52:38
• Duration: 12.947170734405518
• Cummulative cost: $1.58e-02