第4讲 总第14讲 函数依赖及其公理 定理

发表于 更新于 分类于 ， Waline： 本文字数： 5.4k 阅读时长 ≈ 5 分钟

前言

基本内容

  1. 函数依赖
  2. 完全函数依赖与传递函数依赖
  3. 关于函数依赖的公理和定理
  4. 函数依赖集的最小覆盖

重点与难点

  • 一组概念:函数依赖、部分函数依赖和完全函数依赖、传递函数依赖、候选键、非主属性、逻辑蕴涵、闭包、属性闭包、覆盖、最小覆盖等
  • 关于函数依赖的公理和定理,相关的证明
  • 求属性闭包的算法、求最小覆盖的算法

函数依赖

(1)函数依赖的定义

设$R(U)$是属性集合$U=\lbrace A_1,A_2,\cdots,A_n \rbrace $上的一个关系模式,$X$, $Y$是$U$上的两个子集,若对$R(U)$的任意一个可能的关系$r$,  $r$中不可能有两个元组满足在$X$中的属性值相等而在$Y$中的属性值不等,则称**$X$函数决定$Y$**或$Y$函数依赖于$X$, 记作$X \to Y$。

示例

示例：$U=\lbrace 学号,姓名,年龄,班号,班长,课号,成绩 \rbrace$

  • 学号函数决定姓名和年龄:
    • $学号\to\lbrace 姓名,年龄\rbrace$
  • 学号函数决定班长:
    • $班号\to班长$
  • 学号和课号函数决定成绩:
    • $\lbrace 学号,课号\rbrace\to 成绩$

注：函数依赖的分析取决于对问题领域的限定和分析,取决于对业务规则的正确理解。
例如：问题领域中,学生是没有重名的,则有:年龄和家庭住址都函数依赖于姓名。
而在另一个问题领域中,学生是有重名的,则上述函数依赖是不成立的。

设计关系模式时,除给出属性全集外,还需给出数据依赖集合

(2)函数依赖的示例

示例:下列的表就是问题领域, 则存在的函数依赖有哪些呢?

表1


由于属性A上没有重复值,所以属性A可以决定B,A可以决定C
当B相同的时候,A有不同的值,所以B不能决定A
当B属性值相同的时候,C上的对应属性也是相同的,所以B能决定C
$A \to B$,$B \to C$,$A \to C$

表2


当属性A有相同的属性值时候,B上对应的属性值有不同值,所以A不能决定B
当属性A相同的时候,属性C对应的值也相同,所以A能决定C,$A \to C$
当属性A相同的时候,属性D对应的值也相同,所以A能决定D,$A \to D$
当属性B相同的时候,属性A对应的值不相同,所以B不能决定A,$B \nrightarrow A$
当属性B相同的时候,属性C对应的值不相同,所以B不能决定C
当属性B相同的时候,属性D对应的值相同,所以B能决定D,$B \to D$
当属性C相同的时候,属性A对应的值不相同,所以C不能决定A

(3)函数依赖的特性

(1)对$X \to Y$,但$Y\require{cancel} \cancel{\subset}X$, 则称$X\to Y$为非平凡的函数依赖；
(2)若$X \to Y$,则任意两个元组,若X上值相等,则Y上值必然相等,则称X为决定因素；
(3)若$X\to Y$ ,$Y\to X$, 则记作$X \leftrightarrow Y$,互相决定
(4)若Y不函数依赖于X,则记作$X \nrightarrow Y$；
(5)$X\to Y$,有基于模式R的,则要求对任意的关系r成立；有基于具体关系r的,则要求对某一关系r成立；
(6)如一关系r的某属性集X,r中根本没有X上相等的两个元组存在,则$X\to Y$恒成立；

(4)函数依赖的提取练习

请分析下列属性集上的函数依赖
$\textbf{学生(学号,姓名,班级,课号,课程名,成绩,教师,教师职务)}$
$\textbf{员工(员工码,姓名,出生日期,联系电话, 最后学历,毕业学校,培训日期,培训内容,职务变动日期,变动后职务 )}$
$\textbf{图书(书号,书名,出版日期,出版社,书架号,房间号)}$
$\textbf{客户(客户号,客户名称,类别,联系电话,产品编码,产品名称,数量,要货日期)}$

