极小函数依赖集的正确算法及其证明.pdf.pdf

����年�月�西安邮电学院学报����������
第��卷第�期��������������’������������������������������������������������.�����.��
极小函数依赖集的正确算法及其证明�
于思江�,王小兵��
��.西安邮电学院教务处,陕西西安������;�.西安电子科技大学计算机学院,陕西西安��������
摘要:极小函数依赖集是关系数据库理论中的一个重要概念,它在模式分解中起到了重要作用,但是一些国内文献�
介绍的算法存在问题。本文通过一个例子说明了该极小函数依赖集算法的错误,给出了正确的算法,并且出具了�
详细证明。�
关键词:极小函数依赖集;算法;证明�.�
中图分类号.�����.���.��文献标识码:��文章编号:����—������������—��������
�为一个极小函数依赖集。亦称为最小依赖集或最�
引言�小覆盖。�
����中任一函数依赖的右部仅含有一个属性;�
在关系数据库的设计中,经常需要对范式级别�����中不存在这样的函数依赖�—�,使得��
较低的关系进行模式分解,生成若干个高级别的关�与�~������等价;�
系模式,从而降低数据的冗余度,提高数据库的可维�����中不存在这样的函数依赖�—�,�有真�
护性。模式分解算法的性能与关系的函数依赖集的�子集�使得��一����������与�等价。�
大小密切相关:函数依赖集包含的函数依赖个数越�根据定义,极小函数依赖集应该同时满足三个�
少,模式分解算法的性能就越高。这其中牵涉到一�条件:条件���保证函数依赖的右部是单个属性,条�
个重要的概念,极小函数依赖集,它具有较高的理论�件���保证不能包含多余的函数依赖,条件���保证�
和实际应用价值。�函数依赖的左部没有冗余属性。�
国内一些文献对极小函数依赖集都进行了讨�值得注意的是,极小和最小的定义是有严格区�
论【卜��,然而其算法存在一定的问题。国内文献����分的:极小值可以有多个,但是最小值一定是惟一�
和国外文献�����指明了该问题,并给出了正确的求�的���。因为极小函数依赖集不一定是惟一的⋯�,所�
解算法,但是都没有给出确切的证明。本文通过具�以“最小”依赖集和“最小”覆盖中的“最小”称呼并不�
体实例指明了该极小函数依赖集算法的错误之处,�严格,应该避免使用。�
给出了正确的算法,并且出具了详细的证明。�算法�:计算函数依赖集�的极小函数依赖集�
的三个步骤:�
�极小函数依赖集的定义和错误算法����将函数依赖的右部分解为单个属性:对��
中每一函数依赖�—�,若������⋯����≥��,�
文献���中对极小函数依赖集的定义和错误算�则用�����.����,⋯,��替换��;�
法介绍如下。����去除多余的函数依赖:对于�中的每一函�
定义�:如果函数依赖集�满足下列条件,则称�数依赖�—�,若����一��,则从�中去掉��
收稿日期:����—��—���
基金项目:����年陕西省精品课程西安电子科技大学《数据库系统原理》支持�
作者简介:于思江�����一�,女,浙江奉化人,西安邮电学院教务处助理工