关系模式可能存在的问题

  1. 数据冗余 Data Redundancy

存储一些列的重复出现的数据，通常出于效率和语义方面的考虑；但是，浪费存储空间，比如每一个系的系主任姓名重复出现，重复次数甚至与该系所有学生的所有课程成绩出现次数相同。同时，冗余控制不当可能会导致更新异常。

  1. 更新异常 Update Anomaly

数据冗余，更新数据时，维护数据完整性代价大。

  • 插入异常（Insertion Anomaly）
    例子：考虑一个存储学生课程信息的数据库表，其中学生信息和课程信息分别存储在两个表中，通过学生ID关联。如果某个学生还未选修课程，那么在学生表中就没有与该学生相关的记录。
    分析：在这种情况下，插入新学生记录时，如果不同时插入相关的课程信息，就会导致数据不完整。为了避免这种异常，通常需要使用外键或联接来确保插入学生记录时，同时也插入相关的课程信息。

  • 删除异常（Deletion Anomaly）
    例子：考虑一个存储图书信息的数据库表，其中每本书的作者信息也存储在同一表中。如果一本书的作者决定不再写书，那么删除该作者的所有书籍记录可能导致书籍信息的丢失。
    分析：删除异常会导致数据丢失和完整性问题。为避免这种异常，可以将作者信息存储在单独的作者表中，然后使用外键关联两个表，这样在删除作者记录时，书籍记录不会受到影响。

  • 修改异常（Update Anomaly）
    例子：考虑一个存储订单信息的数据库表，其中包括订单号、产品名称和订单总额。如果某个订单中的产品名称发生更改，那么需要在数据库中更新所有相关的订单记录，否则订单信息将不一致。
    分析：修改异常可能导致数据不一致和错误。为避免这种异常，可以将产品信息存储在单独的产品表中，然后在订单表中使用产品ID与产品表关联，而不是直接存储产品名称。这样，在产品名称更改时，只需更新产品表中的记录，而订单表中的记录将保持一致。

函数依赖

设R(U)是属性集合U={A1,A2,...,An}U=\{A1,A2,...,An\}上的一个关系模式，XX，YY是UU上的两个子集，若对R(U)R(U)的任何一个可能的关系rr，rr中不存在有两个元组满足在XX中的属性值相等而在YY中的属性值不等，则称“XX函数决定YY”或者“YY函数依赖于XX”，记作X→YX \rightarrow Y。

特性

  • 对于X→YX \rightarrow Y，但Y⊈XY \not \subseteq X，也就是YY有不同于XX的属性，则称X→YX \rightarrow Y为非平凡的函数依赖nontrivial FD。

  • 反之如果Y⊆XY \subseteq X，比如{X,Y}→X\{X,Y\} \rightarrow X、X→XX \rightarrow X，则称为平凡的函数依赖trivial FD。

  • 若X→YX \rightarrow Y，则任意两个元组，若XX上值相等，则YY上值必然相等，称XX为决定因素。

  • 若X→YX \rightarrow Y，Y→XY \rightarrow X，则记作X↔YX \leftrightarrow Y。

  • X→YX \rightarrow Y，基于模式RR的，则要求对任意的关系rr成立；有基于具体关系rr的，则要求对某一关系rr成立。

  • 如果一个关系rr的某属性集XX，rr中根本没有XX上相等的两个元组存在，则X→YX \rightarrow Y恒成立。

  • 若YY不函数依赖于XX，则记作X↛YX \not \rightarrow Y

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

在R(U)R(U)中，若X→YX \rightarrow Y并且对于XX的任何真子集X′X'都有X′↛YX' \not \rightarrow Y，则称YY完全函数依赖于XX，记为X→FYX \stackrel{F} \rightarrow Y，否则称YY部分函数依赖于XX，记为X→PYX \stackrel{P} \rightarrow Y。

部分函数依赖存在着非受控冗余，需要消除。比如说学号和课号决定姓名，然而有学号即可决定姓名，所以这是部分函数依赖。

传递函数依赖

在R(U)R(U)中，若X→YX \rightarrow Y，Y→ZY \rightarrow Z，且Y⊈XY \not \subseteq X，Z⊈YZ \not \subseteq Y，Z⊈XZ \not \subseteq X，Y↛XY \not \rightarrow X，则称ZZ传递依赖于XX，记为X→TYX \stackrel{T} \rightarrow Y。

比如，U={学号,姓名,年龄,班号,班长,课号,成绩}U=\{学号,姓名,年龄,班号,班长,课号,成绩\}，学号决定班号，班号决定班长，所以学号决定班长是传递函数依赖，这里可见，两段都是非平凡的函数依赖。

传递函数依赖存在着非受控冗余，需要消除。

主属性和非主属性

基于候选键的定义，回顾之前提到的候选键，使用函数依赖的理论来解释就是，设KK为R(U)R(U)中的属性或属性组和，若K→FUK \stackrel{F} \rightarrow U，则称KK为R(U)R(U)上的候选键CK。

