关系模式最小基数候选关键字多项式时间求解算法

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.