Lossless-Join and Dependency-Preserving Decomposition: short notes (Database Management Systems)

Introduction

Normalisation replaces a relation $R$ by smaller relations $R_1, \ldots, R_n$ whose attributes together cover $R$ . Splitting is only safe if two properties hold. The decomposition must be lossless: joining the pieces back must give exactly the original relation, with no extra (spurious) tuples. It should also be dependency preserving: every functional dependency of $R$ must be checkable on the pieces without joining them.

The tasks for a decomposition are to decide whether it is lossless, whether it preserves dependencies, and what the 3NF synthesis or BCNF decomposition algorithm produces. The tests, the two algorithms, and the reason 3NF and BCNF differ on preservation follow.

Prerequisites

Normal Forms: 1NF, 2NF, 3NF and BCNF: the target forms and the role of candidate keys.

Core concepts

A decomposition of $R$ is a set $\{R_1, \ldots, R_n\}$ of schemas with $R_1 \cup \cdots \cup R_n = R$ .

Lossless join. For every legal instance $r$ of $R$ : $\pi_{R_1}(r) \bowtie \cdots \bowtie \pi_{R_n}(r) = r$ . The join always contains $r$ ; a lossy decomposition adds spurious tuples, it never loses tuples. "Lossy" means information about which values belong together is lost.
Projection of $F$ onto $R_i$ . $F_i = \{ X \to Y \in F^+ : X \cup Y \subseteq R_i \}$ . It may contain FDs that are in no member of $F$ .
Dependency preserving. $(F_1 \cup \cdots \cup F_n)^+ = F^+$ : every FD of $F$ follows from the FDs that live inside single pieces.

Binary lossless test. $\{R_1, R_2\}$ is lossless iff $R_1 \cap R_2 \to R_1$ or $R_1 \cap R_2 \to R_2$ is in $F^+$ , that is, iff the common attributes form a superkey of at least one side.

Three decompositions of R(A, B, C, D) with A to B and C to D: AB and ACD share A, a key of AB, so lossless; ABC and CD share C, a key of CD, so lossless; AB and CD share nothing, so lossy — Figure 1. The common-attribute test on three binary decompositions of $R(A, B, C, D)$ with $F = \{A \to B, C \to D\}$ : lossless exactly when the shared attributes determine one whole side.

How it works: the chase test for any number of pieces

For $n$ pieces, build a tableau with one row per $R_i$ and one column per attribute. Row $i$ holds a distinguished symbol $a_A$ in column $A$ if $A \in R_i$ , otherwise a unique symbol $b_{iA}$ . Then repeatedly, for each FD $X \to Y$ , find two rows equal on all columns of $X$ and make them equal on $Y$ (replace a $b$ by an $a$ if one of them is an $a$ , otherwise by one of the $b$ symbols, everywhere it occurs). The decomposition is lossless iff some row becomes all $a$ .

Example tableau. $R(A, B, C, D, E)$ , $F = \{A \to C, B \to D, CD \to E\}$ , pieces $AC$ , $BD$ , $CDE$ , $AB$ :

Row	A	B	C	D	E
$AC$	$a_A$	$b$	$a_C$	$b$	$b$
$BD$	$b$	$a_B$	$b$	$a_D$	$b$
$CDE$	$b$	$b$	$a_C$	$a_D$	$a_E$
$AB$	$a_A$	$a_B$	$b$	$b$	$b$

$A \to C$ (rows $AC$ , $AB$ agree on $A$ ) sets $C = a_C$ in row $AB$ ; $B \to D$ (rows $BD$ , $AB$ ) sets $D = a_D$ ; now rows $CDE$ and $AB$ agree on $CD$ , so $CD \to E$ sets $E = a_E$ . Row $AB$ is all $a$ : lossless.

Algorithms and pseudocode

Testing preservation of one FD without computing $F^+$ .

Text

PRESERVED(X -> Y, decomposition R_1..R_n, F)
  result <- X
  repeat
      for each R_i
          result <- result union (CLOSURE(result intersect R_i, F) intersect R_i)
  until result does not change
  return (Y is a subset of result)

The decomposition preserves $F$ iff every FD of $F$ passes. Polynomial time.

3NF synthesis (lossless and dependency preserving, always):

Text

3NF-SYNTHESIS(R, F)
  Fc <- canonical cover of F, FDs with equal left sides merged
  for each X -> Y in Fc: create schema X union Y
  if no schema contains a candidate key of R: add one candidate key as a schema
  remove any schema contained in another

BCNF decomposition (lossless, may lose FDs):

Text

