# Questions Concerning the Chase Test

1. [5 Marks] Let R(A,B,C,D,E) be decomposed into relations with the following three set of attributes {A,B,C}, {B,C,D}, and {A,C,E}. For each of the following sets of FD's, use the chase test to tell whether the decomposition of R is lossless. For those that are not lossless, give an example of an instance of R that returns more than R when projected onto the decomposed relation and rejoined.

a. A→D, CD→E and E→D.

b. A→D, D→E and C→D.

For the question above, my work for each of the questions is below the concerns. Here are my main concerns:

1. Does the order in which you use the relations matter?
2. Can you end up with less tuples with the chase test?
3. Is my approach correct?

-----------------------Part A below----------------------------------

InitialTableau = T₁ ⋈ T₂ ⋈ T₂

``````+----+----+----+----+----+
| A  | B  | C  | D₁ | E₁ |
+----+----+----+----+----+
| A₂ | B  | C  | D  | E₂ |
+----+----+----+----+----+
| A  | B₂ | C  | D₂ | E  |
+----+----+----+----+----+
``````

-----------------------ANSWER TO QUESTIONS START NOW-----------------------

a) After changing the initial tableau in a way that ensures that the FD's given in the question are satisfied, we get the following tableau.

``````+----+----+----+----+----+
| A  | B  | C  | D₁ | E  |
+----+----+----+----+----+
| A₂ | B  | C  | D  | E₂ |
+----+----+----+----+----+
| A  | B₂ | C  | D₁ | E  |
+----+----+----+----+----+
``````
• Since we do not have an unsubscribed row, this relation is lossy/not lossless.

Example of an instance R (Were going to use the final tableau):

R₁(A,B,C)

``````+----+----+----+
| A  | B  | C  |
+----+----+----+
| A₂ | B  | C  |
+----+----+----+
| A  | B₂ | C  |
+----+----+----+
``````

R₂(B,C,D)

``````+----+----+----+
| B  | C  | D₁ |
+----+----+----+
| B  | C  | D  |
+----+----+----+
| B₂ | C  | D₁ |
+----+----+----+
``````

R₃(A,C,E)

``````+----+----+----+
| A  | C  | E₂ |
+----+----+----+
| A₂ | C  | E₂ |
+----+----+----+
| A  | C  | E  |
+----+----+----+
``````

After Joining the above relations, we get:

``````+----+----+----+----+----+
| A  | B  | C  | D₁ | E  |
+----+----+----+----+----+
| A  | B  | C  | D  | E  |
+----+----+----+----+----+
| A₂ | B  | C  | D₁ | E₂ |
+----+----+----+----+----+
| A₂ | B  | C  | D  | E₂ |
+----+----+----+----+----+
| A  | B₂ | C  | D  | E  |
+----+----+----+----+----+
``````
• since we have 2 more rows than the original tableau, this decomposition is not lossless.

b) After changing the initial tableau in a way that ensures that the FD's given in the question are satisfied, we get the following tableau.

``````+----+----+----+----+----+
| A  | B  | C  | D  | E  |
+----+----+----+----+----+
| A₂ | B  | C  | D  | E  |
+----+----+----+----+----+
| A  | B₂ | C  | D  | E  |
+----+----+----+----+----+
``````
• Since we have an unsubscribed row, this decomposition is lossless.

## 1 Answer

CONFIRMED FROM MY PROF THAT THESE ANSWERS ARE RIGHT

1. Let's start by creating a tableau for each relation, then joining them together, and running the chase test afterwards.

**T₁(R₁(A,B,C,......,)) = Tableau of relation R)**

T₁(R₁(A,B,C))

``````+----+----+----+----+----+
| A  | B  | C  | D₁ | E₁ |
+----+----+----+----+----+
``````

T₂(R₂(B,C,D))

``````+----+----+----+----+----+
| A₂ | B  | C  | D  | E₂ |
+----+----+----+----+----+
``````

T₂(R₂(A,C,E))

``````+----+----+----+----+----+
| A  | B₂ | C  | D₂ | E  |
+----+----+----+----+----+
``````

InitialTableau = T₁ ⋈ T₂ ⋈ T₂

``````+----+----+----+----+----+
| A  | B  | C  | D₁ | E₁ |
+----+----+----+----+----+
| A₂ | B  | C  | D  | E₂ |
+----+----+----+----+----+
| A  | B₂ | C  | D₂ | E  |
+----+----+----+----+----+
``````

-----------------------ANSWER TO QUESTIONS START NOW-----------------------

a) After changing the initial tableau in a way that ensures that the FD's given in the question are satisfied, we get the following tableau.

``````+----+----+----+----+----+
| A  | B  | C  | D₁ | E  |
+----+----+----+----+----+
| A₂ | B  | C  | D  | E₂ |
+----+----+----+----+----+
| A  | B₂ | C  | D₁ | E  |
+----+----+----+----+----+
``````

Since we do not have an unsubscribed row, this relation is lossy/not lossless.

Example of an instance R (We're going to use the final tableau)

R₁(A,B,C)

``````+----+----+----+
| A  | B  | C  |
+----+----+----+
| A₂ | B  | C  |
+----+----+----+
| A  | B₂ | C  |
+----+----+----+
``````

R₂(B,C,D)

``````+----+----+----+
| B  | C  | D₁ |
+----+----+----+
| B  | C  | D  |
+----+----+----+
| B₂ | C  | D₁ |
+----+----+----+
``````

R₃(A,C,E)

``````+----+----+----+
| A  | C  | E  |
+----+----+----+
| A₂ | C  | E₂ |
+----+----+----+
| A  | C  | E  |
+----+----+----+
``````

After Joining the above 3 relations, we get:

R(A,B,C,D,E)

``````+----+----+----+----+----+
| A  | B  | C  | D₁ | E  |
+----+----+----+----+----+
| A  | B  | C  | D  | E  |
+----+----+----+----+----+
| A₂ | B  | C  | D₁ | E₂ |
+----+----+----+----+----+
| A₂ | B  | C  | D  | E₂ |
+----+----+----+----+----+
| A  | B₂ | C  | D₁ | E  |
+----+----+----+----+----+
``````
• since we have 2 more rows than the original tableau, this decomposition is not lossless.

b) After changing the initial tableau in a way that ensures that the FD's given in the question are satisfied, we get the following tableau.

``````+----+----+----+----+----+
| A  | B  | C  | D  | E  |
+----+----+----+----+----+
| A₂ | B  | C  | D  | E  |
+----+----+----+----+----+
| A  | B₂ | C  | D  | E  |
+----+----+----+----+----+
``````
• Since we have an unsubscribed row, this decomposition is lossless.