Foundations of aggregation constraints.
Kenneth A. Ross, Divesh Srivastava, Peter J. Stuckey and S. Sudarshan.
We introduce a new constraint domain, aggregation constraints,
that is useful in database query languages, and in constraint
logic programming languages that incorporate aggregate functions.
We formally study the fundamental problem of determining if a
conjunction of aggregation constraints is satisfiable, and show
that, for many classes of aggregation constraints, the problem is
undecidable. We describe a complete and minimal axiomatization
of aggregation constraints, for the SQL aggregate functions min,
max, sum, count and average, over a non-empty, finite multiset
on several domains. This axiomatization helps identify classes
of aggregation constraints for which the satisfiability check is
efficient. We present a polynomial-time algorithm that directly
checks for satisfiability of a conjunction of aggregation range
constraints over a single multiset; this is a practically useful
class of aggregation constraints. We discuss the relationships
between aggregation constraints over a non-empty, finite multiset
of reals, and constraints on the elements of the multiset. We
show how these relationships can be used to push constraints
through aggregate functions to enable compile-time optimization
of database queries involving aggregate functions and constraints.