Recursive aggregates

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 program input specifying an aggregation function agg having an input type and an output type, a relation s that has a domain and a range, wherein s represents one or more entities to be aggregated over, and a relation t that is a relation from the range of s to the input type of the aggregation function agg;

evaluating an aggregation construct agg* to calculate a relation between the domain of s and the output type of the agg function according to

agg*( s,t )={( m ,agg( n ))|∃ d :( m,d )ε s,nεπ{|t ( y )| yεs ( m )|}}

wherein agg* returns a relation and is monotonic in the relation t;

receiving program input in which the aggregation construct agg* is within a recursive term of a recursive relation definition; and

evaluating the recursive relation definition.

2. The system of claim 1 , wherein the aggregation function agg is a sum, average, count, min, max, product, or concatenation function.

3. The system of claim 1 , wherein the program input comprises an expression in a data language that uses fixed point semantics.

4. The system of claim 3 , wherein the data language is SQL or Datalog.

5. The system of claim 1 , wherein receiving program input specifying an aggregation function agg having an input type and an output type comprises:

receiving program input comprising language elements specifying, explicitly or implicitly, the aggregation construct for the aggregation function agg, the aggregation function agg having multiple input types, and a relation t that is a relation from the range of s to the multiple input types of the aggregation function agg.

6. The system of claim 5 , wherein the aggregation function agg is a sum, average, count, min, max, product, or concatenation function.

7. The system of claim 5 , wherein the program input comprises an expression in a data language that uses fixed point semantics.

8. The system of claim 7 , wherein the data language is SQL or Datalog.

9. The system of claim 1 , wherein receiving program input specifying an aggregation function agg having an input type and an output type comprises:

receiving program input that explicitly specifies the aggregation function agg, the relation s, the relation t, and the aggregation construct agg*.

10. 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 program input specifying an aggregation function agg and arguments for an aggregation construct agg* for the aggregation function agg, wherein the aggregation construct agg* is within a recursive term of a recursive relation definition, the arguments including, explicitly or implicitly:

<to_agg>, a variable that will contain values to be aggregated;

<variables>, one or more variables that are local to the expressions <range> and <term>;

<range>, a constraint on the values of the variables <variables> that defines a relation s, wherein the domain of s is free variables and the range of s is variables listed in <variables>; and

<term>, a constraint that constrains <to_agg> to values that will be aggregated, which defines a relation t that has a domain and a range, wherein the domain of t is the variables listed in <variables> and the range of t is <to_agg>; and

evaluating the recursive relation definition, including evaluating the aggregation construct agg* for the aggregation function agg according to the semantics

agg*( s,t )={( m ,agg( n ))|∃ d :( m,d )ε s,nεπ{|t ( y )| yεs ( m )|}}

wherein agg* returns a relation and is monotonic in the relation t.

11. The system of claim 10 , wherein the agg function is a sum, average, count, min, max, product, or concatenation function.

12. The system of claim 10 , wherein the program input comprises an expression in a data language that used fixed point semantics.

13. The system of claim 10 , wherein the operations further comprise:

receiving program input specifying <to_agg> explicitly.

14. The system of claim 10 , wherein receiving program input specifying arguments for the aggregation construct agg* comprises receiving arguments that explicitly include <to_agg>, <variables>, <range>, and <term>.

15. One or more non-transitory computer-readable storage media encoded with instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:

receiving input specifying, explicitly or implicitly, an aggregation function agg having an input type and an output type, a relation s that has a domain and a range, wherein s represents one or more entities to be aggregated over, and a relation t that is a relation from the range of s to the input type of the aggregation function agg; and

evaluating an aggregation construct agg* to calculate a relation between the domain of s and the output type of the aggregation function agg according to

agg*( s, t )={( m ,agg( n ))|∃ d :( m,d )ε s,nεπ{|t ( y )| yεs ( m )|}}

wherein agg* returns a relation and is monotonic in the relation t;

receiving input in which the aggregation construct agg* is within a recursive term of a recursive relation definition; and

evaluating the recursive relation definition.

16. The one or more non-transitory computer-readable storage media of claim 15 , wherein the aggregation function agg is a sum, average, count, min, max, product, or concatenation function.

17. The one or more non-transitory computer-readable storage media of claim 15 , wherein the input comprises an expression in a data language that uses fixed point semantics.

18. The one or more non-transitory computer-readable storage media of claim 17 , wherein the data language is SQL or Datalog.

19. The one or more non-transitory computer-readable storage media of claim 15 , wherein receiving program input specifying an aggregation function agg having an input type and an output type comprises:

receiving program input that explicitly specifies the aggregation function agg, the relation s, the relation t, and the aggregation construct agg*.

20. One or more non-transitory computer-readable storage media encoded with instruction that, when executed by one or more computers, cause the one or more computers to perform operations comprising:

receiving program input specifying an aggregation function agg and arguments for an aggregation construct agg* for the aggregation function agg, wherein the aggregation construct agg* is within a recursive term of a recursive relation definition, the arguments including, explicitly or implicitly:

<to_agg>, a variable that will contain values to be aggregated;

<variables>, one or more variables that are local to the expressions <range> and <term>;

<range>, a constraint on the values of the variables <variables> that defines a relation s, wherein the domain of s is free variables and the range of s is variables listed in <variables>; and

<term>, a constraint that constrains <to_agg> to values that will be aggregated, which defines a relation t that has a domain and a range, wherein the domain of t is the variables listed in <variables> and the range of t is <to_agg>; and

evaluating the recursive relation definition, including evaluating the aggregation construct agg* for the aggregation function agg according to the semantics

agg*(s, t)={(m, agg(n))|∃d:(m, d)εs, nεn {|t(y)|yεs(m)|}} wherein agg* returns a relation and is monotonic in the relation t.

21. The one or more non-transitory computer-readable storage media of claim 20 , wherein the agg function is a sum, average, count, min, max, product, or concatenation function.

22. The one or more non-transitory computer-readable storage media of claim 20 , wherein the program input comprises an expression in a data language that uses fixed point semantics.

23. The one or more non-transitory computer-readable storage media of claim 20 , wherein the operations further comprise:

receiving program input specifying <to_agg> explicitly.

24. The one or more non-transitory computer-readable storage media of claim 20 , wherein receiving program input specifying arguments for the aggregation construct agg* comprises receiving arguments that explicitly include <to_agg>, <variables>, <range>, and <term>.