一种求解全部候选关键字的快速替换算法

本文通过分析文献（２，３）中所提出的求解关系模式全部候选关键字的替换算法，找出了它们的共同缺陷，即算法每搜索一趟产生的后继候选关键字太少，要想求出全部候选关键字，需经过很多趟的搜索。在此基础上，提出了对替换算法从减少每一趟搜索中需要检查的ＦＤ个数和增加每一趟搜索产生的后继候选关键字两方面进行改进的基本思想。然后，以ＥＦ（Ｘ）为研究对象，讨论了实现这种改进思想的具体方法，并给出了相应的快速替换算法及

A QUICK REPLACING ALGORITHM FOR FINDING ALL CANDIDATE KEYS OF A RELATION SCHEME

In this paper, the common shortcoming of the replacing algorithms forfinding all candidate keys of a relation scheme proposed in literature is found out byanalyzing in detail, namely, the succeed candidate keys are so few that it needs toomany passes of search for finding all candidate keys of a relation scheme. In orderto improve the replacing algorlthm for finding all candidate keys of a relationscheme, the basic ameliorative thinking is proposed, it is that the number of FDchecked in each pass of search should be cut down and the succeed candidate keys ineach pass of search should be increased. In a relation scheme R (U, F), if F is aminimum cover, it must be the set of functional dependency which has the mini-mum cardinality. So, in this paper, all sets of functional dependency are minimumcovers. Besides this, in each pass of search, EF (X) is ehecked. Therefore, thenumber of FD checked in each pass of search must be cut down and the succeedcandidate keys in each pass must be increased. Then, a quick replacing algorithmfor finding all candidate keys of a relation scheme is proposed on above-mentionedameliorative thinking, and, the correctness of the algorithm is proved, the averageand worst-case time complexities of the algorithm are analyzed.