五关系数据理论.doc

第五章 关系数据理论 章 节 6.3 数据依赖的公理系统 6.4 模式的分解 课型 新授课 课时 2节课 班级 2005级11、12班 教 学 目 标 掌握数据依赖的公理系统 教 学 重 点 难 点 重点掌握Armstrong公理 掌握属性集闭包的算法 3. 侯选码的求解理论和算法 教学 关键 数据依赖的公理系统。 关于模式分解的算法。 教学 方法 讲授与课件演示。 教 具 计算机大屏幕投影。 复 习 内 容 函数依赖与范式 引 入 内 容 如何求出给定关系模式的所有函数依赖， 如何求关系模式的码。 讲 解 内 容 6.3 数据依赖的公理系统 ? 1. 逻辑蕴含 定义6.11 对于满足一组函数依赖 F 的关系模式R U，F，其任何一个关系r，若函数依赖X→Y都成立, (即对于r中任意两个元组s,t,若s[X]=t[X]，则s[Y]t[Y])，则称F逻辑蕴含X →Y 例如R(X, Y,Z),F={X→Y, Y→Z} X→Z 为了求得给定关系模式的码，为了从一组给定的函数依赖求得蕴涵的函数依赖，就需要一套推理规则。 这组推理规则是Armstrong于1974年提出的，所以称为 Armstrong公理系统。 2. Armstrong公理系统 ? 一套推理规则，是模式分解算法的理论基础 ?用途:求给定关系模式的码 ?从一组函数依赖求得蕴含的函数依赖 ?关系模式R U，F 来说有以下的推理规则： ?Al.自反律（Reflexivity）：若YX U，则X →Y为F所蕴含。 (Sno,Sname) →Sname 注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F ?A2.增广律（Augmentation）：若X→Y为F所蕴含，且Z→U，则XZ→YZ为F所蕴含。 ?A3.传递律（Transitivity）：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。 定理 6.1 Armstrong推理规则是正确的 （l）自反律:若Y X U，则X →Y为F所蕴含 证: 设Y X U 对R U，F 的任一关系r中的任意两个元组t，s： 若t[X]=s[X]，由于Y X，有t[y]=s[y]，所以X→Y成立. 自反律得证 （2）增广律: 若X→Y为F所蕴含，且Z U，则XZ→YZ 为F所蕴含。 证：设X→Y为F所蕴含，且Z U。 设RU，F 的任一关系r中任意的两个元组t，s； 若t[XZ]=s[XZ]，则有t[X]=s[X]和t[Z]=s[Z]； 由X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]，所以XZ→YZ为F所蕴含. 增广律得证。 （3）传递律：若X→Y及Y→Z为F所蕴含，则 X→Z为 F所蕴含。 证：设X→Y及Y→Z为F所蕴含。 对RU，F 的任一关系 r中的任意两个元组 t，s。 若t[X]=s[X]，由于X→Y，有 t[Y]=s[Y]； 再由Y→Z，有t[Z]=s[Z]，所以X→Z为F所蕴含. 传递律得证。 3. 导出规则 (1) 根据A1，A2，A3这三条推理规则可以得到下面三条推理规则： ?A4 合并规则：由X→Y，X→Z，有X→YZ。 （A2， A3） ?A5 分解规则：由X→Y及 ZY，有X→Z。 （A1， A3） A6 伪传递规则：由X→Y，WY→Z，有XW→Z。 （A2， A3） 证明： ?根据合并规则和分解规则，可得引理6.1 引理6.l X→A1 A2…Ak成立的充分必要条件是X→Ai成立（i=l，2，…，k）。 4. 函数依赖闭包 定义6.12 在关系模式RU，F中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包，记为F+。 F+={X→Y|F|= X→Y } 例：已知关系模式R(XYZ)，F={X→Y,Y→Z},求F+ 。 这里对函数依赖的定义做一下扩充。用φ表示空属性集，并定义φ→φφ函数依赖于任何属性和属性集合。 则φ→φ，X→φ, Y→φ XX XY YZ XZ 计可得到43个函数依赖。 F={X Y,Y Z}, F+计算是NP完全问题，X A1A2...An 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,