$\textbf{学生(学号,姓名,班级,课号,课程名,成绩,教师,教师职务)}$

  • $学号\to \lbrace 姓名,班级 \rbrace$
  • $课号\to 课程名$或者:
    • $\lbrace班级,课号\rbrace\to 教师$
    • $课号\to 教师$
    • $\lbrace学号,课号\rbrace\to 教师$
      • 这几个究竟选择哪一个,取决于对问题领域的理解.
  • $\lbrace学号,课号\rbrace\rightarrow 成绩$
  • $教师\to教师职务$
  • $\lbrace班级,课号\rbrace\to教师$

$\textbf{客户(客户号,客户名称,类别,联系电话,产品编码,产品名称,数量,要货日期)}$

$客户号\to\lbrace客户名称,类别\rbrace$
$产品编码\to产品名称$
$\lbrace客户号,产品编码,要货日期\rbrace\to数量$

完全函数依赖与传递函数依赖

(1)部分函数依赖与完全函数依赖的定义

在$R(U)$中，

  • 若$X\to Y$并且对于$X$的任何真子集$X’ $都有$X’ \nrightarrow Y$,则称$Y$完全函数依赖于$X$, 记为：$X\xrightarrow{f}Y$。
  • 否则称Y部分函数依赖于$X$, 记为：$X\xrightarrow{f}Y$.

示例:$U=\lbrace学号,姓名,年龄,班号,班长,课号,成绩 \rbrace$

  • $\lbrace学号,课号\rbrace \xrightarrow{f}U$
    • 单独的学号不能决定U,单独的课号(真子集)不能决定U,所以是完全函数依赖
  • $\lbrace学号,课号\rbrace \xrightarrow{p} 姓名$
    • 单独的学号就可以决定姓名了,所以是部分函数依赖
  • $\lbrace学号,课号\rbrace\xrightarrow{f} 成绩$
    • 单独的学号(真子集),单独的课号(真子集)都不能决定成绩,所以是完全函数依赖.

部分依赖存在着非受控冗余

(2)部分函数依赖与完全函数依赖的示例

$学生(学号,姓名,班级,课号,课程名,成绩,教师,教师职务)$

  • ${学号, 课号}\xrightarrow{f} U$; 但 ${学号, 课号}\xrightarrow{p} 姓名$
  • ${学号, 课号}\xrightarrow{p} 课程名$

$员工(员工码,姓名,出生日期,联系电话, 最后学历,毕业学校,培训日期,培训内容)$

  • ${员工码, 培训日期} \xrightarrow{p} U$;单独的员工码无法决定培训内容,培训日期可以决定培训内容.所以员工码加上培训日期来可以决定U
  • ${员工码, 培训日期} \xrightarrow{p} {姓名,出生日期 }$,单独的员工码就可以决定该员工的姓名和出生日期了,所以是部分函数决定

$图书(书号,书名,出版日期,出版社,书架号,房间号)$

  • $\lbrace书号,房间号,书架号\rbrace\to U$,书号可以决定书名,出版日期,出版社,

$客户(客户号,客户名称,类别,联系电话,产品编码,产品名称,数量,要货日期)$

$学生(学号,姓名,系号,系主任)$

(3)传递函数依赖的定义

在R(U)中，若$X\to Y$，$Y\to Z$ 且$Y\require{cancel} \cancel{\subset}X$,$Z\require{cancel} \cancel{\subset}Y$,$Z\require{cancel} \cancel{\subset}X$, $Y\nrightarrow X$, 则称Z传递函数依赖于X。

示例:$U=\lbrace学号,姓名,年龄,班号,班长,课号,成绩 \rbrace$
$学号\to班号$ ;$班号\to班长$,所以$学号\to班长$,(“班长”是传递依赖于 “学号”的。)

