数据库设计理论

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

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

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

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

5、数据间的依赖关系太强。 解决的方法：将关系模式分解为一组较理想的关系模式。 第二节函数依赖 一，函数依赖 Fun cti onal Depe ndency 函数依赖是数据依赖的一种，反映属性或属性之间的依存、互相制约的关系， 既反映现实世界的约束关系。 二，函数依赖的定义 设R ( U )是属性U上的一个关系模式，X和Y均为U = A1,A2，An 的子集，r为R的任一关系，如果对于r中的任意两个元组u和v，只要有 UX = VX, 就有UY = VY，则称X函数决定Y ,或称丫函数依赖于X， 记作： X T Y 0 三，函数依赖的语义范畴： 1语义：数据所反映的现实世界事务本质的联系。 2

6、根据语义来确定函数依赖型的存在与否。 3.函数依赖反映属性之间的一般规律，必须在关系模式F的任何一个关系r 都满足约束条件。 回顾概念 键：由一个或多个属性组成。 设R (U)为一个关系模式，F为R的函数依赖集，X为 属性集U的子 (1) 超键：能唯一标识元组的属性集。 如果X U F，则X是R的超键。 (2) 候选键：不含有多余属性的超键 a X 是R的超键。 b 且不存在X的真子集丫，使得丫 U F 则称X是R的候选键 (3) 主键：用户选作元组标识的一个候选键。 (4) 主属性：包含任何一个候选键的属性。 (5) 非主属性：不包含任何一个候选键的属性。 (6) 外键：如果关系R的某一个属

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

8、 Y . 3 X和Y的联系是M : N ( M ,N 1 ) 贝X、Y之间不存在函数依赖。 五函数依赖图：FD图。 六完全函数依赖和部分函数依赖 在R (U)中，如果X 丫，并且对于X的任何真子集X ，都不存在X 丫，则称丫完全依赖于X，记作 X 丫 ( 箭头上加个F表示FULL完全函数依赖) 否则，如果X - 丫，且X中存在一个真子集X,使得X - 丫，则丫部 分函数依赖X 。 X - 丫 （箭头上面加一个P,表示PART,部分函数依赖） 七平凡函数依赖和非平凡函数依赖 设X , 丫 均为某关系的属性集，并且 X -丫, 若丫包含于X，则称X - 丫为平凡函数依赖 （丫是X的子集）。 若丫不

9、包含于X，则称X - 丫为非平凡函数依赖（丫不是X的子集） 第三节函数依赖的蕴涵与公理体系 一，函数依赖的逻辑蕴含 定义：设有关系模式R （ U ），及其函数依赖集F，如果对于R的任何一 个满足F的关系r ，函数依赖X - 丫都成立，则称F逻辑蕴含X - 丫或称 X - 丫可以由F推出，记作： F匸 XY 例题：关系模式R = （ A, B, C ） 则F逻辑蕴含A - C 记作： 7第7页共29页 ，函数依赖集F = A - B , B -C F A C 二，F闭包 定义：若F为关系模式R ( U )的函数依赖集，我们把F以及所有被F逻 辑蕴含的函数依赖的集合称为 F的闭包，记作F+。 F+

10、 = X Y | F 卜 X Y 三,Armstrong 公理 F1自反律：若丫包含于X，则X 丫(丫是X的子集) F2增广律：若X丫为F所蕴含，则XZYZ在R上成立。 F3传递律： 若XY，Y Z在R上成立，则X Z在R上成立。 F4伪增律：Z是W的子集，X Y为F所蕴含，则XW YZ在R上成立。 F5伪传律：若X Y，YV Z为F所蕴含，则XW Z在R上成立。 F6合并律：若X 丫 , X Z为F所蕴含，则XYZ在R上成立。 F7分解律：若Z是丫的子集，X Y为F所蕴含，则X Z在R上成立。 四，属性集的闭包 定义：若F为关系模式R ( U )的函数依赖集，X是U的子集，则由 Armstr

11、ong公理推导出来的所有X Ai所形成的属性集 Ai | i=1,2,n 称为X关于F的闭包记为X +。 属性集闭包的举例： 设：R = ABC, F = A -B, B -C 当 X 分别是 A , B , C , 时，求 X+ 解： 当X =A 时，X+ = =ABC 当X =B 时，X+ = =BC 当X =C 时，X+ = =C 定理 :X 丫 能根据Armstro ng推理规则导出的充要条件是 Y匚X + 只要丫是X+的子集，则X - Y 0 只要X - 丫，则丫 一定是X+的子集 定理：Armstrong公理的完备性定理 函数依赖推理规则系统（自反律、增广律、传递律）是完备的 函数

12、依赖公理体系 Armstrong公理体系 由于Armstrong公理的完备性，Armstrong公理及其推论构成了一个完备的 逻辑推理体系，称为 Armstrong公理体系： A，一套形式推理规则。 B，利用这些推理规则可以求出给定关系模式的关键字。 C，而且可以从关系模式的一组已知函数依赖出发，求得它蕴含的所有函数 依赖。 D，或者对于给定的F和X - 丫，判断X - 丫是否在F+中。 9第9页共29页 E，是关系规范化理论的依据 计算X+的算法 1) 依据: 若F为关系模式R ( U ) 的函数依赖集，X , Z , W 是U的子集，对 于任意的Z- W F ,若Z是X的子集，则X-XW

