博客

函数依赖

1、关系模式的形式化定义

关系模式由五部分组成，即它是一个五元组：

R(U, D, DOM, F)

R：关系名

U：组成该关系的属性名集合

D：属性组U中属性所来自的域的集合

DOM：属性向域的映象集合

F：属性间数据的依赖关系集合

2、函数依赖普遍存在于现实生活中。

例如：设计一个用于学生管理的数据库，该数据库涉及的属性包括学号（Sno）、姓名（Sname）、所在系（Sdept）、住处（Loca）、课程号（Cno）、成绩（Grade）。

假设用一个单一关系模式 SLC<U，F> 来表示该数据库，则该关系模式为：

U = {Sno，Sname，Sdept，Loca，Cno，Grade}

假设有以下语义：

（1）学生的学号是唯一的。

（2）一个系有若干个学生，但一个学生只能在一个系学习。

（3）同一个系的学生住在同一个区域。

（4）一个学生可以选修多门课程，每门课程可以被多个学生选修。

（5）每个学生选修一门课程有一个成绩。

关系模式 SLC<U，F>

U = { Sno，Sname，Sdept，Loca，Cno，Grade }

F ＝{ Sno → Sname, Sno → Sdept, Sdept → Loca, (Sno, Cno) → Grade }

上述关系存在以下几个方面的问题：

⒈ 数据冗余太大

⒉ 更新异常

⒊ 插入异常

⒋ 删除异常

结论：

SLC关系模式不是一个好的关系模式

好的关系模式：应该不会发生插入异常、更新异常和删除异常，并且数据库的冗余要尽可能地少。

在关系模式SLC中，（Sno，Cno）为主键。SLC中U上的一组函数依赖F：

F = {Sno → Sname, Sno → Sdept, Sdept → Loca, (Sno, Cno) → Grade }

可表示成如图5.1所示：

在关系模式SLC中：

Grade完全由主键（Sno，Cno）决定

Sname、Sdept的值由Sno(主键的一部分)决定

Loca的值由Sdept决定，与Sno无直接联系

关系SLC中存在的这些函数依赖就是问题的根本所在，即关系模式中的属性并非完全是由主键确定，有一部分属性只与键的一部分有关。把无直接联系的属性放在一起构成关系模式，必然会产生上述的异常情况。

将SLC改造为以下3个关系模式：

S（Sno，Sname，Sdept，Sno→Sname，Sno→Sdept）

L（Sdept，Loca，Sdept→Loca）

SC（Sno，Cno，Grade，（Sno，Cno）→Grade）

这3个关系模式都不会发生插入异常、更新异常和删除异常的情况，并且数据的冗余也得到了较好的控制。

3、函数依赖的定义

设R(U)是属性集U上的关系模式。X和Y是U的子集。若对于R(U)上的任意一个可能的关系r，如果 r 中不可能存在两个元组，它们在 X 上的属性值相等，而在 Y 上的属性值不等，则称X函数决定Y或 Y 函数依赖于 X，记作X→Y。

其中X 称为这个函数依赖的决定属性组，或称为决定因素，Y 称作被决定因素。

若Y不函数依赖于X，记作X ！→ Y。

若X→Y，且Y→X，则记作X←→Y。

对于函数依赖，有以下几点具体说明：


（1）函数依赖不是指关系模式R的某个或某些关系满足的约束条件，而是指R的所有关系均要满足的约束条件。

（2）函数依赖是语义范畴的概念，只能根据语义来确定一个函数依赖。例如，Sname→Sno这个函数依赖只有在学生不重名的情况下才能成立。如果允许有重名，则Sno就不能函数依赖Sname。

（3）现实中，设计者可以作出强制性的规定以满足需要的函数依赖关系。例如，可以规定不允许同名学生存在，从而保证Sname→Sno成立。

完全函数依赖与部分函数依赖


定义5.3 在关系模式R(U)中，如果X→Y，并且对于X的任何一个真子集X’，都有 X’ ！-> Y, 则称Y完全函数依赖于X，记作X ｆ Y。

若X→Y，但Y不完全函数依赖于X，则称Y部分函数依赖于X，记作X P Y。

例: 在关系SC(Sno, Cno, Grade)中，

由于：Sno！-> Grade，Cno！-> Grade，

因此：(Sno, Cno) ｆ Grade

传递函数依赖


定义5.4 在关系模式R(U)中，如果X→Y，Y→Z，且Y！-> X，Y!→X，则称Z传递函数依赖于X，记作X t Z。

注：如果X→Y，Y→X，则X←→Y，实际上X→Z就是直接函数依赖，而不是传递函数依赖。

例如，在关系模式SLC（Sno，Sname，Sdept，Loca，Cno，Grade）中，（Sno，Cno） f Grade 是完全函数依赖；（Sno，Cno） p Sname是部分函数依赖；由于 Sno→Sdep，Sdept→Loca，所以Sno t Loca是传递依赖依赖。

键

设K是关系模式R<U，F>中的属性或属性组合，若K f U，则K为R的候选键（Cadidate Key）。若候选键多于一个，则选定其中的一个为主键（Primary Key）。

主属性：包含在任何一个候选键中的属性

全键：整个属性组是键

范式

1、范式：为不同程度的规范化设立的不同标准。

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

范式的种类：

第一范式(1NF) 第二范式(2NF)

第三范式(3NF) BC范式(BCNF)

第四范式(4NF) 第五范式(5NF)

“第几范式”是表示关系的某一种级别，所以称某一关系模式R为第几范式 。

