Sven Hartmann
On the implication problem for cardinality constraints and functional dependencies
Preprint series: Preprints aus dem Fachbereich Mathematik, Universität Rostock

MSC:

68R10 Graph theory, See also {05Cxx, 90B10, 90B35, 90C35}

68P15 Database theory

Abstract: In database design, integrity constraints are used to
express database semantics. They specify the way by that the
elements of a database are associated to each other. The
implication problem asks whether a given set of constraints
entails further constraints. In this paper, we study the
finite implication 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 also
key and functional dependencies. Moreover, we construct
Armstrong databases for these constraint sets, which are of
special interest for example-based deduction in database
design.

Keywords: cardinality constraint, key, functional dependency, implication