13、2) 算法的实现 输入：关系模式R上的子集X，R上的函数依赖F 输出：X关于F的闭包X+ 3 )算法： a .令 X (0) = , X + = X ; b. 如果X(0)工X+ ,置X(0) = X +，否则，转到d ; c .对于f中的每个未被访问过的函数依赖 Y - Z ,若Y包含于X+，则令 X + = X + U Z，为被访问过的函数依赖设置访问标志，转b ; d .输出X+ 结论 判定函数依赖X - 丫是否能由F导出的问题，可以转化为求 X+的闭包, 并判定丫是否是X+子集的问题。 即求闭包的问题可以转化为求属性集的问题。 判定给定函数依赖X - 丫是否蕴含与函数依赖集F算法实现:

14、 输入：函数依赖集F ,函数依赖X - 丫 输出：若X - 丫 F+，输出真，否则输出假。 四，函数依赖的等价和覆盖 定义：设F和G是关系模式R ( U )上的两个函数依赖集，如果F+ = G , 则称F等价于G，亦称F覆盖G或者G覆盖F ,记作： 定理1 ,设F和G是关系模式R ( U ) 的两个函数依赖集，那么 的充分必要条件是： G 二时 IL F 匚 G+ 定理2，设F和G是关系模式R ( U ) 的两个函数依赖集，那么 的充分必要条件是 G 二时 IL F 匚 G+ 定理3，每个函数依赖集F都可以被一个右部只有单属性的函数依赖集 所覆盖。 五，最小函数依赖集 设F是函数依赖集，如果F

15、满足 (1) F中每个函数依赖X-丫的右边均为单个属性。 (2) F中的任何一个函数依赖X-A ,其F - ( X -A )都与F不等价。 (3) F中的任何一个函数依赖X- A , Z为X的真子集, (F X -A ) U Z - A 都与 F 不等价。 则称，F为最小函数依赖集。 (2) 是消除右侧冗余。 (3) 是消除左侧冗余。 因为(2), (3)没有先后顺序，所以，最小函数依赖不是唯一的 第四节关系模式的分解 一，关系模式分解的衡量标准 (1) 仅具有无损连接性。(不增减信息) (2) 仅保持函数的依赖集。(不破坏属性间存在的依赖关系) (3) 即具有无损连接性，又保持函数依赖集。

