数据库的设计理论

1、数据库的设计理论第一节，关系模式的设计问J一概念：1 .关系模型：用二维表来表示实体集，用外键来表示实体间的联系，这样的 数据模型，叫做关系数据模型。关系模型包含内涵和外延两个方面：外延：就是关系或实例、或当前值。它与时间有关，随时间的变化而变化。 （主要是由于元组的插入、删除、修改等操作引起的）内涵：内涵是与时间独立的，它包括关系属性、以及域的一些定义和说明。 还有数据的各种完整性约束。数据的完整性约束分为静态约束和动态约束。静态约束包括数据之间的联系（称为数据依赖），主键的设计和各种限制。动态约束主要定义如插入、删除和修改等操作的影响。通常我们称内涵为关系模式。2 .关系模式：是对一个关系

2、的描述，二维表的表头那一行称为关系模式， 乂称为表的框架或记录类型。关系模式的定义包括：模式名、属性名、值域名和模式的主键。关系模式仅 仅是对数据特征的描述。关系模式的一般形式为R （ U , D , DOM , F ）R是关系名。U是全部属性的集合。D是属性域的集合。DOM是U和D之间的映射关系，关系运算的安全限制。F是属性间的各种约束关系，也称为数据依赖。关系模式可以表示为：关系模式（属性名1,属性名2 ,属性名n ）示例：学生（学号，XX,年龄，性别，籍贯）o当且仅当U上的一个关系r满足F时，r就称为关系模式R （U, F）上 的一个关系，R是关系的型，r是关系的值，每个值称为R的一个关

3、系。关系数据库模式：一个数据库是由多个关系构成的。一个关系数据库对应多个不同的关系模式，关系数据库模式是一个数据库中 所有的关系模式的集合。它规定了数据库的全局逻辑结构。关系数据库模式可以表示为：S = Ri < Ui, Di, DOM , Fi > I i= 1,2,., n ）3 .关系子模式关系子模式是用户所用到的那部分数据的描述。外模式是关系子模式的集合。4 .存储模式存储模式及内模式。关系数据库理论的主要内容：（1）数据依赖。数据依赖起着核心的作用。（2） X 式 o（3）模式的设计方法。如何设计一个合理的数据库模式：（1）与实际问题相结合。泛关系模式：把现实问题的所有属

4、性组成一个关系模式泛关系：泛关系模式的实例称为泛关系。泛关系模式中存在的问题：a数据冗余b更新异常，c插入异常d删除异常。（2）数据库设计理论：借助近代代数工具，把抽象的数据理论同实际问题结合起来。理论基础：数据依赖（数据的相关性）。二，关系模式及其评价。1 .关系数据库设计的核心：关系模式的设计。2 .关系模式的设计：按照一定的原则，从数量众多的而乂互相关联的数据中构造出一组即能 较好的反映现实世界，而乂有良好的操作性能的关系模式。3 .关系模式的优劣、评价、改进：冗余度高 修改困难 插入问题 删除问题这些问题的产生原因是：属性间的约束关系太强，即数据间的依赖关系太强。解决的方法：将关系模式

5、分解为一组较理想的关系模式。第二节函数依赖一，函数依赖 Functional Dependency函数依赖是数据依赖的一种，反映属性或属性之间的依存、互相制约的关系, 既反映现实世界的约束关系。二,函数依赖的定义设R （ U ）是属性U上的一个关系模式，X和Y均为U = A1,A2，An 的子集，r为R的任一关系，如果对于r中的任意两个元组u和v ,只要有 UX=VX,就有UY = VY,则称X函数决定Y ,或称Y函数依赖于X, 记作：三，函数依赖的语义X畴:1 .语义：数据所反映的现实世界事务本质的联系。2 .根据语义来确定函数依赖型的存在与否。3 .函数依赖反映属性之间的一般规律，必须在关

6、系模式F的任何一个关系 r都满足约束条件。回顾概念键：由一个或多个属性组成。设R（U）为一个关系模式，F为R的函数依赖集，X为属性集U的 子集。（1）超键：能唯一标识元组的属性集。如果X f U £ F ,则X是R的超键。（2）候选键：不含有多余属性的超键a X是R的超键。b且不存在X的真子集Y ,使得Y - U £产则称X是R的候选键（3）主键：用户选作元组标识的一个候选键。（4）主属性：包含任何一个候选键的属性。（5）非主属性：不包含任何一个候选键的属性。（6）外键：如果关系R的某一个属性组不是该关系本身的候选键，而是另 一个关系的候选键，则称该属性组是R的外来关键码，

