A Polynomial-Time Algorithm to Find a Candidate Key of Minimum Cardinality on a Relation Schema

The candidate key of minimum cardinality problem was pointed out to be NP-complete in literature 1, 2, and 3. In this paper, the concepts, such as set of the same kind attributes, family of sets of the same kind prime attributes, set of the free same kind attributes, and set of the half-free same kind attributes, are proposed, and then, a polynomial-time algorithm to find a candidate key of minimum cardinality on a relation schema in O（n2p）is given.