Lossless join and dependency preservation

Why it exists

A schema that violates a normal form is repaired by decomposition: replace $R$ by smaller relations $R_1, \ldots, R_k$ with $R_1 \cup \cdots \cup R_k = R$. A decomposition is only acceptable if it loses neither data (we must be able to rebuild $R$ by joining the pieces) nor constraints (every dependency should still be checkable inside one piece). GATE asks to test both properties and to run the decomposition algorithms.

Prerequisites

You need normal forms and the reasons for decomposing (normal forms) and closures of attribute sets (functional dependencies).

Precise definitions

Let $R$ have dependencies $F$ and be decomposed into $R_1, \ldots, R_k$.

• The decomposition is lossless-join if for every legal instance $r$ of $R$ (every relation that satisfies $F$) $r = \pi_{R_1}(r) \bowtie \cdots \bowtie \pi_{R_k}(r).$ It always holds that $r \subseteq \pi_{R_1}(r) \bowtie \cdots \bowtie \pi_{R_k}(r)$; a lossy decomposition produces extra, spurious tuples.
• The projection of $F$ on $R_i$ is $F_i = \{X \to Y \in F^+ : X, Y \subseteq R_i\}$ (all implied dependencies that fit inside $R_i$, not only the given ones that do).
• The decomposition is dependency preserving if $(F_1 \cup \cdots \cup F_k)^+ = F^+$, that is, if every dependency of $F$ follows from the dependencies that can be checked inside the individual pieces.

How it works

Lossless join

Why losslessness can fail. $R(A, B, C)$ with $A \to B$ and the instance {(1, x, p), (2, x, q)}. Splitting into $R_1(A, B)$ and $R_2(B, C)$ and joining on $B$ gives four tuples; the two extra ones are spurious. Splitting into $R_1(A, B)$ and $R_3(A, C)$, joined on $A$, gives back exactly $R$:

Test for two pieces. The decomposition of $R$ into $R_1$ and $R_2$ is lossless iff the common attributes determine one of the pieces: $R_1 \cap R_2 \to R_1 \quad \text{or} \quad R_1 \cap R_2 \to R_2 \quad (\text{in } F^+).$ In the example $R_1 \cap R_2 = B$ determines neither $AB$ nor $BC$ (lossy), but $R_1 \cap R_3 = A$ determines $AB$ (lossless).

General test: the chase. Build a tableau with one row per piece: in the column of attribute $X$ put the distinguished symbol $a_X$ if the piece contains $X$, otherwise a fresh symbol $b$. For every dependency $X \to Y$ of $F$, wherever two rows agree on $X$, make their symbols in the columns of $Y$ equal (an $a$ replaces a $b$). Repeat until nothing changes. The decomposition is lossless iff some row consists only of distinguished symbols.

For $R(A, B, C, D)$, $F = \{B \to C, C \to D\}$ and the pieces $AB$, $BC$, $CD$: $B \to C$ makes the first two rows agree on $C$ (the first row gets $a_C$); $C \to D$ then gives $a_D$ to the rows with $a_C$: the first row becomes all distinguished: lossless. A failing case:

With $F = \{A \to B\}$ and pieces $AB$, $BC$ the dependency changes nothing useful and no row becomes all-distinguished: lossy. Moreover the final tableau, read as a relation, is a legal instance (the chase ended, so it satisfies $F$) whose join of projections contains the all-$a$ tuple although the relation does not: an explicit counterexample, checked by program on 400 random decompositions.

Dependency preservation

To test whether $X \to Y \in F$ is preserved, grow a set $Z$ starting from $X$: repeat, for each piece $R_i$, $Z := Z \cup \big((Z \cap R_i)^+ \cap R_i\big)$ until $Z$ stops growing. The dependency is preserved iff $Y \subseteq Z$. (It tests only attribute closures with respect to $F$, never computes $F^+$.) The decomposition is dependency preserving iff every dependency of $F$ passes. The test equals the definition (union of the projected dependencies implies $F$) on 500 random cases.

The two properties are independent

All four combinations occur: $\{AB, AC\}$ for $A \to B$ is both; $\{AB, BC\}$ is dependency preserving but lossy; $\{BC, AC\}$ for $\{AB \to C, C \to B\}$ is lossless but loses $AB \to C$; $\{AC, BC\}$ for $A \to B$ is neither.

BCNF decomposition