7、或称为外键（外码）。如何确定候选码?（1）如果有属性不在函数依赖集中出现，那么它必定包含在候选码中。（2）如果有属性不在函数依赖集中任何函数依赖的右边出现，那么它必定包 含在候选码中。（3）如果该属性或属性组能唯一标识元组，则它就是候选码。根据对数据库的语义描述，确定其中候选码，同时还可以写出该关系模式的 函数依赖集。四，函数依赖的关系属性间的关系决定函数依赖关系。设X和Y都是U的子集：1 X和Y的联系是1:1则X f Y, Y f X .2 X和Y的联系是M ： 1 （M> 1 ）则X f Y.3 X和Y的联系是M ： N （M,N> 1 ）则，X、Y之间不存在函数依赖。五函数依

8、赖图：FD图。六 完全函数依赖和部分函数依赖在R（U）中，如果X f Y，并且对于X的任何真子集X、，都不存在X' f Y，则称Y完全依赖于X ,记作X f Y （箭头上加个F表示FULL完全函数依赖）否则，如果X f Y ,且X中存在一个真子集X',使得X' f Y ,则Y 部分函数依赖X OX f Y （箭头上面加一个P,表示PART,部分函数依赖）七平凡函数依赖和非平凡函数依赖设X,Y均为某关系的属性集，并且 X - Y,若Y包含于X ,则称X f Y为平凡函数依赖（Y是X的子集）。若Y不包含于X ，则称X - Y为非平凡函数依赖（Y不是X的子集）第三节函数依赖的

9、蕴涵与公理体系一，函数依赖的逻辑蕴含定义：设有关系模式R ( U ),及其函数依赖集F,如果对于R的任何一 个满足F的关系r ,函数依赖X - Y都成立，则称F逻辑蕴含X - Y或 称X f Y可以由F推出，记作：FU X>Y例题：关系模式R = (A,B.C),函数依赖集F= AfB,BfC 则F逻辑蕴含A-C记作：Ft A - C二，F闭包定义：若F为关系模式R(U)的函数依赖集，我们把F以及所有被F逻 辑蕴含的函数依赖的集合称为F的闭包，记作r oF+= X-Y I F 卜 X-Y )三，Armstrong 公理Fl自反律：若Y包含于X，则X f Y (Y是X的子集)F2增广律：若

10、X-Y为F所蕴含，则XZ-YZ在R上成立。F3传递律：若X-Y, Y-Z在R上成立，则X-Z在R上成立。F4伪增律：Z是W的子集，X-Y为F所蕴含，则XWf YZ在R上成立。F5伪传律：若X-Y, YW-Z为F所蕴含，则XW-Z在R上成立。F6合并律：若X-Y,XfZ为F所蕴含，则X-YZ在R上成立。F7分解律：若Z是Y的子集，X-Y为F所蕴含，则X-Z在R上成立。四，属性集的闭包定义：若F为关系模式R ( U )的函数依赖集，X是U的子集，则由 Armstrong公理推导出来的所有X - Ai所形成的属性集 Ai I i=12m 称 为X关于F的闭包记为X+。属性集闭包的举例：设：R=ABC

11、,F= A-B,B-C 当 X 分别是 A,B,C,时，求 X+Mzl当当时时时Be = x+C = + X定理：X f Y能根据Armstrong推理规则导出的充要条件是:Y = X +只要Y是X+的子集，则X - Y。只要X f Y ,则Y 一定是X+的子集。定理：Armstrong公理的完备性定理函数依赖推理规则系统(自反律、增广律、传递律)是完备的。函数依赖公理体系Armstrong公理体系由于Armstrong公理的完备性，Armstrong公理及其推论构成了一个完备的逻 辑推理体系，称为Armstrong公理体系：A , 一套形式推理规则。B ,利用这些推理规则可以求出给定关系模式

12、的关键字。C ,而且可以从关系模式的一组已知函数依赖出发，求得它蕴含的所有函数 依赖。D ,或者对于给定的F和X Y ,判断X - Y是否在产中。E ,是关系规X化理论的依据。计算X+的算法1)依据：若F为关系模式R(U)的函数依赖集，X , Z , W是U的子集，对于 任意的ZfWGF,若Z是X的子集，则X-XW2)算法的实现输入：关系模式R上的子集X , R上的函数依赖F输出：X关于F的闭包X+3)算法:a.令 X (0)=小，X-二 X ;b.如果X(0) W f ,置X(0) = X： 否则，转到d ；c.对于f中的每个未被访问过的函数依赖Y f Z ,若Y包含于X+，则令X+ = X

