北工大数据库课件pubc72.pptx

1§3函数依赖理论及其应用（书p52:3.5）一、函数依赖的逻辑蕴涵设：F是关系模式R给定的一组函数依赖集合。对于R的满足F的任意关系r，若能够从F中推导出关系r也满足函数依赖X→Y，则称F逻辑蕴涵X→Y。记为F?X→Y例设：关系模式R（A，B，C），F={A→BC}则：F?A→B

2二、函数依赖Armstrong公理1．函数依赖Armstrong公理A1.自反性（Reflexivity）：A2.增广性（Augmentation）：A3.传递性（Transitivity）：注：XZ（或：X,Z）即X∪Z设：关系模式R（U，F）。若Y?X?U，则X→Y若X→Y，且Z?U，则XZ→YZ若X→Y，Y→Z，则X→Z

32．四条推理规则（1）合并规则：若X→Y，X→Z，则X→YZ（4）伪传递规则：由X→Y，WY→Z，有WX→Z（2）分解规则：若X→YZ，则X→Y,X→Z例试证“合并规则”是正确的。（3）伪增广规则：若X→Y，W?Z，有XW→YZ∵X→Z，∵X→Y，∵X→XY，XY→YZ，∴X→XY（增广性）证:∴XY→YZ（增广性）∴X→YZ（传递性）证毕。

41.函数依赖集F的闭包（Closure）三、函数依赖集的闭包和属性的闭包定义：在关系模式R（U，F）中，F以及它的逻辑蕴涵所构成的函数依赖集合，叫做F的闭包，记为F+。

5例设：R（A，B，C），F={A→B，B→C}则有：A→φ，B→φ，C→φ，AB→φ，AC→φ，BC→φ，ABC→φ，A→A，AB→A，AC→A，ABC→A，A→B，AB→B，AC→B，ABC→B，A→C，AB→C，AC→C，ABC→C，A→AB，AB→AB，AC→AB，ABC→AB，A→AC，AB→AC，AC→AC，ABC→AC，A→BC，AB→BC，AC→BC，ABC→BC，A→ABC，AB→ABC，AC→ABC，ABC→ABC，F+=B→B，BC→B，B→C，BC→C，B→BC，BC→BC，C→C

6其中，X+F={A|X→A是所有由F给定和推导出的函数依赖集合}。2.属性集X关于函数依赖集F的闭包X+F（1）定义例设：R（A，B，C），F={A→B，B→C}。则A+F={ABC}设：F为属性集U上给定的一组函数依赖，X，A?U。则，X+F称为属性集X关于函数依赖集F的闭包，

7（2）计算X+F的算法例设：R（A，B，C），F={A→B，B→C}。求AF+=？初始:AF+={A}(因为：AA总是成立)AF+={AB}(因为F中有：AB)AF+={ABC}(因为F中有：BC)

8解决方案:1)计算:XF+。2)判定:Y??XF+?3．判定一个函数依赖是否属于F+？设：R（U，F），属性组X，Y?U。问：函数依赖X→Y是否被F逻辑蕴涵？即，判定：X→Y?F+？例设：F={A?B,B?C}问：AB?C?F+？解：∵(AB)+F={ABC}，显然有：C?(AB)+F∴AB?C?F+

9∴AB?C?G+,四、函数依赖的等价与复盖定理：F=G的充分必要条件是F?G+,且G?F+如果F+=G+，就说函数依赖集F复盖G，或F与G等价，记为F=G。1.函数依赖集的等价例设：F={A?B,B?C，AB?C}，G={A?B,B?C}解：∵(AB)+G={ABC}，而显然有G?F+成立，∴F=G成立。问：F=G？显然有：C?(AB)+G故：F?G+

10(2)F中每个函数依赖的“左”部都没有“多余”的属性。即：不存在函数依赖X?A，以及Z?X，使得F与(F–?X?A?)∪?