Questions Concerning the Chase Test

You are asking:

I have a question, how did we know that R1 was not in BCNF and needs to be decomposed?

In the BCNF Decomposition Algorithm, when a relation is decomposed, one should find the dependencies of the subschemas, in this case R1(ACDE) and R2(BCD).

Let’s start from R1. To find the dependencies that hold in R1, one should actually project the original dependencies over the subschema, but, for simplicity, we would consider only those dependencies in which all the attributes are present in the subschema.

So, in R1 the dependencies {C D → E, D E → A} hold, C D is the key, and the algorithm continues by searching if the dependency D E → A violates the BCNF (of course the first one does not violates it since C D is the key of R1).

And it is easy to see that D E → A violates the BCNF since D E is not a superkey of the relation, so that now R1 must be decomposed.

So, the answer to your question is:

The algorithm knows that R1 is not in BCNF simply by checking if the dependencies that hold in R1 have a determinant which is not a superkey of R1.

From comments:

After the 1st decomposition, we should calculate the minimal keys again. Am I correct?

We know the key of R1 because of the way in which it is built (as the closure of the determinant of the original dependency CD -> E). We must find the key of R2, instead.

Which part of my answer needs to be corrected?

Simply cancel the sentence "Since, CD->E is already applied in a decomposition, we don't need to use that again. It will produce the same result.", and continue with "(1) Finding the violating FDs: DE->A is violating the BCNF and it is also not applied yet..."

I figured it out and got it confirmed by the lecture, hopefully this will help someone else:

i)

The key is {A,B,E}.

This means that FD1 and FD3 are both partial — but note that FD2 is not, because {D,E} is not a partial key. The decomposition creates one table for each of the FDs, and one for the PK FD:

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

-

ii) Using the above we can create the following tables:

        `R1                R2              R3`
| A  | B  | E  |   | A  | B  | C  |    | B  | D  |
| a1 | b1 | e1 |   | a1 | b1 | c1 |    | b1 | d1 | 
| a2 | b1 | e2 |   | a2 | b1 | c2 |    | b2 | d3 | 
| a2 | b2 | e2 |   | a2 | b2 | c1 |    

Joining R1 and R2 gives:

        R1R2                  R3
| A  | B  | E  | C  |    | B  | D  | 
| a1 | b1 | e1 | c1 |    | b1 | d1 | 
| a2 | b1 | e2 | c2 |    | b2 | d3 | 
| a2 | b2 | e2 | c1 | 

Joining R1R2 with R3:

| A  | B  | E  | C  | D  | 
| a1 | b1 | e1 | c1 | d1 | 
| a2 | b1 | e2 | c2 | d1 | 
| a2 | b2 | e2 | c1 | d3 |

which is equal to:

| A  | B  | C  | D  | E  |
| a1 | b1 | c1 | d1 | e1 |
| a2 | b1 | c2 | d1 | e2 |
| a2 | b2 | c1 | d3 | e2 |

Hence decomposition is lossles with respect to joins.