Proofs¶
1. Lemma: Equivalence of Closure and Armstrong's Axioms¶
Lemma:
Let \(R\) be a schema and \(F\) a set of functional dependencies on \(R\). It holds that:
where \(X^{+}_{F^A} = \{A \in R \mid X \rightarrow A \in F^{A}\}\) is the closure of \(X\) with respect to \(F^A\).
Proof¶
(\(\Rightarrow\)) Direction:
-
Since \(X \rightarrow Y \in F^{A}\), by the Decomposition Rule, we obtain \(X \rightarrow A \in F^{A}\) for all \(A \in Y\).
-
By the definition of \(X^{+}_{F^A}\) (the closure of attributes), if \(X \rightarrow A \in F^{A}\), then \(A \in X^{+}_{F^A}\).
-
Since this holds for all \(A \in Y\), it implies \(Y \subseteq X^{+}_{F^A}\).
(\(\Leftarrow\)) Direction:
-
Since \(Y \subseteq X^{+}_{F^A}\), it holds that \(X \rightarrow A \in F^{A}\) for all \(A \in Y\).
-
By the Union Rule, this implies that \(X \rightarrow Y \in F^{A}\).
2. Theorem: Soundness and Completeness of Armstrong's Axioms¶
Theorem:
For every schema \(R\) and a set \(F\) of functional dependencies, it holds that:
Proof¶
By double inclusion.
Part 1: Soundness (\(F^{A} \subseteq F^{+}\))
Let \(X \rightarrow Y \in F^{A}\). We prove that \(X \rightarrow Y \in F^{+}\) by induction on the number \(n\) of applications of Armstrong's Axioms.
-
Base Case (\(n=0\)):
If the dependency is in \(F\), then clearly \(F \subseteq F^{+}\).
-
Induction Step:
Induction Hypothesis: Assume that for all dependencies derivable with at most \(n\) applications of Armstrong's Axioms, if \(V \rightarrow W \in F^{A}\) is derivable in \(n\) steps, then \(V \rightarrow W \in F^{+}\).
To Prove: Any dependency \(X \rightarrow Y \in F^{A}\) derivable in \(n+1\) steps is also in \(F^{+}\).
We distinguish three cases based on which axiom was used in the \((n+1)\)-th step.
-
Reflexivity:
If \(X \rightarrow Y\) is obtained by reflexivity, then \(Y \subseteq X\). For any legal instance \(r\) and for any tuples \(t_1, t_2 \in r\), if \(t_1[X] = t_2[X]\), then clearly \(t_1[Y] = t_2[Y]\) because \(Y \subseteq X\). Therefore, \(X \rightarrow Y \in F^{+}\).
-
Augmentation:
Suppose \(X \rightarrow Y \in F^{A}\) is obtained by augmentation from \(V \rightarrow W \in F^{A}\). Then \(X = Z \cup V\) and \(Y = Z \cup W\) for some set \(Z \subseteq R\). By the induction hypothesis, \(V \rightarrow W \in F^{+}\).
Let \(r\) be an arbitrary legal instance, and let \(t_1, t_2 \in r\) be any two tuples with \(t_1[X] = t_2[X]\). Since \(X = Z \cup V\), we have \(t_1[Z] = t_2[Z]\) and \(t_1[V] = t_2[V]\). Since \(V \rightarrow W \in F^{+}\) and \(t_1[V] = t_2[V]\), it follows that \(t_1[W] = t_2[W]\). Combined with \(t_1[Z] = t_2[Z]\), this gives \(t_1[Z \cup W] = t_2[Z \cup W]\), which means \(t_1[Y] = t_2[Y]\) since \(Y = Z \cup W\). Therefore, \(X \rightarrow Y \in F^{+}\).
-
Transitivity:
Suppose \(X \rightarrow Y \in F^{A}\) is derived by transitivity from \(X \rightarrow Z \in F^{A}\) and \(Z \rightarrow Y \in F^{A}\) for some set \(Z \subseteq R\). By the induction hypothesis, \(X \rightarrow Z \in F^{+}\) and \(Z \rightarrow Y \in F^{+}\).
Let \(r\) be an arbitrary legal instance, and let \(t_1, t_2 \in r\) be any two tuples with \(t_1[X] = t_2[X]\). Since \(X \rightarrow Z \in F^{+}\) and \(t_1[X] = t_2[X]\), it follows that \(t_1[Z] = t_2[Z]\). Now, since \(Z \rightarrow Y \in F^{+}\) and \(t_1[Z] = t_2[Z]\), we obtain \(t_1[Y] = t_2[Y]\). Therefore, \(X \rightarrow Y \in F^{+}\).
-
Part 2: Completeness (\(F^{+} \subseteq F^{A}\))
We prove the contrapositive: if \(X \rightarrow Y \notin F^{A}\), then \(X \rightarrow Y \notin F^{+}\).
Construct a specific instance \(r\) of \(R\) with two tuples \(t_1\) and \(t_2\) defined as follows:
| Tuple | Attributes in \(X^{+}_{F^A}\) | Attributes in \(R - X^{+}_{F^A}\) |
|---|---|---|
| \(t_1\) | \(1\) | \(1\) |
| \(t_2\) | \(1\) | \(0\) |
Formally:
- \(t_1[A] = 1\) for all \(A \in R\) (i.e., \(\forall A \in R : t_1[A] = 1\)).
- \(t_2[A] = \begin{cases} 1 & \text{if } A \in X^{+}_{F^A} \\\\ 0 & \text{if } A \in R - X^{+}_{F^A} \end{cases}\)
We show that \(r\) is a legal instance (i.e., it satisfies all dependencies in \(F\)) by contradiction.
Suppose \(r\) is not legal. Then there exists a functional dependency \(V \rightarrow W \in F\) that is violated, meaning there exist tuples in \(r\) with equal values on \(V\) but different values on \(W\). Since \(r\) contains only two tuples \(t_1\) and \(t_2\), we must have \(t_1[V] = t_2[V]\) but \(t_1[W] \neq t_2[W]\).
Since \(t_1[V] = t_2[V]\) and \(t_1\) has all \(1\)'s, it follows that \(t_2[V]\) also has all \(1\)'s. By our construction of \(t_2\), this means every attribute in \(V\) belongs to \(X^{+}_{F^A}\), i.e., \(V \subseteq X^{+}_{F^A}\).
By Lemma 1, \(V \subseteq X^{+}_{F^A}\) implies \(X \rightarrow V \in F^{A}\). Since \(V \rightarrow W \in F \subseteq F^{A}\), we can apply transitivity:
By Lemma 1 again, this implies \(W \subseteq X^{+}_{F^A}\). Therefore, by our construction of \(t_2\), we have \(t_2[W]\) consists entirely of \(1\)'s, so \(t_1[W] = t_2[W]\), contradicting our assumption that \(t_1[W] \neq t_2[W]\).
Therefore, \(r\) is legal.
Now suppose, for the sake of contradiction, that \(X \rightarrow Y \notin F^{A}\) but \(X \rightarrow Y \in F^{+}\). Since \(r\) is a legal instance and \(X \rightarrow Y \in F^{+}\), the instance must satisfy this dependency.
By construction, \(X \subseteq X^{+}_{F^A}\), so \(t_1[X] = t_2[X]\). Since \(X \rightarrow Y\) is satisfied, this implies \(t_1[Y] = t_2[Y]\).
Since \(t_1\) has all \(1\)s, we have \(t_1[Y]\) is all \(1\)s, so \(t_2[Y]\) must also be all \(1\)s. By our construction of \(t_2\), this means every attribute in \(Y\) must be in \(X^{+}_{F^A}\), i.e., \(Y \subseteq X^{+}_{F^A}\).
By Lemma 1, \(Y \subseteq X^{+}_{F^A}\) implies \(\boxed{\color{red}{X \rightarrow Y \in F^{A}}}\), contradicting our assumption that \(X \rightarrow Y \notin F^{A}\).
Therefore, if \(X \rightarrow Y \notin F^{A}\), then \(X \rightarrow Y \notin F^{+}\), in other words, if \(X \rightarrow Y \in F^{+}\), then \(X \rightarrow Y \in F^{A}\), hence \(\boxed{F^{+} \subseteq F^{A}}\).
Proof structure clarification:
We prove the contrapositive: \(X \rightarrow Y \notin F^{A} \implies X \rightarrow Y \notin F^{+}\).
Setting up the contradiction: Assume for contradiction that \(X \rightarrow Y \notin F^{A}\) but \(X \rightarrow Y \in F^{+}\). Recall that \(X \rightarrow Y \in F^{+}\) means the dependency is satisfied by every legal instance of \(R\). We construct a specific legal instance \(r\) that will force a contradiction.
Key insight: Although we must prove the statement for all legal instances (since \(F^{+}\) is defined semantically over all legal instances), we only need to construct one specific legal instance to derive the contradiction. This instance is carefully designed to expose the inconsistency between our two assumptions.
The instance \(r\) forces the contradiction: Since \(r\) is legal and \(X \rightarrow Y \in F^{+}\) (which holds in every legal instance by definition), the dependency must be satisfied in \(r\). Specifically, for the two tuples \(t_1, t_2 \in r\), we have \(t_1[X] = t_2[X]\) (by construction, since \(X \subseteq X^{+}_{F^A}\)), which forces \(t_1[Y] = t_2[Y]\).
Deriving the contradiction: Since \(t_1\) consists entirely of \(1\)'s and \(t_1[Y] = t_2[Y]\), we conclude \(t_2[Y]\) must also consist entirely of \(1\)'s. By the construction of \(t_2\), this is only possible if every attribute in \(Y\) belongs to \(X^{+}_{F^A}\), i.e., \(Y \subseteq X^{+}_{F^A}\).
By Lemma 1, \(Y \subseteq X^{+}_{F^A}\) implies \(X \rightarrow Y \in F^{A}\), which directly contradicts our assumption that \(X \rightarrow Y \notin F^{A}\).
Conclusion: The contradiction shows that our assumptions cannot both be true. Therefore, if \(X \rightarrow Y \notin F^{A}\), then necessarily \(X \rightarrow Y \notin F^{+}\). Taking the contrapositive: if \(X \rightarrow Y \in F^{+}\), then \(X \rightarrow Y \in F^{A}\).
3. Algorithm: Closure of X¶
Algorithm Closure(X)¶
Input:
- Relation \(R\).
- Functional Dependencies \(F\).
- Subset \(X \subseteq R\).
Output:
- \(X^{+}\).
Procedure:
- \(Z := X\)
- \(S := \{A \in R \mid \exists (Y \rightarrow V) \in F : (A \in V \land Y \subseteq Z)\}\)
- while \(S \not\subseteq Z\) do
- \(Z := Z \cup S\)
- \(S := \{A \in R \mid \exists (Y \rightarrow V) \in F : (A \in V \land Y \subseteq Z)\}\)
- end while
- return \(Z\)
Complexity¶
Let \(n = |R|\) and \(m = |F|\).
At each iteration we compute \(S = \{A \in R \mid \exists (Y \rightarrow V) \in F : (A \in V \land Y \subseteq Z)\}\) by scanning all dependencies in \(F\) and checking whether \(Y \subseteq Z\), then (if so) adding the attributes in \(V\). This takes \(O(m \cdot n)\) time per iteration.
Each iteration strictly increases \(Z\) until it reaches a fixed point, so there can be at most \(n\) iterations. Therefore the overall running time is \(O(m \cdot n^2)\), i.e., polynomial in the input size.
Theorem¶
The algorithm correctly computes \(X^{+}\).
Proof¶
Termination:
Denote the sequence of sets as \(Z_0, \dots, Z_i, \dots\) computed at each iteration.
Observe that \(Z_i \subseteq Z_{i+1}\) for all \(i\). Thus, \(Z_i\) is a monotonic sequence bounded by \(R\). There exists an index \(f\) such that \(Z_f = Z_{f+1}\), meaning \(S_f \subseteq Z_f\). \(Z_f\) is the output.
Correctness (\(Z_f = X^+\)):
We prove \(Z_f = X^{+}\) by double inclusion.
1. \(Z_f \subseteq X^{+}\)
We proceed by induction on the iteration number \(i\).
-
Base case (\(i=0\)):
\(Z_0 = X \subseteq X^{+}\).
-
Induction step:
Induction Hypothesis: Assume \(Z_i \subseteq X^{+}\).
To Prove: \(Z_{i+1} \subseteq X^{+}\).
Let \(A \in Z_{i+1} = Z_i \cup S_i\). We distinguish two cases:
-
Case 1: If \(A \in Z_i\), then by the induction hypothesis, \(A \in X^{+}\).
-
Case 2: If \(A \in S_i\), then by the definition of \(S_i\), there exists a functional dependency \(Y \rightarrow V \in F\) such that \(Y \subseteq Z_i\) and \(A \in V\).
By the induction hypothesis, \(Y \subseteq Z_i \subseteq X^{+}\). By Lemma 1, this means \(X \rightarrow Y \in F^{A}\).
Since \(Y \rightarrow V \in F \subseteq F^{A}\), we can apply transitivity:
\[ \frac{X \rightarrow Y \in F^{A} \quad Y \rightarrow V \in F \subseteq F^{A}}{X \rightarrow V \in F^{A}} \]By Lemma 1 again, \(V \subseteq X^{+}\). Since \(A \in V\), we have \(A \in X^{+}\).
In both cases, \(A \in X^{+}\). Thus \(Z_{i+1} \subseteq X^{+}\).
-
2. \(X^{+} \subseteq Z_f\)
Let \(A \in X^{+}\). By Lemma 1 (equivalence \(A \in X^{+} \iff X \rightarrow A \in F^{A}\)), this implies \(X \rightarrow A \in F^{A}\). By Theorem 2 (\(F^{A} = F^{+}\)), we have \(X \rightarrow A \in F^{+}\), hence this dependency is satisfied by every legal instance.
Here \(X \rightarrow A\) means the functional dependency with singleton right-hand side, i.e., \(X \rightarrow \{A\}\).
Construct an instance \(r\) of \(R\) with two tuples:
| Tuple | Attributes in \(Z_f\) | Attributes in \(R - Z_f\) |
|---|---|---|
| \(t_1\) | \(1\) | \(1\) |
| \(t_2\) | \(1\) | \(0\) |
Formally:
- \(t_1[B] = 1\) for all \(B \in R\) (i.e., \(\forall B \in R : t_1[B] = 1\)).
- \(t_2[B] = \begin{cases} 1 & \text{if } B \in Z_f \\\\ 0 & \text{if } B \in R - Z_f \end{cases}\)
We show that \(r\) is a legal instance by contradiction.
Suppose \(r\) is not legal. Then there exists a functional dependency \(V \rightarrow W \in F\) that is violated, meaning \(t_1[V] = t_2[V]\) but \(t_1[W] \neq t_2[W]\).
Since \(t_1[V] = t_2[V]\) and \(t_1\) has all \(1\)'s, it follows that \(t_2[V]\) also has all \(1\)'s. By our construction of \(t_2\), this means \(V \subseteq Z_f\).
Let \(B \in W\) be arbitrary. Since \(V \subseteq Z_f\) and \(V \rightarrow W \in F\), by the definition of \(S_f\) we have \(B \in S_f\). Hence \(W \subseteq S_f\). Since \(Z_f\) is terminal (meaning \(S_f \subseteq Z_f\)), we conclude \(W \subseteq Z_f\).
Therefore, by our construction of \(t_2\), we have \(t_2[W]\) consists entirely of \(1\)'s, so \(t_1[W] = t_2[W]\), contradicting our assumption that \(t_1[W] \neq t_2[W]\).
Therefore, \(r\) is legal.
Now, since \(r\) is legal and \(X \rightarrow A \in F^{+}\) (as established above via Lemma 1 and Theorem 2), the instance must satisfy this dependency. Since \(X \subseteq Z_0 \subseteq Z_f\), we have \(t_1[X] = t_2[X]\).
By the definition of satisfaction of a functional dependency, from \(t_1[X] = t_2[X]\) and \(r \models X \rightarrow A\) we obtain \(t_1[A] = t_2[A]\). Since \(t_1[A] = 1\), it follows that \(t_2[A] = 1\). By our construction of \(t_2\), this means \(A \in Z_f\).
Since \(A \in X^{+}\) was arbitrary, this proves \(X^{+} \subseteq Z_f\).
4. Lemma: Closure Inclusion¶
Lemma:
Let \(F\) and \(G\) be two sets of functional dependencies over \(R\). It holds that:
Intuition: If every dependency in \(F\) can be derived from \(G\) (i.e., \(F \subseteq G^{+}\)), then anything we can derive from \(F\) can also be derived from \(G\). This is because derivation is transitive: \(G \implies F \implies F^{+}\) means \(G \implies F^{+}\).
Proof¶
(\(\Rightarrow\)) Direction: \(F \subseteq G^{+} \implies F^{+} \subseteq G^{+}\)
We need to show that every dependency in \(F^{+}\) is also in \(G^{+}\).
Let \(X \rightarrow Y \in F^{+}\) be arbitrary. By Theorem 2, \(X \rightarrow Y \in F^{A}\), meaning it can be derived from \(F\) using Armstrong's Axioms.
We prove by induction on the number \(n\) of axiom applications needed to derive \(X \rightarrow Y\) from \(F\).
Base Case (\(n=0\)):
\(X \rightarrow Y \in F\). By hypothesis, \(F \subseteq G^{+}\), so \(X \rightarrow Y \in G^{+}\).
Induction Step:
Induction Hypothesis: For all dependencies derivable from \(F\) in at most \(n\) steps, they are also in \(G^{+}\).
To Prove: If \(X \rightarrow Y\) is derivable in \(n+1\) steps, then \(X \rightarrow Y \in G^{+}\).
We consider which axiom was used in the \((n+1)\)-th step:
-
Reflexivity: If \(X \rightarrow Y\) is obtained by reflexivity, then \(Y \subseteq X\), so \(X \rightarrow Y \in G^{A} \subseteq G^{+}\) directly.
-
Augmentation: If \(X \rightarrow Y\) is obtained by augmenting \(V \rightarrow W\), then by the induction hypothesis, \(V \rightarrow W \in G^{+}\). Since \(G^{+} = G^{A}\) (by Theorem 2), we can apply augmentation to get \(X \rightarrow Y \in G^{A} \subseteq G^{+}\).
-
Transitivity: If \(X \rightarrow Y\) is obtained from \(X \rightarrow Z\) and \(Z \rightarrow Y\), then by the induction hypothesis, both are in \(G^{+} = G^{A}\). Applying transitivity gives \(X \rightarrow Y \in G^{A} \subseteq G^{+}\).
Therefore, \(F^{+} \subseteq G^{+}\).
(\(\Leftarrow\)) Direction: \(F^{+} \subseteq G^{+} \implies F \subseteq G^{+}\)
Since \(F \subseteq F^{+}\) always holds, and by hypothesis \(F^{+} \subseteq G^{+}\), we have by transitivity of set inclusion:
Therefore, \(F \subseteq G^{+}\).
5. Algorithm: Closure of X in G (Projected Dependencies)¶
Algorithm¶
Input:
- Schema \(R\).
- Functional Dependencies \(F\).
- Decomposition \(S = \{R_1, \dots, R_k\}\).
- Subset \(X \subseteq R\).
Output:
- \(X_{G}^{+}\) where \(G = \bigcup_{i=1}^{k} \pi_{R_i}(F)\).
Procedure:
- \(Z := X\)
- \(S := \bigcup_{i=1}^{k} ((Z \cap R_i)_{F}^{+} \cap R_i)\)
- while \(S \not\subseteq Z\) do
- \(Z := Z \cup S\)
- \(S := \bigcup_{i=1}^{k} ((Z \cap R_i)_{F}^{+} \cap R_i)\)
- end while
- return \(Z\)
Complexity¶
Let \(n = |R|\), \(m = |F|\), and \(k = |\rho|\) (number of relation schemas in the decomposition).
The outer loop can iterate at most \(n\) times, because \(Z\) can gain at most \(n\) new attributes overall.
In one outer iteration, we compute $$ S := \bigcup_{i=1}^{k} \bigl((Z \cap R_i)_{F}^{+} \cap R_i\bigr) $$ which requires computing up to \(k\) attribute-closures of the form \((Z \cap R_i)^+_F\). Each such closure can be computed with the standard closure algorithm in \(O(m \cdot n^2)\) time (as above).
Hence one outer iteration costs \(O(k \cdot m \cdot n^2)\), and the total running time is \(O(k \cdot m \cdot n^3)\).
This is polynomial. The key reason it does not become exponential is that we never enumerate \(F^{+}\) or \(G\) explicitly (both can be exponentially large in \(n\)); we only compute attribute closures, which are polynomial-time.
Theorem¶
The algorithm correctly computes \(X_{G}^{+}\).
Proof¶
Definition (Projection of dependencies). For \(R_j \subseteq R\), the projection of \(F\) onto \(R_j\) is \(\pi_{R_j}(F) = \{\, U \rightarrow V \mid U \cup V \subseteq R_j \land U \rightarrow V \in F^{+} \,\}\).
Let \(Z_0, \dots, Z_f\) be the sequence of iterations, with \(Z_f\) being the outcome. We prove \(Z_f = X_{G}^{+}\) by double inclusion.
Part 1: \(Z_f \subseteq X_{G}^{+}\)¶
We prove \(Z_i \subseteq X_{G}^{+}\) for all \(i \le f\) by induction.
-
Base Case (\(i = 0\)):
\(Z_0 = X \subseteq X_{G}^{+}\) (a set is always contained in its own closure).
-
Induction Step (\(i \to i+1\)):
Induction Hypothesis: Assume \(Z_i \subseteq X_{G}^{+}\).
By Lemma 1 this implies \(X \rightarrow Z_i \in G^{+}\).
To Prove: \(Z_{i+1} \subseteq X_{G}^{+}\).
Let \(A \in Z_{i+1} = Z_i \cup S_i\). We distinguish two cases:
-
Case 1: \(A \in Z_i\).
By the induction hypothesis, \(A \in X_{G}^{+}\). ✓
-
Case 2: \(A \in S_i\).
By the algorithm's definition of \(S_i\), there exists \(j \in \{1, \dots, k\}\) such that \(A \in (Z_i \cap R_j)_{F}^{+} \cap R_j\).
-
From closure membership to FD:
Since \(A \in (Z_i \cap R_j)_{F}^{+}\), by Lemma 1 we have \((Z_i \cap R_j) \rightarrow A \in F^{+}\). -
From \(F^{+}\) to \(G\) via projection:
We also have \(A \in R_j\) and \(Z_i \cap R_j \subseteq R_j\). By the definition of \(\pi_{R_j}(F)\): $$ (Z_i \cap R_j) \rightarrow A \in \pi_{R_j}(F) \subseteq G \subseteq G^{+}. $$ -
Deriving \(X \rightarrow A\) in \(G^{+}\):
By the IH, \(X \rightarrow Z_i \in G^{+}\). Since \(Z_i \cap R_j \subseteq Z_i\), by decomposition \(X \rightarrow (Z_i \cap R_j) \in G^{+}\).
Applying transitivity: $$ \frac{X \rightarrow (Z_i \cap R_j) \in G^{+} \quad (Z_i \cap R_j) \rightarrow A \in G^{+}}{X \rightarrow A \in G^{+}} $$
- Conclusion: \(A \in X_{G}^{+}\). ✓
-
In both cases \(A \in X_{G}^{+}\), so \(Z_{i+1} \subseteq X_{G}^{+}\).
-
Part 2: \(X_{G}^{+} \subseteq Z_f\)¶
Strategy: We show \(X \subseteq Z_f\) and \(Z_f = (Z_f)_{G}^{+}\). Then by monotonicity of closure: $$ X \subseteq Z_f \implies X_{G}^{+} \subseteq (Z_f)_{G}^{+} = Z_f. $$
Step 2.1: \(X \subseteq Z_f\)¶
Immediate from \(Z_0 = X\) and \(Z_i \subseteq Z_{i+1}\) for all \(i\).
Step 2.2: \(Z_f = (Z_f)_{G}^{+}\) (i.e., \(Z_f\) is closed under \(G\))¶
We prove this by double inclusion.
-
(\(\subseteq\)) \(Z_f \subseteq (Z_f)_{G}^{+}\):
For any \(A \in Z_f\), by reflexivity \(Z_f \rightarrow A \in G^{+}\), hence \(A \in (Z_f)_{G}^{+}\) by Lemma 1. ✓
-
(\(\supseteq\)) \((Z_f)_{G}^{+} \subseteq Z_f\):
It suffices to show that one iteration of the standard closure algorithm on \(Z_f\) w.r.t. \(G\) adds nothing new. Define: $$ S' = {A \in R \mid \exists (Y \rightarrow V) \in G : Y \subseteq Z_f \land A \in V}. $$ We prove \(S' \subseteq Z_f\).
Let \(A \in S'\). Then \(\exists\, Y \rightarrow V \in G\) with \(Y \subseteq Z_f\) and \(A \in V\).
-
By definition of \(G = \bigcup_i \pi_{R_i}(F)\), there is an index \(s\) such that \(Y, V \subseteq R_s\) and \(Y \rightarrow V \in F^{+}\).
-
Since \(Y \subseteq Z_f\) and \(Y \subseteq R_s\), we have \(Y \subseteq Z_f \cap R_s\).
-
By monotonicity of closure: \(Y \subseteq Z_f \cap R_s \implies Y_{F}^{+} \subseteq (Z_f \cap R_s)_{F}^{+}\).
-
Since \(Y \rightarrow V \in F^{+}\), by Lemma 1 \(V \subseteq Y_{F}^{+} \subseteq (Z_f \cap R_s)_{F}^{+}\).
-
Hence \(A \in V \subseteq (Z_f \cap R_s)_{F}^{+}\). Combined with \(A \in R_s\), we get \(A \in (Z_f \cap R_s)_{F}^{+} \cap R_s \subseteq S_f\).
-
Since \(Z_f\) is terminal (\(S_f \subseteq Z_f\)), we conclude \(A \in Z_f\). ✓
Therefore \(S' \subseteq Z_f\), which means \(Z_f\) is already a fixed point of the closure algorithm, i.e., \((Z_f)_{G}^{+} = Z_f\).
-
6. Theorem: Lossless Join Properties¶
Definition¶
A decomposition \(S = \{R_1, \dots, R_k\}\) has a lossless join if:
where \(m_{\rho}(r) = \pi_{R_1}(r) \bowtie \dots \bowtie \pi_{R_k}(r)\).
Theorem 1¶
The following statements hold:
- \(r \subseteq m_{\rho}(r)\)
- \(\pi_{R_i}(m_{\rho}(r)) = \pi_{R_i}(r)\)
- \(m_{\rho}(m_{\rho}(r)) = m_{\rho}(r)\)
Proof¶
Part 1: \(r \subseteq m_{\rho}(r)\)
Let \(t \in r\). Consider \(t[R_i]\) for each \(R_i \in S\).
Then \(t \in \{t[R_1]\} \bowtie \dots \bowtie \{t[R_k]\} \subseteq \pi_{R_1}(r) \bowtie \dots \bowtie \pi_{R_k}(r) = m_{\rho}(r)\).
Part 2: \(\pi_{R_i}(m_{\rho}(r)) = \pi_{R_i}(r)\)
We prove by double inclusion.
(\(\subseteq\)) Let \(t_{R_i} \in \pi_{R_i}(m_{\rho}(r))\). Then there exists a tuple \(t' \in m_{\rho}(r)\) such that \(t_{R_i} = t'[R_i]\).
Since \(t' \in m_{\rho}(r)\), there exist tuples \(t_j \in r\) (for \(j = 1, \dots, k\)) such that \(t'[R_j] = t_j[R_j]\) for each \(R_j \in S\).
In particular, \(t_{R_i} = t'[R_i] = t_i[R_i] \in \pi_{R_i}(r)\).
(\(\supseteq\)) Follows from Part 1, since \(r \subseteq m_{\rho}(r)\) implies \(\pi_{R_i}(r) \subseteq \pi_{R_i}(m_{\rho}(r))\).
Part 3: \(m_{\rho}(m_{\rho}(r)) = m_{\rho}(r)\)
From Part 2, we have:
Algorithm Chase¶
Input:
- Schema \(R = \{A_1, A_2, \dots, A_n\}\).
- Functional Dependencies \(F\).
- Decomposition \(\rho = \{R_1, \dots, R_k\}\).
Output:
- \(\texttt{TRUE}\) if \(\rho\) has a lossless join, \(\texttt{FALSE}\) otherwise.
Procedure:
Note: The symbol \(a_j\) denotes a distinguished variable for attribute \(A_j\), while \(b_{ij}\) denotes a non-distinguished variable for attribute \(A_j\) in row \(i\). When equating symbols, if one is an \(a\) (distinguished), the \(b\) becomes that \(a\); if both are \(b\)'s, one is replaced by the other.
Theorem 2¶
A decomposition \(\rho\) has a lossless join if and only if the Chase algorithm returns an instance containing a tuple with all \(a\)'s.
Proof (Left to Right implication)¶
By contradiction. Suppose that \(\rho\) has a lossless join (\(m_{\rho}(r) = r\) for each legal instance \(r\)) and that when the Chase algorithm terminates, the final tableau \(r^f\) does not contain any tuple with all \(a\)'s.
-
\(r^f\) is a legal instance of \(R\), since the algorithm terminates only when there are no more dependency violations in \(F\).
-
The algorithm never changes an \(a\) into a \(b\): \(a\)-symbols are only propagated, never removed. Therefore, for each \(i \in \{1, \dots, k\}\), the projection \(\pi_{R_i}(r^f)\) contains a tuple with all \(a\)'s in the attributes of \(R_i\) — namely, the one in row \(i\) (corresponding to subschema \(R_i\)), which had all \(a\)'s in \(R_i\) from the beginning.
-
Since each \(\pi_{R_i}(r^f)\) contains a tuple that is all \(a\)'s on \(R_i\), the natural join \(m_{\rho}(r^f) = \pi_{R_1}(r^f) \bowtie \dots \bowtie \pi_{R_k}(r^f)\) contains the tuple \((a_1, \dots, a_n)\) with all \(a\)'s.
-
But \(r^f\) does not contain a tuple with all \(a\)'s (by assumption), so \(m_{\rho}(r^f) \neq r^f\). Contradiction. \(\blacksquare\)
Proof (Right to Left implication)¶
Assume: The Chase algorithm terminates with an all-\(a\)'s tuple in the final instance \(r^f\).
To Prove: \(\forall r\) legal instance of \(R\): \(m_{\rho}(r) = r\).
Let \(r\) be an arbitrary legal instance. We need to show \(r = m_{\rho}(r)\).
By Part 1 of Theorem 1, we already know \(r \subseteq m_{\rho}(r)\). It remains to prove \(m_{\rho}(r) \subseteq r\).
Construction of Homomorphism:
Let \(t \in m_{\rho}(r)\) be arbitrary. Since \(t \in m_{\rho}(r) = \pi_{R_1}(r) \bowtie \dots \bowtie \pi_{R_k}(r)\), there exist tuples \(t_1, \dots, t_k \in r\) such that for each \(i \in \{1, \dots, k\}\):
Define a mapping \(h: R \to r\) (homomorphism from the Chase instance to \(r\)) by:
- Map symbol \(a_A\) (where \(A\) is an attribute) to \(t[A]\)
- Map symbol \(b_i^A\) (where row \(i\) corresponds to \(R_i\)) to \(t_i[A]\)
More formally, for each cell in the Chase table:
Initial Correspondence:
In the initial Chase tableau \(r^0\), row \(i\) has: - \(a_A\) in columns corresponding to \(R_i\) - \(b_i^A\) in columns corresponding to \(R \setminus R_i\)
Under the mapping \(h\): - Row \(i\) of \(r^0\) maps to tuple \(t_i \in r\)
This is because for row \(i\): - If \(A \in R_i\): \(h(a_A) = t[A] = t[R_i][A] = t_i[R_i][A] = t_i[A]\) - If \(A \notin R_i\): \(h(b_i^A) = t_i[A]\)
Preservation Under Chase Steps:
Each Chase step enforces a functional dependency \(X \rightarrow Y \in F\). Suppose rows \(i\) and \(j\) agree on \(X\). The algorithm makes them agree on \(Y\) by equating symbols.
Since \(r\) is legal, \(r \models F\). Therefore, when rows \(i\) and \(j\) agree on \(X\) in the Chase: - \(h(\text{row}_i)[X] = h(\text{row}_j)[X]\) (they map to tuples in \(r\) agreeing on \(X\)) - By \(r \models X \rightarrow Y\): \(h(\text{row}_i)[Y] = h(\text{row}_j)[Y]\)
So when the Chase equates symbols in columns of \(Y\), both symbols already map to the same value in \(r\). Thus \(h\) remains well-defined (consistent) after each Chase step.
Final Step:
By assumption, the Chase terminates with an all-\(a\)'s tuple in \(r^f\). This means there is a row in \(r^f\) where every cell contains some \(a_A\).
Under the homomorphism \(h\):
Since this row appears in \(r^f\) and \(h\) maps each Chase row to some tuple in \(r\), we have \(t \in r\).
Conclusion:
Since \(t \in m_{\rho}(r)\) was arbitrary and we showed \(t \in r\), we conclude \(m_{\rho}(r) \subseteq r\).
Combined with \(r \subseteq m_{\rho}(r)\) from Theorem 1, we have \(r = m_{\rho}(r)\) for every legal instance \(r\).
Therefore, \(S\) has a lossless join. \(\blacksquare\)
7. Derived Armstrong Axioms¶
The following rules can be derived from the three basic Armstrong's Axioms (Reflexivity, Augmentation, Transitivity).
Union Rule¶
Statement:
If \(X \to Y\) and \(X \to Z\), then \(X \to YZ\).
Proof:
Given: 1. \(X \to Y\) (hypothesis) 2. \(X \to Z\) (hypothesis)
We want to prove: \(X \to YZ\).
Step 1: Apply Augmentation to \(X \to Y\) by adding \(Z\) on both sides: $$ \frac{X \to Y}{XZ \to YZ} \text{ (Augmentation)} $$
Step 2: Apply Augmentation to \(X \to Z\) by adding \(X\) on the left: $$ \frac{X \to Z}{XX \to XZ} = \frac{X \to Z}{X \to XZ} \text{ (Augmentation)} $$
Step 3: Apply Transitivity to \(X \to XZ\) and \(XZ \to YZ\): $$ \frac{X \to XZ \quad XZ \to YZ}{X \to YZ} \text{ (Transitivity)} $$
Therefore, \(X \to YZ\). \(\blacksquare\)
Decomposition Rule¶
Statement:
If \(X \to YZ\), then \(X \to Y\) and \(X \to Z\).
Proof:
Given: \(X \to YZ\) (hypothesis)
We want to prove: (1) \(X \to Y\) and (2) \(X \to Z\).
Proof of (1): \(X \to Y\)
-
By Reflexivity, since \(Y \subseteq YZ\): $$ YZ \to Y $$
-
Apply Transitivity to \(X \to YZ\) and \(YZ \to Y\): $$ \frac{X \to YZ \quad YZ \to Y}{X \to Y} \text{ (Transitivity)} $$
Proof of (2): \(X \to Z\)
-
By Reflexivity, since \(Z \subseteq YZ\): $$ YZ \to Z $$
-
Apply Transitivity to \(X \to YZ\) and \(YZ \to Z\): $$ \frac{X \to YZ \quad YZ \to Z}{X \to Z} \text{ (Transitivity)} $$
Therefore, both \(X \to Y\) and \(X \to Z\) hold. \(\blacksquare\)
Pseudotransitivity Rule¶
Statement:
If \(X \to Y\) and \(YZ \to W\), then \(XZ \to W\).
Proof:
Given: 1. \(X \to Y\) (hypothesis) 2. \(YZ \to W\) (hypothesis)
We want to prove: \(XZ \to W\).
Step 1: Apply Augmentation to \(X \to Y\) by adding \(Z\) on both sides: $$ \frac{X \to Y}{XZ \to YZ} \text{ (Augmentation)} $$
Step 2: Apply Transitivity to \(XZ \to YZ\) and \(YZ \to W\): $$ \frac{XZ \to YZ \quad YZ \to W}{XZ \to W} \text{ (Transitivity)} $$
Therefore, \(XZ \to W\). \(\blacksquare\)
8. Theorem: 3NF Verification Requires Only \(F\)¶
Intuition: 3NF is defined on elementary functional dependencies. Since every dependency in \(F^+\) is derived via Armstrong's Axioms from \(F\), if the dependencies in \(F\) satisfy the 3NF condition (superkey or prime attribute), the logical structure prevents any combination of them in \(F^+\) from generating a "new" violation.
Theorem¶
Let \(R\) be a relation schema and \(F\) a set of functional dependencies.
3NF Definition: \(\forall X \to A \in F^+\), either:
- \(A \in X\) (trivial), or
- \(X\) is a superkey, or
- \(A\) is a prime attribute.
Statement: If every \(X \to A \in F\) satisfies the 3NF condition, then every \(Y \to B \in F^+\) satisfies the 3NF condition.
Proof¶
By induction on the derivation of \(Y \to B\) using Armstrong's Axioms.
Base Case: \(Y \to B \in F\).
By hypothesis, the dependency satisfies the 3NF condition. ✓
Induction Step: Assume all dependencies derivable in \(\leq n\) steps satisfy 3NF. We show that any dependency derived in step \(n+1\) also satisfies 3NF.
Case 1: Reflexivity
If \(Y \to B\) is derived by reflexivity, then \(B \in Y\). The dependency is trivial, satisfying 3NF by definition. ✓
Case 2: Augmentation
Suppose \(X \to A \in F^A\) satisfies 3NF (by IH), and we derive \(XZ \to AZ\) by augmentation.
Consider any attribute \(B \in AZ\). We need to show \(XZ \to B\) satisfies 3NF.
- If \(B \in XZ\), the dependency is trivial. ✓
- If \(B = A\) (and \(A \notin XZ\)):
- If \(A\) was prime in the original dependency, \(A\) remains prime (primality is a property of the schema, not the specific FD). ✓
- If \(X\) was a superkey, then \(XZ \supseteq X\) is also a superkey. ✓
In all cases, the 3NF condition is preserved. ✓
Case 3: Transitivity
Suppose \(X \to Y \in F^A\) and \(Y \to B \in F^A\) both satisfy 3NF (by IH). We derive \(X \to B\) by transitivity.
- If \(B \in X\), the dependency is trivial. ✓
- If \(B\) is a prime attribute, the 3NF condition is satisfied. ✓
- If \(B\) is non-prime:
- Since \(Y \to B\) satisfies 3NF and \(B\) is non-prime and \(B \notin Y\), we must have that \(Y\) is a superkey.
- Since \(Y\) is a superkey and \(X \to Y\) satisfies 3NF:
- If \(Y \subseteq X\), then \(X\) is a superkey (since \(X \supseteq Y\) and \(Y\) is a superkey). ✓
- Otherwise, since \(X \to Y\) satisfies 3NF with \(Y \not\subseteq X\): either \(X\) is a superkey ✓, or every attribute in \(Y\) is prime. But if every attribute in \(Y\) is prime and \(Y\) is a superkey, then \(X^+ \supseteq Y^+ = R\), so \(X\) is a superkey. ✓
In all cases, \(X\) is a superkey, satisfying the 3NF condition for \(X \to B\). ✓
Conclusion: By induction, every dependency in \(F^+\) satisfies the 3NF condition if every dependency in \(F\) does. Therefore, to check 3NF, it suffices to verify only the dependencies in \(F\). \(\blacksquare\)
9. Theorem: 3NF Decomposition Algorithm (Primitive Version)¶
Algorithm¶
Input:
- Schema \(R\).
- Minimal cover \(F_{\min}\) of the functional dependencies.
Output:
- Decomposition \(\rho\) that preserves \(F_{\min}\) and has a lossless join.
Procedure:
Note: This is a simpler version than the full Bernstein algorithm. It does not group FDs by their left-hand side, so it may produce more relations (e.g., \(\{A, B\}\) and \(\{A, C\}\) instead of \(\{A, B, C\}\) for \(A \to B\) and \(A \to C\)). However, it is easier to prove correct.
Theorem¶
The decomposition \(\rho\) produced by the algorithm satisfies:
- Dependency Preservation: \(\rho\) preserves \(F_{\min}\) (and hence \(F\)).
- Lossless Join: \(\rho\) has a lossless join with respect to \(F\).
Proof of Dependency Preservation¶
Goal: Show that \(F \subseteq G^{+}\), where \(G = \bigcup_{R_i \in \rho} \pi_{R_i}(F)\).
By Lemma 4 (Closure Inclusion), \(F \subseteq G^{+} \iff F^{+} \subseteq G^{+}\), so it suffices to show \(F_{\min} \subseteq G^{+}\) (since \(F_{\min} \equiv F\)).
Let \(X \to A \in F_{\min}\) be arbitrary. By construction of \(\rho\), there exists a relation \(R_j \in \rho\) such that \(X \cup \{A\} \subseteq R_j\).
Case 1: The algorithm added \(R_j = R\) because \(\exists (X \to A) \in F_{\min}\) with \(X \cup \{A\} = R\).
Then trivially \(X \cup \{A\} \subseteq R_j = R\).
Case 2: The algorithm added \(R_j = X \cup \{A\}\) directly.
Then by construction \(X \cup \{A\} = R_j\).
In both cases, we have \(X \cup \{A\} \subseteq R_j\).
Now, since \(X \to A \in F_{\min} \subseteq F \subseteq F^{+}\) and \(X \cup \{A\} \subseteq R_j\), by the definition of projection:
Since \(X \to A \in F_{\min}\) was arbitrary, we have \(F_{\min} \subseteq G^{+}\).
By Lemma 4, this implies \(F_{\min}^{+} \subseteq G^{+}\), i.e., \(F^{+} \subseteq G^{+}\).
Moreover, since \(G = \bigcup_{R_i \in \rho} \pi_{R_i}(F)\) and each \(\pi_{R_i}(F) \subseteq F^{+}\) by definition, we have \(G \subseteq F^{+}\), hence \(G^{+} \subseteq F^{+}\).
Therefore, \(F^{+} = G^{+}\), and \(\rho\) preserves \(F\). \(\blacksquare\)
Proof of Lossless Join¶
Goal: Show that \(\rho\) has a lossless join.
We consider two cases based on the algorithm's execution.
Case 1: \(\exists (X \to A) \in F_{\min}\) such that \(X \cup \{A\} = R\)¶
In this case, \(\rho\) contains \(R\) itself (possibly along with \(S\) if \(S \neq \emptyset\), but \(S\) would be empty since all attributes appear in some FD).
If \(R \in \rho\), then trivially \(\pi_R(r) = r\) for any instance \(r\), so the join is lossless.
More precisely, if \(\rho = \{R\}\), then \(m_\rho(r) = \pi_R(r) = r\).
Case 2: No single FD covers \(R\)¶
We show that \(\rho\) has a lossless join by proving that the Chase algorithm terminates with an all-\(a\)'s tuple.
Key Observation: Since \(F_{\min}\) is a minimal cover, every FD has the form \(X \to A\) where \(A\) is a single attribute. For each such FD, the algorithm creates a relation \(R_j = X \cup \{A\}\).
Chase Argument:
Initialize the Chase tableau with one row per relation in \(\rho\). For the relation \(R_j = X \cup \{A\}\) corresponding to FD \(X \to A\): - Row \(j\) has \(a\)-symbols in columns \(X \cup \{A\}\) - Row \(j\) has \(b_j\)-symbols in columns \(R \setminus (X \cup \{A\})\)
Consider any FD \(X \to A \in F_{\min}\). In the corresponding row \(j\), all attributes of \(X\) have \(a\)-symbols.
Claim: After applying all FDs, we obtain an all-\(a\)'s row.
We prove this by showing that for any attribute \(B \in R\): - If \(B\) appears on the RHS of some FD in \(F_{\min}\), say \(Y \to B\), then there is a row (corresponding to \(Y \to B\)) with \(a\)-symbols in \(Y \cup \{B\}\). - The Chase will propagate \(a\)-symbols to all rows that agree on \(Y\).
Detailed Argument:
Let \(K\) be a key of \(R\) with respect to \(F_{\min}\). Since \(K\) is a key, \(K^{+}_{F_{\min}} = R\).
We show by induction on the closure computation that all attributes in \(K^{+}\) eventually get \(a\)-symbols in some row that already has \(a\)-symbols on \(K\).
Base: \(K \subseteq K^{+}\).
Since \(K\) is a key, \(K\) must be contained in the LHS of the FDs that can derive all attributes. For each attribute \(B \in K\), either: - \(B\) appears in the LHS of some FD, so some row has \(a_B\), or - \(B \in S\) (handled separately).
Induction: Suppose we have established that attributes in some set \(Z \supseteq K\) have \(a\)-symbols in a row that has \(a\)-symbols on \(K\).
If \(Y \to B \in F_{\min}\) with \(Y \subseteq Z\), then: 1. The row corresponding to \(Y \to B\) has \(a\)-symbols in \(Y \cup \{B\}\). 2. Consider any row that has \(a\)-symbols on \(K\). Since \(Y \subseteq Z\) and (by IH) this row has \(a\)-symbols on \(Z\), it has \(a\)-symbols on \(Y\). 3. Applying the FD \(Y \to B\) in the Chase: if two rows agree on \(Y\) (both have \(a\)-symbols), they must agree on \(B\). The row for \(Y \to B\) has \(a_B\), so the other row gets \(a_B\) too.
Since \(K^{+} = R\), eventually all attributes get \(a\)-symbols in some row, producing an all-\(a\)'s tuple.
By Theorem 6.2, this implies \(\rho\) has a lossless join. \(\blacksquare\)
Handling the Separated Attributes \(S\)¶
If \(S \neq \emptyset\) (attributes not appearing in any FD), then \(S\) must be part of every key. The algorithm adds \(S\) to \(\rho\).
For lossless join: since \(S\) is in every key, and the remaining relations cover a key of \(R \setminus S\), the combined decomposition still has a lossless join. Specifically, the key \(K\) of \(R\) satisfies \(S \subseteq K\), and the relations cover \(K\) and can derive all of \(R\) via the FDs.
For dependency preservation: no FD involves attributes in \(S\), so adding \(\{S\}\) to \(\rho\) does not affect which FDs are preserved.
10. Theorem: Bernstein's Synthesis Algorithm Guarantees Lossless Join¶
Theorem¶
The 3NF Synthesis Algorithm (Bernstein's algorithm) produces a decomposition \(\rho\) that has a lossless join with respect to \(F\).
Key Insight¶
The algorithm explicitly adds a relation containing a key \(K\) of \(R\) (Step 4). This guarantees lossless join via a well-known sufficient condition.
Lemma (Key Containment \(\Rightarrow\) Lossless Join)¶
Let \(\rho = \{R_1, \dots, R_k\}\) be a decomposition of \(R\) with functional dependencies \(F\). If some \(R_i \in \rho\) contains a key \(K\) of \(R\), then \(\rho\) has a lossless join.
Proof of Lemma¶
Let \(r\) be any legal instance of \(R\). We show \(m_\rho(r) = r\).
By Theorem 6.1 (Part 1), \(r \subseteq m_\rho(r)\). It remains to show \(m_\rho(r) \subseteq r\).
Let \(t \in m_\rho(r)\). By definition of natural join:
So there exist tuples \(t_1, \dots, t_k \in r\) such that \(t[R_j] = t_j[R_j]\) for each \(j\).
Focus on \(R_i\) containing the key \(K\):
Since \(K \subseteq R_i\), we have \(t[K] = t[R_i][K] = t_i[R_i][K] = t_i[K]\).
Apply key property:
Since \(K\) is a key of \(R\) and \(r\) is a legal instance, \(K \to R \in F^+\).
Therefore, any two tuples agreeing on \(K\) must agree on all of \(R\).
Conclusion:
Since \(t[K] = t_i[K]\) and \(t_i \in r\), and \(K \to R\) holds in \(r\), we must have:
But \(t_i \in r\) and \(t_i[R] = t_i\) (since \(t_i\) is a tuple over \(R\)), so \(t = t_i \in r\).
Since \(t \in m_\rho(r)\) was arbitrary, \(m_\rho(r) \subseteq r\).
Combined with \(r \subseteq m_\rho(r)\), we have \(r = m_\rho(r)\). \(\blacksquare\)
Proof of Main Theorem¶
The Bernstein synthesis algorithm ensures lossless join as follows:
Step 4 of the algorithm states:
If no relation in \(\rho\) contains a key of \(R\), add a new relation \(R_{\text{key}} = K\) where \(K\) is a candidate key of \(R\).
Case 1: Some relation \(R_i\) already contains a key \(K\).
By the Lemma above, \(\rho\) has a lossless join.
Case 2: No relation contains a key.
The algorithm explicitly adds \(R_{\text{key}} = K\) to \(\rho\).
After this addition, \(K \subseteq R_{\text{key}} \in \rho\), so by the Lemma, \(\rho\) has a lossless join.
In both cases, the final decomposition contains a key of \(R\), guaranteeing a lossless join. \(\blacksquare\)
Remark¶
This is why Step 4 ("Add key relation") is essential in the synthesis algorithm. Without it, the decomposition would preserve dependencies but might not have a lossless join. The addition of a key relation is a sufficient (though not always necessary) condition that makes the proof straightforward.