Equivalence between relational algebra statements

Question

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!

Answer 1

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 \}$.