Does natural join distribute over set-difference?

Question

In other words, is it true that: r1 ⋈ (r2 - r3) = r1 ⋈ r2 - r1 ⋈ r3

where r1 r2 and r3 are relations

If it isn't what is the example?

Answer 1

Yes.

Take a tuple t, with all attributes of the JOIN. Let t1 be its "R1" part. Let t2 be its "R2" part (and since R2-R3 is a valid expression, it is also the "R3" part of t).

A tuple t appears in R1 JOIN (R2 MINUS R3) if and only if :

t1 appears in R1, AND t2 appears in R2, AND t2 does not appear in R3.

A tuple t appears in (R1 JOIN R2) MINUS (R1 JOIN R3) if and only if :

t1 appears in R1, AND t2 appears in R2, and (it is not the case that) (t1 appears in R1, AND t2 appears in R3).

since t1 must appear in R1, this reduces to :

t1 appears in R1, AND t2 appears in R2, and NOT (true AND t2 appears in R3).
t1 appears in R1, AND t2 appears in R2, and NOT (t2 appears in R3).

Compare with the first case and observe that the conditions are identical.

Another way of proving the property is by observing than (R2 MINUS R3) is equivalent to (R2 INTERSECT CMP(R3)), with CMP(R3) denoting the complement of R3 (with respect to the universal relation of its type), and then applying distributivity of JOIN OVER INTERSECTION.

Answer 2

I don't have an answer to the question asked, but even if it's true I don't believe the equivalence is symmetrical. Consider

r1 = (a1, a2)
r2 = (a1, a2, a3)
r3 = (a2, a3)

then r1 ⋈ r2 - r1 ⋈ r3 is possible because each operand is union-compatible, while r2 - r3 is not.