relation-theory

发表于 更新于 Disqus：

摘自《数据库系统概论》第六章

关系数据理论

1. 问题

针对一个具体问题，如何构造一个适合它的数据模式

即应该构造几个关系，每个关系由哪些属性组成等。

不好的关系模式：

  • 数据冗余度太大，浪费存储空间
  • 更新异常
  • 插入异常
  • 删除异常

数据依赖

属性值间的相互关联。是数据内在的性质，是语义的体现

主要介绍函数依赖。

不合适的数据依赖，容易造成上述的4个问题。

2. 规范化

2.1 函数依赖

给定关系模式R(U, F)（本章忽略D域，DOM属性到域的映射），X和Y是U的子集。若对于R(U, F)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称“X函数确定Y”或“Y函数依赖于X”，记作 。

X称为这个函数依赖的决定属性组，也称为决定因素。

函数依赖是语义范畴的概念，只能根据数据的语义来确定函数依赖。例如“姓名->年龄”这个函数依赖只有在学生不重名的情况下成立。数据库设计者可以对现实世界作强制的规定。

函数依赖是指关系模式R在任何时刻的关系实例均要满足的约束条件。

非平凡函数依赖：

只讨论非平凡函数依赖。平凡函数依赖没有意义。

完全函数依赖：若 ，但对于X的任何一个真子集X‘，都有 ，则称Y对X完全函数依赖，记作 。否则称为部分函数依赖，记作

传递函数依赖：在R(U, F)中，如果 ，则称Z对X传递函数依赖。记作 。

注意这里不能存在 ，否则X与Y是等价的，Z直接依赖于X。

2.2 码

设K为关系模式R(U, F)中的属性或属性组合。若 ，则称K为R的一个候选码。

若，则K称为超码。

若关系模式R有多个候选码，则选定其中的一个作为主码。

主属性：包含在任何一个候选码的属性。

全码：整个属性组U是码。

外码：关系模式R的属性（组）X并非R的码，但X是另一个关系模式的码，则称X是R的外码。

主码与外码一起提供了表示关系间联系的手段。

2.3 范式 （不允许表中有表）

关系数据库的关系必须满足一定的要求。满足不同程度要求的为不同范式。

一个低一级范式的关系模式，通过模式分解，可以转换为若干个高一级范式的关系集合。这种过程叫做规范化。

1NF：

如果一个关系模式R的所有属性都是不可分的数据项，则 。

不允许表中有表。

2.4 2NF （非主属性不允许部分依赖）

若 ，且每一个非主属性完全函数依赖于任何一个候选码，则 。

采用投影分解法可将一个1NF关系分解为多个2NF关系，可一定程度上减轻原1NF关系存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。但并不能完全消除。

不是很懂这里非主属性的意义所在。

2.5 3NF （非主属性不允许传递依赖）

设关系模式 ，若R中不存在这样的码X、属性组Y及非主属性Z ，使得 成立，，则称 。

不是很懂这里Z是非主属性的意义所在。

不允许传递依赖，自然就不允许部分依赖。

2.6 BCNF（不依赖于非码）

设关系模式 ，若 且 时X必含有码，则 。

BC范式首先解决了3NF中主属性存在的部分依赖问题，例如3NF中可能某候选码中的一个子集可以—>另一个主属性，但是BCNF要求必须是码或码的超集才可以->。其次解决了3NF中主属性存在的传递依赖问题，这个也是类似的情况。

2.7 多值依赖

给定关系模式R(U,F)，X,Y,Z是U的子集，且Z=U-X-Y。关系模式R中多值依赖 成立当且仅当对R的任意关系r给定的一对(x,z)值，有一组Y的值，这组值仅仅决定于x值而与z值无关。

等价定义

非平凡多值依赖：X->->Y，且Z不为空。若Z为空则为平凡多值依赖。

多值依赖的性质：

  • 对称性：若X->->Y，则X->->Z。（可以画个二分图？？？）
  • 传递性：若XYZ=U，X->->Y，Y->->Z，则X->->Z-Y
  • 函数依赖是多值依赖的特殊情况
  • 懒得写了

