On the implication problem for cardinality constraints and functional dependencies

In database design, integrity constraints are used to express database sema ntics. They specify the way by that the elements of a database are associat ed to each other. The implication problem asks whether a given set of const raints entails further constraints. In this paper, we study the finite impl ication problem for cardinality constraints. Our main result is a complete characterization of closed sets of cardinality constraints. Similar results are obtained for constraint sets containing cardinality constraints, but a lso key and functional dependencies. Moreover, we construct Armstrong datab ases for these constraint sets, which are of special interest for example-b ased deduction in database design.