Distribution, commutation and association in database queries

An image showing the commutativity of addition

Image via Wikipedia

Another reminder note.

The RDBMS query engine relies on these laws to build efficient queries:


Numbers may travel (commute)

a + b = b + a or in relational algebra A \Join B = B \Join A


Numbers may freely associate

(a + b) + c = a + (b + c) or in relational algebra (A \Join B) \Join C = A \Join (B \Join C)


Operators can be distributed

3 \times (4 + 5) = 3 \times 4 + 3 \times 5 or, in relational algebra \sigma(A \Join B) = \sigma(A) \Join \sigma(B)

A more general statement of these laws:

Commutative law: f(a, b) = f(b, a)
Associative law: f(a, f(b, c)) = f(f(a, b), c)
Distributive law: f(g(a,b)) = g(f(a,b))

Date has an excellent discussion of all this on pp 124 – 127 of SQL and Relational Theory: How to Write Accurate SQL Code