TY - GEN

T1 - Foundations of aggregation constraints

AU - Ross, Kenneth A.

AU - Srivastava, Divesh

AU - Stuckey, Peter J.

AU - Sudarshan, S.

PY - 1994/1/1

Y1 - 1994/1/1

N2 - 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 axiom~tization 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.

AB - 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 axiom~tization 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.

UR - http://www.scopus.com/inward/record.url?scp=35048883202&partnerID=8YFLogxK

M3 - Conference Paper

AN - SCOPUS:35048883202

SN - 9783540586012

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 193

EP - 204

BT - Principles and Practice of Constraint Programming - 2nd International Workshop, PPCP 1994, Proceedings

A2 - Borning, Alan

PB - Springer

T2 - 2nd International Workshop on the Principles and Practice of Constraint Programming, PPCP 1994

Y2 - 2 May 1994 through 4 May 1994

ER -