CODEWITHSUNDEEP
databasejoinrelational-databaserelational-algebranatural-join
lebowski
lebowski

Reputation: 1051

Is Natural Join distributive over Union?

Given three relations R, S and T, is it true that:

R ⋈ (S U T) = (R ⋈ S) U (R ⋈ T)

If yes, can we prove it?

Upvotes: 2

Views: 1004

Answers (2)

dbilid
dbilid

Reputation: 277

Under Set semantics, as shown by the answer of Tipton, this holds, but under bag semantics, as they used by SQL it's not. Consider the counter-example:

    > create table R(A TEXT);
    Query executed in 0 min. 0 sec 5 msec.
    > create table S(A TEXT);
    Query executed in 0 min. 0 sec 1 msec.
    > create table T(A TEXT);
    Query executed in 0 min. 0 sec 2 msec.
    > insert into R values('a');
    Query executed in 0 min. 0 sec 1 msec.
    > insert into R values('a');
    Query executed in 0 min. 0 sec 0 msec.
    > insert into S values('a');
    Query executed in 0 min. 0 sec 1 msec.
    > insert into T values('a');
    Query executed in 0 min. 0 sec 1 msec.
    > select * from (select * from R JOIN (select * from S UNION select * from T) u ON R.A=u.A);
    a|a
    a|a
    --- [0|Column names ---
    [1|A [2|A:1 
    Query executed and displayed **2 rows** in 0 min. 0 sec 11 msec.
    > select * from R JOIN S ON R.A=S.A UNION select * from R JOIN T ON R.A=T.A;
    a|a
    --- [0|Column names ---
    [1|A [2|A 
    Query executed and displayed **1 row** in 0 min. 0 sec 20 msec.

Upvotes: 0

Euclid Ye
Euclid Ye

Reputation: 521

YES.

Suppose we have 3 relations R, S, T.

First of all, you should know that S and T have to be union compatible so as to perform union operation, which means two relations have same fields.

Prove left -> right:

Suppose a row r belongs to the set of left opeartion. Then, for those values originally from S or T, they must appear either in relation S or T. Without loss of generality, suppose they are from S. Then, row r belongs to R ⋈ S.

Prove right -> left:

Suppose a row r' belongs to the set of right opeartion. Then, r either belongs to R ⋈ S or R ⋈ T.

Without loss of generality, suppose r belongs to R ⋈ S. Then, for those values originally from S, it also belongs to a row in S U T.

Hence, r' belongs to R ⋈ (S U T) .

Therefore, the proposition is correct.

Upvotes: 2

Related Questions