设计理论2函数依赖与范式zff分析

设计理论2

函数依赖与范式目录1、规范化问题的提出2、函数依赖3、范式4、关系模式的分解1、规范化问题的提出在关系数据库系统中，关系模型包括一组关系模式，并且各个关系不是完全孤立的。如何设计一个合适的关系数据库系统，关键是关系数据库模式的设计，一个好的关系数据库模式应该包括多少关系模式，而每一个关系模式又应该包括哪些属性，又如何将这些相互关联的关系模式组建成一个适合的关系模型，这些工作决定了整个系统运行的效率。也是系统成败的关键所在，所以必须在关系数据库的规范化理论的指导下逐步完成。关系数据库的规范化理论最早是由关系数据库的创始人E.F.Codd提出的，后经许多专家学者对关系数据库理论作了深入的研究和发展，形成了一整套有关关系数据库设计的理论。关系数据库设计理论对数据库逻辑设计有重要的指导作用，它主要包括三个方面的内容：数据依赖、范式和模式设计方法，其中数据依赖起着核心作用。例子要求设计教学管理数据库，其关系模式，SCD如下：SCD（SNO，SN，AGE，DEPT，MN，CNO，SCORE）其中SNO表示学生学号，SN表示学生姓名，

AGE表示学生年龄，DEPT表示学生所在系别，

MN表示系主任姓名，CNO表示课程号，

SCORE表示成绩。SNOSNAGEDEPTMNCNOSCORES1赵军17计算机刘军航C190S1赵军17计算机刘军航C285S2钱进18信息王平C557S2钱进18信息王平C680S2钱进18信息王平C7

S2钱进18信息王平C470S3张伟20信息王平C10S3张伟20信息王平C270S3张伟20信息王平C485S4李平20自动化刘军航C193（1）

一个系有若干个学生，但一个学生只属于一个系；（2）

一个系只有一名系主任，但一个系主任可以同时兼几个系的系主任；（3）

一个学生可以选修多门功课，每门课程可被若干个学生选修；（4）每个学生学习的课程有一个成绩。在此关系模式中填入一部分具体的数据，则可得到SCD关系模式的实例，即一个教学管理数据库，如下图所示。

SNOSNAGEDEPTMNCNOSCORES1赵军17计算机刘军航C190S1赵军17计算机刘军航C285S2钱进18信息王平C557S2钱进18信息王平C680S2钱进18信息王平C7

S2钱进18信息王平C470S3张伟20信息王平C10S3张伟20信息王平C270S3张伟20信息王平C485S4李平20自动化刘军航C193根据实际情况，这些数据有以下语义规定：

根据上述的语义规定并分析以上关系中的数据，我们可以看出，（SNO，CNO）属性的组合能唯一标识一个元组，所以（SNO，CNO）是该关系模式的主键。但在进行数据库的操作时，会出现以下几方面的问题。（1）数据冗余。每个系名和系主任的名字存储的次数等于该系的学生人数乘以每个学生选修的课程，同时学生的姓名、年龄也都要重复存储多次，数据的冗余度很大，浪费了存储空间。（2）插入异常。如果某个新系没有招生，尚无学生时，则系名和系主任的信息无法插入到数据库中。因为在这个关系模式中，（SNO，CNO）是主关系键。根据关系的实体完整性约束，组关系键的值不能为空，而这时没有学生，SNO和CNO均无值，因此不能进行插入操作，另外，当某个学生尚未选课，即CNO未知，实体完整性约束还对规定，主关系键的值不能部分为空，同样也不能进行插入操作。（3）删除异常。当某系学生全部毕业而没有招生后时，要删除全部学生的信息，这时系名、系主任也随之删除，而现实是这个系仍然存在，但在数据库中却无法找到该系的信息。另外，如果某个学生不再选修C1

