Methods, systems, and apparatus, including computer programs encoded on computer storage media, for evaluating recursive predicates and exiversal predicates. One of the methods includes receiving an expression having an exiversal quantifier that specifies a condition x and a condition y. The expression is transformed into a second expression having multiple recursive calls, the second expression having a first non-negated term with a first recursive call in the condition y, and a second negated term with a second recursive call in the condition y. The second expression is evaluated using evaluation predicates that include a single delta predicate that replaces only the recursive call in the first non-negated term to identify data elements in the relation having at least one attribute satisfying the condition x and the condition y, and, for each attribute of the data element satisfying the condition x, the attribute also satisfies the condition y.
Please help me write a proper abstract based on the patent claims. CLAIM: 1. A computer-implemented method comprising: receiving an expression having a programming language construct representing an exiversal predicate having an exiversal quantifier, wherein the construct specifies a condition x and a condition y, wherein the condition y includes a recursive call to the expression; transforming the expression into a second expression having multiple recursive calls, the second expression having a first non-negated term with a first recursive call in the condition y, and a second negated term with a second recursive call in the condition y; generating evaluation predicates including a single delta predicate that replaces only the recursive call in the first non-negated term; and evaluating the second expression using the generated evaluation predicates to identify data elements in the relation having at least one attribute satisfying the condition x and the condition y, and, for each attribute of the data element satisfying the condition x, the attribute also satisfies the condition y. 2. The method of claim 1, wherein the condition y includes multiple recursive calls, and wherein generating the evaluation predicates comprises generating respective delta predicates for each recursive call occurring in the first non-negated term. 3. The method of claim 1, wherein transforming the expression into a second expression predicate having multiple recursive calls comprises: transforming the exiversal predicate into the following conjunction of existential terms: exists(i: x(i), y(i)) and not exists(i: x(i), not y(i)) and evaluating the conjunction of existential predicates to identify data elements in the relation satisfying the exiversal predicate. 4. The method of claim 1, wherein evaluating the second expression comprises repeatedly: using the single delta predicate to generate new tuples for a current iteration; and computing a relation for the current iteration, the relation including the new tuples for the current iteration and one or more tuples from a previous iteration, until no new tuples are generated for a current iteration. 5. The method of claim 4, wherein evaluating the second expression comprises evaluating the second expression without performing any iterations of naive evaluation. 6. The method of claim 1, wherein evaluating the expression comprises evaluating the second expression without performing staircase evaluation or naive evaluation. 7. A computer-implemented method comprising: receiving an expression representing a conjunction of terms matching the form of an exiversal term and identifying a relation of data elements over which to apply the expression, wherein each term in the conjunction of terms specifies a condition x and a condition y; determining that the condition y includes a recursive call to the expression; in response, generating evaluation predicates for the expression, including generating a single delta predicate that replaces only a recursive call in a particular term of the conjunction of terms; and evaluating the expression over the relation of data elements to identify each data element in the relation satisfying the conjunction, including repeatedly: using the single delta predicate to generate new tuples for a current iteration, and computing a relation for the current iteration, the relation including the new tuples for the current iteration and one or more tuples from a previous iteration, until no new tuples are generated for a current iteration. 8. The method of claim 7, wherein the conjunction of terms is a conjunction of a non-negated existential term and a negated existential term. 9. The method of claim 8, wherein the expression has the form: exists(i: x(i), y(i)) and not exists (i: x(i), not y(i)) wherein x(i) represents the condition x and y(i) represents the condition y. 10. The method of claim 8, wherein the particular term is the non-negated existential term, and wherein generating the single delta predicate comprises generating a delta predicate that replaces only a recursive call in the non-negated existential term. 11. The method of claim 7, wherein the conjunction of terms is a conjunction of a non-negated existential term and a term having a universal quantifier. 12. The method of claim 11, wherein the particular term is the non-negated existential term, and wherein generating the single delta predicate comprises generating a delta predicate that replaces only a recursive call in the non-negated existential term. 13. The method of claim 11, wherein the expression has the form: exists(i: x(i), y(i)) and forall(i: x(i): y(i)) wherein x(i) represents the condition x and y(i) represents the condition y. 14. The method of claim 7, wherein the condition y includes multiple recursive calls, and wherein generating the evaluation predicates comprises generating respective delta predicates for each recursive call occurring in the particular term of the conjunction of terms. 15. The method of claim 7, wherein evaluating the expression comprises evaluating the expression without performing any iterations of naive evaluation. 16. A system comprising: one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising: receiving an expression having a programming language construct representing an exiversal predicate having an exiversal quantifier, wherein the construct specifies a condition x and a condition y, wherein the condition y includes a recursive call to the expression; transforming the expression into a second expression having multiple recursive calls, the second expression having a first non-negated term with a first recursive call in the condition y, and a second negated term with a second recursive call in the condition y; generating evaluation predicates including a single delta predicate that replaces only the recursive call in the first non-negated term; and evaluating the second expression using the generated evaluation predicates to identify data elements in the relation having at least one attribute satisfying the condition x and the condition y, and, for each attribute of the data element satisfying the condition x, the attribute also satisfies the condition y. 17. The system of claim 16, wherein the condition y includes multiple recursive calls, and wherein generating the evaluation predicates comprises generating respective delta predicates for each recursive call occurring in the first non-negated term. 18. The system of claim 16, wherein transforming the expression into a second expression predicate having multiple recursive calls comprises: transforming the exiversal predicate into the following conjunction of existential terms: exists(i: x(i), y(i)) and not exists(i: x(i), not y(i)) and evaluating the conjunction of existential predicates to identify data elements in the relation satisfying the exiversal predicate. 19. The system of claim 16, wherein evaluating the second expression comprises repeatedly: using the single delta predicate to generate new tuples for a current iteration; and computing a relation for the current iteration, the relation including the new tuples for the current iteration and one or more tuples from a previous iteration, until no new tuples are generated for a current iteration. 20. The system of claim 19, wherein evaluating the second expression comprises evaluating the second expression without performing any iterations of naive evaluation. 21. The system of claim 16, wherein evaluating the expression comprises evaluating the second expression without performing staircase evaluation or naive evaluation. 22. A system comprising: one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising: receiving an expression representing a conjunction of terms matching the form of an exiversal term and identifying a relation of data elements over which to apply the expression, wherein each term in the conjunction of terms specifies a condition x and a condition y; determining that the condition y includes a recursive call to the expression; in response, generating evaluation predicates for the expression, including generating a single delta predicate that replaces only a recursive call in a particular term of the conjunction of terms; and evaluating the expression over the relation of data elements to identify each data element in the relation satisfying the conjunction, including repeatedly: using the single delta predicate to generate new tuples for a current iteration, and computing a relation for the current iteration, the relation including the new tuples for the current iteration and one or more tuples from a previous iteration, until no new tuples are generated for a current iteration. 23. The system of claim 22, wherein the conjunction of terms is a conjunction of a non-negated existential term and a negated existential term. 24. The system of claim 23, wherein the expression has the form: exists(i: x(i), y(i)) and not exists (i: x(i), not y(i)) wherein x(i) represents the condition x and y(i) represents the condition y. 25. The system of claim 23, wherein the particular term is the non-negated existential term, and wherein generating the single delta predicate comprises generating a delta predicate that replaces only a recursive call in the non-negated existential term. 26. The system of claim 22, wherein the conjunction of terms is a conjunction of a non-negated existential term and a term having a universal quantifier. 27. The system of claim 26, wherein the particular term is the non-negated existential term, and wherein generating the single delta predicate comprises generating a delta predicate that replaces only a recursive call in the non-negated existential term. 28. The system of claim 26, wherein the expression has the form: exists(i: x(i), y(i)) and forall(i: x(i): y(i)) wherein x(i) represents the condition x and y(i) represents the condition y. 29. The system of claim 22, wherein the condition y includes multiple recursive calls, and wherein generating the evaluation predicates comprises generating respective delta predicates for each recursive call occurring in the particular term of the conjunction of terms. 30. The system of claim 22, wherein evaluating the expression comprises evaluating the expression without performing any iterations of naive evaluation.