2.8 4NF

关系模式 ，如果对于R的每个非平凡多值依赖 ，X都含有码，则 。

4NF允许的非平凡多值依赖实际上是函数依赖。

3. 数据依赖的公理系统

模式分解算法的理论基础。函数依赖有一个有效且完备的公理系统——Armstrong公理系统

用途：

  • 求给定关系模式的码
  • 从一组函数依赖求得蕴含的函数依赖

逻辑蕴含：给定关系模式R(U, F)，其任何一个关系r，若函数依赖X->Y都成立，则称F逻辑蕴含X->Y。

3.1 Armstrong公理系统

对关系模式 R(U, F) 有以下推理规则：

  • 自反律：若 ，则 为F所蕴含。
  • 增广律：若 为F所蕴含，且 ，则 为F所蕴含。
  • 传递律：若 和 为F所蕴含，则 为F所蕴含。

3.2 导出规则

可通过以上三条推理规则推出以下三条推理规则：

  • 合并规则：由 得 。
  • 伪传递规则：由 得 。
  • 分解规则：由 得 。

根据合并和分解规则，可得引理

成立的充分必要条件是 成立。

3.3 函数依赖闭包

闭包：在关系模式R(U, F)中为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记为 。

属性集闭包：能由根据公理导出。

判定 即判定 。

3.5 函数依赖集等价

如果 ，就说函数依赖集F覆盖G，或者F与G等价。

引理：F与G等价的充要条件是 。

3.6 最小依赖集

如果函数依赖集F满足：

  • F中任一函数依赖的右部仅含有一个属性。
  • F中不存在这样的函数依赖X->A，使得F与F-{X->A}等价。（即F中的函数依赖均不能由F中其他函数依赖导出）
  • F中不存在这样的函数依赖X->A，X有真子集Z使得F-{X->A}U{Z->A}与F等价。（F中各函数依赖左部为最小属性集）

则F为极小函数依赖集。

定理：每一个函数依赖集F均等价于一个极小函数依赖集，此 为F的最小依赖集。

F的最小依赖集不一定是唯一的

求最小依赖集步骤：

  • 将F中的所有依赖右边化为单一元素
  • 去掉F中的所有依赖左边的冗余元素
  • 去掉F中的所有冗余关系

4. 保持函数依赖的模式分解

关系模式 的一个分解是指 ，（其中 ，并且没有 ），即 。

若满足 ，那么该分解是一个保持函数依赖的分解。（可以用上面3.5节中的引理来证明一个分解是否保持函数依赖）

4.1 转换为3NF

1、极小化处理

2、按照相同左部进行分组

可以证明得到的一定是一系列3NF，具体证明在书P190-191

作业

1、设有关系模式 ，其中 ，。

(1). 计算 和 。

解：设 。

计算 ，逐一扫描 中的各个函数依赖，得 。因此 。

计算 ，逐一扫描 中的各个函数依赖，发现无额外元素，即 。

因此 。

设 。

计算 ，逐一扫描 中的各个函数依赖，得 。因此 。

计算 ，逐一扫描 中的各个函数依赖，发现无额外元素，即 。

因此 。

(2). 求 的所有候选码，并说明理由。

解：求出单个属性所对应的属性闭包：

由于只有 包含 ，因此候选码内部必有 。

可得 且 。

且 。

通过额外枚举，可以发现只有上述 、 满足候选码性质。

(3). 最高满足第几范式？为什么？

解：由于 ，因此 部分依赖于候选码 ，不满足第二范式条件。

因此 最高满足第一范式。

2、设有关系模式 ，其中：，求 的最小依赖集。

解：

首先将所有函数依赖的右边转换为单一属性：

然后去除所有函数依赖的左边的冗余属性：

考虑函数依赖 ，由于 ，因此 为冗余属性。故进一步简化：

考虑 是否冗余：不冗余

