Abstract
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.
Original language | English |
---|---|
Title of host publication | Principles and Practice of Constraint Programming - 2nd International Workshop, PPCP 1994, Proceedings |
Editors | Alan Borning |
Publisher | Springer |
Pages | 193-204 |
Number of pages | 12 |
ISBN (Print) | 9783540586012 |
Publication status | Published - 1 Jan 1994 |
Externally published | Yes |
Event | International Workshop on the Principles and Practice of Constraint Programming 1994 - Rosario, Orcas Island, United States of America Duration: 2 May 1994 → 4 May 1994 Conference number: 2nd |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 874 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | International Workshop on the Principles and Practice of Constraint Programming 1994 |
---|---|
Abbreviated title | PPCP 1994 |
Country/Territory | United States of America |
City | Rosario, Orcas Island |
Period | 2/05/94 → 4/05/94 |