Re: How can I proove associtivity of natural in relational algebra?

From: Vadim Tropashko <>
Date: 22 Nov 2005 11:10:46 -0800
Message-ID: <>

Mikito Harakiri wrote:
> The other hint. Start with cartesian product (which is associative),
> and show that selection doesn't affect associativity.

I don't think this would work. Associativity of cartesian product is no more evident than associativity of natural join. Think about allegedly a simpler task of proving that cartesian product is commutative. The nontrivial part is that AxB is formally not the same as BxA, and yet, because there is a natual bijection between the 2 we consider them equivalent.

Next, what about the merge-select rule (the Alise book, p. 55)

replace sigma_F(sigma_F'(q)) by sigma_F/\F'(q)

which has to be used in order to step up from associativity of CP to associativity of natural join. Is it a RA axiom? What exactly is the set of axioms that defines RA?

To the original poster. If you are really interested in the subject (as opposed being time pressed with class assignment) google "relational lattice". Natural join (and union)associativity should be postulated for relational algebra, not proved. Received on Tue Nov 22 2005 - 20:10:46 CET

Original text of this message