0

This is a practice question for a relational algebra question which I don't understand.

Consider two relations $R(A, B)$ and $S(B,C)$. Which of the following relational algebra expressions is not equivalent to the others?

  1. $\pi_{R.A, R.B} (R \Join S)$
  2. $R \Join \pi_{S.B}(S)$
  3. $R \cap (\pi_{A} (R) \times \pi_B (S))$
  4. None, they are all equivalent.

I think 1 yeilds: $X_1(C)$

I think 2 yields $\emptyset$.

I am unsure about 3.

But the answer is that they are all equivalent!

jaynp
  • 2,151

1 Answers1

3

They are indeed all equivalent.

For the first:

  • $R \Join S = \{ (a,b,c) \in A \times B \times C \mid (a,b) \in R \land (b,c) \in S \}$. I have assumed here that the join is on $B$, there being no alternative to join on.
  • $\pi_{A,B} (R \Join S) = \{ (a,b) \in A \times B \mid (a,b) \in R \land \exists c \in C : (b,c) \in S \}$. Projecting the previous set on $A \times B$.

And the second:

  • $\pi_{B}(S) = \{ b \in B \mid \exists c \in C: (b,c) \in S \}$. Projection of $S$ on $B$.
  • $R \Join \pi_{B}(S)$ $=$ $\{ (a,b) \in A \times B \mid (a,b) \in R \land b \in \pi_{B}(S) \}$ $=$ $\{ (a,b) \in A \times B \mid$ $ (a,b) \in R \land \exists c \in C : (b,c) \in S \}$. Again, I have assumed the join is on $B$.

And the third:

  • $\pi_A(R) = \{ a \in A \mid \exists b \in B : (a,b) \in R \}$. Projection of $R$ on $A$.
  • $\pi_B(S) = \{ b \in B \mid \exists c \in C : (b,c) \in S \}$. Projection of $S$ on $B$.
  • $\pi_A(R) \times \pi_B(S) = \{ (a,b) \in A \times B \mid \exists b' \in B : (a,b') \in R \ \land \exists c \in C : (b,c) \in S \}$
  • $R \cap (\pi_A(R) \times \pi_B(S)) = \{ (a,b) \in A \times B \mid (a,b) \in R \land \exists c \in C : (b,c) \in S \}$. Note that the $\exists b'$-clause from the previous line is implied by $(a,b) \in R$.

So all three are equal to $\{ (a,b) \in A \times B \mid (a,b) \in R \land \exists c \in C : (b,c) \in S \}$.

Magdiragdag
  • 15,049