Differential recursive evaluation of recursive aggregates
Methods, systems, and apparatus, including computer programs encoded on computer storage media, for performing differential recursive evaluation of recursive aggregates. One of the methods includes receiving an original recursive expression that defines tuples belonging to an output relation, wherein the original recursive expression has a recursive aggregation construct, the recursive aggregation construct having a range and a recursive term. An aggregates delta rule is applied to the initial delta expression to generate a final delta expression having an existential term and a gamma term. The existential term is evaluated to generate tuples related by the range and tuples in the delta relation, and the aggregation construct is evaluated using tuples generated by the existential term as the range of the aggregation construct. The output relation is updated including adding to the output relation any tuples newly generated by evaluating the final delta expression.
1. 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 original recursive expression that defines tuples belonging to an output relation, wherein the original recursive expression has a recursive aggregation construct, the recursive aggregation construct having a range and a recursive term;
generating an initial delta expression from the original recursive expression;
generating a final delta expression including repeatedly applying one or more differential rules to the initial delta expression, including applying an aggregates delta rule to generate a conjunction of:
(i) an existential term having a subterm that is a conjunction of the range and a delta term that is the recursive term of the aggregation construct, and
(ii) a gamma term having a subterm that is the aggregation construct;
evaluating the original recursive expression on an initial condition to generate one or more tuples;
computing an initial delta relation as a difference between the one or more tuples and the initial condition; and
until the final delta expression generates no new tuples, performing operations comprising:
evaluating the existential term to generate tuples related by the range and tuples in the delta relation,
evaluating the aggregation construct using tuples generated by the existential term as the range of the aggregation construct, and
updating the output relation including adding to the output relation any tuples newly generated by evaluating the final delta expression.
2. The system of claim 1 , wherein evaluating the aggregation construct comprises evaluating the aggregation construct if and only if the existential term generates one or more tuples.
3. The system of claim 2 , wherein the operations further comprise evaluating the existential term before the aggregation construct.
4. The system of claim 1 , wherein the operations further comprise:
applying an aggregates epsilon rule to the initial delta expression to generate an epsilon expression having a conjunction of:
(i) an existential term having a subterm that is a conjunction of the range and an epsilon term having a subterm that is the recursive term of the aggregation construct, and
(ii) a gamma term having a subterm that is the aggregation construct.
5. The system of claim 4 , wherein updating the output relation comprises evaluating the epsilon expression and removing from the output relation any tuples generated by the final epsilon expression.
6. The system of claim 1 , wherein the original recursive expression defines a height, a depth, or a number of nodes in a tree-structured graph.
7. A computer-implemented method comprising:
receiving an original recursive expression that defines tuples belonging to an output relation, wherein the original recursive expression has a recursive aggregation construct, the recursive aggregation construct having a range and a recursive term;
receiving an original recursive expression that defines tuples belonging to an output relation, wherein the original recursive expression has a recursive aggregation construct, the recursive aggregation construct having a range and a recursive term;
generating an initial delta expression from the original recursive expression;
generating a final delta expression including repeatedly applying one or more differential rules to the initial delta expression, including applying an aggregates delta rule to generate a conjunction of:
(i) an existential term having a subterm that is a conjunction of the range and a delta term that is the recursive term of the aggregation construct, and
(ii) a gamma term having a subterm that is the aggregation construct;
evaluating the original recursive expression on an initial condition to generate one or more tuples;
computing an initial delta relation as a difference between the one or more tuples and the initial condition; and
until the final delta expression generates no new tuples, performing operations comprising:
evaluating the existential term to generate tuples related by the range and tuples in the delta relation,
evaluating the aggregation construct using tuples generated by the existential term as the range of the aggregation construct, and
updating the output relation including adding to the output relation any tuples newly generated by evaluating the final delta expression.
8. The method of claim 7 , wherein evaluating the aggregation construct comprises evaluating the aggregation construct if and only if the existential term generates one or more tuples.
9. The method of claim 8 , further comprising evaluating the existential term before the aggregation construct.
10. The method of claim 7 , further comprising:
applying an aggregates epsilon rule to the initial delta expression to generate an epsilon expression having a conjunction of:
(i) an existential term having a subterm that is a conjunction of the range and an epsilon term having a subterm that is the recursive term of the aggregation construct, and
(ii) a gamma term having a subterm that is the aggregation construct.
11. The method of claim 10 , wherein updating the output relation comprises evaluating the epsilon expression and removing from the output relation any tuples generated by the final epsilon expression.
12. The method of claim 7 , wherein the original recursive expression defines a height, a depth, or a number of nodes in a tree-structured graph.
13. 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 original recursive expression that defines tuples belonging to an output relation, wherein the original recursive expression has a recursive aggregation construct, the recursive aggregation construct having a range and a recursive term;
generating an initial delta expression from the original recursive expression;
generating a final delta expression including repeatedly applying one or more differential rules to the initial delta expression, including applying an aggregates delta rule to generate a conjunction of:
(i) an existential term having a subterm that is a conjunction of the range and a delta term that is the recursive term of the aggregation construct, and
(ii) a gamma term having a subterm that is the aggregation construct;
evaluating the original recursive expression on an initial condition to generate one or more tuples;
computing an initial delta relation as a difference between the one or more tuples and the initial condition; and
until the final delta expression generates no new tuples, performing operations comprising:
evaluating the existential term to generate tuples related by the range and tuples in the delta relation,
evaluating the aggregation construct using tuples generated by the existential term as the range of the aggregation construct, and
updating the output relation including adding to the output relation any tuples newly generated by evaluating the final delta expression.
14. The computer program product of claim 13 , wherein evaluating the aggregation construct comprises evaluating the aggregation construct if and only if the existential term generates one or more tuples.
15. The computer program product of claim 14 , wherein the operations further comprise evaluating the existential term before the aggregation construct.
16. The computer program product of claim 13 , wherein the operations further comprise:
applying an aggregates epsilon rule to the initial delta expression to generate an epsilon expression having a conjunction of:
(i) an existential term having a subterm that is a conjunction of the range and an epsilon term having a subterm that is the recursive term of the aggregation construct, and
(ii) a gamma term having a subterm that is the aggregation construct.
17. The computer program product of claim 16 , wherein updating the output relation comprises evaluating the epsilon expression and removing from the output relation any tuples generated by the final epsilon expression.
18. The computer program product of claim 13 , wherein the original recursive expression defines a height, a depth, or a number of nodes in a tree-structured graph.