数据库函数依赖
admin
2024-03-14 01:29:57
0次

目录

  • 数据库函数依赖
    • 属性集的闭包
      • 求解属性集闭包
      • 判断函数依赖是否成立
      • 求解最小依赖集
      • 求解正则覆盖
    • 候选码的应用
      • 候选码的计算
      • 判断范式
    • 参考

数据库函数依赖

在网上看了许多有关数据库函数依赖考题的分析,大都信息不全或者讲不完整,甚至是胡言乱语,看的我也是云里雾里。在浅浅的了解一番之后,决定总结一下有关这方面的做题技巧,为了加深印象也为了应付考试,于是就有了这篇文章。

阅读须知:数据库函数依赖的部分概念非常多,也十分难理解,如果单纯看书那会发现根本看不懂(比如我,书上各式各样的符号解释让人眼花缭乱)。所以本文大都以例子来说明,碰到相关概念再展开定义。

属性集的闭包

令 α\alphaα 是一个属性集,我们将函数依赖集 FFF 下被函数确定的所有属性的集合称为 FFF 下 α\alphaα 的闭包。

求解属性集闭包

书上的算法就不看了,看了也看不懂,直接看题目。

  • 例一:计算属性闭包(BC)+(BC)^+(BC)+

Example:GivenR,R={A,B,C,D,E},F={B→CD,AD→E,B→A}Example:Given \R,R=\{A,B,C,D,E\},F=\{B\rightarrow CD,AD\rightarrow E,B\rightarrow A\} Example:GivenR,R={A,B,C,D,E},F={B→CD,AD→E,B→A}

解:
1.Result{BC}2.Result{ABCD}3.Result{ABCDE}1.Result\{BC\} \\ 2.Result\{ABCD\}\\ 3.Result\{ABCDE\} 1.Result{BC}2.Result{ABCD}3.Result{ABCDE}
很简单,只要根据函数依赖集一步步推到就可以得到,首先是闭包初始状态BCBCBC,接着分别考虑每一个状态,根据依赖 B→CD,B→AB\rightarrow CD,B\rightarrow AB→CD,B→A ,可以将 AAA 和 DDD 加入到闭包中,最后由 AD→EAD\rightarrow EAD→E,将 EEE 也加入到闭包当中。当刚求出的属性闭包与上一个闭包相同时或者已经求出了所有的属性 UUU 时,就停止计算。

  • 例二:计算属性闭包(A)+(A)^+(A)+

Example:GivenR,R={A,B,C,D,E,H},F={A→B,B→DH,A→H,C→E}Example:Given \R,R=\{A,B,C,D,E,H\},F=\{A\rightarrow B,B\rightarrow DH,A\rightarrow H,C\rightarrow E\} Example:GivenR,R={A,B,C,D,E,H},F={A→B,B→DH,A→H,C→E}

有了上面的经验,这个是不是很简单了呢?

解:
1.Result{A}2.Result{ABH}3.Result{ABDH}1.Result\{A\} \\2.Result\{ABH\}\\3.Result\{ABDH\} 1.Result{A}2.Result{ABH}3.Result{ABDH}

判断函数依赖是否成立

直接说定理:如果 YYY 属于 XXX 的属性集闭包,那么依赖 X→YX \rightarrow YX→Y 成立,反之也如此。即 X→Y⇔Y⫅(XF)+X \rightarrow Y \Leftrightarrow Y \subseteqq(X_F)^+X→Y⇔Y⫅(XF​)+

可能还是过于抽象,直接看题。还是上面的例二,问函数依赖 A→DA \rightarrow DA→D 成立吗?

解:

可以求得属性闭包(A)+={A、B、D、H}(A)^+=\{A、B、D、H\}(A)+={A、B、D、H},因为 H⫅(A)+H \subseteqq(A)^+H⫅(A)+,所以此依赖成立。

求解最小依赖集

求解最小依赖集需要用到上述判断依赖集。

还是直接上题目。

  • 例三:取下述依赖集的最小依赖集

