Foundations of aggregation constraints.
Kenneth A. Ross, Divesh Srivastava, Peter J. Stuckey and S. Sudarshan.
We introduce a new constraint domain, aggregation constraints,
which is useful in database query languages, and in constraint
logic programming languages that incorporate aggregate functions.
We study the fundamental problem of checking if a conjunction of
aggregation constraints is solvable, and present undecidability
results for many different classes of aggregation constraints.
We describe a complete and minimal axiomatization of the class
of aggregation constraints over finite multisets of reals, which
permits a natural reduction from the class of aggregation
constraints to the class of mixed integer/real, non-linear
arithmetic constraints. We then present a polynomial-time
algorithm that directly checks for solvability of a useful class
of aggregation constraints, where the reduction-based approach
does not lead to efficient checks for solvability.