Check for a lossless join of the decomposition \(\rho\) (JSP)

There are two common checks to see if a decomposition \(\rho\) of a relation scheme \(R\) is lossless with respect to a set of functional dependencies \(F\):

1. Chase Test (general): Construct a tableau based on the decomposition and apply the functional dependencies to see if you can derive a row with all attributes from the original relation.
2. Quick sufficient test (key containment): If at least one of the relation schemes in the decomposition contains a key of \(R\), the decomposition is lossless. This is sufficient but not necessary; if it fails, run the chase.

Example

Given:

• Relation scheme: \(R = \{A, B, C\}\)
• Functional dependencies: \(F = \{A \to B, B \to C\}\)
• Decomposition: \(\rho = \{R_1 = \{A, B\}, R_2 = \{B, C\}\}\)

Check for lossless join:

1. Chase Test:

   • Construct the tableau (global \(\alpha_X\) for attribute \(X\); fresh \(\beta_{iX}\)'s for missing attrs):

	A	B	C
\(R_1\)	\(\alpha_A\)	\(\alpha_B\)	\(\beta_{1C}\)
\(R_2\)	\(\beta_{2A}\)	\(\alpha_B\)	\(\alpha_C\)

• Apply FDs:

  • \(B \to C\) forces both \(C\) entries to match \(\alpha_C\) (since the \(B\) column already matches on \(\alpha_B\)).
  • \(A \to B\) does not fire because the \(A\) symbols differ.

• After the chase, the first row is \((\alpha_A, \alpha_B, \alpha_C)\) (all \(\alpha\) symbols), so the decomposition is lossless.

• Quick sufficient test (key containment):

  • The key for \(R\) is \(\{A\}\).
  • \(R_1\) contains the key \(\{A\}\), so the decomposition is lossless.

Thus, the decomposition \(\rho\) is lossless with respect to \(F\).

Rich chase walk-through (non-trivial overlaps)

• Relation scheme: \(R = \{A, B, C, D, E\}\)
• Functional dependencies: \(F = \{A \to B, B \to C, CD \to E\}\)
• Decomposition: \(\rho = \{R_1 = \{A, B, D\}, R_2 = \{B, C, E\}, R_3 = \{C, D\}\}\)

Tableau setup (row per piece)

Use shared \(\alpha_X\) for attribute \(X\) when present, fresh \(\beta_{iX}\) when missing:

	A	B	C	D	E
\(R_1\)	\(\alpha_A\)	\(\alpha_B\)	\(\beta_{1C}\)	\(\alpha_D\)	\(\beta_{1E}\)
\(R_2\)	\(\beta_{2A}\)	\(\alpha_B\)	\(\alpha_C\)	\(\beta_{2D}\)	\(\alpha_E\)
\(R_3\)	\(\beta_{3A}\)	\(\beta_{3B}\)	\(\alpha_C\)	\(\alpha_D\)	\(\beta_{3E}\)

Chase steps

Legend: determinants highlighted in \(\textcolor{blue}{\text{blue}}\), newly unified entries in \(\textcolor{green}{\text{green}}\).

1. FD \(A \to B\): No row has a unified \(A\) with differing \(B\) in the same row, so nothing fires.

2. FD \(B \to C\): Rows 1 and 2 share \(\alpha_B\); row 1 has \(\beta_{1C}\) while row 2 has \(\alpha_C\). Unify to \(\alpha_C\) in row 1.

after \(B \to C\)	A	B	C	D	E
\(R_1\)	\(\alpha_A\)	\(\textcolor{blue}{\alpha_B}\)	\(\textcolor{green}{\alpha_C}\)	\(\alpha_D\)	\(\beta_{1E}\)
\(R_2\)	\(\beta_{2A}\)	\(\textcolor{blue}{\alpha_B}\)	\(\alpha_C\)	\(\beta_{2D}\)	\(\alpha_E\)
\(R_3\)	\(\beta_{3A}\)	\(\beta_{3B}\)	\(\alpha_C\)	\(\alpha_D\)	\(\beta_{3E}\)

1. FD \(CD \to E\): Rows 1 and 3 both have \(\alpha_C\) and \(\alpha_D\). Unify their \(E\) to \(\alpha_E\).

after \(CD \to E\)	A	B	C	D	E
\(R_1\)	\(\alpha_A\)	\(\alpha_B\)	\(\textcolor{blue}{\alpha_C}\)	\(\textcolor{blue}{\alpha_D}\)	\(\textcolor{green}{\alpha_E}\)
\(R_2\)	\(\beta_{2A}\)	\(\alpha_B\)	\(\alpha_C\)	\(\beta_{2D}\)	\(\alpha_E\)
\(R_3\)	\(\beta_{3A}\)	\(\beta_{3B}\)	\(\textcolor{blue}{\alpha_C}\)	\(\textcolor{blue}{\alpha_D}\)	\(\textcolor{green}{\alpha_E}\)

Verdict

Row 1 is now all-\(\alpha\) across \(A, B, C, D, E\), so the chase succeeds and the decomposition is lossless. Note how \(CD \to E\) needed the overlap from \(R_3\) to close the loop.