  Codd's rule of entity integrity stipulates that every table has a primary
key. Hence, the attributes of the primary key carry unique and complete value
combinations. In practice, data cannot always meet such requirements. Previous
work proposed the superior notion of key sets for controlling entity integrity.
We establish a linear-time algorithm for validating whether a given key set
holds on a given data set, and demonstrate its efficiency on real-world data.
We establish a binary axiomatization for the associated implication problem,
and prove its coNP-completeness. However, the implication of unary by arbitrary
key sets has better properties. The fragment enjoys a unary axiomatization and
is decidable in quadratic time. Hence, we can minimize overheads before
validating key sets. While perfect models do not always exist in general, we
show how to compute them for any instance of our fragment. This provides
computational support towards the acquisition of key sets.