考虑 是否冗余：不冗余

考虑 是否冗余：可从 与Armstrong推出，故冗余

此时

考虑 是否冗余：不冗余

考虑 是否冗余：可从 得出，故冗余

此时

考虑 是否冗余：不冗余

考虑 是否冗余：不冗余

故得到 的最小依赖集：

3、设有关系模式 ，其中：，试问 是否成立，若成立请给出证明过程。

解：成立。证明如下：

令 。

计算 ，逐一扫描 中的各个函数依赖，得 ，故

计算 ，逐一扫描 中的各个函数依赖，得 。因此可知 ，根据Armstrong公理的性质，可得出 。

4、试用Armstrong公理系统推导出下面的推理规则：若 ，则有 。

解：首先根据增广率，可由 知 。

再根据传递率，可由 知 。

5、已知学生关系模式 。其中： 学号、 姓名、 系名、 系主任名、 课程、 成绩。

（1）写出关系模式 的基本函数依赖和主码。

解：，，，。

主码：。

（2）原关系模式 为第几范式？为什么？分解成高一级范式，并说明为什么？

解：为第一范式。首先对于关系模式 ，其所有属性都是不可分的属性，满足第一范式定义。

其次在该关系模式中，非主属性 部分函数依赖于主码 ，不满足第二范式定义。故 为1NF。

可以进行模式分解：。对于新关系模式 ，其主码为 ，故不存在部分函数依赖（但是存在传递依赖 ，），故为第二范式。对于新关系模式 ，其主码为 ，不存在部分函数依赖，也为第二范式。

（3）将关系分解成第三范式，并说明为什么？

解：在（2）的基础上进一步分解：。

对于 ，其只存在函数依赖 和 ，不存在传递依赖，故为第三范式。

对于 ，其只存在函数依赖 ，不存在传递依赖，故为第三范式。

对于 ，其只存在函数依赖 ，不存在传递依赖，故为第三范式。

6、设有关系模式 ，其中6个属性分别为学生的学号、姓名、年龄、教师的姓名、课程名及课程成绩。假设学生有重名，课程名也可能有重名。又假设教师无重名，且每个教师只教一门课，但一门课可有几个教师同时开设。当某个学生选定某门课后，其上课教师就固定了。

（1）试给出R的所有函数依赖（平凡函数依赖和部分函数依赖可不写）

解：，，，，。

（2） 试给出R的所有候选码。

解：

不存在除 外的属性组被 依赖，故候选码必然包含 。也因此可推出候选码不包含 。

求出单个属性所对应的属性闭包：

。

可知 ，且 。

同样 ，且 。

除此之外，无其余候选码。

7、试证明任何一个二目关系模式 都属于 。

证明：

分以下三种情况讨论：

  • 关系模式 主码为 ，即全码，此时显然为 。
  • 主码为 ，此时必有 ，，且 包含在码中，故满足 的定义。
  • 主码为 ，理由同上

证毕。

8、若 ，试证明 。

证明：利用反证法。

假设关系 中存在码 ，属性组 和非主属性 ，满足 ，即不满足 的定义。

由于 ，故 和 必包含码。

由于 包含码，故 能够决定其余属性组，包括 ，即 。这与假设中的 矛盾，故假设不成立。（本质上是通过让 和 等价来消除传递依赖。）

因此 。

9、设属性 两两不相交，且 。已知：元组 在数据库中，请给出哪些元组也必然在数据库中。

解：根据 ，可得出新的两个元组：,

根据 ， 可得出新的四个元组：。

10、给定关系 如下：

A B C D E

试给出至少2个非对称多值依赖。注：仅写结果不分析不得分。

解：首先有多值依赖 ，这是因为 相对于 有两个取值 ，且对于这两个取值，属性 都有对应属性值 ，即 取值只与 有关。

其次有多值依赖 ，这是因为 相对于 有四个取值 ，且对于这四个取值，属性 都有对应属性值 ，即 取值只与 有关。