0
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just one followup question.. Is there a possibility that R1 and R2 can be in a higher normal form than R upon decomposition? $\endgroup$ – Abhilash Mishra Jan 16 at 2:35
  • $\begingroup$ @AbhilashMishra, yes it is possible. Consider for istance R(ABCD) with {A → C, AB → BCD, BC → A} and the decomposition R1(AC), and R2(ABD}. The original schema is in 3NF, the decomposed relations are in BCNF. $\endgroup$ – Renzo Jan 16 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.