大学计算机系数据库课件--第6讲关系数据理论剖析.ppt

规范化（续） 第四范式4NF 定义：关系模式RU，F∈1NF，如果对于R的每个非平凡多值依赖X→→Y（Y ? X），X都含有码，则R∈4NF。 如果R ∈ 4NF， 则R ∈ BCNF 不允许有非平凡且非函数依赖的多值依赖 允许的非平凡多值依赖必须存在对应的函数依赖 规范化（续） 上例： Teaching(C,T,B) ∈ 4NF 因为：存在非平凡的多值依赖C→→T，且C不是码。 用投影分解法把Teaching分解为如下两个关系模式： CT(C, T) ∈ 4NF CB(C, B) ∈ 4NF C→→T， C→→B是平凡多值依赖。 规范化（续） 总结：关系模式规范化的基本步骤 1NF ↓ 消除非主属性对码的部分函数依赖 消除决定属性 2NF 集非码的非平 ↓ 消除非主属性对码的传递函数依赖 凡函数依赖 3NF ↓ 消除主属性对码的部分和传递函数依赖 BCNF ↓ 消除非平凡且非函数依赖的多值依赖 4NF 关系数据理论 三、数据依赖的公理系统 数据依赖的公理系统 逻辑蕴含 定义1：对于满足一组函数依赖 F 的关系模式R U，F，其任何一个关系r，若函数依赖X→Y都成立, （即r中任意两元组t，s，若 t[X] = s[X]，则 t[Y] = s[Y] ），则称 F 逻辑蕴含X →Y。 数据依赖的公理系统（续） Armstrong公理系统 对于关系模式R U，F ，有以下的推理规则： A1.自反律：若Y ? X ? U，则X →Y为F所蕴含。 A2.增广律：若X→Y为F所蕴含，且Z ? U，则XZ→YZ为F所蕴含。 A3.传递律：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。 数据依赖的公理系统（续） 导出规则 1. 根据A1，A2，A3这三条推理规则可以得到下面三条推理规则： 合并规则：由X→Y，X→Z，有X→YZ。 （A2， A3） 伪传递规则：由X→Y，WY→Z，有XW→Z。 （A2， A3） 分解规则：由X→Y及 Z?Y，有X→Z。 （A1， A3） 2. 根据合并规则和分解规则，可得： 引理1：X→A1 A2…Ak成立的充分必要条件是X→Ai成立（i=l,2,…,k）。 数据依赖的公理系统（续） 函数依赖的闭包 定义2：在关系模式RU，F中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包，记为F +。 （函数依赖的闭包） 定义3：设F为属性集U上的一组函数依赖，X ?U， XF+ ={ A | X→A 能由F 根据Armstrong公理导出}，XF+称为属性集X关于函数依赖集F 的闭包。（属性集的闭包） 数据依赖的公理系统（续） Armstrong公理系统是有效的、完备的 有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在 F + 中； 完备性：F + 中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。 数据依赖的公理系统（续） 引理2 设F为属性集U上的一组函数依赖，X，Y ? U，X→Y能由F 根据Armstrong公理导出的充分必要条件是 Y ?XF+。 用途 将判定X→Y是否能由 F 根据Armstrong公理导出的问题，转化为求出XF+ 、判定Y是否为XF+的子集的问题。 数据依赖的公理系统（续） [例1] 已知关系模式RU，F，其中 U = { A，B，C，D，E }； F = { AB→C，B→D，C→E，EC→B，AC→B }。 求（AB）F+ 。 解 ： 设X（0）=AB； （1） X（1）= AB∪CD=ABCD。 （2） X（2）= X（1）∪E=ABCDE。 （3） X（2）= U，算法终止 ? （AB）F+ =ABCDE。 （AB为候选码） 数据依赖的公理系统（续） 定义4：如果 G + = F +，就说函数依赖集 F 覆盖 G（F是G的覆盖，或G是F的覆盖），或 F 与 G 等价。 定义5：如果函数依赖集F