Prove that the loop in the BCNF decomposition algorithm has the property that the database schema at each subsequent iteration has strictly fewer FDs that violate BCNF than has the schema in the previous iteration.

What will be an ideal response?

Let S = (S; F) be a schema that is not in BCNF. First, we have to clarify which sets of FDs possess the properties stated in the exercise. Here we are talking about the set of all entailed FDs, not the FDs in F. It is easy to ?nd examples where the number of
violating FDs can increase temporarily if we were just looking at the FDs in F rather than F+.
To prove the required result, observe that during each iteration, when there is an FD X ? Y , which violates BCNF, the algorithm decomposes the original schema S = (S; F) into S1=(XY ; F1) and S2=(S ? (Y ? X ); F2). The set of FDs in F1+ ? F2+ is a subset of F+, so it does not have any additional FDs that violate BCNF. Moreover, X ? Y is in F1, but not in F2, and it no longer violates BCNF, since X is a superkey in S1. Therefore the number of violating FDs has decreased.
Note that both S1 and S2 can have other FDs that still violate BCNF, so the decomposition process must continue until none is left.