BCNF Decompositions and Lossless joins for Databases

Question

Hey all I have an assignment that says:

Let R(ABCD) be a relation with functional dependencies A → B, C → D, AD → C, BC → A Which of the following is a lossless-join decomposition of R into Boyce-Codd Normal Form (BCNF)?

I have been researching and watching videos on youtube and I cannot seem to find how to start this. I think I'm supposed to break it down to subschemas and then fill out a table to find which one is lossless, but I'm having trouble getting started with that. Any help would be appreciated!

Answer 1

Your question

Which of the following is a lossless-join decomposition of R into Boyce-Codd Normal Form (BCNF)?

suggests that you have a set of options and you have to choose which one of those is a lossless decomposition but since you have not mentioned the options I would first (PART A) decompose the relation into BCNF ( first to 3NF then BCNF ) and then (PART B) illustrate how to check whether this given decomposition is a lossless-join decomposition or not. If you are just interested in knowing how to check whether a given BCNF decomposition is lossless or not jump directly to PART B of my answer.

PART A

To convert a relation R and a set of functional dependencies(FD's) into 3NF you can use Bernstein's Synthesis. To apply Bernstein's Synthesis -

• First we make sure the given set of FD's is a minimal cover
• Second we take each FD and make it its own sub-schema.
• Third we try to combine those sub-schemas

For example in your case:

R = {A,B,C,D}
FD's = {A->B,C->D,AD->C,BC->A}

First we check whether the FD's is a minimal cover (singleton right-hand side , no extraneous left-hand side attribute, no redundant FD)

• Singleton RHS: All the given FD's already have singleton RHS.
• No extraneous LHS attribute: None of the FD's have extraneous LHS attribute that needs to e removed.
• No redundant FD's: There is no redundant FD.

Hence the given set of FD's is already a minimal cover.

Second we make each FD its own sub-schema. So now we have - (the keys for each relation are in bold)

R₁={A,D,C}
R₂={B,C,A}
R₃={C,D}
R₄={A,B}

Third we see if any of the sub-schemas can be combined. We see that R₁ and R₂ already have all the attributes of R and hence R₃ and R₄ can be omitted. So now we have -

S₁ = {A,D,C}
S₂ = {B,C,A}

This is in 3NF. Now to check for BCNF we check if any of these relations (S₁,S₂) violate the conditions of BCNF (i.e. for every functional dependency X->Y the left hand side (X) has to be a superkey) . In this case none of these violate BCNF and hence it is also decomposed to BCNF.

PART B

When you apply Bernstein Synthesis as above to decompose R the decomposition is always dependency preserving. Now the question is, is the decomposition lossless? To check that we can follow the following method :

Create a table as shown in figure 1, with number of rows equal to the number of decomposed relations and number of column equal to the number of attributes in our original given R.

We put a in all the attributes that our present in the respective decomposed relation as in figure 1. Now we go through all the FD's {C->D,A->B,AD->C,BC->A} one by one and add a whenever possible. For example, first FD is C->D. Since both the rows in column C has a and there is an empty slot in second row of column D we put a a there as shown in the right part of the image. We stop as soon as one of the rows is completely filled with a which indicates that it is a lossless decomposition. If we go through all the FD's and none of the rows of our table get completely filled with a then it is a lossy decomposition.

Also, note if it is a lossy decomposition we can always make it lossless by adding one more relation to our set of decomposed relations consisting of all attributes of the primary key.

I suggest you see this video for more examples of this method. Also other way to check for lossless join decomposition which involves relational algebra.