Normal form after decomposition of a relation

Question

I came across a text recently which claims that if we perform a lossless decomposition of a relation R into smaller relations R1 and R2, and if R is in 3NF, both R1 and R2 are 3NF.

I felt a bit suspicious regarding this claim, but couldn't find anything to prove this statement wrong.

Am I correct in thinking that this statement doesn't hold all the time, or Am I wrong? It would be really helpful if someone can correct me if I am wrong?

Thanks in advance!

Answer 1

I think you are wrong.

Here is a rough sketch of a proof (by contradiction) that the original claim is true.

Suppose that the claim is false: this means that R1 or R2 (or both) are not in 3NF. Without loss of generality, suppose that R1 is not in 3NF. This means that, among all the dependencies holding in R1, there is at least a dependency X → A in which X is not a superkey (and so it is neither a candidate key) and the attribute A is not prime.

Now consider the definition of lossless decomposition: for each possible valid istance r of R, we have that r = π_T1(r) ⨝ π_T2(r), where T1 are the attributes of R1 and T2 are the attributes of R2.

This means that each valid instance of R1 is a projection on the attributes T1 of some valid instance of R. But this implies that if X → A is valid in an instance r1 of R1, it will be also valid in an instance r of R obtained by joining r1 with some instance of R2 (because, for the definition of join, the tuples of r1 will appear in r unchanged, possibly repeated).

So this means that X → A is also valid in R, contradicting the initial hypothesis that R is in 3NF.