1. A computer-implemented method comprising: receiving a request to compute identifiers for tuples of one or more recursively defined relations; and performing the following operations until no new tuples are generated for any of the one or more recursively defined relations: selecting one or more of the recursively defined relations to evaluate, performing one or more iterations of recursive evaluation for each of the selected one or more relations, computing respective keys for each tuple of any new tuples, wherein each key for each tuple is computed using each element of one or more elements of the tuple, determining, for each key computed for each new tuple, whether the key occurs in a respective cache of keys for a relation of the tuple, for each key that occurs in the cache of keys, obtaining a tuple for the key from the cache and adding the obtained tuple to a new relation; for each key that does not occur in the cache of keys, generating a new identifier for the key, adding, to a new relation for each key of each tuple of any keys that do not occur in the cache of keys for a relation, a new tuple comprising (1) elements of the tuple and (2) the new identifier for the key, and adding each key for each new tuple that does not occur in the cache of keys for the relation of the tuple to the cache of keys for the relation.