Foundations of aggregation constraints

Kenneth A. Ross, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

7 Citations (Scopus)

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 languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - 2nd International Workshop, PPCP 1994, Proceedings
EditorsAlan Borning
PublisherSpringer
Pages193-204
Number of pages12
ISBN (Print)9783540586012
Publication statusPublished - 1 Jan 1994
Externally publishedYes
Event2nd International Workshop on the Principles and Practice of Constraint Programming, PPCP 1994 - Rosario, Orcas Island, United States of America
Duration: 2 May 19944 May 1994

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume874 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference2nd International Workshop on the Principles and Practice of Constraint Programming, PPCP 1994
Country/TerritoryUnited States of America
CityRosario, Orcas Island
Period2/05/944/05/94

Cite this