13、+ U Z ,为被访问过的函数依赖设置访问标志，转b ；d.输出X+结论判定函数依赖X - Y是否能由F导出的问题，可以转化为求X+的闭 包，并判定Y是否是X+子集的问题。即求闭包的问题可以转化为求属性集的问题。判定给定函数依赖X - Y是否蕴含与函数依赖集F算法实现：输入：函数依赖集F ,函数依赖X - Y输出：若X - Y £户，输出真，否则输出假。四，函数依赖的等价和覆盖定义：设F和G是关系模式R(U)上的两个函数依赖集，如果产二6+, 则称F等价于G ,亦称F覆盖G或者G覆盖F ,记作：F三G定理1 ,设F和G是关系模式R(U)的两个函数依赖集，那么F+ = G+ 的充分必要

14、条件是：G U F+ 且 F U G+定理2,设F和G是关系模式R(U)的两个函数依赖集，那么F+ = G+ 的充分必要条件是G = F+ 且 F £ G +定理3 ,每个函数依赖集F都可以被一个右部只有单属性的函数依赖集G 所覆盖。五，最小函数依赖集设F是函数依赖集，如果F满足(1)F中每个函数依赖XT 的右边均为单个属性。(2) F中的任何一个函数依赖X-A,其F-(X-A)都与F不等价。(3) F中的任何一个函数依赖X-A,Z为X的真子集，(F - Xf A ) U Z f A 都与 F 不等价。则称，F为最小函数依赖集。(2)是消除右侧冗余。(3)是消除左侧冗余。因为(2),