特性

  • 可任选一候选键作为R的主键PK。

  • 因为候选键可以有多个，所以任意候选键中的属性称为主属性Prime Attribute，其他属性成为非主属性。

举例说明

比如对于属性集合学生(学号，年龄，家庭住址，课程号，成绩，教师，教师职务):

学号和课程号能够决定集合中的所有属性，所以学号和课程号可以构成候选键，剩余属性为非主属性。

再比如，属性集合商店(商店，商品，商品经营部，商品经营部经理):

商店和商品可以决定商品经营部，商店和商品经营部可以决定商品经营部经理，

逻辑蕴含和闭包

设F是关系R(U)R(U)中的一个函数依赖集合，XX,YY是RR的属性子集，如果能从FF这个函数依赖集合中推导出X→YX \rightarrow Y，则称FF逻辑蕴含X→YX \rightarrow Y，记作F⊨X→YF \models {X \rightarrow Y}。FF可能逻辑蕴含了不止一个函数依赖。

被FF逻辑蕴含的所有函数依赖集合称为FF的闭包，记作F+F^{+}，换言之，能从函数依赖集合FF中推导出的所有函数依赖组成的集合，称为FF的闭包。

如何得到一组函数依赖关系的所有闭包F+F^{+}？

初始化F+F^{+}为与FF相同的函数依赖集合；
重复以下步骤，直到F+F^{+}不再发生改变:

  • 对于F+F^{+}的每个函数依赖，使用自反律，增广律
  • 将生成的新函数依赖添加到F+F^{+}中
  • 对于F+F^{+}中的每一对函数依赖，检查他们是否可以使用传递律进行组合
  • 如果可以组合，将生成的新功能添加到F+F^{+}中

举例说明

The Procedure for Computing F+F^{+}

F={X→Y,Y→Z}F=\{X \rightarrow Y, Y \rightarrow Z\}

F+={XY→X,XY→Y,XY→Z,XZ→X,XZ→Y,XZ→Z...}F^{+}=\{XY \rightarrow X, XY \rightarrow Y, XY \rightarrow Z, XZ \rightarrow X, XZ \rightarrow Y, XZ \rightarrow Z...\}

Armstrong公理

设FF为R(U)R(U)的一组函数依赖，记为R(U,F)R(U,F)。

自反律 Reflexivity

若属性集Y⊆XY \subseteq X，X⊆UX \subseteq U，则X→YX \rightarrow Y被FF逻辑蕴含，假设有一属性集合XX，表示一个人的姓名和年龄，即X={姓名,年龄}X=\{姓名,年龄\}，可以推出由XX推导出姓名或者年龄或者两者共同构成的集合即XX本身。

增广律 Augmentation

若X→Y∈FX \rightarrow Y {\in} F，且Z⊆UZ \subseteq U，则XZ→YZXZ \rightarrow YZ被FF逻辑蕴含，换言之，如果X→YX \rightarrow Y在FF这个函数依赖集合中，另一属性（组）ZZ是属性集UU中的元素，那么从FF中可以推导出XZXZ函数决定YZYZ。

传递律 Transitivity

若X→Y∈FX \rightarrow Y {\in} F，且Y→ZY \rightarrow Z，则X→ZX \rightarrow Z被FF逻辑蕴含。

以上，XX,YY,ZZ均为非空属性集合。

举例说明

R=(A,B,C,G,H,I)F={A→B,A→C,CG→H,CG→I,B→H}R=(A,B,C,G,H,I) \\ F=\{A \rightarrow B, A \rightarrow C, CG \rightarrow H, CG \rightarrow I, B \rightarrow H\}

可以推出比如:

根据传递律，A→HA \rightarrow H。

根据增广律，CG→HCG \rightarrow H，CG→ICG \rightarrow I。

根据增广律以及传递律

CG→CGICGI→HICG→HICG \rightarrow CGI \\ CGI \rightarrow HI \\ CG \rightarrow HI

Armstrong引理

合并律 Additivity

若X→YX \rightarrow Y，且X→ZX \rightarrow Z，则X→YZX \rightarrow YZ，因为根据增广律可得X→XYX \rightarrow XY，XY→YZXY \rightarrow YZ，再有传递律可得结果。

分解律 Projectivity

即合并律的逆过程，现在要你证明分解律{X→YZ}⊨X→Y\{X \rightarrow YZ\} \models {X \rightarrow Y}，首先，根据条件可知X→YZX \rightarrow YZ，根据自反律得到YZ→YYZ \rightarrow Y或者YZ→ZYZ \rightarrow Z，再根据传递性可得出结果。

伪传递律 Pseudo-transitivity

若X→YX \rightarrow Y，且若WY→ZWY \rightarrow Z，则若XW→ZXW \rightarrow Z，通俗来讲就是构造函数依赖之间的传递性。

举例说明

