REPETITIONS AND PERMUTATIONS OF COLUMNS IN THE SEMIJOIN ALGEBRA

Codd defined the relational algebra [E.F. Codd, Commu-ni ca ti ons o f the AC M 13(1970) 377–387; E.F. Codd, Relational com-pleteness of data base sublanguages, in D a ta B a se System s, R. Rustin,Ed., Prentice-Hall (1972) 65–98] as the algebra with operations pro-jection, join, restriction, union and difference. His projection operatorcan drop, permute and repeat columns of a relation. This permutingand repeating of columns does not really add expressive power to therelational algebra. Indeed, using the join operation, one can rewriteany relational algebra expression into an equivalent expression whereno projection operator permutes or repeats columns. The fragment ofthe relational algebra known as the semijoin algebra, however, lacks afull join operation. Nevertheless, we show that any semijoin algebraexpression can still be simulated in a natural way by a set of expressionswhere no projection operator permutes or repeats columns