课程，本应该只删去C1，但C1是主关系键的一部分，为保证实体完整性，必须将整个元组一起删掉，这样，有关学生的所有句路的其他信息也随之丢失。（4）更新异常。如果某学生改名，则该学生的所有记录都要逐一修改SN的值；又如某系更换系主任，则属于该系的学生记录都要修改MN的内容，稍有不慎，就有可能漏改某些记录，这就会造成数据库的不一致性，破坏了数据的完整性。

由于存在以上问题，我们说，SCD是一个不好的关系模式。产生上述问题的原因，直观地说，是因为关系中“包罗万象”，内容太复杂了。那么，怎样才能得到一个好的关系模式呢？我们把关系模式SCD分解为

学生关系S（SNO，SN，AGE，DEPT）选修课SC（SNO，CNO，SCORE）系关系D（DEPT，MN）三个结构简单的关系模式。SNOSNAGEDEPTS1赵军17计算机S2钱进18信息S3张伟20信息S4李平21自动化如下图所示SSNOCNOSCORES1C190S1C285S2C557S2C680S2C7

S2C470S3C10S3C270S3C485S4C193DEPTMN计算机刘军航信息王平自动化刘军航SCD在以上三个关系模式中，实现了信息的某种程度的分离：S中存学生基本信息，与所选课程及系主任无关D中存储系的有关信息，与学生无关SC中存储的学生选课的信息，而与学生及系的有关信息无关与SCD相比，分解为三个关系模式后，数据的冗余程度明显降低。同时，由于数据冗余度的降低，数据没有重复存储，也不会引起更新异常。当新插入一个系时，只要在关系D中添加一个记录就可以了；当某个学生尚未选课时，只要在关系S中添加一条学生记录就可以了，而与选课关系无关，这就避免了插入异常。当一个系的学生全部毕业时，只需在S中该系的全部学生记录，而关系D中有关该系的信息仍然保留，从而不会引起异常删除。经过上述分析，我们说分解后的关系模式是一个好的关系数据库模式。从而得出结论，一个好的关系模式应该具备四个条件：（1）尽可能少的数据冗余（2）没有插入异常（3）没有删除异常（4）没有更新异常一个好的关系模式并不是在任何情况下都是最优的，比如查询某个学生选修课程名及所在系的系主任时，要通过连接，而连接所需的系统开销非常大，因此要以实际设计的目标出发进行设计。

