Abstract. We study algebras whose elements are relations, and the operations are natural "manipulations" of relations. This area goes back to 140 years ago to works of de Morgan, Peirce, Schr\"oder. Well known examples of such kinds of algebras are the varieties RCA_n of cylindric algebras of n-ary relations, RPEA_n of polyadic equality algebras of n-ary relations, and RRA of binary relations with composition. We prove that any axiomatization, say E, of RCA_n has to be very complex in the following sense: for every natura number k there is an equation in E containing more than k distinct variables and all the operation symbols, if n>2 is finite. Completely analogous statement holds for the case when n is infinite. This improves Monk's famous non-finitizability theorem for which we give here a simple proof. We prove analogous nonfinitizability properties of the larger varieties SNr_nCA_{n+k}. We prove that the complementation-free subreducts of RCA_n do not form a variety. We also investigate the reason for this "non-finite axiomatizability" behaviour of RCA_n. We look at all the possible reducts of RCA_n and investigate which are finitely axiomatizable. We obtain several positive results in this direction. Finally, we summarize the results and remaining questions on a figure. We carry through the same programme for RPEAN_n and for RRA. By looking into the reducts we also investigate what other kinds of natural algebras of relations are possible with more positive behaviour than that of the well known ones. Our investigations have direct consequences for the logical properties of the n-variable fragment L_n of first order logic. The reason for this is that RCA_n and RPEAN_n are the natural algebraic counterparts of L_n while the varieties SNr_nCA_{n+k} are in connection with the proof theory of L_n.