Chapter 7, Problem 35E

Explanation of Solution

Ensuring that the resulting decomposition is lossless:

• Instead of using BCNF, it is possible to have a lossless decomposition into 3NF itself.
• For this, it is required that one schema at least should have a candidate key for the schema that is being composed.
• The set of functional dependencies F on a schema R is considered.
• The decomposition of R which is dependency-preserving, sigma={R₁,R₂,...,R_n} is assumed.
• Suppose X is a candidate key for R and a legal instance of R is r.
• Suppose j=Project_X(r) join Project_R1(r) join Project_R2(r) ... Join Project_Rn(r).
• To prove that r=j, it is claimed that, t₁ and t₂ are two tuples, where t₁=t₂ such that t₁[X]=t₂[X].
• The inductive argument is used for proving this claim.
• Let F'=F₁ union F₂ union ... union F_n, where each F_i is the restriction of F to the schema R_i in sigma. Closure of X is computed under F'.
• Induction is applied the number of times that the for loop in the algorithm executes.

Basis:

In the first step of the algorithm, result is assigned to X, and hence given that t₁[X]=t₂[X], it is known that t₁[result]=t₂[result] is true.

Induction Step:

• Let t₁[result]=t₂[result] be true at the end of the k^th execution of the for loop...