注意2、函数依赖函数依赖普遍地存在于现实生活中比如，描述一个学生的关系，可以由学号(SNO)、姓名（SNAME）、年龄(AGE)等几个属性。由于一个学号只对应一个学生，一个学生只有一个姓名和一个年龄。因而，当“学号”值确定之后，姓名和年龄的值也就被唯一地确定了，就如同自变量x确定之后，相应的函数值f(x)也就唯一确定了一样，所以说SNO函数决定SNAME和AGE，或者说SAME、AGE函数依赖于SNO，记为SNO->SNAME，SNO->AGE。定义设R(U)是属性集U上的关系模式，X与Y是U的子集，若对于R(U)的任意一个当前值r，如果对r中的任意两个元组t和s，都有t[X]≡s[X]，就必须有t[Y]≡s[Y](即若它们在X上的属性值相等，则在Y上的属性值也一定相等），则称“X”函数决定Y或“Y”函数依赖于X，记作X→Y，并称X为决定因素这里t[X]，s[X]分别表示元组t，s在属性集X上的值，函数依赖是对关系R的一切可能的当前值r定义的，不是针对某个特定关系，也就是说，对于X的每一个具体的值，都有惟一的Y值与之对应，即Y值由X值决定，因而这种数据依赖称为函数依赖。符号表示：

（1）若X→Y，则X称为决定因素。（2）若X→Y，Y→X，则记作X←→Y。（3）若Y不函数依赖于X，则记作X→Y。

\例子函数依赖是语义范畴的概念，根据语义来确定一个函数依赖。例如：姓名→年龄这个函数依赖只有在没有同名人的条件下成立，如果允许有相同姓名，则年龄就不再依赖于姓名了，设计者也可以对现实世界作强制的规定。例如规定不允许同名人出现，因而使“姓名－>年龄函数依赖成立。这样当插入某个元组时，这个元组上属性值必须满足规定的函数依赖，若发现有同名人存在，则拒绝插入该元组。但是如果没有强制，那么我们就要寻找新的属性了，比如身份证号－>姓名。【例】有一个关系模式R（学号，姓名，出生年月，系编号，系负责人）。在R的关系r中，存在着如下函数依赖：学号→姓名（每个学号只能对应一个出生年月）；学号→出生年月（每个学生只能对应一个出生年月）;

系编号→系负责人（每个系只能有一名负责人）。分类和键函数依赖平凡函数依赖非平凡函数依赖完全函数依赖部分函数依赖传递函数依赖定义设X,Y均为某关系上的属性集，且X→Y

若Y包含于X，则称X→Y为：平凡函数依赖，若Y不包含于X，则称X→Y为：非平凡函数依赖。定义在R（U）中，如果X→Y，并且对于X的任何一个真子集X’，都有

X’→Y，则称Y对X完全函数依赖，记作XY。F【例】有一关系模式S（学号，姓名，系名称，出生年月）。若无重名还存在学号←→姓名函数依赖在S中存在如下完全函数依赖：学号系名称，学号出生年月通常记为学号→系名称，学号→出生年月FF定义在R（U）中，如果X→Y，X’→Y，则称Y对X部分函数依赖，记作

XY。P【例】有一关系模式SC（学号，课程号，成绩，教师编号）。在SC中，（学号，课程号）成绩（学号，课程号）→教师编号（相当于X→Y）课程号→教师编号（相当于X’→Y）F因此（学号，课程号）教师编号P\定义设有关系模式R(U)，X，Y，Z∈U，如果X→Y，Y→Z，且Y不∈X，

Y不函数决定X，则有X→Z，称Z传递函数依赖于X。【例】关系模式R（学号，姓名，出生年月，系编号，系负责人）在此关系模式中有如下函数依赖：学号→系编号（相当于X→Y）系编号→学号（相当于Y→X）系编号→系负责人（相当于Y→Z）因此，在R中存在传递函数依赖学号系负责人。T键

键是唯一标识实体的属性集，这是对键的直观定义，下面用函数依赖的概念来定义它。定义设K为R（U）中的属性或属性组合，若KU，则K为R的候选键（CandidateKey）。若候选键多于一个，则选定其中的一个为主键（PrimaryKey），也称为键（Key）；当只有一个候选键时这个候选键即是主键，F包含在任何一个候选键中的属性，叫主属性（PrimeAttribute）。不包含在任何主键中的属性称为非主属性（NonprimeAttribute），或非键属性（Non-keyAttribute）。

主键可为单个属性，也可为属性组。在特殊情况下，主键可以由整个元组组成，称为全键（All-key）。如在关系模式S（学号，姓名，系名称，出生年月）中，学号是主键，而在关系模式SC（学号，课程号，成绩，教师编号）中，属性组合（学号，课程号）是主键，下面举一个全键的例子。

外键定义关系模式R中属性或属性组X并非R的主键，但X是另一个关系模式的主键，则称X是R的外来键（ForeignKey），也称外键。

设有关系模式A（作者，书籍，读者），假设一个作者可以编著多本书，某一本书可由多个作者编著。读者可以阅读不同作者的不同书籍，这个关系模式的主键为（作者，书籍，读者）。

如在关系模式SC（学号，课程号，成绩，教师编号）中，学号不是主键，但学号是关系模式S（学号，姓名，系名称，出生年月）的主键，则学号是关系模式SC的外键。主键与外键提供了一个表示关系间联系的手段。如关系模式S与SC的联系就是通过学号来实现的。3、范式在关系模式的设计中，函数依赖起着重要作用，关系模式设计的好坏依赖于它的函数依赖是否满足特定的要求。满足特定要求的模式称为范式（NormalForm）。满足不同程度要求的模式为不同范式。关系模型的奠基人E.F.Codd在1971年至1972年间系统地提出了第一范式（1NF）、第二范式（2NF）和第三范式（3NF）的概念，讨论了规范化问题。1974年，E.F.Codd和Boyce又共同提出了一个新范式，即BCNF。1976年Fagin提出第四范式（4NF）。现在已有人提出第五范式（5NF）。所谓“第几范式”是表示关系模式的某一种级别，因此，范式这个概念可以理解成符合某种级别的关系模式的集合。一般地，如果R属于第x范式，那么就可以写成R∈xNF。各种范式之间的关系满足5NF4NF3NF2NF1NF，如下图所示。5NF4NF3NF2NF1NF第一范式第一范式定义关系模式R的每一个属性都是不可分解的，则称R为第一范式的模式，记为R∈1FN模式。例如：工资关系｛工号，姓名，工资（基本工资，津贴，交通补助）｝

A123，赵颖，（1000，200，30）

B123，张三，（1200，100，20）

C123，李四，（1000，150，40）例如：选课关系（学号，课程）

123，（操作系统，计算机原理，数据结构）

124，（C程序设计，数字电路）

125，（离散数学）解决办法：转换为单个属性工资关系｛工号，姓名，基本工资，津贴，交通补助｝

A123，赵颖，1000，200，30B123，张三，1200，100，20C123，李四，1000，150，40选课关系，可以改为学号和各个课程一起作主键学号课程007501程序设计007501操作系统007501数据库007501电工学007501继电保护定义如果R∈1NF，且每一个非主属性完全函数依赖于主键则R∈2NF。【例】有一关系模式SGD（学号，课程号，姓名，系名称，系负责人，成绩）在该模式中，有以下函数依赖存在：（学号，课程号）成绩学号→姓名（学号，课程号）姓名学号→系名称（学号，课程号）系名称学号→系负责人（学号，课程号）系负责人系名称→系负责人FPPP

通过分析及由主键的定义可知SGD中的主键为（学号，课程号），因此，姓名，系名称，系负责人，成绩均是非主属性，而非主属性中只有成绩是完全依赖于主键，其他属性是部分函数依赖于主键，因此，关系模式SGD不符合2NF定义，即SGD∈2NF。经过以上分析，可以得到两个结论：（1）从1NF关系中消除非主属性对关系键的部分函数依赖，则可得到2NF关系。（2）如果R的关系键为单属性，或R的全体属性均为主属性，则R∈2NF。第二范式下面将SGD分解为两个关系模式：SG（学号，课程名，成绩）SD（学号，姓名，系名称，系负责人）

SG的主键是（学号，课程号），SD的主键是学号，从前面的函数依赖分析中得知，关系模式SG和SD的非主属性对主键都是完全函数依赖，因此，SG∈2NF，SD∈2NF。一个关系模式R不属于2NF，就会产生以下问题：（1）插入异常（2）删除异常（3）修改复杂详细内容参见本书相关章节

分析上面的例子可知，问题的关键在于非主属性有两种，一种对主键完全函数依赖，比如成绩；另一种对主键部分函数依赖，比如姓名、系名称和系负责人。对于第二种情况，如果进行关系模式分解，消除非主属性对主键的部分依赖，就可以解决关系模式SGD2NF存在的3个问题。∈定义如果R∈2NF，且每一个非主属性不传递函数依赖于主键，则R∈3NF。【例】考察上例中的两个关系模式SG和SD。显然，SG中不存在传递函数依赖，因此，SG∈3NF，下面分析SD中的函数依赖：由传递函数依赖的定义可得：

解决上述问题的办法是将关系模式SD分解，消除关系模式SD中存在的传递函数依赖。学号→系名称系名称→学号系名称→系负责人学号系负责人T因此SD3NF∈第三范式下面将SD分解为两个关系模式：SDN（学号，姓名，系名称）DM（系名称，系负责人）

SDN的主键是学号，DM的主键是系名称。在这两上关系模式中既不存在部分函数依赖，也不存在传递函数依赖，因此SDN∈3NF，DM∈3NF。SG（学号，课程名，成绩）SG（学号，姓名，系名称，系负责人）【例】考察关系模式SG（学号，课程号，成绩），它只有一个主键（学号，课程号），并且没有任何属性对（学号，课程号）部分函数依赖或传递函数依赖，所以SG∈3NF。同时，SG中（学号，课程号）是唯一的决定因素，所以SG∈BCNF。【例】有一关系模式SCT（学生，课程，教师），在该关系模式中，存在如下对应关系：（1）对于每门课，每个学生的授课教师只有一位；（2）每位教师只讲授一门课；（3）每门课可由不同教师讲授。BCNF（BoyceCoddNormalForm）是由Boyce与Codd提出的。它比3NF更进了一步，是修正的第三范式，有时也称为扩充的第三范式。（1）所有非主属性对每一个主键都是完全函数依赖；（2）所有的主属性对每一个不包含它的主键也是完全函数依赖；（3）没有任何属性完全函数依赖于非主键的任何一组属性。定义关系模式R∈1NF，若X→Y且YX时X必含有主键，则R∈BCNF。由于3NF不能很好地处理含有多个候选键和候选键是组合项的情况，人们定义了一个更强的范式BCNF，一个满足BCNF的关系模式有以下特点：∪BC范式由语义可得到如下函数依赖：（学生，课程）→教师教师→课程（学生，教师）→课程这些对应关系可用右图表示。学生课程教师学生教师课程关系模式SCT的函数依赖【例】有一关系模式SCP（学生，课程，名次）。在SCP中有如下对应关系：（1）每个学生选修每门课程的成绩有一定的名次；（2）每门课程中每一名称只有一个学生（即没有并列名次）。由语义可得到如下函数依赖：（学生，课程）→名次（课程，名次）→学生

由上面的分析可知，在该关系中有两个候选键（学生，课程）和（学生，教师），因为没有任何非主属性，因而也不存在非主属性对主键的部分函数依赖或传递函数依赖，所以SCT∈3NF。另外，因为教师→课程，也就是教师是决定因素，但教师不是主键，由BCNF的定义可知，SCTBCNF。∈

显然，这个关系模式有两个候选键（学生，课程）和（课程，名次），并且没有非主属性对主键的部分函数依赖或传递函数依赖，因此，SCP∈3NF。另外，除（学生，课程）和（课程，名次）之外没有其他决定因素，所以，SCP∈BCNF。

不满足BCNF的关系模式同样存在着更新异常。假设在SCT（学生，课程，教师）中，存在这样的元组（王峰，计算机网络，孙效），当删除信息“王峰学习计算机网络课程”时，将同时失去“教师孙效主讲计算机网络课程”这一信息。

为什么会产生更新异常呢？因为教师是决定因素，但却不是候选键。如何解决这个问题呢？仍然采用关系模式分解的办法。如果将SCT分解为如下两个关系模式：SC（学生，课程）TC（教师，课程）则SC∈BCNF，TC∈BCNF，这样分解之后解决了SCT中存在的更新异常问题

一个数据库模式中的关系模式如果都属于BCNF，那么在函数依赖范畴内，它已消除了插入和删除异常。3NF的“不彻底性”表现在存在主属性对主键的部分函数依赖或传递函数依赖。这个过程可以用下图来描述：消除非主属性对主键的部分函数依赖消除非主属性对主键的传递函数依赖消除主属性对主键的部分函数依赖和传递函数依赖1NF2NF3NFBCNF（关系模式规范的分解过程）

在关系数据库中，对关系模式的基本要求是满足第一范式。这样的关系模式就是合法的、允许的。但是，人们根据实际情况，可以将关系模式逐步分解达到2NF，3NF，BCNF。全部表格将所有栏目分解成最小数据项1NF关系消除部分函数依赖消除传递函数依赖消除主属性对非主属性的函数依赖消除多值依赖2NF关系3NF关系BCNF关系4NF关系规范化过程4、关系模式的分解通过前面范式的介绍，我们知道原始的关系模式需要进行改进来满足数据库设计的规范性。那么我们在改进原始关系模型的时候要注意些什么呢，有什么方法呢？一个关系模式的分解可以是多种多样的，但不管怎样分解，最后产生的若干个关系模式应与原关系模式等价。关于“等价”的概念存在3种不同的含义：（1）分解具有“无损连接性”。（2）分解要“保持函数依赖”。（3）分解既要“保持函数依赖”，又要具有“无损连接性”。这三个含义也是实现分解的三条不同的准则。按照不同的准则，关系模式所能达到的分离程序各不相同，各种范式就是对分离程度的测试。学号系名称系负责人007101006401006402992101电力系计算机系计算机系信息系王洪肖海肖海杨君关系模型S

由已知的事实可得到S上的函数依赖如下：学号→系名称，系名称→系负责人显然，S中存在传递函数依赖：学号→系负责人，所以它会发生更新异常。例如，如果992101号学生毕业，在表中需删除该学生信息，则信息系的系主任杨君的信息也被删掉了；反过来，如果水利系还没有招收学生，那么这个系的系主任信息也无法存入。下面对S（学号，系名称，系负责人）进行3种形式的分解。

（1）将S（学号，系名称，系负责人）分解为S1，S2和S33张表如下：

DEPT电力系计算机系信息系S1S#007101006401006402992101S2MN王洪肖海杨君S3

显然，这3张表都属于BCNF。但是要查询“007101号学生在哪个系学习”或者“电力系的系主任是谁”这样的问题，在这3张表中是找不到答案的。因此，这样的分解毫无意义。关系模式的分解至少应该不丢失原有信息，这就产生了无损连接性的概念。

无损连接性可以这样理解，如果关系模式的一个分解与原模式等价，那么在原模式下的任一合法实例（即任一满足原模式数据依赖集的实例关系）在分解之后应能通过自然连接运算恢复出来，这一特征通常称为分解的无损连接性。（2）将S（学号，系名称，系负责人）分解为：S1（学号，系名称）和S2（学号，系负责人）。

可以证明，这个分解是可恢复的，它保持了无损连接性，且分解后的S1和S2都属于BCNF，但是对于存储异常，它仍然没有解决。原因就在于原来在S中存在的函数依赖DEPT→MN，现在在S1和S2中都不存在了。为此，人们又要求分解具有“保持函数依赖”的特性，即模式分解后，函数依赖集合应保持不变。（3）将S（学号，系名称，系负责人）分解为：S1（学号，系名称）和S2（系名称，系负责人）。

可以看出该分解既具有无损连接。该分解既具有无损连接性，又保持函数依赖，它既解决了更新异常，又没有丢失原关系的信息，这正是最合理和恰当的分解。

分解的无损连接性和保持函数依赖性有严格的判别算法和理论依据。有兴趣的读者可参考数据库原理方面的有关书籍，这里只介绍关于模式分解的关键知识。（1）若要求分解保持函数依赖，那么关系模式分解总可以达到3NF，但不一定能达到BCNF；（2）若要求分解既保持函数依赖，又具有无损连接性，则可以达到

3NF，但不一定能达到BCNF；（3）若要求分解具有无损连接性，那一定可达到4NF。

规范化理论为数据库设计提供了理论指南和工具。但是，并不是规范化程度越高，模式就越好。分解得过细，即使对消除存储异常有些好处，但查询时需要更多连接操作，很可能得不偿失。

因此，进行数据库设计时，必须结合应用环境和现实世界的具体情况合理地选择数据库模式。练习我们描述一个问题，大家来作出它的E-R模型，并且合理的转化为数据库的多个表。例子：市面上有很多书，书都有作者，而且写这本书的作者还要拿稿酬要求建立一个本问