BCNF-DECOMPOSE(R, F)
  result <- {R}
  while some R_i in result is not in BCNF
      find X -> Y holding on R_i (in the projection of F+), nontrivial, X not a superkey of R_i
      replace R_i by (X union Y) and (R_i - (Y - X))
  return result

Each split is lossless because the two pieces share $X$ and $X \to X \cup Y$ . Testing BCNF of a piece needs the projected FDs, so the algorithm is exponential in the worst case.

Mathematical explanation

Why the binary test works. Suppose $R_1 \cap R_2 \to R_2$ . Take any tuple $t$ of the join: it comes from $t_1 \in \pi_{R_1}(r)$ and $t_2 \in \pi_{R_2}(r)$ that agree on $R_1 \cap R_2$ . Let $u \in r$ be a tuple projecting to $t_1$ . Since $u$ agrees with the source of $t_2$ on $R_1 \cap R_2$ and that set determines $R_2$ , $u$ agrees with it on all of $R_2$ , so $t = u \in r$ . No spurious tuple appears.

Why BCNF can lose dependencies and 3NF cannot. 3NF synthesis creates one schema per FD of the canonical cover, so every FD lives in some piece. BCNF decomposition splits wherever a left side is not a superkey and can separate the attributes of another FD. For $R(A, B, C)$ with $AB \to C$ , $C \to B$ , every BCNF decomposition breaks $AB \to C$ .

Why synthesis adds a key. The key schema makes the chase succeed: starting from the key row, each FD of the cover fills one more column, ending with an all- $a$ row.

Worked examples

Example 1: spurious tuples. $r(A, B, C) = \{(1, x, p), (2, x, q)\}$ with only $A \to B$ . Decompose into $AB$ , $BC$ : $\pi_{AB} = \{(1, x), (2, x)\}$ , $\pi_{BC} = \{(x, p), (x, q)\}$ , and the join has 4 tuples, 2 of them spurious, $(1, x, q)$ and $(2, x, p)$ . The common attribute $B$ determines neither side. Decomposing into $AB$ , $AC$ is lossless ( $A \to B$ ).

Example 2: the binary test (Figure 1). $R(A, B, C, D)$ , $F = \{A \to B, C \to D\}$ . $\{AB, ACD\}$ : common $A$ , $A \to B$ , lossless. $\{ABC, CD\}$ : common $C$ , $C \to D$ , lossless. $\{AB, CD\}$ : nothing in common, lossy (the join is a Cartesian product). $\{AB, BCD\}$ : common $B$ , $B^+ = B$ , lossy.

Example 3: chase. In the tableau above, dropping the piece $AB$ leaves $\{AC, BD, CDE\}$ , which is lossy. Two ways to see it. Directly: in the starting tableau no FD applies at all, because no two rows agree on $A$ , on $B$ , or on both $C$ and $D$ , so the chase stops at once with no all- $a$ row. Structurally: a row that becomes all $a$ proves that its piece determines every attribute, so a lossless decomposition always has a piece that is a superkey; here no piece contains the only candidate key $AB$ . The decomposition $\{AC, BD, ABE\}$ is lossless (row $ABE$ fills $C$ and $D$ ) but does not preserve $CD \to E$ .

Example 4: lossless but not preserving. $R(A, B, C)$ , $F = \{AB \to C, C \to B\}$ , decomposed into $\{AC, BC\}$ : common $C$ , $C \to B$ , lossless; both pieces are in BCNF; $AB \to C$ is lost.

Example 5: preserving through a derived FD. $R(A, B, C)$ , $F = \{A \to B, B \to C\}$ . $\{AB, BC\}$ is lossless and preserves both FDs. $\{AB, AC\}$ is lossless (common $A$ ) but loses $B \to C$ ; note that the projection onto $AC$ contains $A \to C$ , which is not in $F$ .

Example 6: 3NF synthesis. $R(A, B, C, D, E)$ , $F = \{A \to B, B \to C, CD \to E\}$ (already canonical). Schemas $AB$ , $BC$ , $CDE$ . The only candidate key is $AD$ (neither $A$ nor $D$ is on a right side, and $(AD)^+ = ABCDE$ ); no schema contains it, so add $AD$ . Result $\{AB, BC, CDE, AD\}$ : every piece is in 3NF (in fact BCNF), the chase succeeds from row $AD$ , and every FD lives in one piece.

Example 7: BCNF decomposition of the same relation. $A \to B$ violates BCNF on $R$ . Splitting on $A$ with $A^+ = ABC$ gives $ABC$ and $ADE$ . In $ABC$ , $B \to C$ violates BCNF: split into $BC$ and $AB$ . $ADE$ has projected FD $AD \to E$ and key $AD$ : BCNF. Result $\{AB, BC, ADE\}$ , lossless, but $CD \to E$ is lost (no piece contains $C$ , $D$ and $E$ ).

