第14讲 褂氆理系统 .pptVIP

6.3 数据依赖的公理系统 Armstrong公理系统 FD的闭包，属性集的闭包 候选码 极小函数依赖集 逻辑蕴含 定义6.11 对于满足一组函数依赖 F 的关系模式R U，F，其任何一个关系r，若函数依赖X→Y都成立（即r中的任意两元组t，s，若t[X]=s[X]，则t[Y]=s[Y]），则称 F逻辑蕴含X →Y。 1. Armstrong公理系统 关系模式R U，F 来说有以下的推理规则： Al.自反律（Reflexivity）： 若Y ? X ? U，则X →Y 为F 所蕴含。 A2.增广律（Augmentation）：若X→Y为F所蕴含，且Z ? U，则XZ→YZ 为F 所蕴含。 A3.传递律（Transitivity）：若X→Y及Y→Z 为F 所蕴含，则X→Z为F所蕴含。 可以从逻辑蕴含的定义出发证明推理规则的正确性。 2. 导出规则 根据A1，A2，A3这三条推理规则可以得到下面三条推理规则： 合并规则：由X→Y，X→Z，有X→YZ。 伪传递规则：由X→Y，WY→Z，有XW→Z。 分解规则：由X→Y及 Z?Y，有X→Z。 3. 函数依赖集的闭包 定义6.l2 在关系模式RU，F中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包，记为F+。 求闭包的算法 算法6.l 求属性集X（X ? U）关于U上的函数依 赖集F 的闭包XF+ . 输入：X，F 输出：XF+ 步骤： 1）令X（0）=X，i=0 2）求B,这里B = {A |(? V)( ? W) ( V→W?F∧V ? X（i）∧A? W)}； 3）X（i+1）=B∪X（i） 4）判断X（i+1）= X （i）吗? 若相等或X（i+1）=U , 则X（i+1）就是XF+ , 算法终止。 若否，则 i=i+l，返回第（2）步。 回顾： 函数依赖集的闭包 属性集的闭包 候选码求解方法 1.查找只在左边出现的属性集X; 2.若X非空: 判断X的闭包是否为U,若是则即为所求码; 否则,考查两边都出现的属性y：依次检查X与y的各种极小组合,判断其闭包是否为U; 3.若X为空: 考查两边都出现的属性y：依次检查y的各种极小组合,判断其闭包是否为U; 6. 函数依赖集等价 定义6.14 如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。 7. 最小依赖集 定义6.15 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。 (1) F中任一函数依赖的右部仅含有一个属性。 (2) F中不存在这样的函数依赖X→A，使得F与 F-{X→A}等价。 (3) F中不存在这样的函数依赖X→A， X有真 子集Z使得F-{X→A}∪{Z→A}与F等价。 极小化过程 对F进行“极小化处理”，找出F的一个最小依赖集: (1)右部单属性： 逐一检查F 中各函数依赖FDi：X→Y，若Y=A1A2 …Ak， 则用 { X→Aj | j=1，2，…， k} 来取代X→Y。 注意 F的最小依赖集Fmin不一定是唯一的,它与对各函数依赖FDi 及X→A中X各属性的处置顺序有关。 * * 根据推理规则，很容易得到这样一个重要事实： 引理6.l X→A1 A2…Ak成立的充分必要条件是X→Ai成立（i=l，2，…，k）。 F={X Y,Y Z}, F +计算是NP完全问题 F+={ X φ, Y φ, Z φ, XY φ, XZ φ, YZ φ, XYZ φ, X X, Y Y, Z Z, XY X, XZ X, YZ Y, XYZ X, X Y, Y Z , XY Y, XZ Y, YZ Z, XYZ Y, X Z, Y YZ, XY Z, XZ Z, YZ YZ, XYZ Z, X XY, XY XY, XZ XY, XYZ XY, X XZ, XY YZ, XZ XZ, XYZ YZ X YZ, XY XZ, XZ XY, XYZ