精华内容
下载资源
问答
  • 主键,超键,外键,候选键函数依赖,第一范式,第二范式,第三范式,BCNF,第四范式
    2020-12-19 11:43:16

    最近回顾了下数据库的相关知识,正好借着这个机会,把其中一些概念重新理一理,也加深一些印象。

    首先我们来看看数据库中的基本概念:

    超键(super-key):在一个关系中能唯一地标志一个元组。

    候选键(candidate):最小的超键,其任意真自己都不能成为一个超码。例如,(身份证号,姓名)和(身份证号)都可以试超键,但(身份证号)是候选码。

    主键(primary key):用户选作元组标识的一个候选键程序主键。主键通常由用户从候选码中选择出来的。

    外键(foreign key):假设存在两组关系,r和s,其中r(A, B, C), s(B, D),在关系r上的属性B称作参照s的外键,r也成为外码依赖的参照关系,s叫做外码被参照关系。参照关系中外键的值必须在参照关系中存在或者null

    主属性:包括在候选键中的属性。

    熟悉了这些概念之后我们来看看范式。

    范式(Normal Form)

    目前常见的范式包括第一范式(1NF),第二范式(2NF),第三范式(3NF),Boyce-Codd(BCNF)和第四范式(4NF)。

    第一范式:关系模式中的所有熟悉的域都是原子的。

    如果某个域中元素被认为是不可分的,则成这个域为原子的。如姓名,可以拆分为姓和名,因此,这里的姓名是非原子的。1NF的缺点是存在数据的冗余以及当插入更新删除是容易出现异常。

    第二范式:在满足第一范式的关系模式中,每一个非主属性完全函数依赖于任何一个候选键,则R属于第二范式。

    满足第一范式的关系模式可以通过模式分解,生产满足第二范式的多个关系模式。

    模式分解需要满足一下两个条件

    无损分解:

    在分解之后,n个分解关系通过自然连接(自然连接是在等值连接的基础上去掉相同的列,如果自然连接中找不到等值信息那么自然连接就等价于笛卡尔积)形成的二维表和没分解之前关系的二维表是等价的(元组没有增加也没有减少),则称这种分解形成的关系模式保持无损连接性;

    R1∩R2→(R1-R2)或R1∩R2→(R2-R1)

    保持函数依赖(functional dependency):

    函数依赖借助了数学上的函数概念 α→β,即在属性集α上的值相同时,其在属性集β上的值也相同,我们称β函数依赖与α,α函数决定β。

    若分解之后的关系模式中仍然存在和没分解之前属性的函数依赖关系则称保持分解的函数依赖性。

    (F1∪F2)+=F+

    这里面的F+称作F的闭包,即当给定函数依赖集F,存在其他函数依赖被F逻辑蕴含,例如如果A→B,且B→C则可推出A→C。这里了可以利用Armstrong公理找出F+。

    Armstrong公理:

    自反律:若β⊆α,则α→β;

    增补律:若α→β,则γα→γβ;

    传递律:若α→β且β→γ,则α→γ。

    平凡依赖 (trivial  functional dependency):被所有关系实例都满足的函数依赖成为平凡依赖。一般来说,若β⊆α,则α→β是平凡的,相反,则α→β是不平凡的。

    部分依赖:已知α→β,存在α中的真子集可以函数决定β。例如α为(学号,身份证号),β为(姓名)α中的真子集(学号或者身份证号)可以决定β。

    完全依赖:已知α→β,不存在α中的真子集可以函数决定β。例如α为(学号,学校名),β为(姓名)α中的真子集(单独的学号或者学校名)不能决定β。

    传递依赖:若α→β且β→γ,则α→γ。例如α为学号,β为学院,γ为院长。

    第三范式:关系模式R中,所有函数依赖α→β满足以下条件之一:

    * α→β是平凡依赖

    * α是R的超键

    * β-α中的每个属性A都包含于R的一个候选码中。

    这里主要说一下第三条。

    因此,第三范式换句话说,在满足第三范式的关系模式中,非主属性必须直接完全函数依赖于主键,中间不能有其他函数,即不能是传递函数依赖。

    第二、三范式消除的是非主属性对键的部分依赖和传递依赖。

    BC范式:关系模式R中,所有函数依赖α→β满足以下条件之一:

    * α→β是平凡依赖

    * α是R的超键

    第三范式和BC范式的区别在于第三范式允许主属性传递依赖于键码而BC范式不允许任何属性传递依赖于主键,包括主属性。因此,两个属性的肯定是满足BC范式的。

    例如:R=(J,K,L),F={JK→L,L→K}。这个情况下满足第三范式,但不满足BC范式。这里的候选键可以是JK和JL。

    因此相比于BC范式,第三范式存在冗余。

    第四范式:

    设R是一个关系模型,D是R上的多值依赖集合。如果D中存在多值依赖,α→→β,满足一下条件之一则属于第四范式:

    α→→β是评分的;

    α为R的超键。

    更多相关内容
  • 候选键的本质是找一组键,能够完全表示所有元素。如果能理解,最好不要死记解题格式。如果不是很理解,可参考以下思路,个人见解。1.只在左边的的一定是候选键说明此键可以表示别人,但无法被别人表示。2.只在右边...

    找候选键的本质是找一组键,能够完全表示所有元素。

    如果能理解,最好不要死记解题格式。

    如果不是很理解,可参考以下思路,个人见解。

    1.只在左边的的一定是候选键说明此键可以表示别人,但无法被别人表示。

    2.只在右边的一定不是候选键说明此键只能被别人表示,而不能表示别人。

    3.两边都没有的一定是候选键说明既不能表示别人,也不能被别人表示,则只能自己表示自己。

    4.两边都有的需讨论。两边都有的要具体讨论。

    最后要检查一下是不是最小集。

    注:候选键可能不唯一。

    例如提问的这题,红背景太刺眼了,我给列出来了。

    第一步:C和E一定是候选键。

    第二步:A一定不是候选键。

    然后开始分析:

    若想得到B,B只能由CDE得出,而D只能由B推出,则B和D至少有一个为候选键。

    假设B为候选键,观察关系式,D可由B推出,A可由BD推出,G可由CE推出。即全部被表示,成立。故,确定{BCE}为候选键。

    假设D为候选键,观察关系式,B可由CDE推出,A可由BD推出,G可由CE推出。即全部被表示,成立。故,确定{CDE}也为候选键。

    综上,本题候选键为{BCE}、{CDE}

    我也是最近学习的,若有问题,欢迎及时指出。

    展开全文
  • 一、函数依赖1. 函数依赖定义:设 R(U) 是属性集合 U={ A1, A2, ... , An } 上的一个关系模式,X, Y 是 U 上的两个子集,若对 R(U) 的任意一个可能的关系 r ,r 中不可能有两个元组满足在 X 中的属性值相等而在 Y 中...

    一、函数依赖

    1. 函数依赖

    定义:设 R(U) 是属性集合 U={ A1, A2, ... , An } 上的一个关系模式,X, Y 是 U 上的两个子集,若对 R(U) 的任意一个可能的关系 r ,r 中不可能有两个元组满足在 X 中的属性值相等而在 Y 中的属性值不等,则称 “ X 函数决定 Y ” 或 “ Y函数依赖于X ” ,记作

    白话:在一个关系 R 中,属性(组) Y 的值是由属性(组) X 的值所决定的 。又可以说,在关系 R 中,若两个元组的 X 属性值相同,那么这两个元组的 Y 属性值也相同。

    为什么叫做函数依赖? 函数的定义:对于定义域中任意 x ,有且只有一个 y 与之对应。 属性之间的依赖:对于相同的 X 属性值,有且只有一个 Y 属性值与之对应。

    本质:函数依赖的本质就是反应了 一个关系中属性之间的约束关系,或者依赖关系。函数依赖是一种数据依赖。

    举例:1. U = { 学号,姓名,年龄,专业 }

    {学号}

    { 姓名,年龄,专业 }

    函数依赖 分为 非平凡函数依赖 和 平凡函数依赖。 非平凡函数依赖:对

    ,但

    ,则称

    为非平凡的函数依赖。也就是说 X 决定 Y,但是 Y 不在 X 中,这种叫做非平凡函数依赖。否则就是平凡函数依赖。

    2. 完全函数依赖和部分函数依赖

    定义:在关系 R(U) 中, 若

    ,且对于 X 的任何真子集 X‘ 都有 X’

    Y,则称 Y 完全函数依赖于 X,记为:

    。否则称 Y函数部分依赖于 X,记为

    白话:完全函数依赖就是说 属性组 X 的所有属性一起(即完全)才能决定属性 Y,去掉任何一个属性都不行。相反的,部分函数依赖就是说 属性组 X 中的 部分属性就可以决定 Y ,用不着全部。

    Insight:如果 属性(组)Y 部分函数依赖于 属性组 X,则说明属性组 X 中存在着对属性(组) Y 的非受控冗余。在设计数据库时应避免这种情况。(对应着 2NF )。

    举例:U = {学号,姓名,年龄,班号,班长,课号,成绩 }

    {学号,课号}

    U

    { 学号,课号 }

    { 姓名,年龄 }

    { 学号,课号 }

    { 成绩 }

    解释:单个学号可以决定性别和年龄,单个学号就可以决定成绩。因此

    是部分函数依赖。

    3. 传递函数依赖

    定义:在 R(U) 中,若

    ,且

    ,则称 Z 传递函数依赖于 X 。

    白话:如果 X 函数决定 Y,Y 函数决定Z,且 Y、Z 都不包含于 X,Z 不包含于 Y ,Y 不能决定 X,则称 Z 传递函数依赖于 X。 注意!:若

    ,可以得到

    ,但 不能说 Z 传递函数依赖于 X。

    Insight:传递函数依赖存在着非受控冗余。

    举例:学生( 学号,姓名,系号,系主任 )

    {学号}

    { 系号 }

    {系号}

    { 系主任 }

    {学号}

    { 系主任 }

    “系主任” 是传递依赖于 “学号” 的。

    图示:

    注:以上图片来自哈工大战德臣老师的PPT

    4. 与函数依赖相关的概念

    (1). 候选键

    定义:设 K 为 R(U) 中的属性或属性组合,若

    ,则称 K 为 R(U) 上的候选键。

    白话:对于关系 R(U) 中的属性(组)K,如果 U 完全函数依赖于 K,即 K 中的所有属性一起才能决定 U,则称 K 为 R(U) 的候选键。

    (2). 主键

    如果有多个候选键,则可以选择任一候选键作为主键。

    (3). 主属性

    包含在任一候选键中的属性称为主属性,其他属性称为非主属性。

    (4). 外来键

    若 R(U) 中的属性(组)X 不是 R 的候选键,却是另一关系 S(U) 的候选键,则称 X 为 R(U) 的外来键,简称外键。

    白话:一个关系的外键是另一关系的候选键。

    (5). 逻辑蕴含

    定义:设 F 是关系 R(U) 中的一个函数依赖集合,X、Y 是 R 的属性子集,如果能从 F 这个函数依赖集合中推导出

    ,则称 F 逻辑蕴含

    ,或者说

    是 F 的逻辑蕴含。记作

    (6). 闭包

    定义 :被 F 逻辑蕴含的所有函数依赖集合称为 F 的闭包,记作

    白话:也就是说,能从 函数依赖集 F 中推导出的所有函数依赖组成的集合,称为 F 的闭包。(学过泛函的话应该能感觉到有种完备的概念)。

    如果

    ,则称 F 是一个 全 函数依赖族。(函数依赖完备集)。

    二、函数依赖的 Armstrong 公理及其引理

    设 F 为 R(U) 的一组函数依赖,记为 R(U, F) 。

    1. 函数依赖的 Armstrong 公理

    (1). 自反律

    ,则

    被 F 逻辑蕴含。

    白话:若 属性集 Y 包含于 X,X 包含于 U,则

    ,则

    。也就是说 如果属性集 Y 属于 X,则 X 可以决定 Y,又可以说 属性集 X 可以决定 他的属性 子集。(平凡函数依赖)

    (2). 增广律

    ,且

    ,则

    被 F 逻辑蕴含。

    白话:如果

    在 F 这个函数依赖集合中,另一属性(组) Z 是属性集 U 中的元素,那么从 F 中可以推导出 XZ 函数决定 YZ。

    (3). 传递律

    ,且

    ,则

    被 F 逻辑蕴含。

    2. 函数依赖的 Armstrong 的引理

    2.1 引理1

    (1). 合并律

    ,则

    。 证明:根据增广律可以得到

    ,再根据传递律得到,

    (2). 伪传递律

    ,则

    。 证明:证明方法依然是 增广律 和 传递律。

    (3). 分解律

    ,则

    。 证明:根据自反律可以得到

    ,再根据传递律,得证

    2.2 引理2

    如果 A1,A2,... ,An是属性,则

    当且仅当对每个 Ai 有

    2.3 属性(集)闭包 和 引理3

    (1). 属性(集)闭包定义

    对 R(U, F) ,

    ,令:

    = Ai 用 armstrong 三个公理 可从 F 导出

    ,称

    为 X 关于 F 的属性(集)闭包。

    区分 闭包和属性(集)闭包: 闭包指的是 F的闭包,该集合包含的元素是函数依赖。 属性集闭包是 X属性(集) 关于 F 的属性(集)闭包,该集合包含的元素是属性。

    (2). 引理3

    若 从 F 这个函数依赖集合中可以用 Armstrong 公理 导出

    ,当且仅当

    解释:只有 Y 这个属性 在 X 关于 F 的属性(集)闭包中,才能推出

    ,只要能推出 X 决定 Y,那 Y 一定在 X 关于 F 的属性(集)闭包中。

    2.4 覆盖 和 引理4、5

    (1) 覆盖

    定义:对 R(U) 上的两个函数依赖集合 F、G,如果

    ,则称 F 和 G 也是等价的,也称作 F 覆盖 G 或者 G 覆盖 F。

    (2) 引理4

    (3) 引理5

    每个函数依赖集 F 可被一个 其右端至多有一个属性的函数依赖集 G 覆盖。

    2.5 最小覆盖

    (1). 最小覆盖

    F 满足:F 中每个函数依赖的右边部分都是单个属性;

    对任何

    ,有 F -

    不等价于 F;

    对任何

    ,( F-

    不等价于F。

    则 F 为 最小覆盖 或者 最小依赖集。

    解释: 对于第 2 点,如果去掉

    这个函数依赖,那么从 F 中不能推导出

    ,也就是说 F 中的每一个函数依赖都是必需的,一个不能少。 对于第 3 点,Z 是 函数依赖的 左边部分 的一个子集,如果去掉

    这个函数依赖,加上 X 子集

    的依赖依然不等价于F,即

    是不能由

    代替的。

    (2). 定理

    每个函数依赖集 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。

    展开全文
  • 算法:按以下步骤求候选键: 1.只在FD右部出现的属性,不属于候选码; 2.只在FD左部出现的属性,一定存在于某候选码当中; 3.外部属性一定存在于任何候选码当中; 4.其他属性逐个与2,3的属性组合,求属性闭包,直至X的...
  • 题目描述:已知关系R(A, B, C, D), 有函数依赖集F = { A->C; B->D; B,D->A }, 问{A,B}是不是R的候选键
  • 候选键算法 最小函数依赖集 关系模式R(U,D,DOM,F) R:关系名,符号化的元组定义 U:一组属性 D:属性组U中的属性所来自的域 DOM:属性到域的映射 F:属性组U上的一组数据依赖 函数依赖集的闭包 F:FD...
  • 数据库函数依赖关系模式范式候选键主键码学习教案.ppt
  • 主码:主关键字(主键,primary key)是被挑选出来,作表的行的唯一标识的候选关键字(也称为候选键)。一个表只有一个主关键字。主关键字又可以称为主键。 主键可以由一个字段(注释1),也可以由多个字段组成,...
  • 数据库函数依赖关系模式范式候选键主键码PPT学习教案.pptx
  • 3、候选键 一、求最小函数依赖集 步骤: 1、先将右边都变成单属性 2、依赖集中不能出现冗余的函数依赖(重复的函数依赖) 3、左边没有多余的属性 举个例子: 1.首先将右边都变成单属性, A->BC,B->C,A->B,...
  • 【数据库】搞懂 超码、候选码、主码、函数依赖

    千次阅读 多人点赞 2019-07-31 17:57:02
    今天看了数据库范式,结果盯着一篇知乎回答看了很久还是没搞明白,在讲码的时候我看到的其它博客好像不太一样,由于讲到了函数依赖、唯一标识等这些,我就去看了函数依赖,看完再回来看结果还是发现哪里不对,所以...
  • 一、函数依赖: 1.完全函数依赖: 通过AB能得出C,但是AB单独得不出C,那么说C完全依赖于AB。 2.部分函数依赖: 通过AB能得出C,通过A也能得出C,通过B也能得出C,那么说C部分依赖于AB。 3.传递函数依赖: 通过A得到...
  • 对于给定的关系R(A1,A2,…An)和函数依赖集F,可将其属性分为4类: L类 仅出现在函数依赖左部的属性。 R 类 仅出现在函数依赖右部的属性。 N 类 在函数依赖左右两边均未出现的属性。 LR类 在函数依赖左右两边均...
  • 数据库函数依赖___关系模式__范式_候选键_主键_码
  • 第二步:检查F中的每一个函数依赖A→B,如果属性集A中所有属性均在Y中,而B中有的属性不在Y中,则将其加入到Y中; 第三步:重复第二步,直到没有属性可以添加到属性集Y中为止。 最后得到的Y就是X的闭包 举个例子 ...
  • 函数依赖键和范式

    千次阅读 2017-02-27 19:51:06
    1.函数依赖 X→Y,表示Y依赖于X; X→Y,且Y→X不成立,Y→Z,则X→Z,表示Z传递依赖于X。 2.键 3.图解法求候选键 4.范式
  • 一、函数依赖:在关系R中,若属性或者属性集 A 中 两个元祖的值相等,如果这两个元祖中对应的属性或者属性集B中的值也相同,则记作A——>B。 A函数决定B; 或者 B函数依赖于A。例1:...
  • 一个是最小依赖函数集,一个是求候选码,一个是求闭包,一个是要把关系模式分解成3NF且保持函数依赖,一个是分解成3NF且保持函数依赖和无损连接。 记录一下我对这几个问题的求法。可能会有哪里有漏洞,希望可以指...
  • 设关系R(ABCDE)及R上成立的函数依赖集为F,F={A→D, A→B, E→D, D→B,BC →D, DC →A},求: (1)求F的最小函数依赖集F’。 (2)求关系R的候选码。 (3)求具有无损连接且保持函数依赖性的3NF分解。 答: (1) ...
  • 说到部分函数依赖,传递函数依赖,必须谈到2个概念,“非主属性”“主属性”。 主属性:组成主键的属性,就是主属性。例如,属性集{学号,姓名,联系电话},学号是主键。学号是主键的属性,所以学号是主属性。 ...
  • 候选最小函数依赖

    千次阅读 2015-11-10 14:25:46
    (1)求候选码 设关系模式R为(BOISQD),F={S→D,I→S,IS→Q,B→Q}关系中l类(只出现在左边)L=(IB) 关系中R类(只出现在右边)R=(DQ) 关系中LR类(两边都有)LR=(S) 关系中NLR类(两边都没有)NLR=(O) NLR类O一定...
  • 数据库中的函数依赖键和范式

    千次阅读 2018-05-27 21:07:35
    1.函数依赖X→Y,表示Y依赖于X;X→Y,且Y→X不成立,Y→Z,则X→Z,表示Z传递依赖于X。2.键主属性:表示在候选键中的属性;超键:是指能够唯一标识一个元组的属性集;候选键:能够唯一标识一个元组,且不含多属性;...
  • 给定函数依赖集合F={ A2→(A3,A5); (A1, A3)→A6; (A2,A6)→ A4 },则关于R既保持 依赖又无损连接地分解成第三范式,分解正确 的是 A.p={R1(A2,A3, A5), R2(A1,A3,A6), R3(A2,A4,A6) } B.p={R1(A2,A3, A5), R2(A1...
  • 什么是关键码? 设关系模式R的属性集是U,X是U的一个子集,F是在R上成立的一个函数依赖集。如果X→U在R上成立(即X→U在中),那么称X是...对于给定的关系模式R(, ,…, )和函数依赖集F,可将其属性分为以下四类。 ...
  • 【闭包就是由一个属性直接或间接推导出的所有属性的集合】  例(1): 设有关系模式R(U,F),其中U={A,B,C,D,E,I},... (2)在F中寻找尚未使用过的左边是AE的子集的函数依赖,结果是: A→D, E→C;所以 X(1...
  • 目录数据库系统原理-函数依赖和关系模式分解第一范式如何处理非原子值原子性关系数据库设计中易犯的错误模式分解无损连接分解优化关系模式的步骤函数依赖函数依赖定义函数依赖的使用函数依赖集的闭包Armstrong公理...
  • 无损连接分解的快捷判别方法  首先要申明,这种快捷方法是有前提的,前提就是分解后的关系模式只有两个。...这里的求交相减运算的对象是关系模式的属性。  【例题】  关系模式R(U,F),其中U={W,X,...
  • 详解数据库函数依赖【码】

    千次阅读 2017-11-10 21:46:55
    在上一篇关于范式的文章里提到了在学习范式前应先了解函数依赖的定义,所以这篇文章存在的意义就是为之前的做铺垫 ORZ在了解函数依赖前,首先要明白数据依赖的概念。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,901
精华内容 4,360
关键字:

基本函数依赖和候选键