基于卡诺图确定函数依赖集规范覆盖.pdfVIP

基于卡诺图确定函数依赖集规范覆盖 张亦舜 浙江工商大学计算机与信息工程学院，浙江杭州（310035 ） E-mail：zys64@ 摘 要：关系数据库理论中，确定函数依赖集的规范覆盖是一个关键的问题。主要的算法烦 琐而费时，且难以求得全部的结果。本文依据函数依赖理论与逻辑代数对应部分的等价性， 引入化简逻辑函数的卡诺图法求函数依赖集的规范覆盖。首先将函数依赖集对应的卡诺图定 义为函数依赖图，接着讨论了依据给定的函数依赖集通过函数依赖图确定规范覆盖的方法， 由于每个函数依赖图代表了一类彼此等价的函数依赖集，最后将此方法自然推广到求函数依 赖集等价类的全部规范覆盖。 关键词：关系数据库，函数依赖集，规范覆盖，卡诺图 中图分类号：TP301 1．引言 目前，关系数据库系统得到了广泛的应用。关系数据库系统采用关系模型作为数据的组 织方式。关系模型是由E.F.Codd1970年首先提出的[1]，此后，许多研究者发表了多篇论文， 奠定了关系模型的理论基础。 函数依赖是关系数据库理论及设计中最主要，最基本的一类数据依赖。许多算法如关系 模式分解等都要求用一个函数依赖集的覆盖作为输入。在所有与给定函数依赖集等价的各种 覆盖中[2],规范覆盖无疑是最重要和最常用的。 确定与一个给定函数依赖集等价的规范覆盖的算法[3,4]，主要是按照定义利用Armstrong 关于函数依赖的推理规则[5]对函数依赖集简化。这种方法虽然直接明了，但当函数依赖集中 元素及其包含的属性较多时，由于要大量计算属性集关于函数依赖集的闭包，将导致计算量 的急剧增加。算法最终的结果取决于处置函数依赖及函数依赖左部属性的顺序。要得到不同 的规范覆盖，就必须考虑各种计算顺序，这显然是极其烦琐而复杂的。 算法的不足主要由于函数依赖间的联系在函数依赖集中不能有效地反映。根据函数依赖 与逻辑代数的等价关系[6]，函数依赖集的化简可以转化为对应的逻辑函数的化简，卡诺图法 是化简逻辑函数的一种图形方法，具有形象、直观和方便等优点。本文讨论利用卡诺图法求 给定函数依赖集的规范覆盖。卡诺图直观地反映了函数依赖间的联系，因此克服了上述方法 的困难，可以简便地确定各个等价的规范覆盖，并且能够直观地判断出各函数依赖的差别， 为此文中对函数依赖进行了划分，引进了绝对冗余、相对冗余及必要函数依赖的概念。 2 ．函数依赖与逻辑代数 本节简要介绍文章涉及的有关函数依赖、逻辑代数和卡诺图等知识，详细的内容可参考 有关文献[4,7,8] 。 2.1 函数依赖 定义 设 F 为属性集 U 上的函数依赖集，X ⊆U ，X + {A | X →A 能根据 Armstrong F 推理规则导出｝，X + 称为属性集X 关于函数依赖集 F 的闭包。 F 定义 由函数依赖集F 应用 Armstrong 的推理规则导出的函数依赖称为被F 逻辑蕴含， 为F 所逻辑蕴含的函数依赖的全体叫做 F 的闭包，记为：F + -1- 定义 给定两个函数依赖集 F 和 G，如果∀X →Y ∈F 有X →Y ∈G+ ，则称 G 覆 盖 F ，如果 G 覆盖 F ,且 F 覆盖 G ,则称 G 与 F 等价,记为 F ≡G.，即互相蕴含 F ≡G .的充分必要条件是F ⊆G+ ，和G ⊆F + 。 定义 如果函数依赖集 F 满足下列条件，则称 F 为规范覆盖。 1) F 中任意覆盖的右部仅含有一个属性。 2) F 中不存在这样的函数依赖X →A ，使得F 与F −{X →A} 等价。 3) F 中不存在这样的函数依赖X →A ，X 有真子集 Z 使得F −{X →