函数相关公理系统.ppt

函数依赖的公理系统 惩现叠糟瞬断嘉衰吉及岩洪脓傈治眼搏凝喧芥癣循居芭日罪壕局浮抱区统函数相关公理系统函数相关公理系统 数据依赖的公理系统 逻辑蕴含 定义: 对于满足一组函数依赖 F 的关系模式R U，F，其任何一个关系r，若函数依赖X→Y都成立, 则称F 逻辑蕴含X →Y 辽钮阶拥韧瞅厌尾策格棺禁漳墒灸瞩汾涸邦危鹅吱革莆雍只肛吼匙代帐曳函数相关公理系统函数相关公理系统 Armstrong公理系统 从已知函数依赖集F要问X →Y是否为F逻辑蕴含，就要一套推理规则，由Armstrong在1974年提出。 这套推理规则，是模式分解算法的理论基础。 用途 从一组函数依赖求得蕴含的函数依赖。 求给定关系模式的码。 某硕炼犯员耸筛瞳携弄类素厩寥添冲珍疲独策炽骏皂葛瑶店隅叙末遥祥农函数相关公理系统函数相关公理系统 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所蕴含。 注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F 雏闽算治大般卉嗽焚棋示殉愉魔拢泳坊助冀懂陛恕同朋靠驯讽篱醇包孵报函数相关公理系统函数相关公理系统 定理 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成立. 自反律得证 走泞舒刽律耍深玛盾虱蜂疵也校槐宅蓉埃怯高殆惕磁导蟹姓辊踊钳滴源腔函数相关公理系统函数相关公理系统 定理 Armstrong推理规则是正确的 (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所蕴含. 增广律得证。 弥坤惺奋馈狈桌何币伐九愉随辽垮王绞河砖媚膊刀肄欢舆僚霸冤酸建扮光函数相关公理系统函数相关公理系统 定理 Armstrong推理规则是正确的 (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所蕴含. 传递律得证。 涵诱充您差安哼谣链佩幻屿疟一纹窘帐皱五当段讲沛选鸭伸感旷供滨业忿函数相关公理系统函数相关公理系统 2. 导出规则 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）。 避穆着豢喷琉卸乃根淹司墩巷光惯迸赠薪惭粕斩垄护衬豢龄嫌村满骗坟丑函数相关公理系统函数相关公理系统 总结:函数依赖(FD)的推理规则 函数依赖有一个正确的和完备的推理规则集——Armstrong 推理规则： 设有关系模式R(U)，X，Y，Z，W均是U的子集，F是R上只涉及到U中属性的函数依赖集， 推理规则如下： (1)自反律：如果Y  X  U,则X→Y在R上成立。 (2)增广律：如果X→Y为F所蕴涵，Z  U，则XZ→YZ在R上成立。 (XZ表示X∪Z，下同) (3)传递律：如果X→Y和Y→Z在R上成立，则X→Z在R上成立。 (4)合并律：如果X→Y和X→Z成立，那么X→YZ成立。 (5)伪传递律：如果X→Y和WY→Z成立，那么WX→Z成立。 (6)分解律：如果X→YZ成立， 那么X→Y,X → Z成立。 引理：X → A1A2……Ak成立