Decomposition: lossless join, dependency preservation, BCNF and 3NF algorithms

Last week you learned to find the normal form of a schema. If the normal form is low, the fix is to split the schema into pieces (decomposition). But not every split is good. You want two things from a decomposition:

1. Lossless join: when the pieces are joined back with NATURAL JOIN, you must get exactly the original table.
2. Dependency preservation: every FD must be checkable in the individual pieces, without a join.

Typical exam questions: “Is this decomposition lossless?”, “Is it dependency preserving?”, “Decompose R into BCNF”, “Apply the 3NF synthesis algorithm”.

A lossy decomposition: seeing it in data

From the sample database, derive a table that holds each student’s department and the course they took (S7, whose department is NULL, is left out): enr(stu_id, dept_name, course_id), 13 rows. The only FD is $\text{stu\_id} \to \text{dept\_name}$.

Now let us split it in the wrong place:

CREATE TABLE r1 AS SELECT DISTINCT stu_id, dept_name FROM enr;    -- 5 rows
CREATE TABLE r2 AS SELECT DISTINCT dept_name, course_id FROM enr; -- 10 rows
SELECT COUNT(*) FROM r1 NATURAL JOIN r2;

18

The 13-row table came back as 18 rows. You can see the excess with EXCEPT:

SELECT stu_id, dept_name, course_id FROM r1 NATURAL JOIN r2
EXCEPT SELECT * FROM enr;

These rows are called spurious tuples. Why only CS? The join is made on dept_name, and CS has three students (S1, S2, S5). r2 keeps the information “a CS student took this course” but has lost which student it was. EE and MATH each have a single student, so no mix-up occurs there.

PITFALL · “lossy” does not mean losing rows. In a lossy decomposition the join produces more rows. What is lost is information: you can no longer tell which rows are real.

The correct split: r1(stu_id, dept_name) and r3(stu_id, course_id). The intersection is stu_id, and since $\text{stu\_id} \to \text{dept\_name}$, stu_id is the key of r1. r1 NATURAL JOIN r3 gives exactly 13 rows, and the EXCEPT result is empty.

The binary test

If you split $R$ into $R_1$ and $R_2$, the decomposition is lossless if and only if one of these FDs is in $F^+$:

$R_1 \cap R_2 \to R_1 \qquad \text{or} \qquad R_1 \cap R_2 \to R_2$

That is, the intersection must be a superkey of one of the pieces. Calculation: take the closure of the intersection.

$R(A,B,C,D)$, $F = \{A \to B,\ C \to D\}$:

Three or more pieces: the chase test

The binary test is only for two pieces. For more, use the tableau method:

1. The columns are the attributes of R, with one row per piece.
2. In each row, write a for the columns the piece contains and b (specific to the row) for the others.
3. For each $X \to Y$: for two rows that are equal on the X columns, equate their Y values (if one is a, both become a).
4. Repeat until there are no changes. If a row consisting entirely of a’s appears, it is lossless.

Worked example. $R(A,B,C,D,E)$, $F = \{A \to B,\ C \to D,\ BD \to E\}$, pieces (A,B), (C,D), (A,C,E).

         A    B    C    D    E
R1(AB)   a    a    b    b    b
R2(CD)   b    b    a    a    b
R3(ACE)  a    b    a    b    a

A -> B : R1 and R3 are equal on A  → R3.B = a
C -> D : R2 and R3 are equal on C  → R3.D = a
R3     : a    a    a    a    a      → LOSSLESS

If you try (A,B), (C,D), (B,D,E) with the same F, no FD can be applied (there are no two rows equal on A or on C, and no two rows equal on BD), and no all-a row appears: lossy. An intuition (not a rule): in the first example the winning row was R3, which contains the candidate key AC. In the second example there is no piece that holds A and C together.

Dependency preservation

Let $F_i$ be the projection of $F^+$ onto $R_i$: the FDs in $F^+$ all of whose attributes are inside $R_i$. A decomposition is preserving if $(F_1 \cup F_2 \cup \dots)^+ = F^+$. Practical test: for each $X \to Y$ in F, take the closure of $X$ using only the projected FDs; if Y comes out, it is preserved.

