Controlling Entity Integrity with Key Sets

Codd's rule of entity integrity stipulates that every table has a primary key. Key sets can control entity integrity when primary keys do not exist. While key set validation is quadratic, update maintenance for unary key sets is efficient when incomplete values only occur in few key columns. We establish a binary axiomatization for the 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 Armstrong relations do not always exist, we show how to compute them for any instance of our fragment. Similarly, we show how unary keys sets can be mined from relations using hypergraph transversals. Finally, we establish an axiomatization and computational complexity for the implication problem of key sets combined with NOT NULL constraints.