专栏首页软件开发 -- 分享 互助 成长函数依赖集闭包、属性集闭包、超键、候选键和最小函数依赖集的求法。

函数依赖集闭包、属性集闭包、超键、候选键和最小函数依赖集的求法。

函数依赖集的闭包

F:FD的集合称为函数依赖集。

F闭包:由F中的所有FD可以推导出所有FD的集合,记为F+。

例1,对于关系模式R(ABC),F={A→B,B→C},求F+。

根据FD的定义,可推出F+={φ→φ,A→φ,A→A,A→B,A→C,A→AB,A→BC,A→ABC,…},共有43个FD。其中,φ表示空属性集。

属性集闭包

属性集闭包定义 : 对F,F+中所有X→A的A的集合称为X的闭包,记为X+。可以理解为X+表示所有X可以决定的属性。

属性集闭包的算法:

A+:将A置入A+。对每一FD,若左部属于A+,则将右部置入A+,一直重复至A+不能扩大。

超键、候选键

若X+包含R的所有属性,则X是超键。当X不可约时则为候选键。   如上例:A+=ABC,则A为超键,因为A不可约则为候选键。

 设关系模式R中U=ABC.......等N个属性,U中的属性在FD中有四种范围:

(1)左右出现;

(2)只在左部出现;

(3)只在右部出现;

(4)不在左右出现;

 求候选键算法:

1.R:只在FD右部出现的属性,不属于候选码;

2.L:只在FD左部出现的属性,一定存在于某候选码当中;

3.N:外部属性一定存在于任何候选码当中;

4.其他属性逐个与2,3的属性组合,求属性闭包,直至X的闭包等于U,若等于U,则X为候选码。

例2,对于关系模式R(ABCD),F={A→B,B→C,D→B},求其候选键。

先按照属性集闭包的算法,求各个闭包,然后求得候选键。

(1)      求A+。 

①       A+=A。  ②       由A→B,而A €A+可知,则A+=AB。

③       由B→C,而B  A+可知,则A+=ABC。

④       A+封闭,即A+=ABC。

(2) 求B+、C+、D+。 

按步骤(1)可得:B+=BC,C+=C,D+=BCD。

(3) 求其候选键。 显然,R的候选键为AD。

例3,对于关系模式R(ABC),F={A→BC,BC→A},求其候选键。

(1)   求属性的闭包。  按例2可得:A+=ABC,B+=B,C+=C。 

(2)    求属性集的闭包。  由BC→A,则(BC)+=ABC,其余属性集闭包为属性闭包的并集。

(3)   求其候选键。 显然,R的候选键为A和BC。

最小函数依赖集

定义:如果函数依赖集F满足以下条件,则称F为一个极小函数依赖集。也称为最小依赖集或最小覆盖。

(1)F中任一函数依赖的右部仅含有一个属性。

(2)F中不存在这样的函数依赖X→A,使得F与F-{X→A}等价。

(3)F中不存在这样的函数依赖X→A,X有真子集Z使得F-{X→A}U{Z→A}与F等价。

最小依赖集通用算法:

① 用分解的法则,使F中的任何一个函数依赖的右部仅含有一个属性;

② 去掉多余的函数依赖:从第一个函数依赖X→Y开始将其从F中去掉,然后在剩下的函数依赖中求X的闭包X+,看X+是否包含Y,若是,则去掉X→Y;否则不能去掉,依次做下去。直到找不到冗余的函数依赖;

③ 去掉各依赖左部多余的属性。一个一个地检查函数依赖左部非单个属性的依赖。例如XY→A,若要判Y为多余的,则以X→A代替XY→A是否等价?若A属于(X)+,则Y是多余属性,可以去掉。

例4、求F={A→B,B→A,B→C,A→C,C→A},最小(极小)函数依赖集合

1、利用分解规则,将所有的函数依赖变成右边都是单个属性的函数依赖。从题目来看,F中的任何一个函数依赖的右部仅含有一个属性: {A→B,B→A,B→C,A→C,C→A}

2、去掉F中多余的函数依赖

(1)设A→B冗余,从F中去掉A→B,则F1={B→A,B→C,A→C,C→A}。计算(A)F1+:设X(0)=A,计算X(1):扫描F1中各个函数依赖,找到左部为A或A子集的函数依赖,A→C。故有X(1)=X(0)U C=AC;扫描F1中各个函数依赖,找到左部为AC或为AC子集的函数依赖,C→A,X(2)=X(1)U C=AC.但AC不包含B,故A->B不能从F中去掉。

