LR最小替换集求解算法研究

RESEARCH ON AN ALGORITHM TO FIND THE LR MINIMUM REPLACING SET

摘要: 文中对Ｄ．Ｍａｉｅｒ提出的关于关系数据库中的ＬＲ最小集的结构进行了分析．提出了一个比“ＬＲ最小集”更为简化的ＦＤ集的覆盖——ＬＲ最小替换集．给出了一个求ＬＲ最小替换集的多项式时间算法．修正了Ｄ．Ｍａｉｅｒ在其文中给出的一个ＦＤ集为最优覆盖的必要条件．

Abstract: The structure of the LR minimum set proposed by D.Maier is analysed,and a cover of FD LR minimum replacing set is proposed,which is simpler than the LR minimum set.A polynomial time algorithm to find the LR minimum replacing set is given.The necessary condition given by D.Maier is revised,on which a FDs is the optimal cover.