Example:GivenR,R={A,B,C,D,E,I},F={A→C,AB→C,C→DI,CD→I,EC→AB,EI→C}Example:Given \R,R=\{A,B,C,D,E,I\},F=\{A\rightarrow C,AB\rightarrow C,C\rightarrow DI,CD\rightarrow I,EC\rightarrow AB,EI\rightarrow C\} Example:GivenR,R={A,B,C,D,E,I},F={A→C,AB→C,C→DI,CD→I,EC→AB,EI→C}

解:

第一步右部化为单属性,经过分解后上述依赖集就变成如下依赖集:
F={A→C,AB→C,C→D,C→I,CD→I,EC→A,EC→B,EI→C}F=\{A\rightarrow C,AB\rightarrow C,C\rightarrow D,C\rightarrow I,CD\rightarrow I,EC\rightarrow A,EC\rightarrow B,EI\rightarrow C\} F={A→C,AB→C,C→D,C→I,CD→I,EC→A,EC→B,EI→C}
第二步判断依赖是否可以去除。把依赖集中的每一个依赖一个个尝试,看把这个依赖去掉后,还能不能导出这个依赖关系,如果能,则依赖多余要去除;如果不能,则保留。如果看能不能导出依赖关系呢?就要用到我们上述判断函数依赖是否成立了,其实就是判断依赖式左边的闭包包不包含右边。

举例,把 A→CA\rightarrow CA→C 去掉(已经去掉了,此依赖就不可用了),就看 AAA 的闭包里还有没有 CCC,再结合之前求解闭包的方法,可以知道 (A)+={A}(A)^+=\{A\}(A)+={A},并没有 CCC,所以此依赖不多余,不可去除。再判断 AB→CAB\rightarrow CAB→C ,可得 (AB)+={A、B、C、D、I}(AB)^+=\{A、B、C、D、I\}(AB)+={A、B、C、D、I},包含 CCC,也就说明没有这个依赖,此依赖也可以得到,所以把它去掉。再继续判断下一个直到最后,需要注意的是,此时 AB→CAB\rightarrow CAB→C 已经去掉,之后的判断过程就不可再用此依赖了。

最后我们得到依赖集:
F={A→C,C→D,CD→I,EC→A,EC→B,EI→C}F=\{A\rightarrow C,C\rightarrow D,CD\rightarrow I,EC\rightarrow A,EC\rightarrow B,EI\rightarrow C\} F={A→C,C→D,CD→I,EC→A,EC→B,EI→C}
第三步判断左部冗余属性。找到依赖式左部属性大于等于2的,然后依次去除一个属性,判断剩余属性的闭包能否推断出依赖式右部,如果能,则说明去除的属性多余,去掉;如果不能,则说明去除的属性有用,保留。

由于A→C,C→DA\rightarrow C,C\rightarrow DA→C,C→D 左部已经是单属性,就不考虑。直接看第三个 CD→ICD\rightarrow ICD→I,首先去掉属性 CCC,计算 (D)+={D}(D)^+=\{D\}(D)+={D},说明没有 CCC 推不出来 III,即 CCC 不可去掉,同理删除 DDD,计算 (C)+={C、D、I}(C)^+=\{C、D、I\}(C)+={C、D、I},说明没有 DDD 也能推出来 III,即 DDD 可去掉。再依次判断接下来的几个,最后得到最小依赖集:
F={A→C,C→D,C→I,EC→A,EC→B,EI→C}F=\{A\rightarrow C,C\rightarrow D,C\rightarrow I,EC\rightarrow A,EC\rightarrow B,EI\rightarrow C\} F={A→C,C→D,C→I,EC→A,EC→B,EI→C}
整个求解过程较为繁琐。需要注意的是第二步和第三步的细微区别。第二步判断依赖是要先把依赖删除,再利用其他的依赖关系看看能不能推出来此依赖,而第三步判断冗余属性时原本的依赖式是全部可用的。

再看一个例子吧。

  • 例四:取下述依赖集的最小依赖集

Example:GivenR,R={A,B,C},F={A→BC,B→C,A→B,AB→C}Example:Given \R,R=\{A,B,C\},F=\{A\rightarrow BC,B\rightarrow C,A\rightarrow B,AB\rightarrow C\} Example:GivenR,R={A,B,C},F={A→BC,B→C,A→B,AB→C}