R=(A,B,C,D)F={A→B,A→C,BC→D}Please prove A→DR=(A,B,C,D) \\ F=\{A \rightarrow B, A \rightarrow C, BC \rightarrow D\} \\ \text{Please prove } A \rightarrow D

根据增广律，AC→BCAC \rightarrow BC，根据传递律和BC→DBC \rightarrow D，AC→DAC \rightarrow D，由A→CA \rightarrow C，根据增广律，得到A→ACA \rightarrow AC，再根据传递律得到A→DA \rightarrow D。

属性集的闭包

使用递归，终止条件，前后两次闭包内结果一致，则返回，通过求属性闭包，我们能找到CK，同时通过属性集闭包的运算，我们可以判断某一个函数依赖是否遵循一组属性依赖集。规范一下写法，如果有R=ABCDEFR=ABCDEF，Z={AB→C,BC→AD,D→E,CF→B}Z=\{AB \rightarrow C, BC \rightarrow AD, D \rightarrow E, CF \rightarrow B \}，请问，AB→DAB \rightarrow D是否遵循ZZ函数依赖集合。

AB+=ABinitiallyAB+=ABCusingAB→CAB+=ABCDusingBC→ADAB+=ABCDEusingD→E{AB}^{+}=AB \hspace{1em} initially \\ {AB}^{+}=ABC \hspace{1em} using\hspace{0.01em}AB \rightarrow C \\ {AB}^{+}=ABCD \hspace{1em} using\hspace{0.01em} BC \rightarrow AD \\ {AB}^{+}=ABCDE \hspace{1em} using\hspace{0.01em} D \rightarrow E

可见，上述如果R中不含有F，那么AB的属性集闭包能够推出所有属性集。

候选键的计算

找出超键，然而删元素，比如对于ABCD组成的R, A->B, BC->D, A->C

先通过左侧得出ABC->ABCD，然后在ABC的基础上删元素，删除A，BC的闭包只能推出BCD；删除C，AB的闭包可以推出ABCD，保留；删除B，AC的闭包可以推出ABCD，保留；在此基础上再删，AC删除C，A的闭包也能推出ABCD…

要小心互相指向的情况，因为这样可能会有可能不止一个候选键。

下面有几个辅助判别的技巧，函数依赖中的元素可以被分为四种情况：

  • 只出现在左侧的属性，一定是CK的一部分，因为如果不提供，则无法被函数决定

  • 只在右侧出现的属性，一定不是CK的一部分，因为一定可以被CK函数决定

  • 既出现在左侧，又出现在右侧，可能是也可能不是，老老实实根据删除的顺序判断

  • 两侧都没有出现，一定是CK的一部分

例题及模板

R=ABCDER=ABCDE, FD={A→B,BC→A,D→E}FD=\{A \rightarrow B, BC \rightarrow A, D \rightarrow E\}, find all the CK of relation R

Step 11:
Let X:={A,B,C,D}X:=\{A,B,C,D\}

Step 22:
Try to remove AA
{B,C,D}+={A,B,C,D,E}\{B,C,D\}^{+}=\{A,B,C,D,E\}
Thus X:{B,C,D}X:\{B,C,D\}

Step 3,4,53,4,5:
Attempt to remove B,C,DB,C,D separately
{C,D}+={C,D,E}\{C,D\}^{+}=\{C,D,E\}
{B,D}+={B,D,E}\{B,D\}^{+}=\{B,D,E\}
{B,C}+={A,B,C}\{B,C\}^{+}=\{A,B,C\}
None can be removed
So {B,C,D}\{B,C,D\} is a candidate key and add to TT

Step 66:
To find another super key, let X:={A,C,D}X:=\{A,C,D\}

Step 7,8,97,8,9:
Attempt to remove A,C,DA,C,D separately
{C,D}+={C,D,E}\{C,D\}^{+}=\{C,D,E\}
{A,D}+={A,B,D,E}\{A,D\}^{+}=\{A,B,D,E\}
{A,C}+={A,B,C}\{A,C\}^{+}=\{A,B,C\}
None can be removed
So {A,C,D}\{A,C,D\} is a another candidate key and add to TT

All the CK of relation RR are {A,C,D}\{A,C,D\} and {B,C,D}\{B,C,D\}.

超键的计算

以上面找候选键的例子为例，计算超键的个数，有两种方法，枚举和组合计算

根据候选键{A,C,D}\{A,C,D\}和 {B,C,D}\{B,C,D\}，R={A,B,C,D,E}R=\{A,B,C,D,E\}，候选键{A,C,D}\{A,C,D\}剩余BEBE，候选键{B,C,D}\{B,C,D\}剩余AEAE

从BEBE和AEAE中选，可得(C20+C21+C22)∗2=8(C20+C21+C22)*2=8，再减去一个重复组成部分ABCDABCD和ABCDEABCDE，最终有6个超键。

总结

五类问题

  • 判断一个relation的FD
  • 求closure
  • 求CK
  • 求SK的个数
  • 求某个FD是否蕴含在F中

快来参与讨论吧~