Example 1. $R(A,B,C,D)$, $F = \{A \to B,\ B \to C,\ C \to D\}$, pieces (A,B), (A,C), (C,D).

The projections: $A \to B$, $A \to C$, $C \to D$. With this set $\{B\}^+ = \{B\}$: $B \to C$ is lost. The decomposition is lossless but not preserving. If you had chosen the pieces (A,B), (B,C), (C,D), all three FDs would be inside a piece.

Example 2. $R(A,B,C)$, $F = \{A \to B,\ B \to C,\ C \to A\}$, pieces (A,B), (B,C). No piece contains $C \to A$. But since $\{B\}^+ = ABC$, there is $B \to A$ in the projection onto AB and $C \to B$ in the projection onto BC. $C \to B \to A$: $C \to A$ is preserved.

PITFALL · the projection is not taken from F alone. When finding the FDs that fall in a piece, it is not enough to look at the list in F and ask “are the attributes of this FD in the piece?”. You must also think of the FDs coming from $F^+$; the way to do this is to take the closure of every subset in the piece.

The BCNF decomposition algorithm

result := {R}
while there is a Ri in result that is not in BCNF:
    find an X -> Y that holds in Ri and where X is not a superkey
    replace Ri with  (X+ ∩ Ri)  and  Ri − (X+ − X)

In every split the intersection is X and X is the key of the first piece, so the result is always lossless. Preservation is not guaranteed.

Worked example. $R(A,B,C,D,E)$, $F = \{A \to B,\ BC \to D,\ D \to E\}$. A and C are not on the right, and $\{A,C\}^+$ = ABCDE: the only key is AC. At each step we choose the shortest violating left side.

ABCDE : A -> B violates.  A+ ∩ Ri = AB         →  AB  and  ACDE
AB    : BCNF
ACDE  : D -> E violates.  D+ ∩ Ri = DE         →  DE  and  ACD
DE    : BCNF
ACD   : projection AC -> D, AC is a key        →  BCNF
Result: AB, DE, ACD

Preservation check: $BC \to D$. B and C are not in the same piece, and with the projections $\{B,C\}^+ = \{B,C\}$. Lost. If you had started with $D \to E$ in the first step, you might have found a different result; decomposition is not unique, so write down the order you chose in the exam.

University example: wide(S, N, C, T, G) = (stu_id, stu_name, course_id, title, grade), $F = \{S \to N,\ C \to T,\ SC \to G\}$. The algorithm gives CT, NS and CGS: course(course_id, title), student(stu_id, stu_name), takes(stu_id, course_id, grade). This time all three FDs are preserved; this is the answer to why the tables we use in the course are split this way.

The 3NF synthesis algorithm

1. Find the canonical cover Fc of F
2. For every X -> Y in Fc, create a schema (X ∪ Y)
3. If no schema contains a candidate key of R, add a candidate key as a separate schema
4. Delete the schemas that are a subset of another schema

The result is a 3NF decomposition that is both lossless and dependency preserving.

The same example: $F_c = \{A \to B,\ BC \to D,\ D \to E\}$ (nothing is redundant). The schemas are AB, BCD, DE. None contains AC, so add AC. The result is AB, BCD, DE, AC. The chase test says lossless, and each of the three FDs is inside a piece. In this example all the pieces even came out as BCNF; this is not always the case.

BCNF or 3NF?

The classic dilemma: tutoring(stu_id, subject, tutor_id), $\text{tutor\_id} \to \text{subject}$, $\{\text{stu\_id, subject}\} \to \text{tutor\_id}$. BCNF decomposition gives (tutor_id, subject) and (stu_id, tutor_id). It is lossless, but the rule “a student has a single tutor in a subject” can no longer be checked in a single table. The designer often chooses to stay in 3NF and keep this rule enforceable.

Common mistakes