给定关系模式R<UF>，其中U为属性集，F是U上的一组函数依赖，那么Armstrong公理系统..

2018年上半年上午试卷综合知识

第 43 题


知识点	函数依赖 Armstrong公理系统
关键词	函数依赖函数
章/节	数据库系统

给定关系模式R<U,F>，其中U为属性集，F是U上的一组函数依赖，那么Armstrong公理系统的增广律是指（）。

A. 若X→Y，X→Z，则X→YZ为F所蕴涵

B. 若X→Y，WY→Z，则XW→Z为F所蕴涵

C. 若X→Y，Y→Z为F所蕴涵，则X→Z为F所蕴涵

D. 若X→Y为F所蕴涵，且Z⊆U，则XZ→YZ为F所蕴涵

相关试题规范化理论

第45题

2011年上半年

设有员工实体Employee (员工号，姓名，性别，年龄，电话，家庭住址，家庭成员，关系，联系电话)。其中，“家庭住址”包括邮编、省、市、街道信息；“家庭成员，关有多个家庭成员..

第43题

2016年上半年

假设关系R(A₁，A₂，A₃)上的一个分解为ρ={(A₁,A₂),(A₁

第43题

2014年上半年

给定关系模式R(U,F)，U={A,B,C,D}，F={AB→C,CD→B}。关系R（42），且分别有（43）。

知识点讲解

· 函数依赖

· Armstrong公理系统

函数依赖

设R（U）是属性U上的一个关系模式，X和Y是U的子集，r为R的任一关系，如果对于r中的任意两个元组u和v，只要有u[X]=v[X]，就有u[Y]=v[Y]，则称X函数决定Y，或称Y函数依赖于X，记为X→Y。

从函数依赖的定义可以看出，如果有X→U在关系模式R（U）上成立，并且不存在X的任一真子集X′使X′→U成立，那么称X是R的一个候选键。也就是X值唯一决定关系中的元组。由此可见，函数依赖是键概念的推广，键是一种特殊的函数依赖。

在R（U）中，如果X→Y，并且对于X的任何一个真子集X′，都有X′→Y不成立，则称Y对X完全函数依赖。若X→Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖。

在R（U）中，如果X→Y（Y不是X的真子集），且Y→X不成立，Y→Z，则称Z对X传递函数依赖。

设U是关系模式R的属性集，F是R上成立的只涉及U中属性的FD集，则有以下三条推理规则：

（1）自反性：若Y?X?U，则X→Y在R上成立；

（2）增广性：若X→Y在R上成立，且Z?U，则XZ→YZ在R上成立；

（3）传递性：若X→Y和Y→Z在R上成立，则X→Z在R上成立。

这里XZ、YZ等写法表示X∈Z，Y∈Z。上述三条推理规则是函数依赖的一个正确的和完备的推理系统。根据上述三条规则还可以推出其他三条常用的推理规则：

（1）并规则：若X→Y和X→Z在R上成立，则X→YZ在R上成立；

（2）分解规则：若X→Y在R上成立，且Z?Y，则X→Z在R上成立；

（3）伪传递规则：若X→Y和WY→Z在R上成立，则WX→Z在R上成立。

在关系模式R（U，F）中为F所逻辑蕴含的函数依赖全体叫做F的闭包，记作F⁺。

设F为属性集U上的一组函数依赖，X是U的子集，那么相对于F属性集X的闭包用X⁺表示，它是一个从F集使用推理规则推出的所有满足X→A的属性A的集合：

X⁺={属性A|X→A在F⁺中}

如果G⁺=F⁺，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。

如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，也称为最小依赖集或最小覆盖。

（1）F中任一函数依赖的右部仅含有一个属性；

（2）F中不存在这样的函数依赖X→A，使得F与F-{X→A}等价；

（3）F中不存在这样的函数依赖X→A，X有真子集Z使得F-{X→A}∨{Z→A}与F等价。

Armstrong公理系统

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→A₁A₂…A_k成立的充分必要的条件是X→A_i成立（i=1，2，3，…，k）。证明略。

函数依赖的闭包F⁺及属性的闭包

函数依赖的闭包F⁺

【定义7.16】关系模式R（U，F）中为F所逻辑蕴含的函数依赖的全体称为F的闭包，记为：F⁺。

属性的闭包

【定义7.17】设F为属性集U上的一组函数依赖，

，

能由F根据Armstrong公理导出｝，则称

为属性集X关于函数依赖集F的闭包。

算法：求属性的闭包

。

输入：X，F。

输出：

。

步骤：

①令X^（0）=X，I=0

②求B，

③X^（ⁱ^+1）=B∪ X^（ⁱ^）

④X^（ⁱ^+1）=X^（ⁱ^）？

⑤若相等，或X^（ⁱ^）=U，则X^（i）为属性集X关于函数依赖集F的闭包。且算法终止。

⑥若不相等，则i=i+1，返回②。

候选码的求解方法

给定一个关系模式R（U，F），U=｛A₁，A₂，…，A_n｝，F是R的函数依赖集，那么，可以将属性分为如下四类：

.L：仅出现在函数依赖集F左部的属性。

.R：仅出现在函数依赖集F右部的属性。

.LR：在函数依赖集F左右部都出现的属性。

.NLR：在函数依赖集F左右部都未出现的属性。

根据候选码的特性，对于给定一个关系模式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｝等价，即去掉各函数依赖左边的多余属性。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5