TY - JOUR

T1 - Foundations of aggregation constraints

AU - Ross, Kenneth A.

AU - Srivastava, Divesh

AU - Stuckey, Peter J.

AU - Sudarshan, S.

PY - 1998/2/28

Y1 - 1998/2/28

N2 - We introduce a new constraint domain, aggregation constraints, that is useful in database query languages, and in constraint logic programming languages that incorporate aggregate functions. We formally study the fundamental problem of determining if a conjunction of aggregation constraints is satisfiable, and show that, for many classes of aggregation constraints, the problem is undecidable. We describe a complete and minimal axiomatization of aggregation constraints, for the SQL aggregate functions min, max, sum, count and average, over a non-empty, finite multiset on several domains. This axiomatization helps identify classes of aggregation constraints for which the satisfiability check is efficient. We present a polynomial-time algorithm that directly checks for satisfiability of a conjunction of aggregation range constraints over a single multiset; this is a practically useful class of aggregation constraints. We discuss the relationships between aggregation constraints over a non-empty, finite multiset of reals, and constraints on the elements of the multiset. We show how these relationships can be used to push constraints through aggregate functions to enable compile-time optimization of database queries involving aggregate functions and constraints.

AB - We introduce a new constraint domain, aggregation constraints, that is useful in database query languages, and in constraint logic programming languages that incorporate aggregate functions. We formally study the fundamental problem of determining if a conjunction of aggregation constraints is satisfiable, and show that, for many classes of aggregation constraints, the problem is undecidable. We describe a complete and minimal axiomatization of aggregation constraints, for the SQL aggregate functions min, max, sum, count and average, over a non-empty, finite multiset on several domains. This axiomatization helps identify classes of aggregation constraints for which the satisfiability check is efficient. We present a polynomial-time algorithm that directly checks for satisfiability of a conjunction of aggregation range constraints over a single multiset; this is a practically useful class of aggregation constraints. We discuss the relationships between aggregation constraints over a non-empty, finite multiset of reals, and constraints on the elements of the multiset. We show how these relationships can be used to push constraints through aggregate functions to enable compile-time optimization of database queries involving aggregate functions and constraints.

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

U2 - 10.1016/S0304-3975(97)00011-X

DO - 10.1016/S0304-3975(97)00011-X

M3 - Article

AN - SCOPUS:0000701345

SN - 0304-3975

VL - 193

SP - 149

EP - 179

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -