**MSC:**- 68R10 Graph theory, See also {05Cxx, 90B10, 90B35, 90C35}
- 90C35 Programming involving graphs or networks
- 90C10 Integer programming

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.