解:

第一步右部化为单属性,经过分解后上述依赖集就变成如下依赖集:
F={A→B,A→C,B→C,AB→C}F=\{A\rightarrow B,A\rightarrow C,B\rightarrow C,AB\rightarrow C\} F={A→B,A→C,B→C,AB→C}
第二步判断是否有多余依赖式。可以发现式子 A→C,AB→CA\rightarrow C,AB\rightarrow CA→C,AB→C 都是多余的,所以删除。

第三步由于没有左部多属性的式子,所以不用判断,即此依赖集的最小依赖集:
F={A→B,B→C}F=\{A\rightarrow B,B\rightarrow C\} F={A→B,B→C}

求解正则覆盖

其实正则覆盖只是在最小依赖集最后多加了一步合并。因为正则覆盖有定义:

FFF 中不可以存在两个依赖 α1→β1,α2→β2\alpha_1\rightarrow \beta_1,\alpha_2\rightarrow \beta_2α1​→β1​,α2​→β2​,满足 α1=α2\alpha_1=\alpha_2α1​=α2​

  • 例五:求解下列依赖集的正则覆盖

Example:GivenR,R={A,B,C,D,E},F={A→BC,BCD→E,B→D,A→D,E→A}Example:Given \R,R=\{A,B,C,D,E\},F=\{A\rightarrow BC,BCD\rightarrow E,B\rightarrow D,A\rightarrow D,E\rightarrow A\} Example:GivenR,R={A,B,C,D,E},F={A→BC,BCD→E,B→D,A→D,E→A}

解:

前面还是按照求解最小依赖集的方式。

第一步右部化为单属性,经过分解后上述依赖集就变成如下依赖集:
F={A→B,A→C,BCD→E,B→D,A→D,E→A}F=\{A\rightarrow B,A\rightarrow C,BCD\rightarrow E,B\rightarrow D,A\rightarrow D,E\rightarrow A\} F={A→B,A→C,BCD→E,B→D,A→D,E→A}
第二步判断是否有多余依赖式。可以发现式子 A→DA\rightarrow DA→D 是多余的,所以删除。此时依赖集:
F={A→B,A→C,BCD→E,B→D,E→A}F=\{A\rightarrow B,A\rightarrow C,BCD\rightarrow E,B\rightarrow D,E\rightarrow A\} F={A→B,A→C,BCD→E,B→D,E→A}

第三步判断冗余属性,我们只需要判断 BCD→EBCD\rightarrow EBCD→E 即可,可以得到属性 DDD 是多余的,所以去除。得到最小依赖集:
F={A→B,A→C,BC→E,B→D,E→A}F=\{A\rightarrow B,A\rightarrow C,BC\rightarrow E,B\rightarrow D,E\rightarrow A\} F={A→B,A→C,BC→E,B→D,E→A}
根据正则覆盖的定义,需要把 A→B,A→CA\rightarrow B,A\rightarrow CA→B,A→C 合并,最后的正则覆盖:
F={A→BC,BC→E,B→D,E→A}F=\{A\rightarrow BC,BC\rightarrow E,B\rightarrow D,E\rightarrow A\} F={A→BC,BC→E,B→D,E→A}

候选码的应用

候选码的计算

如何快速选出候选码?我总结了一个方法:

  1. 先找入度为0的属性,即从未出现在闭包依赖式右部的属性(做了挺多题的,发现至少都能找到一个)
  2. 判断它的闭包是否为 UUU(即闭包是否包含全属性)
  3. 如果能,此属性就是候选码。如果不能,就继续在此属性上添加属性,知道找到闭包为 UUU 为止(此时说的为止是指以当前找到的候选码长度为标准,意思就是说我找到了一个长度为3的候选码,我要接着判断有没有其他长度为3的也是候选码,全部找完就可以,因为候选码是最小的超码)

还是有点抽象哈,举例子。

  • 例六:求下述依赖集的候选码

