## 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 |