DIFFERENTIAL RECURSIVE EVALUATION

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for performing differential recursive evaluation. One of the methods includes receiving an original recursive expression that defines tuples belonging to an output relation. A final delta expression is generated including repeatedly applying one or more delta rules to the initial delta expression, wherein the final delta expression has at least one call to a delta relation that represents tuples generated by the final delta expression on a previous iteration. Until the final delta expression generates no new tuples, the final delta expression is evaluated using the tuples computed by the final delta expression on the previous iteration wherever the call to the delta relation occurs and the output relation is updated including adding to the output relation any tuples newly generated by evaluating the final delta expression.