Codd defined the relational algebra [E.F. Codd, Communications of the ACM13 (1970) 377–387;
E.F. Codd, Relational completeness of data base sublanguages, in Data Base Systems, R. Rustin, Ed.,
Prentice-Hall (1972) 65–98] as the
algebra with operations projection, join, restriction, union and
difference. His projection operator can drop, permute and repeat
columns of a relation. This permuting and repeating of columns does
not really add expressive power to the relational algebra. Indeed,
using the join operation, one can rewrite any relational algebra
expression into an equivalent expression where no projection
operator permutes or repeats columns. The fragment of the relational
algebra known as the semijoin algebra, however, lacks a full join
operation. Nevertheless, we show that any semijoin algebra
expression can still be simulated in a natural way by a set of
expressions where no projection operator permutes or repeats
columns.