Sven Hartmann Konrad Engel
Minimal Instances of Database Schemes with Additive Cardinality Constraints
Preprint series: Preprints aus dem Fachbereich Mathematik, Universität Rostock

MSC:

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

90C35 Programming involving graphs or networks

90C10 Integer programming

Abstract: In the entity-relationship approach to database design,
integrity constraints are used to express database semantics. Cardinality
constraints are a frequently used way of imposing restrictions to the
structure of databases. In this paper, we consider additive cardinality
constraints which specify lower and upper bounds on the total number of
relationships an entity of a fixed type may be involved in. It is natural
to ask for the smallest fully-populated database that yields a given set
of integrity constraints. For additive cardinality constraints this problem
is proved to be NP-complete. However, the problem can be tackled via
branch & bound. To solve the relaxed optimization problem we use
mincost flow methods in a suitable network depending on the given database
scheme.
Keywords: entity-relationship approach, cardinality constraints, branch-and-bound