精华内容
下载资源
问答
  • 第一范式:定义很,其实说的就是列不可分。 如:   出厂日期  总额   数量 单价 在关系数据库中不能出现这种情况。   第二范式定义:若R∈1NF,且每一个非主属性完全函数依赖于码,则R...

    下面是Markdown来的,有些地方内容展现并不友好,建议直接看原文点击查看

    数据库中的函数依赖,主码,候选码等的区别点击打开链接

     

    数据库中的范式:分为,1NF,2NF,3NF,BCNF,4NF。一般我们,我们设计数据库到第三范式就算完整的了。它们的关系如下:

    第一范式:定义很多,其实说的就是列不可分。

    如:

     

    出厂日期

     总额

     

    数量

    单价

    在关系数据库中不能出现这种情况。

     

    第二范式定义:若R∈1NF,且每一个非主属性完全函数依赖于码,则R∈2NF。意思是非主属性完全依赖于码(候选码,主码),这里需要注意一下,是非主属性(候选码之外的属性),在前一篇文章已经说过。

    如:

     

    (学号, 系名, 课程号, 成绩) ∈1NF
      
    (学号, 系名, 课程号, 成绩)不属于 2NF
      

    在该关系模式中,学号+课程号是码,其他属性都是非主属性,但是只有成绩完全依赖于码,系名是部分依赖,因为学号就可以推出学生所在的系了。

     

    第三范式定义它的定义。。不打了,太烦了。其实说的就是消除 传递依

    。每一个非主属性都要直接依赖于码,不能传递依赖于码。如:在一个

    学生表中,我们规定一个系的学生是住在同一个宿舍区域的,于是,该关

    系模型为:

    学生表(学号, 系名, 宿舍区)

    在这关系中,学号为码,学号——>系名,学号——>宿舍区,但是,系名也能推出宿舍区,变成   学号——>系名——>宿舍区,即宿舍区传递依赖于学好了。

    解决方法:拆分成两个表:

    1(学号,系名),2(系名,宿舍区)

    从上面我们可以看到,在两个表中我们可以看到,当两个表通过外键(1表的系名,2中系名为主健)关联后,另一个表的的信息(如2表中的宿舍区)不能再写到包含外键关系的表中(1表)。

     

    BC范式:前面的三个范式是针对非主属性的,BC范式则是针对于码(什么是码,前篇文章说过),它要求每个函数的依赖关系中其决定因素都要包含码。

    如:

     

    在关系模式STJ(S,T,J)中,S表示学生,T表示教师,J表示课程。

               函数依赖:(S,J)→T,(S,T)→J, T→J 其中,(S,J)和(S,T)都是候选                 码。

    可以看出STJ中,它是属于第三范式的,因为没有哪一组依赖关系中,非主属性传递或者部分 依赖于码,(记住是非主属性,是候选码以外的属性,T在候选码中),但是,它不属于BC范式,因为T是决定因素,T不包含码(候选码的任何一个真子集都不能叫候选码)。

     

     

    多值依赖定义:第四范式需要掌握的一个内容。它说的就是设R(U)是一个属性集U上的一个关系模式, X、 Y和Z是U的子集,并且Z=U-X-Y。关系模式R(U)中多值依赖 X→→Y成立,当且仅当对R(U)的任一关系r,给定的一对(x,z)值,有一组Y的值,这组值仅仅决定于x值而与z值无关(想不到好的方法把它概括起来,哎!)

    判定方法:对于任意关系中,如果存在两个元组(就是行),记为A,B,如果他们的某一属性X的值相等,那么我们交换它们另外的属性Y的值后,得到的新的两个元组,在表中是可以在原来的表中找到与它们相匹配的元组的。

    如:

    该表中的码为(C,T,B)我们可以找到第一和第四行,它们的属性X=物理是相同的,当我们交换Y=教员属性后得到(物理,王军,普通物理学)和(物理,李勇,普通 物理学),与原来的表相比,是一毛一样的。我们也可以交换第三行和第四行,得到(物理,王军,物理习题集)和(物理,李勇,普通物理学),与原来表相比,我们还是能找到与它们相匹配的元组的。

     

     

    平凡多值依赖和非平凡的多值依赖:

    若X→→Y,而Z=φ,则称X→→Y为平凡的多值依赖否则称X→→Y为非平凡的多值依赖。

     

    多值依赖与函数依赖的区别:

     

    1)若函数依赖X→Y在R(U)上成立,则对于任何Y' 属于Y均有X→Y' 成立

     

    2)多值依赖X→→Y若在R(U)上成立,不能断言对于任何Y' 属于Y有X→→Y' 成立,因为多值依赖中,其实就是一对一组,一个老师可能交多门课,所以不同老师可能有教相同的课,所以不能推出X→→Y' 成立。我们可以看出,如果把一组改为一个,实际上就是函数依赖,所以所函数依赖是多值依赖的特例,多值依赖不一定是函数依赖,但函数依赖一定是多值依赖。

     

     

    多值依赖性质:

     

    (1)多值依赖具有对称性

    若X→→Y,则X→→Z,其中Z=U-X-Y

    (2)多值依赖具有传递性

    若X→→Y,Y→→Z, 则X→→Z –Y

    (3)函数依赖是多值依赖的特殊情况。

    若X→Y,则X→→Y。

    (4)若X→→Y,X→→Z,则X→→YU Z。

    (5)若X→→Y,X→→Z,则X→→Y∩Z。

     

    (6)若X→→Y,X→→Z,则X→→Y-Z,X→→Z -Y。

     

     

     

     

    第四范式:1)不允许有非平凡且非函数依赖的多值依赖


                     2)允许的非平凡多值依赖是函数依赖

                     3)平凡的多值依赖属于第四范式

     

    像,我们上面的图表(C,T,B),如果改成属于第四范式,就要分为:

     

                               CT(C, T) ∈ 4NF

                 CB(C, B) ∈ 4NF

    其中, C→→T, C→→B是平凡多值依赖。

     

    总结:

    目的:尽量消除插入、删除异常,修改复杂,数据冗余

     

     

     

    展开全文
  • 第6章 关系数据理论—多值依赖和4NF 本篇文章全部内容来自数据库系统概论第五版—王珊、萨师煊著。 这是对自己学习的总结,如有错误,请大家指正,一起进步! 1、多值依赖 例:学校某一门课程由个教授讲授,他们...

    第6章 关系数据理论—多值依赖和4NF


    本篇文章全部内容来自数据库系统概论第五版—王珊、萨师煊著。
    这是对自己学习的总结,如有错误,请大家指正,一起进步!


    1、多值依赖

    例:学校某一门课程由多个教授讲授,他们使用同一套参考书。每个教师可以讲授多门课程,每种参考是可以供多门课程使用。可以用一个非规范化的关系来表示教师T、课程C和参考书B之间的关系。如表所示:

    课程C教师T参考书B
    物理李勇普通物理学
    物理李勇光学原理
    物理李勇物理习题集
    物理王军普通物理学
    物理王军光学原理
    物理王军物理习题集
    数学李勇数学分析
    数学李勇微分方程
    数学李勇高等代数
    数学张平数学分析
    数学张平微分方程
    数学张平高等代数

    关系模式Teacher(C,T,B)的码是(C,T,B),所以Teacher属于BCNF,但是当某一课程增加一名讲课教师时,必须插入多个元组,类似的情况,如果某一门教材需要删除时,则必须删除多个元组。

    根据以上例子,可以发现这类关系模式具有一种多值依赖的数据依赖。

    **定义:**设R(U)是属性集U上的一个关系模式。X,Y,Z是U的子集,并且Z=U-X-Y。关系模式R(U)中多值依赖X->->Y成立,当且仅当对R(U)的任意关系r,给定的一对(x,z)值,有一组Y的值,这组值仅仅决定于x值,与z值无关。

    例:

    • 在关系模式Teacher中,对于一个(物理,光学原理)有一组T值{李勇,王军},这组值仅仅决定于课程C上的值(物理)。对于另一个(物理,普通物理学),它对应的一组T值仍是{李勇,王军},虽然参考书的值已经改变啦,因此T多值依赖于C。

    • 同样在关系模式Teacher中,对于一个(数学,李勇)有一组B值{数学分析,微分方程,高等代数},这组值仅仅决定于课程C上的值(数学)。对于另一个(数学,王军),它对应的一组B值仍是{数学分析,微分方程,高等代数},虽然教师T值已经改变啦,因此B多值依赖于C。

    若X->->Y(Y多值依赖于X),而Z是空值,则称Y多值依赖于X为平凡的多值依赖。

    例:关系模式WSC(W,S,C)中,W表示仓库,S表示保管员,C表示商品。假设每个仓库由若干个保管员,有若干个商品。每个保管员保管所在仓库的所有商品,每种商品被所有保管员保管。

    WSC
    W1S1C1
    W1S1C2
    W1S1C3
    W1S2C1
    W1S2C2
    W2S2C3
    W2S3C4
    W2S4C5
    W2S4C4

    多值依赖具有的性质:

    • 多值依赖具有对称性。
    • 多值依赖具有传递性。
    • 函数依赖可以看作是多值依赖的特殊情况。
    • 若X->->Y,X->->Z,则X->->YZ。
    • 若X->->Y,X->->Z,则X->->Y与Z的交集。
    • 若X->->Y,X->->Z,则X->->Y-Z,X->->Z-Y(差集)。

    多值依赖和函数依赖的区别:

    • 多值依赖的有效性与属性集的范围有关。
    • 若函数依赖X->Y在R(U)上成立,则对于任何Y的子集都函数依赖于X,在多值依赖中,这种情况不一定成立。

    4、4NF(第四范式)

    定义:关系模式R<U,F>属于1NF,如果对于R的每个非平凡多值依赖X->->Y(Y不包含于X),X都含有码,则称R<U,F>属于4NF。

    4NF就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。

    对每个非平凡的多值依赖X->->Y,X都含有候选码,于是就有X->Y,所以4NF所允许的非平凡的多值依赖实际上是函数依赖。

    例:在关系模式WSC中,W->->C,W->->S,它们都是非平凡的多值依赖。然而W不是码,关系模式WSC的码是(W,S,C),所以关系模式WSC不属于4NF。

    一个关系模式达到了BCNF但不是4NF ,仍然具有不好的性质,以WSC为例,WSC不属于4NF,但是WSC属于BCNF。在某一时刻时,某一仓库W1有n个保管员,存放m件物品,则关系中 分量W1的元组数目一定有mxn个。每个保管员重复存储m次,每种物品重复存储n次,数据的冗余度太大。

    采用投影分解法,消去非平凡且非函数依赖的多值依赖。

    WS(W,S)
    WC(W,C)
    
    展开全文
  • 函数依赖:设是属性集合上的一个关系模式,X,Y上U上的两个子集,若对的任意一个可能的关系r,r中不可能有两个元组满足在X中的属性相等而在Y中的属性不等,则称“X函数决定Y”或“Y函数依赖于X”,计作 ...

    一、函数依赖

    1.1 函数依赖的定义

    • 函数依赖:设R(U)是属性集合U=\left \{ A_1,A_2,...,A_n \right \}上的一个关系模式,X,Y上U上的两个子集,若对R(U)的任意一个可能的关系r,r中不可能有两个元组满足在X中的属性值相等而在Y中的属性值不等,则称“X函数决定Y”或“Y函数依赖于X”,计作X\rightarrow Y
    • 示例

    • 函数依赖的特性
      • X\rightarrow Y,但Y\not\subset X,则称X\rightarrow Y为非平凡函数依赖
      • X\rightarrow Y,则任意两个元组,若X上值相等,则Y上值必然相等,则称X为决定因素
      • X\rightarrow YY\rightarrow X,则记作X\leftrightarrow Y
      • 若Y不函数依赖于X,则记作X \not\rightarrow Y
      • X\rightarrow Y,有基于模式R的,则要求对任意的关系r成立,有基于具体关系r的,则要求对某一关系r成立

      • 如一关系r的某属性集X,r中根本没有X上相等的两个元组存在,则X\rightarrow Y恒成立

    二、完全函数依赖和传递函数依赖

    2.1 部分函数依赖与完全函数依赖的定义

    • R(U)中,若X\rightarrow Y并且对于X的任何真子集X'都有X' \not\rightarrow Y,则称Y完全函数依赖于X,记为:X \overset{f}{\rightarrow} Y,否则称Y部分函数依赖于X,记为:X\overset{p}{\rightarrow} Y
    • 示例

    2.2 传递函数依赖

    • R(U)中,若X\rightarrow YY\rightarrow ZY \not\subset XZ \not\subset YZ \not\subset XY \not\rightarrow X,则称Z传递函数依赖于X
    • 示例

    三、函数依赖相关的几个重要概念

    3.1 候选键的定义

    • 候选键:设K为R(U)中的属性或属性组合,若K\overset{f}{\rightarrow} U,则称K为R(U)上的候选键。
    • 说明
      • 可任选一候选键作为R的主键
      • 包含在任一候选键中的属性称主属性,其他属性称非主属性
      • 若K是R的一个候选键,S\supset K,则称S为R的一个超键
    • 示例

    3.2 外来键的定义

    • R(U)中的属性或属性组合X并非R的候选键,但X却是另一关系的候选键,则称X为R的外来键,简称外键

    3.3 逻辑蕴涵的定义

    • 设F是关系模式R(U)中的一个函数依赖集合,X,Y是R的属性子集,如果从F中的函数依赖能够推导出X\rightarrow Y,则称F逻辑蕴涵X\rightarrow Y,或称X\rightarrow Y是F的逻辑蕴涵。记作:F\models X\rightarrow Y
    • 说明
      • 设F是关系模式R(U)的函数依赖集合,X\rightarrow Y是一个函数依赖,若对R中的每个满足F的关系r,能够用形式逻辑推理的方法推出r也满足X\rightarrow Y,则称F\models X\rightarrow Y
      • 若满足F的每个关系均满足X\rightarrow Y,则说F逻辑蕴涵X\rightarrow Y

    3.4 闭包的定义

    • 被F逻辑蕴涵的虽哦有函数依赖集合称为F的闭包,记作:F^{+}
    • 说明
      • F^{+}=F,则说F是一个全函数依赖族(函数依赖完备集)。
    • 示例

    四、关于函数依赖的公理和定理

    4.1 函数依赖的Armstrong公理

    • R(U)是属性集U=\left \{ A_1,A_2,...,A_n \right \}上的一个关系模式,F为R(U)的一组函数依赖,记为:R(U,F),则有如下的规则成立:
      • [A1]自反律:若Y\subseteq X\subseteq U,则X\rightarrow Y被F逻辑蕴涵。
      • [A2]增广律:若X\rightarrow Y\in F,且Z\subseteq U,则XZ\rightarrow YZ被F逻辑蕴涵。
      • [A3]传递律:若X\rightarrow Y\in F,且Y\rightarrow Z,则X\rightarrow Z被F逻辑蕴涵。
    • [引理1]Armstrong's Axiom规则A1, A2, A3是有效的(正确的)。
    • [引理2]由Armstrong‘s Axiom可推出如下结论:
      • 合并律:若X\rightarrow YX\rightarrow Z,则X\rightarrow YZ
      • 伪传递律:若X\rightarrow YWY\rightarrow Z,则XW\rightarrow Z
      • 分解律:若X\rightarrow YZ\subseteq Y,则X\rightarrow Z
    • [引理3]如果A_1,A_2,...A_3是属性,则X\rightarrow A_1,A_2,...,A_n当且仅当对每个A_iX\rightarrow A_i(1\leq i\leq n)

    4.2 属性闭包

    • R\left ( U,F \right )X\subseteq UU=\left \{ A_1,A_2,...,A_n \right \},令:

    • X_{F}^{+}为X关于F的属性(集)闭包
    • 注:显然X\subseteq X_{F}^{+}
    • [引理4]:X\rightarrow Y可从F由Armstrong Axiom导出,当且仅当Y\subseteq X_F^{+}

    五、函数依赖集的最小覆盖

    5.1 覆盖的概念

    • R(U)上的两个函数依赖集合F、G,如果F^{+}=G^+,则称F和G是等价的,也称F覆盖G或G覆盖F。
    • [引理5]:F^+=G^+\Leftrightarrow F\subseteq G^+\wedge G\subseteq F^+

    5.2 属性闭包的计算算法

    • 计算一属性集关于一组函数依赖的属性闭包
    • Input:有限属性集合U,U上的函数依赖集合F,及U的子集X
    • Output:X关于F的属性闭包X^+,记为X_{F}^{+}
    • Method:按下列规则递归计算属性序列X^{(0)},X^{(1)},...
      • X^{(0)}=X,i=0
      • B=\left \{ A\mid (\exists V)(\exists W)(V\rightarrow W\in F\wedge V\subseteq X^{(i)}\wedge A\subseteq W) \right \}
      • X^{(i+1)}=B\cup X^{(i)}
      • if X^{(i+1)}\neq X^{(i)} then i=i+1;goto 2
      • X_F^+=X^{(i)},算法终止
    • 示例

    5.3 函数依赖集的性质

    • [引理6]每个函数依赖集F可被一个其右端至多有一个属性的函数依赖之集 G覆盖。

    5.4 最小覆盖

    • 若F满足以下条件,则称F为最小覆盖或最小依赖集
      • F中每个函数依赖的右部都是单个属性
      • 对任何X\rightarrow A\in F,有F-\left \{ X\rightarrow A \right \}不等价于F
      • 对任何X\rightarrow A\in FZ\subset X\left ( F-\left \{ X\rightarrow A \right \} \right )\cup \left \{ Z\rightarrow A \right \}不等价于F
    • [定理]:每个函数依赖集F都有等价的最小覆盖F^{+}​​​​​​​
    展开全文
  • 联系(Relationship)1:1联系:如果实体集E1中的每个实体最多只能和实体集E2中一个...函数依赖(FunctionDependency)定义设关系模式R(U),属性集合U={A1,A2,…,An},X,Y为属性集合U的子集,如果对于关系模式R(U)...

    联系(Relationship)1:1联系:如果实体集E1中的每个实体最多只能和实体集E2中一个实体有联系,反之亦然,那么实体集E1对E2的联系成为一对一联系,记为1:1;

    1:N联系:一对多,记为1:N;

    M:N联系:多对多联系,记为M:N。

    函数依赖(Function

    Dependency)

    定义设关系模式R(U),属性集合U={A1,A2,…,An},X,Y为属性集合U的子集,如果对于关系模式R(U)的任一可能的关系r,r中的任意两个元组u、v,若有u[X]=v[X],就有u[Y]=v[Y],则称X函数决定Y,或称Y函数依赖于X。用符号X→Y表示。其中X为决定因素,Y为被决定因素。若对于R(U)的任意一个可能的关系r,r中不可能存在两个元组在X上的属性值性等,而在Y上的属性值不等。 (1) 函数依赖是语义范畴的概念,只能根据语义来确定一个函数依赖关系。

    (2)

    函数依赖X→Y的定义要求关系模式R的任何可能的关系r中的元组都满足函数依赖条件。术语(1)若X→Y,则X称作决定因素(Determinant)

    (2)若X→Y,Y→X,称作XY。

    (3)若Y不函数依赖于X,称作X -/-> Y。

    (4)X→Y,若Y不包含X,则称X→Y为非平凡的函数依赖。正常讨论的都是非平凡的函数依赖。

    (5)X→Y,若Y包含X,则称X→Y为平凡的函数依赖。

    (6)完全函数依赖(full

    functional dependency):在R(U)中,设X、Y是关系模式R(U)中不同的属性子集,若存在

    X→Y,且不存在 X的任何真子集X',使得

    X'→Y,则称Y完全函数依赖 ( full functional dependency ) 于X。记作

    X-F->Y。

    (7)部分函数依赖:在关系模式R(U)中,X、Y是关系模式R(U)中不同的属性子集,若X→Y成立,如果X中存在任何真子集X',而且有X'→Y也成立,则称Y对X是部分函数依赖,记作:X-P->Y。

    (8)设R是关系模式,U是其属性集,K包含于U。若K完全函数确定U,则称K是R的候选键(又叫候选关键字,候选码)。包含在任意候选键内的属性称为键属性(又叫主属性),不是键属性的属性称为非键属性(又叫非主属性)。显然,候选键可以唯一标识关系的元组。候选键可能不唯一,通常指定一个候选键作为识别元组的主键。

    候选键的严格定义:

    关系模式R(U)的属性集合K ∈U的候选键,如果

    (1)R(U)的任何一个关系实例的任意两个元素在属性集合K上的值部不相同————唯一性

    (2)K的任何真子集都不满足条件 ————最小性

    通俗点,候选键在每一行数据里的值都不相同,就像自动增长的id一样,可以说成是候选的主键。

    码(键)是数据系统中的基本概念。所谓码就是能唯一标识实体的属性,它是整个实体集的性质,而不是单个实体的性质。

    它包括超码,候选码,主码。

    超键(super

    key):在关系中能唯一标识元组的属性集称为关系模式的超键(又叫超码),超码是一个或多个属性的集合,这些属性可以让我们在一个实体集中唯一地标识一个实体。超码的任意超集也是超码,也就是说如果K是超码,那么所有包含K的集合也是超码。

    候选键(candidate

    key):不含有多余属性的超键称为候选键(又叫候选码)。候选码是从超码中选出的,自然地候选码也是一个或多个属性的集合。因为超码的范围太广,很多是我们并不感兴趣即无用处的。所以候选码是最小超码,它们的任意真子集都不能成为超码。

    主键(primary key):用户选作元组标识的一个候选键程序主键(又叫主码)

    一题搞懂什么是候选键

    学号

    姓名

    性别

    年龄

    系别

    专业

    20020612

    李辉

    20

    计算机

    软件开发

    20020613

    张明

    19

    计算机

    软件开发

    20020614

    王小玉

    18

    物理

    力学

    20020615

    李淑华

    17

    生物

    动物学

    20020616

    赵静

    21

    化学

    食品化学

    20020617

    赵静

    20

    生物

    植物学

    【题目】数据库中有一个学生信息表如上所示,在该表中不能作为候选键的属性集合为( )

    (选择一项)

    a){学号} b){学号、姓名} c){年龄、系别} d){姓名、性别} e){姓名、专业}

    【解析】透过概念,我们可以了解到,超键包含着候选键,候选键中包含着主键。主键一定是惟一的。为什么呢?因为他的爷爷超键就是惟一的。

    我们分析一下上面的题目,a,b,c,d,e,5个答案都可以作为超键,他们组合在一起的集合可以用来惟一的标识一条数据记录(实体)。

    请注意我们的要求:候选键。候选键要求是不能包含多余属性的超键,我们看一下答案b。在答案b中,如果我们不使用姓名也可以惟一的 标识一条数据实体,可以说姓名字段在这里是多余的。那么很明显,b选项包含了多余字段属性。那么这题答案应该选择b。

    那么其他的4个选项都可以作为候选键,假设很幸运,a){学号}被选择作为用户正在使用的候选键来惟一标识元组了,那么他很幸运的获得了主键的称号

    【答案】b

    (9)若关系R的属性子集X是另一关系S的候选键,则称X是R关于S的外部键。主键和外部键描述了关系之间的联系。

    (10)传递函数依赖:在关系模式R(U)

    中,如果Y→X,X→A,且X

    Y(X不决定Y), A

    X(A不属于X),那么称Y→A是传递依赖。

    函数依赖的推理规则

    1.

    逻辑蕴含  给定一个关系模式,只考虑给定的函数依赖是不够的,必须找出在该关系模式上成立的其他函数依赖。

    逻辑蕴含:设F是关系模式R(U)的函数依赖集合,由F出发,可以证明其他某些函数依赖也成立,我们称这些函数依赖被F逻辑蕴含。"F蕴含X→Y"意味着关系实例只要满足F就满足X→Y。  例如,设F={ A→B,B→C },则函数依赖A→C被F逻辑蕴含,记作:F |=

    A→C。即函数依赖集 F 逻辑蕴含函数依赖A→C。

    2.

    F的闭包F+

    对于一个关系模式,如何由已知的函数依赖集合F,找出F逻辑蕴涵的所有函数依赖集合呢?这就是我们下面要讨论的问题。

    F的闭包F+:设F为一个函数依赖集,F的闭包是指F逻辑蕴涵的所有函数依赖集合。

    F的闭包记作F+。

    例如,给定关系模式R(A,B,C,G,H,I),函数依赖集合F={A→B,A→C,CG→H,CG→I,B→H}。可以证明函数依赖A→H被F逻辑蕴涵。

    设有元组s和t,满足s[A]=t[A],根据函数依赖的定义,由已知的A→B,可以推出s[B]=t[B]。又根据函数依赖B→H,可以有s[H]=t[H]。因此,已经证明对任意的两个元组s和t,只要有s[A]=t[A],就有s[H]=t[H]。所以,函数依赖A→H被F逻辑蕴涵。

    计算F的闭包F+,可以由函数依赖的定义直接计算,如上面的示例。但是,当F很大时,计算的过程会很长。为了从已知的函数依赖推导出其它函数依赖,Armstrong

    提出了一套推理规则,称为Armstrong 公理

    ,通过反复使用这些规则,可以找出给定F的闭包F+。其推理规则可归结为如下3条:自反律(reflexivity)、增广律(augmentation)和

    传递律(transitivity)。

    3.Armstrong 公理

    设U为属性总体集合,F为U上的一组函数依赖,对于关系模式R(U,F),X、Y、Z为属性U的子集,有下列推理规则:

    A1:自反律(reflexivity) 若Y X U,则X→Y为F所蕴函。

    A2:增广律(augmentation) 若X→Y为F所蕴函,且Z是U的子集,则XZ→YZ为F所蕴函。式中XZ和YZ是X∪Z 和 Y∪Z的简写。

    A3:传递律(transitivity)  若X→Y、Y→Z为F所蕴函,则X→Z为F所蕴函。

    由自反律所得到的函数依赖都是平凡的函数依赖,自反律的使用并不依赖于F,而只依赖于属性集U。

    Armstrong公理是有效的和完备的。可以利用该公理系统推导F的闭包F+。由于利用Armstrong公理直接计算F+很麻烦。根据A1,

    A2, A3这三条推理规则还可以得到其他规则,用于简化计算F+的工作。如下面扩展的三条推理规则:

    *合并规则: 由X→Y, X→Z, 有X→YZ

    *伪传递规则: 由X→Y, WY→Z, 有XW→Z

    *分解规则: 由X→YZ, 则有X→Z,X→Y

    Armstrong公理可以有多种表示形式,例如,增广律A2可以用合并规则代替。例如,用自反律A1,传递律A3和合并规则可推导出增广律A2。

    证明:XZ →X (A1:自反律)   X →Y (给定条件)   XZ →Y (A3:传递律)  XZ →Z

    (A1:自反律)  XZ →YZ (合并规则)4.属性集的闭包

    原则上讲,对于一个关系模式R(U,F),根据已知的函数依赖F,反复使用前面的规则,可以计算函数依赖集合F的闭包F+。但是,利用推理规则求出其全部的函数依赖F+是非常困难的,而且也没有必要。因此,可以计算闭包的子集,即选择一个属性子集,判断该属性子集能函数决定哪些属性,这就是利用属性集闭包的概念。

    (1)属性集闭包的定义

    设F为属性集U上的函数依赖集,X∈U,即X为U的一个子集。在函数依赖集F下被X函数决定的所有属性为F+下属性集X的闭包,记作X+。即X+={

    A| X→A } 。

    (2)计算属性集闭包X+的算法如下:

    输入:X,F

    输出: X+ 迭代算法的步骤:

    ① 选取X+的初始值为X ,即X+={X};

    ② 计算X+, X+={X,Z} ,其中Z要满足如下条件:

    Y是X+的真子集,且F中存在一函数依赖Y→Z。实际上就是以X+中的属性子集作为函数依赖的决定因素,在F中搜索函数依赖集,找到函数依赖的被决定属性Z放到X+中。

    判断:如果X+没有变化?或X+等于U?则X+就是所求的结果,算法终止。否则转②。

    因为U是有穷的,所以上述迭代过程经过有限步骤之后就会终止。

    例如,已知关系模式R(U,F),U={A,B,C,D,E,G},F={AB→C,D→EG,C→A,BE→C,BC→D,AC→B,CE→AG},求(BD)+

    解:

    ① (BD)+ = {BD};

    计算(BD)+ ,在F中扫描函数依赖,其左边为B,D或BD的函数依赖,得到一个D→EG。所以,(BD)+=

    {BDEG}。

    计算(BD)+,在F中查找左部为BDEG的所有函数依赖,有两个:D→EG和BE→C。所以(BD)+={(BD)∪EGC}={BCDEG}。

    计算(BD)+,在F中查找左部为BCDEG子集的函数依赖,除去已经找过的以外,还有三个新的函数依赖:C→A,BC→D,CE→AG。得到(BD)+={(BD)∪ADG}={ABCDEG}。

    ⑤ 判断(BD)+=U,算法结束。得到(BD)+={ABCDEG}。

    说明:上面说明(B,D)是该关系模式的一个候选码。

    5.

    Armstrong公理系统的有效性和完备性

    ①Armstrong公理系统的有效性指的是:由F出发根据Armstrong公理系统推导出来的每一个函数依赖一定是F所逻辑蕴含的函数依赖。

    ②Armstrong公理系统的完备性指的是:对于F所逻辑蕴含的每一函数依赖,必定可以由F出发根据Armstrong公理系统推导出来。

    6. 极小函数依赖集(最小函数依赖集)

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

    ① F中的任何一个函数依赖的右部仅含有一个属性;

    ② F中不存在这样一个函数依赖X→A,使得F与F-{X→A}等价;

    ③ F中不存在这样一个函数依赖X→A,X有真子集Z使得F-{X→A}∪{Z→A}与F等价。

    求最小函数依赖集分三步:

    1.将F中的所有依赖右边化为单一元素

    此题fd={abd->e,ab->g,b->f,c->j,cj->i,g->h};已经满足

    2.去掉F中的所有依赖左边的冗余属性. 作法是属性中去掉其中的一个,看看是否依然可以推导

    此题:abd->e,去掉a,则(bd)+不含e,故不能去掉,同理b,d都不是冗余属性 ab->g,也没有

    cj->i,因为c+={c,j,i}其中包含i所以j是冗余的.cj->i将成为c->i F={abd->e,ab->g,b->f,c->j,c->i,g->h};

    3.去掉F中所有冗余依赖关系.

    做法为从F中去掉某关系,如去掉(X->Y),然后在F中求X+,如果Y在X+中,则表明x->是多余的.需要去掉.

    此题如果F去掉abd->e,F将等于{ab->g,b->f,c->j,c->i,g->h},而(abd)+={a,d,b,f,g,h},其中不包含e.所有不是多余的.

    同理(ab)+={a,b,f}也不包含g,故不是多余的.

    b+={b}不多余,c+={c,i}不多余

    c->i,g->h多不能去掉.

    所以所求最小函数依赖集为

    F={abd->e,ab->g,b->f,c->j,c->i,g->h};

    多值依赖

    1、定义

    设R(U)是属性集U上的一个关系模式。X,Y,Z是U的子集,并且Z=U-X-Y。关系模式R(U)中多值依赖X→→Y成立,当且仅当对R(U)的任一关系r,给定的一对(x,z)值有一组Y的值,这组值仅仅决定于x值而与z值无关。

    若X→→Y,而Z=,则称X→→Y为平凡的多值依赖。否则称X→→Y为非平凡的多值依赖。

    多值依赖也可以形式化地定义如下:

    在关系模式R(U)的任一关系r中,如果对于任意两个元组t,s,有t[X]=s[X],就必存在元组w,v∈r(w和v可以与s和t相同),使得w[X]=v[X]=t[X],而w[Y]=t[Y],w[Z]=s[Z],v[Y]=t[Z],即交换s,t元组的Y值所得的两个新元组必在r中,则称Y多值依赖于X,记为X→→Y。其中,X和Y是U的子集,Z=U-X-Y。

    多值依赖属4nf的定义范围,比函数依赖要复杂得多,很多书上都没有讲清楚。

    2、说得简单点就是

    在关系模式中,函数依赖不能表示属性值之间的一对多联系,这些属性之间有些虽然没有直接关系,但存在间接的关系,把没有直接联系、但有间接的联系称为多值依赖的数据依赖。例如,教师和学生之间没有直接联系,但教师和学生可通过系名,或任课把教师和学生联系起来。

    3、举例如下

    【例1】有这样一个关系

    ,假设一个一个产品只能放到一个仓库中,但是一个仓库可以由若干管理员,那么对应于一个

    【例2】(C,B)上的一个值(物理,光学原理)对应一组T值(李平,王强,刘明),这组值仅仅决定于课程C上的值,也就是说对于(C,B)上的另一个值(物理,普通物理学),它对应的一组T值仍是(李平,王强,刘明),尽管这时参考书B的值已经改变了。因此T多值依赖于C,即C→→T。

    4、多值依赖具有下列性质

    ●多值依赖具有对称性。即若X→→Y,则X→→Z,其中Z=U-X-Y。

    ●多值依赖具有传递性。即若X→→Y,Y→→Z,则X→→Z-Y。

    ●函数依赖可以看作是多值依赖的特殊情况。

    ●若X→→Y,X→→Z,则X→→YZ。

    ●若X→→Y,X→→Z,则X→→Y∩Z。

    ●若X→→Y,X→→Z,则X→→Y-Z,X→→Z-Y。

    ●多值依赖的有效性与属性集的范围有关。

    ●若多值依赖X→→Y在R(U)上成立,对于Y'

    Y,并不一定有X→→Y’成立。但是如果函数依赖X→Y在R上成立,则对于任何Y'

    Y均有X→Y’成立。

    范式

    • 如果某个数据库模式都是第一范式的,则称该数据库模式是属于第一范式的数据库模式。【无重复的列】

    缺点:数据冗余,删除异常,插入异常,修改复杂• 如果关系模式R为第一范式,并且R中每一个非主属性完全函数依赖于R的某个候选键,则称为第二范式模式。【消去非主属性对键的部分函数依赖】 缺点:删除异常,插入异常,修改复杂• 如果关系模式R是第二范式,且每个非主属性都不传递依赖于R的候选键,则称R为第三范式模式。【消去非主属性对键的部分和传递函数依赖】• 若关系模式R是第一范式,且每个属性都不传递依赖于R的候选键。这种关系模式就是BCNF模式。【消去主属性对键的部分和传递函数依赖】

    若R上的多值依赖集合D中成立非平凡多值依赖X→→Y时,X必是R的超键,则R∈4NF。

    由BCNF的定义可以得到以下结论,一个满足BCNF的关系模式有: 所有非主属性对每一个码都是完全函数依赖。

    所有的主属性对每一个不包含它的码,也是完全函数依赖。

    没有任何属性完全函数依赖子非码的任何一组属性。

    由于R∈BCNF,按定义排除了任何属性对码的传递依赖与部分依赖;所以R∈3NF。

    • 若关系模式R是第一范式,且对于R的每个非平凡多值依赖X→→Y(Y

    X),X都含有码,则称R∈4NF。【消除非平凡且非函数依赖的多值依赖】

    4NF就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。因为根据定义,对于每一个非平凡的多值依赖X→→Y,X都含有候选码,于是就有X→Y,所以4NF所允许的非平凡的多值依赖实际上是函数依赖。

    •设R,R1,R2,...,Rn是关系模式,U,U1,U2,...,Un分别是R,R1,R2,...,Rn的属性集合,而且U=U1∪U2∪...∪Un。如果R的任意关系实例r满足:

    r=πR1(r) ⋈ πR2(r) ⋈

    ... ⋈ πRn(r),则称R满足联结依赖,记作⋈(R1,R2,...,Rn)

    R中除了超建构成的联结依赖外,没有其他联结依赖存在,称R为5NF。

    判断无损连接和函数依赖

    大部分是对一个关系模式分解成两个模式的考察,分解为三个以上模式时无损分解和保持依赖的判断比较复杂,考的可能性不大,因此我们只对“一个关系模式分解成两个模式”这种类型的题的相关判断做一个总结。

    以下的论述都基于这样一个前提:

    R是具有函数依赖集F的关系模式,(R1 ,R2)是R的一个分解。

    首先我们给出一个看似无关却非常重要的概念:属性集的闭包。

    令α为一属性集。我们称在函数依赖集F下由α函数确定的所有属性的集合为F下α的闭包,记为α+ 。

    下面给出一个计算α+的算法,该算法的输入是函数依赖集F和属性集α,输出存储在变量result中。

    算法一:

    result:=α;

    while(result发生变化)do

    for each

    函数依赖β→γ in F do

    begin

    if β∈result then result:=result∪γ;

    end

    属性集闭包的计算有以下两个常用用途:

    ·判断α是否为超码,通过计算α+(α在F下的闭包),看α+ 是否包含了R中的所有属性。若是,则α为R的超码。

    ·通过检验是否β∈α+,来验证函数依赖是否成立。也就是说,用属性闭包计算α+,看它是否包含β。

    (请原谅我用∈符号来表示两个集合之间的包含关系,那个表示包含的符号我找不到,大家知道是什么意思就行了。)

    看一个例子吧,2005年11月系分上午37题:

    给定关系R(A1,A2,A3,A4)上的函数依赖集F={A1→A2,A3→A2,A2→A3,A2→A4},R的候选关键字为________。

    (37)A. A1  B. A1A3  C. A1A3A4  D. A1A2A3

    首先我们按照上面的算法计算A1+ 。

    result=A1,

    由于A1→A2,A1∈result,所以result=result∪A2=A1A2

    由于A2→A3,A2∈result,所以result=result∪A3=A1A2A3

    由于A2→A4,A2∈result,所以result=result∪A3=A1A2A3A4

    由于A3→A2,A3∈result,所以result=result∪A2=A1A2A3A4

    通过计算我们看到,A1+ =result={A1A2A3A4},所以A1是R的超码,理所当然是R的候选关键字。此题选A 。

    好了,有了前面的铺垫,我们进入正题。

    无损分解的判断。

    如果R1∩R2是R1或R2的超码,则R上的分解(R1,R2)是无损分解。这是一个充分条件,当所有的约束都是函数依赖时它才是必要条件(例如多值依赖就是一种非函数依赖的约束),不过这已经足够了。

    保持依赖的判断。

    如果F上的每一个函数依赖都在其分解后的某一个关系上成立,则这个分解是保持依赖的(这是一个充分条件)。

    如果上述判断失败,并不能断言分解不是保持依赖的,还要使用下面的通用方法来做进一步判断。

    该方法的表述如下:

    算法二:

    对F上的每一个α→β使用下面的过程:

    result:=α;

    while(result发生变化)do

    for each

    分解后的Ri

    t=(result∩Ri)+ ∩Ri

    result=result∪t

    这里的属性闭包是在函数依赖集F下计算出来的。如果result中包含了β的所有属性,则函数依赖α→β。分解是保持依赖的当且仅当上述过程中F的所有依赖都被保持。

    下面给出一个例题,2006年5月系分上午43题:

    ●设关系模式R,其中U={A, B, C, D,

    E},F={A→BC,C→D,BC→E,E→A},则分解ρ={R1(ABCE),R2(CD)}满足 (43) 。

    (43) A.具有无损连接性、保持函数依赖

    B.不具有无损连接性、保持函数依赖

    C.具有无损连接性、不保持函数依赖

    D.不具有无损连接性、不保持函数依赖

    先做无损链接的判断。R1∩R2={C},计算C+。

    Result=C

    由于C→D,C∈result,所以result=result∪D=CD

    可见C是R2的超码,该分解是一个无损分解。

    再做保持依赖的判断。

    A→BC,BC→E,

    E→A都在R1上成立(也就是说每一个函数依赖左右两边的属性都在R1中),C→D在R2上成立,因此给分解是保持依赖的。

    选A。

    再看一个复杂点的例题。2007年5月数工40-41题。

    ●给定关系模式R,U={A, B, C, D,

    E},F={B→A,D→A,A→E,AC→B},其候选关键字为 (40) ,则分解ρ={R1(ABCE),R2(CD)}满足 (41) 。

    (40) A.ABD

    B.ABE

    C.ACD

    D.CD

    (41) A.具有无损连接性、保持函数依赖

    B.不具有无损连接性、保持函数依赖

    C.具有无损连接性、不保持函数依赖

    D.不具有无损连接性、不保持函数依赖

    看见了吧,和前面一题多么的相像!

    对于第一问,分别计算ABCD四个选项的闭包,

    (ABD)+ = { ABDE }

    (ABE)+ = { ABE }

    (ACD)+ = { ABCDE }

    (CD)+ = { ABCDE }

    选D。

    再看第二问。

    先做无损链接的判断。R1∩R2={C},计算C+。

    result=C

    因此C既不是R1也不是R2的超码,该分解不具有无损分解性。

    再做保持依赖的判断。

    B→A,A→E,AC→B在R1上成立,D→A在R1和R2上都不成立,因此需做进一步判断。

    由于B→A,A→E,AC→B都是被保持的(因为它们的元素都在R1中),因此我们要判断的是D→A是不是也被保持。

    对于D→A应用算法二:

    result=D

    对R1,result∩R1=ф(空集,找不到空集的符号,就用这个表示吧),t=ф,result=D

    再对R2,result∩R2=D,D+ =ADE ,t=D+ ∩R2=D,result=D

    一个循环后result未发生变化,因此最后result=D,并未包含A,所以D→A未被保持,该分解不是保持依赖的。

    选D。

    展开全文
  • 一、 问题的提出 ...2、多值依赖。 关系数据库中所存在的问题: 数据冗余 更新异常 插入异常 删除异常 但是一个好的模式应当不会发生插入异常、删除异常和更新异常,数据冗余尽可能减少。 二、 规范化
  • 数据依赖

    2021-03-28 15:50:22
    人们已经提出了许多类型的数据依赖,其中最重要的是函数依赖和多值依赖。 举例说明 函数依赖极为普遍的存在现实生活中,比如描述一个学生的关系,可以有学号,姓名,系号等几个属性,由于一个学号只对应一个学生,一...
  • 原子性是指一个操作是不可中断的,要么全部执行成功要么全部执行失败,及时在个线程一起执行的时候,一个操作一旦开始,就不会被其他线程所干扰。 int a = 10; //1 a++; //2 int b=a; //3 a = a+1; //4 其中只有1...
  • -数据依赖 -范式(1NF,2NF,3NF,BCNF) -关系模式的规范化 关系:描述实体及其属性、实体间的联系。 -它是一张二维表,是所涉及属性的笛卡尔积的一个子集。 关系模式:用来定义关系。 Student (Sno, Sname, Ssex, ...
  • tensorflow赋值和依赖

    2021-09-24 14:33:59
    黄色的是参考边 reference edge 表示节点的输出用于改变箭头指向的向量,但对于指向的向量来说不存在DAG里的拓扑依赖 灰色的是数据流边 dataflow edge 箭头指向的向量的计算在DAG中对上游向量存在拓扑依赖 import ...
  • 验证信号为矩形信号,结果显示虚部是不为零且最大幅等于 ... Matlab中的一些小技巧 (转于它处,仅供参考) 1.. Ctrl+C 中断正在执行的操作 如果程序不小心进入死循环,或者计算时间太长,可以在命令窗口中使用Ctrl+c来...
  • Java求两个数平均

    2021-03-05 20:46:25
    如何正确的求2个数的平均。在练习算法二分查找的时候发现的,以前没有注意到的bug备注:数据以int类型为例一、以前的通用写法/*** 求a+b平均* @param a* @param b* @return a+b的平均*/static int avg(int a ,...
  • tmAST/tmFG,球队助攻数/球队命中数 即球员罚中越,数值越大,球队整体战越强(得分主要依赖于助攻,罚球机会少),数值越小。 第四项是衡量球员罚球上的贡献。 第五项:-VOP*TO VOP= lgPTS / (lgFGA - lgORB +...
  • 同时,图像的类要分的越,那么这种子空间之间的交叠现象就越严重,及时再去从每个类别的子空间中去寻找线性不变的子空间或者因子,也无法消除这种交叠性----Fisher算法试图绕过去,但是却付出了严重依赖初始数据的...
  • 是公说公有理,婆说婆有理的问题,只是个人理解不同而称呼有异,这也给一些人,尤其是初学者带来一定的困扰,鉴于此,特整理《数据库常用专业术语的基本概念的定义与理解》这篇文章,行文参考了很网上的资料(请...
  • 马尔可夫性质:一句话总结就是“未来只与现在有关”,即给定一个过程当前状态及历史的所有状态,其未来状态仅依赖于当前状态,与历史状态无关,这种性质叫做马尔科夫性质。这里比较有意思的事情是,有些非马尔可夫...
  • 关系模式无损连接或保持依赖的分解算法3.1 关系模式分解成BCNF3.2 关系模式分解成3NF3.3 既保持依赖,又无损连接的分解3.4 无损连接分解成4NF![在这里插入图片描述]...
  • 【DP】 有依赖的背包问题
  • 球员效率

    2021-07-29 02:16:21
    [1]中文名球员效率外文名Player Efficiency Rating提出者约翰·霍林格性质篮球高阶数据球员效率概念简介编辑语音PER评估了球员每分钟的贡献同时根据比赛节奏进行了调整。在每分钟下,我们...
  • 为了使用这项新特性,你需要在你的仓库里创建一个vcpkg.json的清单文件,用来声明各个程序包的依赖关系。请注意,在命令行模式下安装的程序库还暂未支持版本控制(例如,使用vcpkg install library_name)。版本控制...
  • 数据处理之异常处理

    千次阅读 2021-03-17 19:52:39
    异常是指那些在数据集中存在的不合理的,需要注意的是,不合理的是偏离正常范围的,不是错误。比如人的身高为-1m,人的体重为1吨等,都属于异常的范围。虽然异常不常出现,但是又会对实际项目分析有...
  • (2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有义性;(3)有穷性,算法必须能在有限的时间内做完,包括合理的执行时间的含义;(4)拥有足够的情报。算法的基本要素:一是对...
  • 并发三大性质

    2021-06-03 21:13:02
    一个操作或者个操作 要么全部执行并且执行的过程不会被任何因素打断,要么就都不执行。 2. 可见性 一个线程对共享变量的修改,能够及时的被其他线程看到。 共享变量 如果一个变量在个线程的工作内存中都存在...
  • 二、类图中属性的表示方式三、类图中方法的表示方式四、类图中类关系的表示方式1、依赖(Dependence)2、关联(Association)3、聚合(Aggregation)4、组合(Composition)5、泛化(Generalization)6、实现...
  • 在机器学习中,异常检测和处理是一个比较小的分支,或者说,是机器学习的一个副产物,因为在一般的预测问题中,模型通常是对整体样本数据结构的一种表达方式,这种表达方式通常抓住的是整体样本一般性的性质,而那些...
  • 6. 函数依赖及其公理定理 6.1 函数依赖 6.2 部分或完全函数依赖 6.3 传递函数依赖 6.4 候选键 6.5 逻辑蕴含 6.6 闭包 6.7 关于函数依赖的公理和定理 6.8 属性集闭包 6.9 覆盖 6.10 最小覆盖 6.11 多值依赖 6.12 多值...
  • 近期有网友在博客中留言,希望俺介绍散列校验文件的知识。所以俺干脆写一篇“文件完整性校验”的扫盲教程。由于本文是扫盲性质,尽量不涉及太技术化的内容。 ★啥是“完整性校验”? 所谓的“完整性校验”,...
  • 依赖注入与服务定位器(Dependency Injection/Service Location)¶Phalcon\Di 是一个实现依赖注入和定位服务的组件,而且它本身就是一个装载它们的容器。因为Phalcon是高度解构的,整合框架的不同组件,使用 Phalcon\...
  • 《计算机软件功能测试基本知识之边界》由会员分享,可在线阅读,更相关《计算机软件功能测试基本知识之边界(7页珍藏版)》请在人人文库网上搜索。1、边界测试? 本章内容 边界分析(掌握) 健壮性测试(掌握) ...
  • 详解GCN的性质

    2021-04-20 22:58:00
    GCN 的性质 GCN 与 CNN 的联系 1. 图像是一种特殊的图数据 在图像中如果将像素视作节点,将像素之间空间坐标的连线作为彼此之间的边,如此图像数据就变成了一种结构非常规则的图数据,CNN 中的卷积计算则是用来出来...
  • GZone 一般被 RZone 依赖,提供的大部分是读取服务。 CZone(City Zone):顾名思义,这是以城市为单位部署的单元。同样部署了不可拆分的数据和服务,比如用户账号服务,客户信息服务等。理论上 CZone 会被 RZone 以...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 75,959
精华内容 30,383
关键字:

多值依赖的性质