On the Computational Complexity of Cardinality Constraints in Relational Databases

Abstract

We show that the problem of determining whether of not a lossless join property holds for a database, in the presence of key dependencies and cardinality constraints on the domains of the attributes is NP-complete.