Skip to content

Check if \(\rho\) preserves \(F\)

Goal: after decomposing \(R\) into \(\rho = \{R_1, R_2, \dots\}\), you want to enforce the same FDs without recombining the tables. A decomposition preserves \(F\) if every FD in \(F\) still holds when you only know the projected FDs that each piece can enforce.

Quick recipe (iterative check)

  • (Optional) Replace \(F\) with a minimal cover \(G\).
  • For each FD \(X \to A\) in \(G\):
  • If some \(R_i\) contains \(X \cup \{A\}\), that FD is trivially preserved.
  • Otherwise, run the iterative algorithm that computes \(X_G^+\) from \(F\) (see compute \(X_G^+\) from \(F\)) using that \(X\) and the same decomposition \(\rho\). If \(A \in X_G^+\), the FD is preserved; if not, the decomposition fails preservation.
  • The decomposition preserves \(F\) iff every FD passes the check.

Why this avoids manual projections

The union of all projections \(G = \bigcup_i \pi_{R_i}(F)\) is implicit in the iterative algorithm: each iteration feeds the attributes you already know into every piece \(R_i\), uses \(F\) to see what those attributes can force, and keeps only the attributes that live in that piece. This converges to \(X_G^+\) without enumerating every projected FD.

Example (preserves a non-trivial FD)

  • \(R = \{A, B, C\}\)
  • \(F = \{A \to B, B \to C, A \to C\}\)
  • Decomposition \(\rho = \{R_1 = \{A, B\}, R_2 = \{B, C\}\}\)

Trivial checks: \(A \to B\) sits in \(R_1\), \(B \to C\) sits in \(R_2\). The interesting FD is \(A \to C\), which is not contained in any single \(R_i\).

Iterative computation for \(X = \{A\}\):

  • Start \(Z = \{A\}\).
  • Piece \(R_1\): \(Z \cap R_1 = \{A\}\); \((\{A\})^+_F = \{A, B, C\}\); restrict to \(R_1\) gives \(\{A, B\}\) → add \(B\).
  • Piece \(R_2\): \(Z \cap R_2 = \{B\}\); \((\{B\})^+_F = \{B, C\}\); restrict to \(R_2\) gives \(\{B, C\}\) → add \(C\).
  • No more growth: \(X_G^+ = \{A, B, C\}\) contains \(C\), so \(A \to C\) is preserved. All FDs in \(F\) are therefore preserved by \(\rho\).

Example (fails to preserve)

  • \(R = \{A, B, C, D, E\}\)
  • \(F = \{A \to B, B \to C, AC \to D, D \to E\}\)
  • Decomposition \(\rho = \{R_1 = \{A, B, C\}, R_2 = \{A, C, D\}, R_3 = \{A, E\}\}\)

FDs \(A \to B\), \(B \to C\), and \(AC \to D\) are all contained in some \(R_i\). The FD \(D \to E\) is not; we test it with \(X = \{D\}\).

Iterative computation:

  • Start \(Z = \{D\}\).
  • \(R_1\): \(Z \cap R_1 = \emptyset\) → no contribution.
  • \(R_2\): \(Z \cap R_2 = \{D\}\); \((\{D\})^+_F = \{D, E\}\); intersect with \(R_2\) gives \(\{D\}\) → nothing new.
  • \(R_3\): \(Z \cap R_3 = \emptyset\) → no contribution.
  • Fixpoint reached with \(Z = \{D\}\), so \(E \notin X_G^+\) and \(D \to E\) is not preserved. The decomposition fails.