时间：2022-12-29 00:30:01 | 来源：信息时代
时间：2022-12-29 00:30:01 来源：信息时代
键 : 关系模式的一种特殊子集,关系中的每个对象在其上取的值都是该对象的唯一标识。
如果X是函数依赖模式(R,∑)中R的一个子集,它满足∑⊧X→R,但对任何一个X的真子集X′都有∑⊧/X′→R,则称X为(R,∑)的键。 由于∑⊧X→R,所以,从函数依赖的定义知每个元组u在键X上的取值u[X]都是每个元组的唯一标识。键是Codd首先提出的。
一个函数依赖模式可能有多个键。包含在任何一个键中的属性都称为主属性,不属于任何键的属性都称为非主属性。
例如,关系模式CSL{学号,课程号,课程名,学习期限,成绩,奖学金},CSL上的函数依赖集合∑={课程号→学习期限,{学号,课程号}→成绩,成绩→奖学金,课程号→课程名,课程名→课程号}。对于函数依赖模式(CSL,∑),由Armstrong公理系统(Armstrong公理系统请见函数依赖条目)可以知:
∑⊧{学号, 课程号}→成绩
∑⊧{学号, 课程号}→奖学金
∑⊧{学号, 课程号}→学习期限
∑⊧{学号, 课程号}→课程名
∑⊧{学号, 课程号}→课程号
∑⊧{学号, 课程号}→学号
以∑⊧{学号,课程号}→CSL(反复应用Armstrong公理的F4)。
然而∑⊧/学号→成绩及∑⊧/课程号→成绩,所以,∑⊧/学号→CSL及∑⊧/课程号→CSL,所以,{学号,课程号}是一个键。同理,从Armstrong公理系统可知,{学号,课程名}也是(CSL,∑)的一个键,而且容易验证(CSL,∑)再没有其他键了。于是对于(CSL,∑)有:键是{学号,课程号}及{学号,课程名},主属性是: 学号,课程号,课程名; 非主属性是: 学习期限,成绩,奖学金。
显然计算键可从R的一元子集开始,按子集元素个数递增(宽度优先)来进行,当检验出一个X是键后,它的超集就不再做检验,即可用最少的计算次数而求得所有键。
求函数依赖模式(R,∑)全部键的问题可多项式地归约为一个图覆盖问题。因为众所周知图覆盖问题是NP完全问题,所以求函数依赖模式(R,∑)全部键的问题是NP完全问题。
设Ω={R1,R2,…,Rn}是一个数据库模式,∑1,∑2,…,∑n分别是R1,R2,…,Rn上的函数依赖集合,Xi是函数依赖模式(Ri,∑i)上的键, 若XiRj,1≤i,j≤n,i≠j,则称Xi是函数依赖模式(Ri,∑i)上的外部键。外部键主要用于各关系模式之间的连接。
关键词：数据
在线咨询