15、 (3)没有先后顺序，所以，最小函数依赖不是唯一的。第四节关系模式的分解一，关系模式分解的衡量标准(1)仅具有无损连接性。(不增减信息)(2)仅保持函数的依赖集。(不破坏属性间存在的依赖关系)(3)即具有无损连接性，又保持函数依赖集。二，分解的无损连接性：1 .定义：设F是关系模式R的函数依赖集o = RI ( UI , Fl ), R2 (U2 , F2),Rk ( Uk , Fk )是R的一个分解，= Jlui(r) x 兀U2(r)JIUk (r) 或者m。二四五Ui (r) 1=1 1如果R满足F的任何一个关系均有r = m(j(r)则分解具有无损连接性。定理：设。二(RI <

16、U1,F1 > , R2 < U2 , F2 > ,Rk <Uk , Fk >) 为关系模式的一个分解，r为R的任何一个关系ri = JT ui (r)则：(1)KJ (r)(2)如果 S = mo (r)则 JT ui (S) = ri(3) mo (mo (r)= mo (r)9 / 23结论：分解后的关系作自然联结必包含分解前的关系。即分解不会丢失信息，但可 能增加信息。只有r=mo(r)时，分解才具有无损连接性。为什么要进行关系分解？一个关系分解后，可以存放原来不能存放的信息(通常称为“悬挂”的元组), 这是实际所需要的，正是分解的优点。在做自然联结时，这

17、类“悬挂”元组自然丢失了，但不是信息的丢失，而是 合理的。检验分解无损联结的算法设关系模式R(A1 ,A2,An)F是他的函数依赖集，。=(RI ,R2,R3,. Rk 为 R 的一个分解。算法(1)构造初始表构造一个k行n列的初始表，其中每列对应于R的一个属性，每行用于表 示分解后的一个模式组成。如果属性Aj属于关系模式Ri ,则在表的第i行第j 列置符号aj ,否则，置符号bij.(2)根据F中的函数依赖修改表的内容考察F中的每一个函数依赖X - Y ,在属性组X所在的那些列上寻 找具有相同符号的行，如果找到这样的两行或更多行，则修改这些行，使这些行 上的属性组Y所在的列上的元素相同。修改

18、规则：如果Y所在的要修改的行中有一个为aj ,则这些元素均变 为aj ,否则，改动为bmj ,其中m为这些行的最小行号。注意：若某个bij被改动，则该列中凡是与bij相同的符号均作相同的 改动。循环的对F中的函数依赖进行逐个处理，直到发现表中有一行变为：al ,a2,a3,an或者不能再被修改为止。(3)断分解是否无损联结如果通过修改，发现表中有一行变为al,a2,，an ,则分解是无损联 结的，否则，分解不具有无损联结性。定理：检验分解无损联结的算法，能够正确判定一个分解是否具有无损联结性。定理：设。=(RI ,R2 )是模式R的一个分解，F是R的函数依赖集, 那么，。是R (关于F的)的无

19、损分解的充要条件是：(RI n R2) - R1 R2 EF或者(RI A R2) - R2 - RI GF保持函数依赖的分解定义：设F是关系模式R在所有属性集U上的函数依赖集，Z是U的 子集，F在Z上的一个投影用nz ( F )表示，定义为：五 z ( F )= X-Y X-Y GF+ 且 XY 是 Z 的子集设关系模式R的一个分解。= RI , R2 ,，Rk 如果Fi = JIRi的并集(Fl U F2 U Fk ) = F"则，分解保持函数依赖集F关系模式满足的确定条件称为X式。根据满足的约束条件不同，X式可以 分为 INF、2NF、3NF、BF、4NF、5NF 等。不同的X

20、式，性质不同。关系模式规X化:把一个低一级的关系模式分解为高一级的关系模式的过程。回顾概念# / 231 .超键：能唯一标识元组的属性集。2 .候选键：不含有多余属性的超键a. X是R的超键。b. 且不存在X的真子集Y,使得Y-U GP则称X是R的候选键3 .主键：用户选作元组标识的一个候选键。4 .主属性：包含在任何一个候选键中的属性。5 .非主属性：不包含在任何一个候选键中的属性。6 .外键：如果关系R的某一个属性组，不是该关系本身的候选关键字，而 是另一关系的候选关键字，则称该属性组是R的外来关键字或外部关键 字。完全函数依赖和部分函数依赖在R（U）中，如果X - Y ,而且对于X的任意

21、真子集X： 都不存在 X，一 Y ,则称丫完全依赖于X ,否则，如果X - Y ,且存在X的真子集 X使得X，f Y成立，则丫部分函数依赖于Y。完全函数依敕XY部分函数依触X 旦 Y如何确定关系模式中的候选码？（1）如果有属性不在函数依赖集中出现，那么它必须包含在候选码中。（2）如果有属性不在函数依赖集中任何函数依赖的右边出现，那么它必定包 含在候选码中。（3）如果该属性或属性组能唯一的标识元组，则它就是候选码。未给出关系模式的函数依赖集，如何确定其中的候选码？根据对数据库的语义描述，确定其中的候选码，同时还可以写出该关系模式 上的函数依赖集。关系模式的所有域为简单域，其元素不可再分，是数据项

22、而不是数据组，这 样的关系模式称为第一 X式：1NF存在的问题：数据冗余，插入异常，删除异常，修改异常。第二X式：2NF给定关系模式R及其上的函数依赖集F，如果R上的任何一个非主属 性都完全依赖于他的每一个候选关键字，则称R是第二X式：2NF若关系模型H包含的每个关系模式都是2NF的，则称该关系模型是 2NF 的。存在的问题：可能存在数据冗余，插入异常，删除异常，修改异常。结论：若R £ 1NF ,且R中所有的候选码为单一属性，则R e 2NF o传递函数依赖在R(U)中，如果X-Y,YfZ,并且Z不是丫的子集，那么 称X f Z传递函数依赖，即Z传递函数依赖于X>第三X式给定

23、关系模式R及其上的函数依赖F ,如果R的任何一个非主属性都不 传递函数依赖于他的任何一个候选码，则称R是第三X式3NF o若关系模型H包含的每一个关系模式都是3NF的，则称该关系模式是 3NF 的。定理：一个3NF的关系模式必定是3NF的。BF (改进了的3NF )# / 23给定关系模式R及其上的函数依赖集F ,如果F中每一个非平凡函数依 赖X f Y的左部（决定因素）X中必含有候选码，则称R是Boyde/Codd X式，简称BF。R e INF若X f Y且Y不是X的子集，X中必含有候选码。则R G BFBF的内涵（1）非主属性对候选码完全函数依赖。（2）主属性对不含他的候选码完全函数依赖

24、。（3）没有属性完全函数依赖于一组非主属性。（4）主属性不传递函数依赖于任何一个候选码。（5）主属性不传递函数依赖于任何一个候选码。定理：BF满足3NF o重叠的候选码一个模式有两个非单属性的候选码，且二者的交集非空，则称这两个候选码 是重叠的。若模式中没有重叠的候选码时，则2NF 一定是BF。只有当模式中有重叠的候选码时，3NF不一定是BF o总结：1NFI消除了非主属性对候选码的部分函数依赖。2NFI消除了非主属性对候选码的传递函数依赖。3NF*消除了主属性对候选码的部分和传递函数依赖。BF规X化的基本思想逐步消除不合适的函数依赖，使数据库的各个关系模式达到某种程度上的分 离。模式分解的算

25、法模式分解的基本要求：分解后的关系模式与分解前的关系模式等，即分解必须(1)具有无损联结性，(2)保持函数依赖。逐步分解的定理：设F是关系模式R的函数依赖集P = RI , R2 ,.，Rk 是R关于F的一个无损连接分解。1 .若P 1 = SI , S2 ,Sm 是Ri关于Fi的一个无损连接分解，其中 Fi = n Ri (F)，则 P2 = RI, -Ri-1, SI,Sm, Ri+1, ，Rk 是 R关于F的无损分解。2 .设P 3= RI,Rk, Rk+1,Rn 是R的一个分解，其中P是P 3 的子集，则P3也是关于F的无损联结分解面向BF且具有无损联结的分解算法1 :输入：关系模式R

26、 ,函数依赖集F , 输出：R的一个无损联结的分解.，其中每一个子模式都满足F 在其上投影的BF.算法实现：反复运用逐步分解定理，逐步分解关系模式R使得每次分解都具有 无损联结性。而且每次分解出来的子关系模式都至少有一个具有BFX式。（1）置初值。= R ,（2）检查P中的关系模式，如果均属BF则转到第4步。（3）在P中找出不属于BF的关系模式S ,那么S中必能找出一个函 数依赖X-A EF （A不包含于X）且X不是S的候选码。因此，XA必然不 包含S的全部属性。把 S 分解为 SI ,S2 ,设 S1 = XA,S2 = S A,并以 SI ,S2 代 替R中的S ,返回（2）o（4）终止分

27、解，输出P .算法出现的问题：（1）分解结果不是唯一的。（2）分解不保证保持函数依赖。面向3NF且保持函数依赖的分解算法2 输入：关系模式R及其上的最小函数依赖集F.输出：R的保持函数依赖的分解，其中每个关系模式是关于F在其上投影的3NF o算法实现：（1）如果R中存在一些不在F中出现的属性，则将他们单独构成一个关 系模式，并从关系模式R中消去。（2）如果F中有一个函数依赖X A ,且XA = R，则R不用分解, 算法终止。（3）对F中的每个函数依赖X - A ,构造一个关系模式XA o 如果 X f Al , X f A2 Xf An 均属于F ,则构造一个关系模式XA1 A2.An。本算法

28、注意，必须是最小函数依赖集F ,否则出错。面向3NF既有无损联结性，又保持函数依赖分解算法：输入：关系模式R及其上的最小函数依赖集F o 输出：R的具有无损联结性及保持函数依赖的分解。算法实现：（1）按算法2对关系模式R进行分解，设结果为PP = RI ,R2 , Rk （2） X是R的候选码t = Pu x 是R的一个分解。（3）求t的最小集合。（当Ri是Rj的子集Gt时，消去Ri ）定理算法的正确性。设X是R的候选码，则t = P ux是R的一个分解，且所有的关系都 满足3NF ,同时具有无损联结性，和保持函数依赖性。由于P中全部模式均为3NF , X中属性之间不存在传递和部分函数依赖, 即X也是3NF的，分解t也具有无损联结性。由于X是R的候选码，验证 表中模式X所对应的行，经修改后全部由a组成。模式设计的原则关系模式R相对于函数依赖F分解成数据库模式P = RI , R2，,Rk 一般具有下面4个特性。（1）P中的每个关系模式Ri上应具有某种X式的性质。（如 3NF, BF ）（2）无损联结性。（3）保持函数依赖集。（4）最小性，即P中模式个数应最少，且模式中属性总数应最少。一个好的模式设计方法应符合下了三条原则。（1）表达性。（2）分理性,（3）最小冗余性-多值依赖函数依赖有效的表达了属性