专栏首页软件开发 -- 分享 互助 成长分解成3NF的保持函数依赖的分解算法:

分解成3NF的保持函数依赖的分解算法:

转换成3NF的保持函数依赖的分解算法:

ρ={R1<U1,F1>,R2<U2,F2>,...,Rk<Uk,Fk>}是关系模式R<U,F>的一个分解,U={A1,A2,...,An},F={FD1,FD2,...,FDp},并设F是一个最小依赖集,记FDi为Xi→Alj,其步骤如下:

① 对R<U,F>的函数依赖集F进行极小化处理(处理后的结果仍记为F);

② 找出不在F中出现的属性,将这样的属性构成一个关系模式。把这些属性从U中去掉,剩余的属性仍记为U;

③ 若有X→A€ F,且XA=U,则ρ={R},算法终止;

④ 否则,对F按具有相同左部的原则分组(假定分为k组),每一组函数依赖Fi所涉及的全部属性形成一个属性集Ui。若Ui¢ Uj(i≠j),就去掉Ui。由于经过了步骤②,故

,于是构成的一个保持函数依赖的分解。并且,每个Ri(Ui,Fi)均属于3NF且保持函数依赖。

对于步骤1中函数集的极小化处理可以参见博客 http://i.cnblogs.com/PostDone.aspx?postid=4445027&actiontip

例1:关系模式R<U,F>,其中U={C,T,H,I,S,G},F={CS→G,C→T,TH→I,HI→C,HS→I},将其分解成3NF并保持函数依赖。

(一)计算F的最小函数依赖集

① 利用分解规则,将所有的函数依赖变成右边都是单个属性的函数依赖。由于F的所有函数依赖的右边都是单个属性,故不用分解。

② 去掉F中多余的函数依赖

A.设CS→G为冗余的函数依赖,则去掉CS→G,得:

F1={C→T,TH→I,HI→C,HS→I}

计算(CS)F1+:

设X(0)=CS

计算X(1):扫描F1中各个函数依赖,找到左部为CS或CS子集的函数依赖,找到一个C→T函数依赖。故有X(1)=X(0)∪T=CST。

计算X(2):扫描F1中的各个函数依赖,找到左部为CST或CST子集的函数依赖,没有找到任何函数依赖。故有X(2)=X(1)。算法终止。

(CS)F1+= CST不包含G,故CS→G不是冗余的函数依赖,不能从F1中去掉。

B.设C→T为冗余的函数依赖,则去掉C→T,得:

F2={CS→G,TH→I,HI→C,HS→I}

计算(C)F2+:

设X(0)=C

计算X(1):扫描F2中的各个函数依赖,没有找到左部为C的函数依赖。故有X(1)=X(0)。算法终止。故C→T不是冗余的函数依赖,不能从F2中去掉。

C.设TH→I为冗余的函数依赖,则去掉TH→I,得:

F3={CS→G,C→T,HI→C,HS→I}

计算(TH)F3+:

设X(0)=TH

计算X(1):扫描F3中的各个函数依赖,没有找到左部为TH或TH子集的函数依赖。故有X(1)=X(0)。算法终止。故TH→I不是冗余的函数依赖,不能从F3中去掉。

D.设HI→C为冗余的函数依赖,则去掉HI→C,得:

F4={CS→G,C→T,TH→I,HS→I}

计算(HI)F4+:

设X(0)=HI

计算X(1):扫描F4中的各个函数依赖,没有找到左部为HI或HI子集的函数依赖。故有X(1)=X(0)。算法终止。故HI→C不是冗余的函数依赖,不能从F4中去掉。

E.设HS→I为冗余的函数依赖,则去掉HS→I,得:

F5={CS→G,C→T,TH→I,HI→C}

计算(HS)F5+:

设X(0)=HS

计算X(1):扫描F5中的各个函数依赖,没有找到左部为HS或HS子集的函数依赖。故有X(1)=X(0)。算法终止。故HS→I不是冗余的函数依赖,不能从F5中去掉。即:F5={CS→G,C→T,TH→I,HI→C,HS→I}

③ 去掉F5中各函数依赖左边多余的属性(只检查左部不是单个属性的函数依赖)

没有发现左边有多余属性的函数依赖。故最小函数依赖集为:

F={CS→G,C→T,TH→I,HI→C,HS→I}

(二)由于R中的所有属性均在F中都出现,所以转下一步。

(三)对F按具有相同左部的原则分为:R1=CSG,R2=CT,R3=THI,R4=HIC,R5=HSI。所以ρ={R1(CSG),R2(CT),R3(THI),R4(HIC),R5(HSI)}。

声名:本文参考自百度文库

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    用户1215536
  • 欧拉回路

    一、定义 欧拉回路:图G,若存在一条路,经过G中每条边有且仅有一次,称这条路为欧拉路,如果存在一条回路经过G每条边有且仅有一次, 称这条回路为欧拉回路。具有欧拉...

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

    函数依赖集的闭包 F:FD的集合称为函数依赖集。 F闭包:由F中的所有FD可以推导出所有FD的集合,记为F+。 例1,对于关系模式R(ABC),F={A→B,B...

    用户1215536
  • 机器学习(二) ——线性回归、代价函数与梯度下降基础

    机器学习(二) ——线性回归、代价函数与梯度下降基础 (原创内容,转载请注明来源,谢谢) 一、线性回归 线性回归是监督学习中的重要算法,其主要目的在于用一个...

    用户1327360
  • 将.m文件转换为.exe可执行文件

    第二步:在MATLAB下使用:mcc -m 文件名.m ,将 .m 文件编译成 .exe 文件。

    AIHGF
  • Python Seaborn (3) 分布数据集的可视化

    在处理一组数据时,通常首先要做的是了解变量是如何分布的。这一章将简要介绍seborn中用于检查单变量和双变量分布的一些工具。你可能还想看看分类变量的章节,来看看...

    数据猿
  • 智能合约:特权功能暴露、矿工特权隐患

    如果这俩情况同时发生在同一函数上,就意味着所有人都可以调用这个函数来获得合约的余额,当然,也不一定是析构函数,其他涉及敏感操作的函数(比如未鉴权的合约所有人转移...

    yichen
  • Vue路由Hash模式分析

    Vue-router是Vue的核心组件,主要是作为Vue的路由管理器,Vue-router默认hash模式,即使用URL的Hash来模拟一个完整的URL,当UR...

    WindrunnerMax
  • Vue路由History模式分析

    Vue-router是Vue的核心组件,主要是作为Vue的路由管理器,Vue-router默认hash模式,通过引入Vue-router对象模块时配置mode属...

    WindrunnerMax
  • android监听器实例代码

    (1) ListView事件监听 setOn ItemSelectedListener:鼠标滚动时触发 setOnItemClickListener: ...

    砸漏

扫码关注云+社区

领取腾讯云代金券