16、二，分解的无损连接性： 1 定义：设F是关系模式R的函数依赖集 ,Rk( Uk, Fk ) (T = R1 ( U1 , F1 ) , R2 ( U2 , F2 ), 是R的一个分解， Jlui(r) x TlU2(r) 或者 =m % (r) 1=1 如果R满足F的任何一个关系均有 r 二 mo (r) 则分解具有无损连接性。 ,Rk ) 定理 :设(T =( R1 , R2 , 为关系模式的一个分解，r为R的任何一个关系 ri = (1) n ui (r)贝U： (2) 如果 S = m (T (r)贝Un ui(S) = ri (3) ma (m a (r)= m a (r) 结论： 分

17、解后的关系作自然联结必包含分解前的关系。即分解不会丢失信息，但可 能增加信息。 只有r = m a (r)时，分解才具有无损连接性。 为什么要进行关系分解 一个关系分解后，可以存放原来不能存放的信息(通常称为“悬挂”的元组), 这是实际所需要的，正是分解的优点。 在做自然联结时，这类“悬挂”元组自然丢失了，但不是信息的丢失，而是 合理的。 检验分解无损联结的算法 设关系模式R ( A1 , A2 ,An) F是他的函数依赖集， (7 = R1 , R2 , R3 ,Rk 为 R 的一个分解。 算法 (1) 构造初始表 构造一个k行n列的初始表，其中每列对应于 R的一个属性，每行用于表 示分解后

18、的一个模式组成。如果属性Aj属于关系模式Ri ，则在表的第i行第 j列置符号aj ，否则，置符号bij . (2) 根据F中的函数依赖修改表的内容 考察F中的每一个函数依赖X - Y，在属性组X所在的那些列上寻找 具有相同符号的行，如果找到这样的两行或更多行，则修改这些行，使这些行上 的属性组Y所在的列上的元素相同。 修改规则：如果丫所在的要修改的行中有一个为 aj ，则这些元素均变 为aj ，否则，改动为bmj , 其中m为这些行的最小行号。 注意：若某个bij被改动，则该列中凡是与bij相同的符号均作相同的 改动。 循环的对F中的函数依赖进行逐个处理，直到发现表中有一行变为： al , a

19、2 , a3 ,an或者不能再被修改为止。 (3) 断分解是否无损联结 如果通过修改，发现表中有一行变为 a1,a2 ,，an ，则分解是无 损联结的，否则，分解不具有无损联结性。 定理：检验分解无损联结的算法，能够正确判定一个分解是否具有无损联结性。 定理：设c = ( R1 , R2 )是模式R的一个分解，F是R的函数依赖集, 那么，c是R (关于F的)的无损分解的充要条件是: (R1 A R2) R1 R2 F 或者 (R1 A R2 ) R2 R1 F 保持函数依赖的分解 定义：设F是关系模式R在所有属性集U上的函数依赖集，Z是U的子 集，F在Z上的一个投影用 n z ( F )表示，

20、定义为： n z ( F ) = X Y | X Y F+ 且 XY 是 Z 的子集 设关系模式R的一个分解 c = R1 , R2 ,，Rk 如果Fi = n Ri的并集 (F1 U F2 U Fk ) + = F + 贝U，分解保持函数依赖集F 关系模式满足的确定条件称为范式。根据满足的约束条件不同，范式可以分 为 1NF、2NF 3NF BCNF 4NF 5NF 等。 不同的范式，性质不同。 关系模式规范化：把一个低一级的关系模式分解为高一级的关系模式的过程。 回顾概念 1 超键：能唯一标识元组的属性集。 2. 候选键：不含有多余属性的超键 a. X 是R的超键。 b.且不存在X的真子集

21、丫，使得丫 - U F+ 则称X是R的候选键 3. 主键：用户选作元组标识的一个候选键。 4. 主属性：包含在任何一个候选键中的属性。 5. 非主属性：不包含在任何一个候选键中的属性。 6. 外键：如果关系R的某一个属性组，不是该关系本身的候选关键字，而 是另一关系的候选关键字，则称该属性组是 R的外来关键字或外部关键 字。 完全函数依赖和部分函数依赖 在R ( U )中，如果X - 丫，而且对于X的任意真子集X，都不存在 X- 丫，则称丫完全依赖于X，否则，如果X - 丫 ,且存在X的真子集 X,使得X - 丫成立，则丫部分函数依赖于丫 。 完全函数依赖X 旦 Y部分函数依赖X Y 如何确定

22、关系模式中的候选码 (1) 如果有属性不在函数依赖集中出现，那么它必须包含在候选码中。 (2) 如果有属性不在函数依赖集中任何函数依赖的右边出现，那么它必定包 含在候选码中。 (3) 如果该属性或属性组能唯一的标识元组，贝尼就是候选码。 未给出关系模式的函数依赖集，如何确定其中的候选码 根据对数据库的语义描述，确定其中的候选码，同时还可以写出该关系模式 上的函数依赖集。 第一范式：1NF 关系模式的所有域为简单域，其元素不可再分，是数据项而不是数据组，这 样的关系模式称为第一范式 ：1NF 存在的问题：数据冗余，插入异常，删除异常，修改异常。 第二范式：2NF 给定关系模式R及其上的函数依赖集

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

24、系模式都是3NF的，则称该关系模式是3NF 的。 定理：一个3NF的关系模式必定是3NF的。 BCNF (改进了的 3NF ) 给定关系模式R及其上的函数依赖集F，如果F中每一个非平凡函数依 赖X - Y的左部(决定因素)X中必含有候选码，则称 R是Boyde /Codd 范式，简称BCNF。 R 1NF 若X 丫且Y不是X的子集，X中必含有候选码。 贝U R BCNF BCNF的内涵 (1) 非主属性对候选码完全函数依赖。 (2) 主属性对不含他的候选码完全函数依赖。 (3) 没有属性完全函数依赖于一组非主属性。 (4) 主属性不传递函数依赖于任何一个候选码。 (5) 主属性不传递函数依赖于

25、任何一个候选码。 定理：BCNF满足3NF。 重叠的候选码 一个模式有两个非单属性的候选码，且二者的交集非空，则称这两个候选码 是重叠的。 若模式中没有重叠的候选码时，则 2NF 一定是BCNF。 只有当模式中有重叠的候选码时，3NF不一定是BCNF。 总结： 1NF J消除了非主属性对候选码的部分函数依赖。 2NF ；消除了非主属性对候选码的传递函数依赖。 3NF ；消除了主属性对候选码的部分和传递函数依赖。 BCNF 规范化的基本思想 逐步消除不合适的函数依赖，使数据库的各个关系模式达到某种程度上的分 离。 模式分解的算法 模式分解的基本要求： 分解后的关系模式与分解前的关系模式等，即分解

26、必须 (1) 具有无损联结性， (2) 保持函数依赖。 逐步分解的定理： 设F是关系模式R的函数依赖集 P = R1 , R2 ,，Rk 是R关于F的一个无损连接分解。 1 .若p 1 = S1 , S2 ,，Sm 是Ri关于Fi的一个无损连接分 解，其中 Fi = n Ri (F),则 p 2 = R1,Ri-1,S1,Sm,Ri+1,Rk 是 R关于F的无损分解 2 .设p 3 = R1,Rk,Rk+1,Rn 是R的一个分解，其中p是p 3 的子集，则P 3也是关于F的无损联结分解。 面向BCNF且具有无损联结的分解 算法1 :输入：关系模式R，函数依赖集F， 输出：R的一个无损联结的分解

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

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

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