## 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 $\{ \wedge,\vee,\lhd NOT \rhd, \lhd INV \rhd \}$ , 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:
$x \lhd OR \rhd y = \lhd NOT \rhd (\lhd NOT \rhd x \wedge \lhd NOT \rhd y )$
and likewise its lattice dual:
$\lhd NOT \rhd (\lhd NOT \rhd x \vee \lhd NOT \rhd y )$

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

$R10 = \lhd INV \rhd R00$
$R01 = \lhd NOT \rhd R00$
$R11 = \lhd INV \rhd \lhd NOT \rhd R00$

so the question extends if the set $\{ \wedge,\vee,\lhd NOT \rhd, \lhd INV \rhd, R00 \}$ 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 $\{ \wedge,\vee,\lhd NOT \rhd \}$. Then, boolean constants are expressible in terms of those, e.g.:
$0 = \lhd NOT \rhd x \wedge x$
Here is similar relational lattice expression
$R00 = \lhd NOT \rhd(x \vee \lhd NOT \rhd(x \vee \lhd INV \rhd x))$

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