|
|
|
|
|
|
|
|
|
| 第55题
2013年上半年
|
|
26%
|
|
| 给定关系模式R(U,F),其中，属性集U={A,B,C,D,E,G}，函数依赖集F={A→B,A→C,C→D,AE→G}。若将R分解为如下两个子..
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
数据依赖是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系，是现实世界属性间相互联系和约束的抽象，是数据内在的性质，是语义的体现。函数依赖则是一种最重要、最基本的数据依赖。
|
|
|
|
（1）函数依赖。设R(U)是一个属性集U上的关系模式，X和Y是U的子集。若对R(U)的任何一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数决定Y或Y函数依赖于X，记作X→Y。
|
|
|
（2）非平凡的函数依赖。如果X→Y，但Y X，则称X→Y是非平凡的函数依赖。
|
|
|
（3）平凡的函数依赖。如果X→Y，但Y X，则称X→Y是平凡的函数依赖。
|
|
|
（4）完全函数依赖。在R(U)中，如果X→Y，并且对于X的任何一个真子集X'，都有X'不能决定Y，则称Y对X完全函数依赖，记作 。
|
|
|
（5）部分函数依赖。如果X→Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作 。部分函数依赖也称局部函数依赖。
|
|
|
|
（6）传递依赖。在R(U,F)中，如果X→Y，Y?X，Y不能函数决定X，Y→Z，则称Z对X传递依赖。
|
|
|
|
（7）码。设K为R(U,F)中的属性的组合，若K→U，且对于K的任何一个真子集K'，都有K'不能决定U，则K为R的候选码，若有多个候选码，则选一个作为主码。候选码通常也称为候选关键字。
|
|
|
|
（8）主属性和非主属性。包含在任何一个候选码中的属性叫做主属性，否则叫做非主属性。
|
|
|
|
（9）外码。若R(U)中的属性或属性组X非R的码，但X是另一个关系的码，则称X为外码。
|
|
|
|
（10）函数依赖的公理系统（Armstrong公理系统）。设关系模式R(U,F)中，U为属性集，F是U上的一组函数依赖，那么有以下的推理规则。
|
|
|
|
.A1自反律（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所蕴含。
|
|
|
|
|
|
.合并规则：若X→Y，X→Z，则X→YZ为F所蕴含。
|
|
|
|
.伪传递率：若X→Y，WY→Z，则XW→Z为F所蕴含。
|
|
|
|
.分解规则：若X→Y及Z?Y，则X→Z为F所蕴含。
|
|
|
|
引理X→A1A2…Ak成立的充分必要条件是X→Ai（i=1,2,…,k）成立。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Armstrong公理系统（或称函数依赖的公理系统）：设关系模式R（U，F），其中U为属性集，F是U上的一组函数依赖，那么有如下推理规则：
|
|
|
（1）A1自反律：若 ，则X→Y为F所蕴涵。
|
|
|
（2）A2增广律：若X→Y为F所蕴涵，且 ，则XZ→YZ为F所蕴涵。
|
|
|
|
（3）A3传递律：若X→Y，Y→Z为F所蕴涵，则X→Z为F所蕴涵。
|
|
|
|
|
|
（1）合并规则：若X→Y，X→Z，则X→YZ为F所蕴涵。
|
|
|
|
（2）伪传递率：若X→Y，WY→Z，则XW→Z为F所蕴涵。
|
|
|
（3）分解规则：若X→Y， ，则Ⅹ→Z为F所蕴涵。
|
|
|
|
引理：X→A1A2…Ak成立的充分必要的条件是X→Ai成立（i=1，2，3，…，k）。证明略。
|
|
|
函数依赖的闭包F+及属性的闭包
|
|
|
|
|
|
【定义7.16】关系模式R（U，F）中为F所逻辑蕴含的函数依赖的全体称为F的闭包，记为：F+。
|
|
|
属性的闭包
|
|
|
【定义7.17】设F为属性集U上的一组函数依赖， ， 能由F根据Armstrong公理导出｝，则称 为属性集X关于函数依赖集F的闭包。
|
|
|
算法：求属性的闭包 。
|
|
|
|
|
输出： 。
|
|
|
|
|
|
|
②求B，
|
|
|
|
|
|
|
|
⑤若相等，或X（i）=U，则X（i）为属性集X关于函数依赖集F的闭包。且算法终止。
|
|
|
|
|
|
|
|
给定一个关系模式R（U，F），U=｛A1，A2，…，An｝，F是R的函数依赖集，那么，可以将属性分为如下四类：
|
|
|
|
|
|
|
|
|
|
|
|
根据候选码的特性，对于给定一个关系模式R（U，F），可以得出如下结论：
|
|
|
结论1：若 是L类属性，则X必为R的任一候选码的成员。若 ，则X必为R的唯一候选码。
|
|
|
结论2：若 是R类属性，则X不是R的任一候选码的成员。
|
|
|
结论3：若 是NLR类属性，则X必为R的任一候选码的成员。
|
|
|
结论4：若 是L类和NLR类属性组成的属性集，若 ，则X必为R的唯一候选码。
|
|
|
|
|
|
【定义7.18】如果函数依赖集F满足下列条件，则称F为一个最小函数依赖集，或称极小函数依赖集或最小覆盖。
|
|
|
|
（1）F中的任一函数依赖的右部仅有一个属性，即无多余的属性。
|
|
|
|
（2）F中不存在这样的函数依赖X→A，使得F与F-｛X→A｝等价，即无多余的函数依赖。
|
|
|
|
（3）F中不存在这样的函数依赖X→A，X有真子集Z使得F与F-｛X→A｝∪｛Z→A｝等价，即去掉各函数依赖左边的多余属性。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