Example:GivenR,R={A,B,C,D},F={AB→C,AC→BD}Example:Given \R,R=\{A,B,C,D\},F=\{AB\rightarrow C,AC\rightarrow BD\} Example:GivenR,R={A,B,C,D},F={AB→C,AC→BD}

解:

首先看从未再依赖式右部出现的属性为 AAA,所以先看 (A)+={A}≠U(A)^+=\{A\}\neq U(A)+={A}​=U,所以 AAA 不是候选码,然后逐一添加属性,判断 (AB)+={ABCD}=U(AB)^+=\{ABCD\}= U(AB)+={ABCD}=U,所以 ABABAB 是候选码,接着判断 (AC)+={ABCD}=U(AC)^+=\{ABCD\}= U(AC)+={ABCD}=U,所以 ACACAC 也是候选码,最后 (AD)+={AD}≠U(AD)^+=\{AD\}\neq U(AD)+={AD}​=U,所以 ADADAD 不是候选码。

此时就不用添加属性了,因为已经是长度最小了。所以此依赖集的候选码集合就是 {AB,AC}\{AB,AC\}{AB,AC}

判断范式

1NF、2NF、3NF、BCNF的概念书上都有,不做过多解释了,我自己也看不懂那个杀软定义(

那么要如何判断一个关系模式是几范式呢?

背景

现在给出关系模式和函数依赖(functional dependency,简称FD)集,判断关系模式的所属范式

方法

  1. 求候选码,确定主属性和非主属性(有关主属性以及非主属性,参考候选码、超码等码的概念)。
  2. 判断是否有非平凡FD(依赖式左部不含候选码)
    • 没有,则是BCNF
    • 有非平凡FD
      • 若这些FD的右部都是主属性,则是3NF
      • 若不存在非主属性对码的部分依赖,即任何候选码的任何真子集都不确定非主属性,则是2NF
      • 否则是1NF(判断属性的域是否为原子性,一般都是的…)

概括

抽象,所以看例子

例七:判断下述依赖集是什么范式
Example:GivenR,R={B,C,D,E,G,H},F={BCD→EGH,E→D,G→C}Example:Given \R,R=\{B,C,D,E,G,H\},F=\{BCD\rightarrow EGH,E\rightarrow D,G\rightarrow C\} Example:GivenR,R={B,C,D,E,G,H},F={BCD→EGH,E→D,G→C}
解:

求候选码 BCD、BCE、BDG、BEGBCD、BCE、BDG、BEGBCD、BCE、BDG、BEG,可得主属性 B、C、D、E、GB、C、D、E、GB、C、D、E、G,非主属性 HHH

可得非平凡FD:E→D,G→CE\rightarrow D,G\rightarrow CE→D,G→C,所以不是BCNF

又因为非平凡FD的右边属性都是主属性,所以是3NF

例八:判断下述依赖集是什么范式
Example:GivenR,R={A,B,C,D},F={AB→C,C→D}Example:Given \R,R=\{A,B,C,D\},F=\{AB\rightarrow C,C\rightarrow D\} Example:GivenR,R={A,B,C,D},F={AB→C,C→D}
求候选码 ABABAB,可得主属性 A、BA、BA、B,非主属性 C、DC、DC、D

可得非平凡FD:C→DC\rightarrow DC→D,所以不是BCNF

又因为非平凡FD的右边属性不是主属性,所以不是3NF

接下来判断是否为2NF。根据定义,2NF不存在非主属性对码的部分依赖(关于部份依赖,详见平凡依赖,非平凡依赖,完全依赖,部分依赖,传递依赖,直接依赖的区别 )。所以我们先构造完整依赖,判断依赖函数是否存在冗余属性,如果有就说明不满足不存在部份依赖,不为2NF。

只能对此题。构造非主属性对候选码的完整依赖 AB→C,AB→DAB\rightarrow C,AB\rightarrow DAB→C,AB→D,判断冗余属性(最小依赖集是不是用过呢?),可得两个依赖函数都没有冗余属性,即不存在非主属性对候选码的部份依赖,都是完全依赖,即符合2NF。

参考

求最小依赖集方法

数据库规范化理论大题考点

如何判断范式(1NF、2NF、3NF、BCNF)

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...