Decomposition and Schema Normalization

Question 1

What should good decomposition achieve?

Answer 1

minimize redundancy, avoid information loss (lossless-join), preserve the FDs (dependency preserving), ensure good query performance

Question 2

Lossless join

Answer 2

If for any initial instance R,

the decomposed instance R’ = R

Question 3

A decomposition is lossless-join iff at least one of the FDs in in F+

Answer 3

A1 ^ A2 -> A1

A1 ^ A2 -> A2

Question 4

A decomposition is dependency preserving if

Answer 4

by enforcing FD F1 over R1 and FD F2 over R2, we can enforce F over R

Question 5

Boyce Codd Normal Form (BCNF)

Answer 5

A relation is in BCNF if whenever X -> B is a non-trivial FD, then X is a superkey in R

Question 6

BCNF other definition

Answer 6

For ever attribute set X:
either X+ = X
or X+ = all attributes

Question 7

BCNF Decomposition Properties

Answer 7

BCNF decompostion:

• removes certain types of redundancy
• is a lossless join
• is not always dependency preserving

Question 8

3NF Definition

Answer 8

whenever X -> A, one of the following is true:
A in X (trivial FD)
X is a superkey
A is part of some key of R (prime attribute)

Question 9

3NF Characteristics

Answer 9

Lossless join and dependency preserving decomposition into a collection of 3NF relations is always possible.

Question 10

3NF Algorithm

Answer 10

Apply the algorithm for BCNF decomposition until all relations are in 3NF
compute a minimal basis F’ of F
For each non-preserved FD X-> A in F’, add a new relation R(X,A)

Question 11

Is normalization always good?

Answer 11

No, suppose A and B are always used together, but normalization says they should be in diff talbes > performance loss