示例:$学生(学号,姓名,系号,系主任)$
$学号\to系号$; $系号\to系主任$,所以$学号\to系主任$(“系主任”是传递依赖于 “学号”的)

传递依赖存在着非受控冗余

(4)传递函数依赖的示例

$\textbf{商店(商店,商品,商品经营部,经营部经理)}$

  • $\lbrace商店,商品经营部\rbrace\to经营部经理$
  • $\lbrace商店,商品经营部\rbrace\to经营部经理$
    所以有传递依赖:$\lbrace商店,商品\rbrace\to经营部经理$

$\textbf{学生(学号,姓名,班级,班主任,课号,课程名,成绩,教师,教师职务)}$

  • $学号\to班级;班级\to班主任$;
  • $\lbrace学号,课号\rbrace\to教师;教师\to教师职务$;
    所以有传递依赖:$\lbrace学号,课号\rbrace\to教师职务$

$\textbf{员工(员工码,姓名,部门,部门经理)}$

  • $员工码\to部门$
  • $部门\to部门经理$
    所以有传递依赖:$员工码\to部门经理$

图书(书号,书名,出版日期,出版社,书架号,房间号,管理员)
客户(客户号,客户名称,类别,联系电话,产品编码,产品名称,数量,要货日期)

函数依赖相关的几个重要概念

(1)候选键的定义

设K为R(U)中的属性或属性组合,若$K\xrightarrow{f}U$,则称K为(U)上的候选键(Candidate Key)。

  • 唯一性
  • 最小性

主键

(1)可任选一个候选键作为R的主键(Primary Key)；

主属性

(2)包含在任一候选键中的属性称主属性(Prime Attribute),其他属性称非主属性；

超键

(3)若K是R的一个候选键,$S\supset K$, 则称S为R的一个超键(Super Key)。候选键是没有多余属性的超键,候选键带上任意个其他属性可被视为超键
唯一性,没有最小性

(2)候选键的示例

$\textbf{学生(学号,年龄,家庭住址,课程号,成绩,教师,教师职务)}$
学生(学号,年龄,家庭住址,课程号,成绩,教师,教师职务)

  • 候选键:学号和课程号就可以决定所有的属性,所以学号和课程号就是一个候选键,$\lbrace学号,课程号\rbrace$
  • 主属性:学号,课程号
  • 非主属性:年龄,家庭住址,成绩,教师,教师职务.

$\textbf{商店(商店,商品,商品经营部,商品经营部经理)}$
候选键是??,非主属性是??

  • 候选键:商店和商品可以决定商品经营部,商品经营部可以决定商品经营部经理,所以商店和商品可以决定所有的属性,所以候选键为商店和商品{商店,商品}
  • 非主属性:商品经营部,商品经营部经理.

$\textbf{学生(学号,姓名,所属系别,系主任)}$
候选键是??,非主属性是??
候选键:学号
非主属性:姓名,所属系别,系主任

(3)外键

若R(U)中的属性或属性组合X并非R的候选键，但X却是另一关系的候选键，则称X为R的外来键(Foreign Key)，简称外键。
示例:
$R=\lbrace合同号,合同名,签订日期,{\color{red}{供应商名}}\rbrace$
$S=\lbrace供应商名,地址,执照号,法人代表\rbrace$
合同号是关系R个候选键:$合同号\xrightarrow{f} \lbrace合同号,合同名,签订日期,供应商名\rbrace$
供应商名是关键S的候选键:$供应商名\xrightarrow{f}\lbrace供应商名,地址,执照号,法人代表\rbrace$
所以供应商名,在关系R中是外键

(4)逻辑蕴涵的定义

设F是关系模式R(U)中的一个函数依赖集合，X,Y是R的属性子集，如果从F中的函数依赖能够推导出$X\to Y$，则称F逻辑蕴涵$X\to Y$, 或称$X\to Y$是F的逻辑蕴涵。记作$F\models X\to Y$。

省略

(5)闭包的定义

被F逻辑蕴涵的所有函数依赖集合称为F的闭包(Closure)，记作$F^+$