Suppose that two relations R(A, B) and S(A, B) have exactly the same schema.…
Suppose that two relations R(A, B) and S(A, B) have exactly the same schema.
Consider the following equalities in relational algebra. Which of the following equalities are true?
Answer: A. R ∩ S = R - (R - S); B. R ∩ S = S - (S - R); C. R ∩ S = R NATURAL JOIN S — Answer: The following equalities are true: R ∩ S = R - (R - S); R ∩ S = S - (S - R); R ∩ S = R NATURAL JOIN S. The equality with the Cartesian product is…
- A.
R ∩ S = R - (R - S)
- B.
R ∩ S = S - (S - R)
- C.
R ∩ S = R NATURAL JOIN S
- D.
R ∩ S = R x S
Attempted by 18 students.
Show answer & explanation
Correct answer: A, B, C
Answer: The following equalities are true: R ∩ S = R - (R - S); R ∩ S = S - (S - R); R ∩ S = R NATURAL JOIN S. The equality with the Cartesian product is false.
Proof that R ∩ S = R - (R - S): If x ∈ R ∩ S then x ∈ R and x ∈ S, so x ∉ (R - S), hence x ∈ R - (R - S). Conversely, if x ∈ R - (R - S) then x ∈ R and not(x ∈ R and x ∉ S). Since x ∈ R, we must have x ∈ S, so x ∈ R ∩ S. Therefore the sets are equal.
Proof that R ∩ S = S - (S - R): This is the symmetric argument of the previous item: membership in S but not in S - R forces membership in R, so the result is the intersection.
Reason that R ∩ S = R NATURAL JOIN S when schemas are identical: A natural join matches tuples on all common attributes. If the two relations have exactly the same attributes, a tuple appears in the natural join precisely when that same tuple is present in both relations. Thus the natural join returns exactly the intersection.
Why R ∩ S ≠ R × S in general: The Cartesian product forms combined tuples from R and S, not the tuples that appear in both relations. For example, let R = {(1,2)} and S = {(1,2)}. Then R ∩ S = {(1,2)} but R × S = {((1,2),(1,2))}, which has a different structure and meaning, so the equality fails.
A video solution is available for this question — log in and enroll to watch it.