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

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

作　　者：郝忠孝[1] 刘国华[1] 

机构地区：[1]东北重型机械学院

出　　处：《计算机研究与发展》1995年第2期27-33,共7页Journal of Computer Research and Development

基　　金：国家自然科学基金;黑龙江省自然科学基金

摘　　要：文献［１］、［２］、［３］均明确指出，求一个关系模式的最小基数候选关键字问题是一个ＮＰ完全问题。作者在深入分析主属性在ＦＤ集、最小基数候选关键字关系模式和候选关键字集合中的结构特性的基础上，提出了同类属性集，同类主属性组集族，自由、半自由同类属性集等概念。在此基础上，给出了一个求关系模式最小基数候选关键字的Ｏ（ｎ２ｐ）级算法。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.

关 键 词：候选关键字 关系模式 数据库 多项式时间算法 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]