(2)设B→A冗余,从F中去掉B→A,则F2={A→B,B→C,A→C,C→A}。计算(B)F2+:设X(0)=B,计算X(1):扫描F2中各个函数依赖,找到左部为B或者B子集的函数依赖,B→C.故有X(1)=X(0)U C =BC;扫描F2中各个函数依赖,找到左部为BC或为BC子集的函数依赖,C->A,X(2)=X(1)U A=ABC.X(2)包含所有属性,故B→A可从F中去掉。

(3)设B→C冗余,从F中去掉B→C,则F3={A→B,A→C,C→A}。计算(B)F3+:扫描F3中各个函数依赖,找不到左部为B或B子集的函数依赖,因为找不到这样的函数依赖,故有X(1)=X(0)=B,(B)F1+= B不包含C,故B→C不是冗余的函数依赖,不能从F1中去掉。

(4)设A→C冗余,从F中去掉A→C,则F4={A→B,B→C,C→A}。计算(A)F4+:设X(0)=A,计算X(1):扫描F4中各个函数依赖,找到左部为A或A子集的函数依赖,A→B。故有X(1)=X(0)U B=AB;扫描F4中各个函数依赖,找到左部为AB或为AB子集的函数依赖,B→C,X(2)=X(1)U C=ABC.X(2)包含所有属性,故A→C可从F中去掉。

(5)设C→A冗余,从F中去掉C→A,则F4={A→B,B→C}。计算(C)F5+:设X(0)=C,计算X(1):扫描F5中各个函数依赖,找到左部为C或C子集的函数依赖,找不到左部为C或C子集的函数依赖,因为找不到这样的函数依赖,故有X(1)=X(0)=C,(B)F1+= C不包含A,故C→A不是冗余的函数依赖,不能从F中去掉。

(6)至此,所有依赖均以验算完毕,故F最小(极小)函数依赖集合为:{A→B,B→C,C→A}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++ 之虚函数的实现原理

    c++的多态使用虚函数实现,通过“晚绑定”,使程序在运行的时候,根据对象的类型去执行对应的虚函数。

    用户1215536
  • 数据库的规范化

    一、基础概念 实体:现实世界中客观存在并可以被区别的事物。比如“一个学生”、“一本书”、“一门课”等。 属性:教科书上解释为:“实体所具有的某一特性”,由此可见...

    用户1215536
  • 分解成3NF的保持函数依赖的分解算法:

    转换成3NF的保持函数依赖的分解算法: ρ={R1<U1,F1>,R2<U2,F2>,...,Rk<Uk,Fk>}是关系模式R<U,F>的一个分解,U={A1,...

    用户1215536
  • Python学习,这些高阶函数和高阶特性值得一学

    Python语言这么火,不论是对于刚开始学习的编程小白或者有接触过其他语言(c/c++/java等等)的同学来说,写代码的时候难免会受本身惯性思维或者其他语言的...

    云飞
  • 函数和方法的区别

    黑泽君
  • 交互式使用 R题(shell)

    交互式shell是一种很方便的环境,可以进行各种尝试,随时调整过程。与Python、Ruby等语言一样,R也提供了shell环境。本文开始的例子就是以交互的方式...

    学到老
  • 交互式使用 R题(shell)

    交互式使用 R 交互式shell是一种很方便的环境,可以进行各种尝试,随时调整过程。与Python、Ruby等语言一样,R也提供了shell环境。本文开始的例子...

    学到老
  • 腾讯云函数计算冷启动优化实践

    随着当下Serverless、FaaS生态的不断发展以及小程序的空前繁荣,越来越多的企业和个人用户把自己的应用,小程序部署到腾讯云无服务器云函数平台上,但随之而...

    腾讯云serverless团队
  • Hadoop集群搭建Linux环境准备基础配置安装HadoopHA集群安装HIVE安装MySQL安装HBASE安装Flume问题总结

    本文主要讲解了Hadoop集群环境的搭建过程,实际应用中应该不会这样做,而是通过一些管理工具进行安装,比如可视化安装:Ambari。

    spilledyear
  • 在单台云主机搭伪分布式hadoop环境

    Hadoop是大数据的基础框架模型,处理大数据,不应只谈偏向业务环境的大数据(如超市买婴儿尿不湿同时还应该推荐啤酒的经典案例),作为解决方案经理,技术是不能缺少...

    希望的田野

扫码关注云+社区

领取腾讯云代金券