Example 8: running PRESERVED on a cycle. $R(A, B, C, D)$ , $F = \{A \to B, B \to C, C \to D, D \to A\}$ , pieces $AB$ , $BC$ , $CD$ . Every single attribute is a key, so row $AB$ of the chase becomes all $a$ ( $B \to C$ , then $C \to D$ ) and the decomposition is lossless. $A \to B$ , $B \to C$ , $C \to D$ each lie inside a piece. $D \to A$ lies in none, so run the test, visiting $AB$ , $BC$ , $CD$ in each pass:

Pass	Piece that adds something	result
start		$D$
1	$CD$ : $D^+ \cap CD = CD$	$CD$
2	$BC$ : $C^+ \cap BC = BC$	$BCD$
3	$AB$ : $B^+ \cap AB = AB$	$ABCD$

$A \subseteq$ result, so $D \to A$ is preserved, and the decomposition is lossless and dependency preserving. The FD travels round the cycle through the pieces.

Example 9: what a key piece does. $R(A, B, C, D)$ , $F = \{A \to B, C \to D\}$ . The only candidate key is $AC$ .

$\{AB, CD\}$ : no common attribute, lossy.
$\{AB, CD, AC\}$ : the row for $AC$ gets $B$ from $A \to B$ and $D$ from $C \to D$ , so it becomes all $a$ : lossless. This is exactly the key schema that 3NF synthesis adds.
$\{AB, BC, CD\}$ : lossy. Initially in the chase, rows $AB$ and $BC$ agree on $B$ , but no FD has left side $B$ ; rows $BC$ and $CD$ agree on $C$ , so $C \to D$ gives row $BC$ the symbol $a$ under $D$ . The final rows are $AB$ : $(a, a, b, b)$ , $BC$ : $(b, a, a, a)$ , $CD$ : $(b, b, a, a)$ , with no all- $a$ row.
Concrete spurious tuples: $r = \{(1, 1, 1, 1), (2, 1, 2, 2)\}$ satisfies both FDs, and $\pi_{AB}(r) \bowtie \pi_{BC}(r) \bowtie \pi_{CD}(r)$ has 4 tuples, two of them spurious, for example $(1, 1, 2, 2)$ .

Important properties and observations

A decomposition never loses tuples; lossy means spurious tuples are added.
Binary test: use the exact FD criterion $(R_1\cap R_2)\to R_1$ or $(R_1\cap R_2)\to R_2$ in $F^+$ . A disjoint decomposition is ordinarily lossy, but can be lossless if the empty determinant determines an entire piece. With no such constant dependency, no common attributes means lossy.
Chase: works for any number of pieces; lossless iff some row becomes all distinguished.
3NF synthesis is always lossless and preserving; BCNF decomposition is always lossless but may lose FDs.
Preservation uses projections of $F^+$ , not just the FDs of $F$ that happen to fit inside a piece.
Lossless and preserving are independent: Examples 4 and 3 ( $\{AC, BD, CDE\}$ ) show each without the other.

Common misconceptions.

"A lossy decomposition loses tuples." It adds spurious ones.
"If some FD of $F$ fits in no single piece, the decomposition is not preserving." It can still be preserved through derived FDs: for $F = \{A \to B, B \to C, C \to A\}$ and pieces $AB$ , $BC$ , the FD $C \to A$ fits in neither, yet $C \to B$ (in $BC$ ) and $B \to A$ (in the projection onto $AB$ ) imply it. Use the PRESERVED test.
"Pairwise lossless joins make a multi-way decomposition lossless." Use the chase for three or more pieces.

GATE examination perspective

Is it lossless? Binary test for two pieces, chase for more.
Is it dependency preserving? Check every FD with PRESERVED or by projecting closures.
Count or list the relations. Consider those produced by 3NF synthesis or BCNF decomposition.
Combined questions. Decompositions that are lossless but not preserving, or the reverse.
Spurious tuples. Count the tuples of a join of projections on a small instance.

Summary

Normal Forms: 1NF, 2NF, 3NF and BCNF: prerequisite; the targets of the algorithms here.

Lossless-Join and Dependency-Preserving Decomposition

Introduction

Prerequisites

Core concepts

How it works: the chase test for any number of pieces

Algorithms and pseudocode

Mathematical explanation

Worked examples

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

How it works: the chase test for any number of pieces

Algorithms and pseudocode

Mathematical explanation

Worked examples

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps