Chapter 7, Problem 16PE

Explanation of Solution

Ensuring a dependency-preserving decomposition into 3NF is a lossless decomposition:

• Let F be a set of functional dependencies which hold on a schema R.
• Let sigma={R₁,R₂,...,R_n} be a dependency-preserving 3NF decomposition of R.
• Let X be a candidate key for R.
• Consider a legal instance r of R. Let j=Project_X(r) join Project_R1(r) join Project_R2(r) ... Join Project_Rn(r).
• 1. ○ It is required to prove that r=j.
  2. ○ It is claimed that, t₁ and t₂ are two tuples, where t₁=t₂ such that t₁[X]=t₂[X].
  3. ○ The inductive argument is used for proving this claim.
  4. ○ 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'.
  5. ○ 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...