2、具体分类

第一范式

·如果关系模式R的所有属性都是不可分的数据项，则称R属于第一范式，记为R∈1NF

。

在关系数据库中，第一范式是对关系模式的最低要求，不满足第一范式的数据库模式不能称为关系数据库。

但是满足第一范式的关系模式并不一定是一个好的关系模式。

关系模式SLC（Sno，Sname，Sdept，Loca，Cno，Grade），由于每个属性不可再分，所以SLC∈1NF。

我们知道，该模式存在着数据冗余、插入异常、更新异常和删除异常。

原因是含有不合适的函数依赖：

（Sno，Cno） f Grade

（Sno，Cno） p Sname, Sno → Sname

（Sno，Cno） p Sdept, Sno → Sdept

（Sno，Cno） p Loca, Sno → Loca

函数依赖中，只有属性Grade对键（Sno，Cno）是完全函数依赖，而其它非主属性对键都是部分函数依赖，导致数据操作中出现了异常问题。

所以需要对关系模式SLC进行投影分解，向高一级范式转化。

第二范式

若关系模式R∈1NF ，并且每一个非主属性都完全函数依赖于R的码，则 R∈2NF

。

关系模式SLC中，Sno、Cno为主属性，Sname、Sdept、Loca、Grade均为非主属性。只有Grade对键是完全函数依赖，其余非主属性对键均为部分函数依赖，所以SLC∈2NF。

解决方法

采用投影分解法，将部分函数依赖从SLC中分离出来，得到以下两个关系模式：

SC（Sno，Cno，Grade）

SL（Sno，Sname，Sdept，Loca）

其中，SC的键为（Sno，Cno），SL的键为Sno。

分解后关系模式SC和LC中的非主属性对键都是完全函数依赖，所以：

SC∈2NF， SL∈2NF。

显然，在SLC模式中存在的一些异常问题在一定程度上得到了解决。

但是，将一个1NF关系分解为多个2NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。

第三范式

关系模式R<U，F> 中若不存在这样的键X、属性组Y及非主属性Z(Z  Y), 使得X→Y，Y→Z，成立，且Y→X，则称R∈3NF。

可以证明：若R∈3NF ，则每一个非主属性既不部分函数依赖于码，也不传递函数依赖于码。

SC(Sno，Cno，Grade，(Sno，Cno)→ Grade)∈3NF

SL(Sno，Sname，Sdept，Loca)不属于3NF

解决方法


采用投影分解法，把SL分解为两个关系模式，以消除传递函数依赖：

S（Sno，Sname，Sdept）∈3NF

L（Sdept，Loca）∈3NF

S的码为Sno， L的码为Sdept。

• 若R∈3NF，则R的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。

• 如果R∈3NF，则R也是2NF。

• 采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数

• 冗余度大、修改复杂等问题。

• 将一个2NF关系分解为多个3NF的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。
  
  

候选关键字，主属性

1、有些实体可以有多个键，所以一般将满足键定义的属性集称为

候选键（Candidate Key）

。当实体集有多个候选键时，通常只选其中的一个，被选定的那个候选键称为

主键（Primary Key）

。

2、候选键Candidate key）

若关系中的某一属性组的值能唯一地标识一个元组，则称该属性组为候选键。

在最简单的情况下，候选键只包含一个属性。在最极端的情况下，关系模式的所有属性的组合是这个关系模式的候选码，称为全键（All-key）

3、主键(Primary key)

若一个关系有多个候选键，则选定其中一个为主键(Primary key)

候选键的诸属性称为

主属性

（Prime attribute）。

不包含在任何候选键中的属性称为

非主属性

（Non-key attribute）

关系模型中三类完整性约束：

1》实体完整性

注意：实体完整性规则规定关系的所有主属性都不能取空值

​ 2》参照完整性

在关系模型中实体及实体间的联系都是用关系来描述的，因此可能存在着关系与关系间的参照（引用）。

外键定义：设F 是关系R 的一个或一组属性，但不是关系R 的键。如果F 与关系S 的主键相对应，则称F是关系R的外键（Foreign Key），并称R 为参照关系，S 为被参照关系或目标关系。

参照完整性规则

规则：若属性（或属性组）F 是关系R 的外键，它与关系S 的主键相对应（关系R 和S不一定是不同的关系），则对于R 中的每个元组在F 上的值

• 要么等于S 中某个元组的主键值

• 要么取空值(F 的每个属性值均为空值)。

​ 3》用户定义的完整性

​ 用户定义的完整性是针对某一具体关系数据库的约束条件，反映某一具体应用所涉及的数据必须满足的语义要求。

​ 关系模型应提供定义和检验这类完整性的机制，以便用统一的系统的方法处理它们，而不要由应用程序承担这一功能。

例如：课程 ( 课程号，课程名，学分)
“课程名”属性必须取唯一值
非主属性“课程名”也不能取空值
“学分”属性只能取值{1，2，3，4}

关系代数运算符

自然连接

1、什么是自然连接

自然连接是一种特殊的等值连接

两个关系中进行比较的分量必须是相同的属性组


在结果中把重复的属性列去掉


自然连接的含义：

若R和S具有相同的属性组B

2、举例

查询优化的一般准则

选择运算应尽可能先做


目的：减小中间关系


在执行连接操作前对关系适当进行预处理


按连接属性排序

在连接属性上建立索引


投影运算和选择运算同时做


目的：避免重复扫描关系


将投影运算与其前或其后的双目运算结合


目的：减少扫描关系的遍数