We consider implicit representation of an arbitrary family of relations on finite sets. We derive upper and lower bounds for the general cases and for a number of restricted subfamilies, in particular for sparse and symmetric relations, and for relations first-order definable from families for which labeling schemes are already known. Our work extends existing work on implicit representation of graphs in two ways: (i) the known upper and lower bounds for many standard families of graphs are special cases of the results we derive; (ii) we allow families of relations to relate elements on both distinct sets and on multiple copies of the same set, and for different relations in the same family to have different arities, and to be defined on distinct or overlapping sets. The present paper is the first to study bounds on the size of labeling schemes for relations (including graphs) defined from existing relations using basic operations such as first-order logic. The techniques used to prove new results in this setting may be of independent interest.