## Independence of Relational Operations

### September 4, 2012

Proving that standard relational algebra operations are independent is considered an exercise in standard database theory course. Here is extract from prof. Kolaitis slides:

Theorem: Each of the five basic relational algebra operations is

independent of the other four, that is, it cannot be expressed by a

relational algebra expression that involves only the other four.

Proof Sketch: (projection and cartesian product only)

Property of projection:

It is the only operation whose output may have arity smaller than its input.

Show, by induction, that the output of every relational algebra expression

in the other four basic relational algebra is of arity at least as big as the

maximum arity of its arguments.

Property of cartesian product:

It is the only operation whose output has arity bigger than its input.

Show, by induction, that the output of every relational algebra expression

in the other four basic relational algebra is of arity at most as big as the

maximum arity of its arguments.

Exercise: Complete this proof.

This seems convincing until we carry over this question to relational bilattice. Then it is evident that , that is *natural join*, *generalized union*, *negation*, and *inversion* are independent. Indeed, natural join and generalized union are monothonic on both attributes and tuples, so he proof sketch from relational algebra can be employed here as well. Next, negation is domain-dependent operations which can produce tuples not present in the original relation. Likewise, inversion is “attribute”-dependent operation which can add attributes not present in the original relation.

What about the second lattice structure, are those operations independent of these four? Outer union can be expressed via De Morgan’s law:

and likewise its lattice dual:

Next, there are 0-ary operations, that is constants `R00`

(aka `TABLE_DUM`

), `R01`

(aka `TABLE_DEE`

), `R10`

, and `R11`

(not to be confused with universal relation). The later three can be expressed in therms of the first one

so the question extends if the set is independent. It is instructive to compare our conjecture with Boolean Algebra. There are many independent sets of operations in BA, the most ubiquitous being . Then, boolean constants are expressible in terms of those, e.g.:

Here is similar relational lattice expression

To conclude, relational algebra cast in genuine algebraic shape contains a set of four independent operations.