# Database Theory - Does the dependency preservation and lossless join properties hold for every decomposition of a relation into 3NF?

I was reading Database Systems, 6th ed by Ramez Elmasri and Shamkant Navathe. In the textbook they make a claim (in Chapter 15, section 15.2 Properties of Relational Decompositions) which I quote below:

Claim 1. It is always possible to find a dependency-preserving decomposition $$D$$ with respect to $$F$$ [$$F$$ is the set of FDs of a relation $$R$$] such that each relation $$R_i$$ in $$D$$ is in 3NF

I have a few questions regarding this.

1. Is it possible to have multiple (different) decompositions of a relation into 3NF, as the claim seems to imply?

2. Is it the case that every decomposition (assuming the answer to first is Yes) of a relation into 3NF is dependency preserving? If not, please provide an example where a decomposition into 3NF does not uphold the dependency preserving property. Also, what about lossless join property?

Thanks!

1. Is it possible to have multiple (different) decompositions of a relation into 3NF, as the claim seems to imply?

Yes, consider for instance the relation schema R(A, B, C, D), with F, a cover of the functional dependencies holding in R, equal to:

A → B
C A → D
D → A


Both the decomposition:

R1(A B)
R2(A D)
R3(C D)


and

R1(A B)
R2(A C D)


are in 3NF (actually the first is also in BCNF).

1. Is it the case that every decomposition (assuming the answer to first is Yes) of a relation into 3NF is dependency preserving?

No, in the first decomposition the functional dependency AC → D is not preserved. Note that both decompositions are lossless (in general, there is no interest in lossy decompositions).

Final note: since there are different possible decompositions, these and their properties depends on the algorithm used to find them. For instance, the classical “analysis” algorithm for BCNF is guaranteed to produce a lossless decomposition, but it is not guaranteed to preserve the dependencies, while the classical “synthesis” algorithm to produce the 3NF is guaranteed to be lossless and preserve the dependencies, as well (but it could find a decomposition in which not all the anomalies are eliminated).

• Hey! Thanks for clearing that up. Can you please provide a formal proof for the claim, or provide some links? Also, can you suggest some books that have in-depth coverage (I have read Korth, so I am comparing with it) regarding normal forms and related theorems (like the one I mentioned in the question) ? Nov 10, 2019 at 12:13
• For the point 1, the proof is given by the example. For the second point I do not know if every possibile decomposition in 3NF has always the property of preserving the dependencies (even if I suspect that this is true). What is sure is that the synthesis algorithm produces a decomposition that preserves the dependencies (and you can read the details for instance in: Bernstein, Philip A. “Synthesizing Third Normal Form Relations from Functional Dependencies.” ACM Transactions on Database Systems 1, no. 4 (1976): 277–298). Nov 10, 2019 at 16:21
• Books that go into details of the normalization theory: “Maier, D. (1983). The Theory of Relational Databases. Computer Science Press, Rockville, Maryland.” “Mannila, H. and Räihä, K. (1992). The Design of Relational Databases. Addison- Wesley, Reading, Massachusetts.” “Abiteboul, S., Hull, R., and Vianu, V. (1995). Database Foundations. Addison-Wesley, Reading, Massachusetts.” Nov 10, 2019 at 16:24