Treffer: Cardinality constraints in disjunctive deductive databases

We investigate cardinality constraints of the form M →e K, where M is a set and θ is one of the comparison operators =, ≤, or ≥; such a constraint states that exactly, at most, or at least, respectively, K elements out of the set M have to be chosen. We show how a set C of constraints can be represented by means of a positive-disjunctive deductive database Pc, such that the models of Pc correspond to the solutions of C. This allows for embedding cardinality constraints into applications dealing with incomplete knowledge. We also present a sound calculus represented by a definite logic program Pcc, which allows for directly reasoning with sets of exactly cardinality constraints (i.e., where θ is =). Reasoning with Pcc is very efficient, and it can be used for performance reasons before Pc is evaluated. For obtaining completeness, however, Pc is necessary, since we show the theoretical result that a sound and complete calculus for exactly-cardinality constraints does not exist.