Algorithm. While some piece $R_i$ is not in BCNF, take a violating dependency $X \to Y$ with $X$ not a superkey of $R_i$ (use the closure within $R_i$, $Y := X^+ \cap R_i - X$) and replace $R_i$ by $R_i - Y$ and $X \cup Y$. The two new pieces share $X$, which determines $X \cup Y$, so each step is lossless; the process terminates with all pieces in BCNF. The result is always lossless, but may not be dependency preserving.

$R(A, B, C)$ with $AB \to C$ and $C \to B$: $C \to B$ violates BCNF ($C$ is not a superkey). The pieces are $(C, B)$ and $(A, C)$, both in BCNF and with the join equal to $R$. But the dependency $AB \to C$ fits in neither piece: two tuples $(a_1, c_1)$ and $(a_1, c_2)$ in $R_2$ and $(c_1, b_1)$, $(c_2, b_1)$ in $R_1$ each satisfy their own dependencies and yet join to two tuples that violate $AB \to C$. A BCNF decomposition that preserves all dependencies does not always exist; this schema has none.

3NF synthesis

Algorithm.

1. Compute a minimal cover $F_c$ of $F$: right sides single attributes; no extraneous attribute in a left side; no redundant dependency. (Example: $\{A \to BC,\ B \to C,\ A \to B,\ AB \to C\}$ has the minimal cover $\{A \to B,\ B \to C\}$.)
2. For every distinct left side $X$ in $F_c$ create a relation $X \cup \{\text{all } A \text{ with } X \to A \in F_c\}$.
3. If no created relation contains a candidate key of $R$, add a relation consisting of a candidate key.
4. Remove relations contained in another.

The result is in 3NF and is both lossless and dependency preserving (checked on 300 random schemas). Example: $R(A, B, C, D, E)$ with $\{A \to B,\ B \to C,\ D \to E\}$: the minimal cover is the set itself; the relations are $AB$, $BC$, $DE$; the only candidate key is $AD$, which none of them contains, so $AD$ is added. Result $\{AB, BC, DE, AD\}$: lossless, preserving, and (here) also the result of the BCNF algorithm. (Computing a minimal cover: split the right sides, delete extraneous attributes from left sides by testing closures, then delete every dependency that the rest implies; the order of the deletions can lead to different, equally valid minimal covers.)

Summary of guarantees

Worked examples

Cheat box

Traps and GATE patterns

Connections

The normal forms that motivate decomposition are on the previous page; minimal covers are the subject of a later page (canonical cover and 3NF synthesis); redundancy that survives BCNF needs multivalued dependencies (4NF).

PYQs

In the context of relational database normalization, which
of the following statements is/are true?

Consider a relational schema team(name , city , owner)
with functional dependencies {name → city , name →
owner}
.
The relation team is decomposed into two relations,

DATABASE MANAGEMENT  SYSTEM
t1(name , city) and t2(name , owner). Which of the
following statement(s) is/are TRUE?

Consider the relation R(P, Q, S, T, X, Y, Z, W) with the
following functional dependencies.

PQ → X; P→YX ; Q→ Y; Y → ZW

Consider the decomposition of the relation R into the
constituent relations according to the following two
decomposition schemes.

DATABASE MANAGEMENT  SYSTEM

D1 : R=[(P, Q, S,T); (P,T, X); (Q,Y); (Y, Z,W)]

D2 : R= [(P, Q,S); (T, X); (Q,Y); (Y,Z,W)]

Which one of the following options is correct?

Let the set of functional dependencies F = {QR → S, R
→ P, S → Q} hold on a relation schema X = (PQRS).
X is not in BCNF. Suppose X is decomposed into two
schemas Y and Z, where Y = (PR) and Z = (QRS).
Consider the two statements given below.
I.
Both Y and Z are in BCNF
II.
Decomposition of X into Y and Z is dependency
preserving and lossless.

Which of the statements is/are correct ?

Let R(A, B, C, D) be a relational schema with the
following functional dependencies:

F={A → B, B → C, C → D, D → B}

The decomposition of R into (A, B), (B, C), (B, D)

Which one of the following statements about normal
forms is FALSE?

Let r be a relation instance with schema R = (A, B, C,
D). We define
r1 = πA,B,C (r) and r2 = πA,D (r).
Let s = r1 ⋈ r2, where ⋈ denotes natural join. Given
that the decomposition of r into r1 and r2 is lossy,
which one of the following is TRUE?

Self-check

Revision card

References