4. The method of claim 1 , further comprising: receiving a query that references a variable having the algebraic data type; and computing one or more tuples that satisfy the query, wherein each of the one or more tuples that satisfies the query is an injector tuple defined by a respective injector relation of one of the alternative subtypes for the algebraic data type.
1. A computer-implemented method 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 the respective domain relation of 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.