Compute \(X_G^+\) from \(F\)¶
Algorithm: closure under projected functional dependencies¶
This algorithm computes the closure of a set of attributes \(X\) under the union of projected functional dependencies \(G = \bigcup \pi_{R_i}(F)\).
Input:
- A universal schema \(R\).
- A set of functional dependencies \(F\).
- A decomposition \(\rho = \{R_1, R_2, \dots, R_k\}\).
- A subset of attributes \(X \subseteq R\).
Output:
- The closure \(X_G^+\) (denoted as \(Z\)).
Procedure¶
-
Initialize the result set with the input attributes: $$ Z \gets X $$
-
Refine the set by iteratively applying the dependencies until no further changes occur:
Repeat until \(Z\) does not change:
-
For each sub-schema \(R_i\) in the decomposition \(\rho\):
- Compute the contribution from this sub-schema:
$$ \text{contribution} \gets (Z \cap R_i)^+_F \cap R_i $$
- Update the result set:
$$ Z \gets Z \cup \text{contribution} $$
-
Return \(Z\).
Explicit Logic Breakdown¶
- \(Z \cap R_i\): Isolates the attributes in the current result that are actually present in the sub-relation \(R_i\).
- \(( \dots )^+_F\): Applies the original functional dependencies \(F\) to those specific attributes to see what they determine globally.
- \(\cap R_i\): Constrains the newly found attributes to only those that "live" within \(R_i\), effectively simulating the projected dependency \(\pi_{R_i}(F)\).
Worked example (iterative growth)¶
- \(R = \{A, B, C, D, E\}\)
- \(F = \{A \to B, B \to C, C \to D, D \to E\}\)
- Decomposition \(\rho = \{R_1 = \{A, B\}, R_2 = \{B, C\}, R_3 = \{C, D\}, R_4 = \{D, E\}\}\)
- Query FD: \(A \to E\) (not contained in any single \(R_i\)), so we compute \(X_G^+\) for \(X = \{A\}\).
| iteration | current \(Z\) | piece \(R_i\) | \(Z \cap R_i\) | \((Z \cap R_i)^+_F\) | contribution \((\cdot) \cap R_i\) | updated \(Z\) |
|---|---|---|---|---|---|---|
| 0 | \(\{A\}\) | \(R_1=\{A,B\}\) | \(\{A\}\) | \(\{A,B,C,D,E\}\) | \(\{A,B\}\) | \(\{A,B\}\) |
| 1 | \(\{A,B\}\) | \(R_2=\{B,C\}\) | \(\{B\}\) | \(\{B,C,D,E\}\) | \(\{B,C\}\) | \(\{A,B,C\}\) |
| 2 | \(\{A,B,C\}\) | \(R_3=\{C,D\}\) | \(\{C\}\) | \(\{C,D,E\}\) | \(\{C,D\}\) | \(\{A,B,C,D\}\) |
| 3 | \(\{A,B,C,D\}\) | \(R_4=\{D,E\}\) | \(\{D\}\) | \(\{D,E\}\) | \(\{D,E\}\) | \(\{A,B,C,D,E\}\) |
| 4 | \(\{A,B,C,D,E\}\) | all | unchanged | unchanged | \(\emptyset\) | fixpoint |
Comments:
- Each pass only adds attributes that belong to the current piece, but uses the global \(F\) to see what those attributes imply.
- After four short steps the fixpoint is reached and \(E \in X_G^+\), so \(A \to E\) is preserved by this decomposition.