Foundations of aggregation constraints

Reviewer: Daniel L. Chester

The authors examine the problem of determining whether a set of constraints involving aggregation functions is satisfiable. In particular, they examine the satisfiability problem for constraints involving the SQL aggregation functions min, max, sum, count, and average. They show that, in the most general case, these satisfiability problems are undecidable. In special cases, however, which may be quite common, these problems are decidable, and often decidable in little time. While the paper shows that, in some simple cases, the aggregation constraint satisfiability problem is NP-complete, the bulk of the paper shows how many instances of the problem can be solved efficiently by adding axioms that characterize the aggregation functions. It also presents algorithms for deciding in polynomial time whether a set of range constraints involving aggregation functions is satisfiable. The formal results reported in this paper should interest developers of database query systems, because knowing when a query is unsatisfiable can avert unnecessary access to the database. The proofs of the theorems in this paper and the algorithms provided should also suggest ways to answer some queries more efficiently when they are satisfiable. Researchers should find this paper to be a good starting point for further research on some new classes of constraint satisfaction problems.