Cardinality constraints in disjunctive deductive databases

We investigate cardinality constraints of the form M -theta K, where M is a set and theta is one of the comparison operators or "greater than or equal to"; 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 P-c, such that the models of P-c 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 P-cc, which allows for directly reasoning with sets of exactly-cardinality constraints (i.e., where theta is "="). Reasoning with P-cc is very efficient, and. it can be used for performance reasons before P-c is evaluated. For obtaining completeness, however, P-c is necessary, since we show the theoretical result that a sound and complete calculus,for exactly-cardinality constraints does not exist.