ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

14. Mathematical Aspects of Computer Science

1991 MS Classification: 68R10 Hartmann, Sven, Universität Rostock New results on the consistency of cardinality constraints An entity-relationship database scheme is a hypergraph G whose vertices and edges are the entity and relationship types of the scheme, respectively. From G we obtain a database instance G^{t} by blowing up G, i. e. by replacing every original vertex (edge) by a class of new vertices (edges). Usually, database schemes come along with certain integrity constraints that limit the possible structure of instances. Cardinality constraints are frequently used to impose bounds on the vertex degrees in G^{t}. Checking whether cardinality constraints are consistent (satisfiable) under certain additional conditions leads to combinatorial and discrete programming problems. In particular, we use shortest-path and min-cost flow methods to provide efficient solutions and discuss a variations of the original problem.