Candidate keys for relations

摘要

An algorithm is presented that finds K, the set of all keys for a given set A of attribute names and a given set D[0] of functional dependencies, in time polynomial in |A|, |D[0]| and |K|. It is shown that the problem of deciding whether or not there is a key having cardinality not greater than a specified integer is NP-complete. It is also shown that the problem of deciding whether or not a specified attribute name is prime is NP-complete.