数据库之函数依赖公理体系共34页文档
- 格式:ppt
- 大小:2.91 MB
- 文档页数:34
函数依赖及范式函数依赖基本概念:•函数依赖:FD(function dependency),设有关系模式R(U),X,Y是U的子集,r 是R的任一具体关系,如果对r的任意两个元组t1,t2,由t1[X]=t2[X]导致t1[Y]=t2[Y], 则称X 函数决定Y,或Y函数依赖于X,记为X→Y。
X→Y为模式R的一个函数依赖。
•部分函数依赖:即局部依赖,对于一个函数依赖W→A,如果存在X W(X包含于W)有X→A成立,那么称W→A是局部依赖,否则称W→A为完全函数依赖。
•传递依赖:在关系模式中,如果Y→X,X→A,且X Y(X不决定Y),A X(A不属于X),那么称Y→A是传递依赖。
•函数依赖集F的闭包F+: 被逻辑蕴涵的函数依赖的全体构成的集合,称为F的闭包(clo sure),记为F+。
•最小依赖集:如果函数集合F满足以下三个条件(1)F中每个函数依赖的右部都是单属性;(2) F中的任一函数依赖X→A,其F-{X→A}与F是不等价的;(3)F中的任一函数依赖X→A,Z为X的子集,(F-{X→A})∪{Z→A}与F不等价。
则称F为最小函数依赖集合,记为Fmin。
函数依赖的公理系统:设有关系模式R(U),X,Y,Z,W均是U的子集,F是R上只涉及到U中属性的函数依赖集,推理规则如下:•自反律:如果Y X U,则X→Y在R上成立。
•增广律:如果X→Y为F所蕴涵,Z U,则XZ→YZ在R上成立。
(XZ表示X∪Z,下同) •传递律:如果X→Y和Y→Z在R上成立,则X→Z在R上成立。
以上三条为Armstrong公理系统•合并律:如果X→Y和X→Z成立,那么X→YZ成立。
•伪传递律:如果X→Y和WY→Z成立,那么WX→Z成立。
•分解律:如果X→Y和Z Y成立,那么X→Z成立。
这三条为引理注意:•函数依赖推理规则系统(自反律、增广律和传递律)是完备的。
•由自反律所得到的函数依赖均是平凡的函数依赖。
四种范式的含义:•如果某个数据库模式都是第一范式的,则称该数据库模式是属于第一范式的数据库模式。
数据库函数依赖和范式总结1 函数依赖1.1 定义:一个集合R(U,F),U为属性全集,F为函数依赖集合。
F中存在着{Xi->Yi...};对于每个X都存在着一个Y与之唯一对应。
意思就是相当于X为主键,Y由主键决定。
比如一个学生他的学号相当于X,而他的姓名与年龄这些其他信息相当于Y。
但是X有时候并不是一个值,比如一个学生他的成绩需要有两个属性才能知道他的成绩,学号+课程号->成绩1.2 平凡函数依赖与非平凡函数依赖平时我们主要讨论的是非平凡函数依赖。
平凡函数依赖概念:Y集合属性属于X集合属性的子集非平凡函数则相反1.3 逻辑蕴涵(为后面求闭包做好基础)X,Y为属性集合U的子集,且X->Y不存在于F中。
即我们需要通过F中的函数依赖推出X->Y称为函数依赖。
而所有函数依赖的集合则称为闭包1.4 函数依赖的推理规则(就是求函数依赖的逻辑蕴涵)1.4.1 几个公理1.4.1.1 公理一(自反律):Y属于X的子集,则X->Y 数学公式描述 Y?X?U1.4.1.2 公理二(增广律):X->Y成立,Z?U也成立,则 XZ?YZ1.4.1.3 公理三(传递律):X->Y成立,Y->Z成立,则 X->Z1.4.2 公理的推广1.4.2.1 推广一(合并律):X->Y,X->Z,则X->YZ1.4.2.2 推广二(伪传递律):X->Y,YW->Z,则XW->Z(证明只需要在XY两边*W)1.4.2.3 推广三(分解律):X->Y成立,Z?Y,则 X->Z1.4.2.4 推广四(复合律):X->Y,W->Z,则XW->YZ1.5 完全函数依赖与部分函数依赖(范式中基础知识)X->Y的集合中,若X的任一真子集x都能 x->Y则为部分函数依赖,若不能则的完全函数依赖,如果X没有真子集则也称为完全函数依赖。
第6.3 数据依赖的公理系统与函数依赖闭包一、函数依赖的逻辑蕴涵定义:设有关系模式R(U)及其函数依赖集F,如果对于R的任一个满足F的关系r 函数依赖X→Y(X→Y不属于F集)都成立,则称F逻辑蕴涵X→Y,或称X→Y可以由F 推出。
例:关系模式 R=(A,B,C),函数依赖集F={A→B,B→C}, F逻辑蕴涵A→C。
证:设u,v为r中任意两个元组:若A→C不成立,则有u[A]=v[A],而u[C]≠v[C]由A→B, B→C,知u[A]=v[A], u[B]=v[B], u[C]=v[C],即若u[A]=v[A]则u[C]=v[C],和假设矛盾。
故F逻辑蕴涵A→C。
本例A→C不属于F集,但A→C可由F依赖集{A→B,B→C}推断而出,且F依赖集中的所有元组都满足函数依赖A→C,故F逻辑蕴涵A→C。
该特性称为函数依赖的可传递性二、Armstrong公理1、定理6.1:若U为关系模式R的属性全集,F为U上的一组函数依赖,设X、Y、Z、W均为U的子集,对R(U,F)有:F1(自反性):若X⊇Y(表示X包含Y),则X→Y为F所蕴涵;(F1':X→X)F2(增广性): 若X→Y为F所蕴涵,则XZ→YZ为F所蕴涵;YZ》Y(F2':XZ→Y)F3(传递性): 若X→Y,Y→Z为F所蕴涵,则X→Z为F所蕴涵;F4(伪增性):若X→Y,W⊇Z(表W包含Z)为F所蕴涵,则XW→YZ为F所蕴涵;F5(伪传性): 若X→Y,YW→Z为F所蕴涵, 则XW→Z为F所蕴涵;F6(合成性): 若X→Y,X→Z为F所蕴涵,则X→YZ为F所蕴涵;F7(分解性): 若X→Y,Z⊆Y (表示Z属于Y)为F所蕴涵,则X→Z为F所蕴涵。
函数依赖推理规则F1∽F7都是正确的。
2、Armstrong公理:推理规则F1、F2、F3合称Armstrong公理;F4 ∽ F7可由F1、F2、F3推得,是Armstrong公理的推论部分。
数据库原理--函数依赖和范式关系数据库设计范式介绍 .1 第⼀范式(1NF)⽆重复的列 所谓第⼀范式(1NF)是指数据库表的每⼀列都是不可分割的基本数据项,同⼀列中不能有多个值,即实体中的某个属性不能有多个值或者不能有重复的属性。
如果出现重复的属性,就可能需要定义⼀个新的实体,新的实体由重复的属性构成,新实体与原实体之间为⼀对多关系。
在第⼀范式(1NF)中表的每⼀⾏只包含⼀个实例的信息。
简⽽⾔之,第⼀范式就是⽆重复的列。
说明:在任何⼀个关系数据库中,第⼀范式(1NF)是对关系模式的基本要求,不满⾜第⼀范式(1NF)的数据库就不是关系数据库。
1.2 第⼆范式(2NF)属性完全依赖于主键[消除部分⼦函数依赖] 第⼆范式(2NF)是在第⼀范式(1NF)的基础上建⽴起来的,即满⾜第⼆范式(2NF)必须先满⾜第⼀范式(1NF)。
第⼆范式(2NF)要求数据库表中的每个实例或⾏必须可以被唯⼀地区分。
为实现区分通常需要为表加上⼀个列,以存储各个实例的唯⼀标识。
例如员⼯信息表中加上了员⼯编号(emp_id)列,因为每个员⼯的员⼯编号是唯⼀的,因此每个员⼯可以被唯⼀区分。
这个唯⼀属性列被称为主关键字或主键、主码。
第⼆范式(2NF)要求实体的属性完全依赖于主关键字。
所谓完全依赖是指不能存在仅依赖主关键字⼀部分的属性,如果存在,那么这个属性和主关键字的这⼀部分应该分离出来形成⼀个新的实体,新实体与原实体之间是⼀对多的关系。
为实现区分通常需要为表加上⼀个列,以存储各个实例的唯⼀标识。
简⽽⾔之,第⼆范式就是属性完全依赖于主键。
1.3 第三范式(3NF)属性不依赖于其它⾮主属性[消除传递依赖] 满⾜第三范式(3NF)必须先满⾜第⼆范式(2NF)。
简⽽⾔之,第三范式(3NF)要求⼀个数据库表中不包含已在其它表中已包含的⾮主关键字信息。
例如,存在⼀个部门信息表,其中每个部门有部门编号(dept_id)、部门名称、部门简介等信息。