The Unified Modeling Language (UML) has become a universal tool for the formal object-oriented specification of hard- and software. In particular, UML class diagrams and so-called multiplicities, which restrict the number of links between objects, are essential when using UML for applications like the specification of admissible configurations of components.

In this paper we give a formal definition of the semantics of UML class diagrams and multiplicities. We extend results obtained in the context of Entity Relationship diagrams to cover UML specific extensions like the (non-)uniqueness attribute of binary associations. We show that the consistency of such specifications can be checked in polynomial time, and give an algorithm for computing minimal configurations (models). The core of our approach is a translation of UML class diagrams to Diophantine inequations.