24. The computer program product of claim 17 , wherein generating respective domain relations using definitions of each of the alternative subtypes comprises evaluating the definition of the alternative subtype as a predicate in an underlying programming language.
17. A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising: receiving an expression in a database query language, the expression having a programming language construct representing an algebraic data type, wherein the expression specifies two or more alternative subtypes, and wherein a particular alternative subtype of the two or more alternative subtypes is a recursively defined subtype; generating respective domain relations using definitions of each of the alternative subtypes within the expression, wherein each domain relation for each alternative subtype has domain tuples belonging to the alternative subtype, including generating a recursively defined domain relation for the recursively defined alternative subtype and performing one or more iterations of recursive evaluation for the recursively defined domain relation to generate one or more new domain tuples belonging to the recursively defined domain relation; generating respective domain id relations for each of the domain relations, wherein each domain id relation for each domain relation of each alternative subtype defines uniquely identified tuples that each assign a unique domain identifier to each of the domain tuples belonging to each alternative subtype, including performing, for each domain tuple of one or more new domain tuples generated for the recursively defined domain relation, operations comprising: determining that the elements of the new domain tuple are not represented in a cache of keys; and in response, generating a new domain identifier for the new domain tuple and adding a new domain id tuple to the domain id relation, the new domain id tuple having all elements of the new domain tuple and the new domain identifier; generating a union relation for the algebraic data type, wherein the union relation assigns a respective branch identifier to each of the two or more alternative subtypes and defines union tuples that each have a domain identifier of a domain tuple and a branch identifier of a subtype to which the domain tuple belongs; assigning unique union identifiers for union tuples belonging to the union relation; and generating respective injector relations for each of the alternative subtypes, wherein each injector relation for each alternative subtype defines, for a particular domain tuple of an alternative subtype, an injector tuple having elements from the particular domain tuple and a union identifier corresponding to the particular domain tuple.