跳转至

规范化

冗余1

数据冗余指的是在数据库中存在重复存储相同信息的情况. 这可能是因为设计不当, 数据合并或者操作错误等原因造成的. 虽然在某些情况下数据冗余可能有正面作用, 比如数据备份和恢复. 但是大部分时候, 它会造成存储空间浪费, 增加数据管理的复杂性, 并可能引发数据一致性问题.

影响1

数据冗余最直接的影响就是浪费存储空间. 在一个包含冗余数据的系统中, 相同的信息会被多次存储. 这种冗余占用了大量的存储空间, 尤其对于大规模数据集来说, 这种空间浪费是显著的.

其次, 在有冗余数据的系统中, 保持数据的一致性是一个重要的挑战. 如果不同的副本之间没有正确地同步, 那么就可能产生不一致的数据, 从而影响到依赖这些数据的决策和操作.

最后, 冗余数据会使数据管理变得复杂, 为了保持数据的一致性, 当某个数据项需要更新的时候, 所有包含则个数据项的地方都需要更新, 这增加了数据维护的工作量和出错的可能性.

异常

以学生选课表为例, 数据冗余可能会导致三种异常:

  • 更新异常: 如果该门课程的房间号发生了变化, 例如从"R101"改为"R203", 那么所有与此房间关联的记录都要进行更新, 如果遗漏了某条记录, 会导致数据不一致的情况, 即更新异常
  • 删除异常: 如果所有的学生都退选了这个课程, 那么该课程的房间信息就会被删除, 因为它是和学生记录一起存储的, 这样就会导致丢失该课程的房间信息, 即删除异常
  • 插入异常: 如果我们想为某个课程预定一个房间, 但是还没有任何学生选修这个课程, 我们无法单独存储房间信息, 因为房间信息依赖于学生-课程关联, 即插入异常

好坏数据库设计

坏的数据库设计常常:

  • 还有冗余(浪费磁盘空间)
  • 导致更新, 删除, 插入异常

好的数据库设计常常:

  • 最小的冗余
  • 没有更新, 删除, 插入异常

解决方法

规范化设计过程以避免异常. 规范化, Normalization是定义什么是好的关系型设计的过程. 其主要目的是解决数据库中的更新, 插入, 删除等操作时可能出现的异常, 避免不好的设计, 改善数据库的结构. 在了解规范化之前需要了解函数依赖, 因为它是规范化的核心工具.

函数依赖

函数依赖, Functional Dependencies, 用来捕捉属性之间的语义关系, 检测消除不良设计, 识别冗余数据. 其非正式的定义为属性X的值决定了属性Y的值. 例如每一门课都只会在一个教室上, COMP9120只会在R101房间上, 这里课程决定了房间号. 其正式的定义为: 假设X和Y是两组属性, X和Y之间的关系可以用一个函数来表示, 它的本质是, X的一个值不能映射到多个Y的值, 这意味着X和Y之间的关系是n对1或1对1的关系. 如UoS->Room.

确定函数依赖

那么, 我们如何确定该函数依赖呢? 或者说, 如何发现函数依赖呢?

主要通过两种方式:

  • 考虑属性的语义
  • 分析表中的实际数据

在大多数情况下, 我们使用语义来判断函数依赖. 当使用数据来确定函数依赖的过程又被称为知识挖掘, knowledge mining. 如图. 从数据可以大致判断, 分行的名称和城市之间有一个函数依赖, 贷款编号和客户名称/数量之间有一个函数依赖, 贷款编号和分行名称之间有一个函数依赖, 城市和资产之间有一个函数依赖, 但是, 这样确定依赖不是特别靠谱, 请见下方注意.

注意

我们可以通过查看表中的某个实例, 来判断函数依赖不成立. 但是, 我们无法通过观察任何数量的实例, 推断出某个函数依赖成立. 这是因为函数依赖是关于所有可能的合法实例的声明, 不仅仅基于当前看到的某些实例. 因此, 仅凭部分数据或者实例, 无法确定函数依赖在所有情况下都成立, 需要更加广泛的验证.

Armstrong公理

Armstrong公理是函数依赖推理规则的基础, 它主要包含三个公理.

  • 自反性: reflexivity, 如果B ⊆ A, A → B; 当右侧的属性出现在左侧, 那么称之为一个平凡函数依赖; 例如cpoints, uos_name → uos_name, 因为uos_name已经出现在左侧
  • 增广性: augentation, 如果A → B, 那么对于任何属性集C, AC → BC; 例如cpoints → wload推导出cpoints, uos_name → wload, uos_name, 即在两侧同时增加uos_name
  • 传递性: transitivity, 如果A → B且B → C, 那么A → C; 例如uos_code → cpoints和cpoints → wload推导出uos_code → wload
例子

给定下列表:

Name Color Category Dept Price
Gizmo Green Gadget Toys 49
Widget Black Gadget Toys 59
Gizmo Green Whatsit Garden 99

已知的函数依赖:

  • Name → Color
  • Category → Dept
  • Color, Category → Price

根据给出的函数依赖, 我们推断Name, Category → Price对于所有的实例都成立, 现在利用Armstrong公理证明.

  1. 根据增广性, 有Name, Category → Color, Category
  2. 根据传递性, Color, Category → Price, 所以Name, Category → Price

函数依赖闭包

能从函数依赖集F中推导出的所有函数依赖组成的集合, 成为F的闭包. 计算闭包方法如下:

  1. 初始化: 设定初始闭包F+=F, 也就是闭包开始的时候等于原始的函数依赖集F
  2. 循环迭代:
    1. 对于闭包F+中的每个函数依赖FD, 应用自反性和增广性规则, 推导出新的函数依赖, 将新推导出的函数依赖加入到F+中
    2. 对于闭包F+中的每一对函数依赖F1和F2, 如果F1和F2可以通过传递性规则组合成新的函数依赖, 将结果加入到F+中
  3. 停止条件: 当闭包F+不再发生变化的时候, 算法终止

在最坏情况下, 函数闭包会随着F中属性数量的增加而呈现指数级增长, 这意味着计算F+在某些情况下可能会非常耗时, 下面是一个简单的例子.

例子

假设我们在关系R中有三个属性A, B, C. 已知的函数依赖集F为F={A → B, B → C}. 可以计算出F+如图所示.

Armstrong公理具有:

  • 健全性: 当将其应用于函数依赖集F的时候, 只会生成在F+中的有效函数依赖
  • 完备性: 通过反复应用公理, 可以生成闭包F+中的所有函数依赖

基于Armstrong公理还能导出一些附加规则.

  • 分解: decomposition, 如果A → BC, 那么可以推导出A → B和A → C
  • 联合: union, 如果A → B且A → C, 则可以推导出A → BC

超键和候选键

超键是一个能够唯一识别关系中的每个元组的属性的集合. 如果K是关系R的超键, 那么K → R, 即K决定了R中的所有的属性. 候选键是超键(或者直接叫做键)是属性最少的超键, 即候选键的子集不是候选键, 可能有很多的候选键, 但是其中只能有一个是主键.

属性闭包

给定一个函数依赖集F和一个属性集X, 属性集X+(称为X的闭包)是所有由X在F下确定的属性的集合, 记作X → X+. 属性集合能够用于检查某个属性集是否是关系的键:

  • 如果一个属性集的闭包是整个关系的所有属性集合, 那么这个属性集就是超键
  • 如果一个超键是最小的, 即它的任何真子集都不是超键, 那么这个超键就是候选键

算法:

  1. 初始化: 将初始结果result设置为给定的属性集X={A1, A2, ..., An}
  2. 迭代查找依赖项: 不断地查找形如A1A2...Am → C的函数依赖, 其中A1, A2, ..., Am已经包含在result中, 但是C不包含在result中
  3. 更新闭包结果: 将C加入到result中
  4. 重复步骤2, 直到没有更多的属性能够加入到result
  5. 集合result就是X+
例子

找到下列关系中的候选键:

PhD(sid, first, last, dept, advisor, award, description)

已知下列函数依赖:

  • sid → first, last
  • advisor → dept
  • description → award
  • sid, dept → advisor, description

设X=(sid, dept)我们来看一下X是不是候选键.

不断地迭代查找依赖项: (sid, dept)+ =

  1. ---> sid, dept
  2. ---> sid, dept, first, last
  3. ---> sid, dept, first, last, advisor, description
  4. ---> sid, dept, first, last, advisor, description, award

由于(sid, dept)+中的属性是关系的所有属性的集合, 所以它是一个超键. 那么它是一个候选键吗?

  • (sid)+ ---> sid, first, last, 不是一个超键
  • (dept)+ ---> dept, 不是一个超键

所以(sid, dept)是一个候选键.

类型2

平凡/非平凡函数依赖

  • 平凡函数依赖: 当关系中属性集合Y是属性集合X的子集的时候, 即Y ⊆ X, 存在函数依赖X → Y, 即一组属性函数决定了它的所有子集
  • 非平凡函数依赖: 当关系中属性集合Y不是属性集合X的子集的时候, 存在函数依赖X → Y

完全/部分函数依赖

  • 完全函数依赖: 设X, Y是关系R的两个属性集合, X'是X的真子集, 存在X → Y, 但对于每一个X', 都有X' !→ Y
  • 部分函数依赖: 设X, Y是关系R的两个属性集合, 存在X → Y, 若X'是X的真子集, 存在X' → Y, 如图

传递函数依赖

设X, Y, Z是关系R中互不相同的属性集合, 存在X → Y(Y !→ X), Y → Z, 则称Z传递函数依赖于X.

非主属性/主属性

  • 非主属性: non-prime attribute, 是关系数据库中的一种属性, 它不属于候选键的一部分
  • 主属性: prime attribute, 属于候选键的一部分

范式

范式, normal form是关系型数据库设计中的一种结构化标准, 用于组织数据以减少冗余, 提高数据一致性和查询效率. 范式的目的是通过满足一系列规则和限制, 确保数据库设计的合理性, 并避免数据冗余和数据异常.

第一范式

第一范式, 1NF, 要求数据表中的每个字段都必须是不可再分的原子值. 其目的是确保数据的基本结构化, 使表中单元格只能存储一个数据项.

例子

如假设一个学生表中有一列"联系方式", 其中既存储了学生的手机号码, 也存储了电子邮件地址, 这不符合第一范式. 要符合第一范式, 应该将手机号和电子邮件分成两个独立的字段, 如图.

第二范式

第二范式, 2NF, 是在1NF的基础上, 没有部分依赖, 要求非主属性完全依赖于主键.

例子

例如假设有一个成绩表有三个字段(学生ID, 课程) → 成绩, 并且还有学生姓名字段, 因为学生姓名只依赖于学生ID, 而与课程无关, 所以它违反了2NF. 解决的方法是将学生信息分离到另一个表中.

假设有表, 这样就会造成重复, 这个老师所教的所有的UoS中, Teacher_position这个信息都会被重复. 解决的方法是将拆分为两个关系, 然后检查拆分后的关系是否符合2NF. 可以拆为R1(Teacher_name, Teacher_position)和R2(Teacher_name, UnitOfStudy).

第三范式

第三范式, 3NF, 是在2NF的基础上, 非主属性不能依赖于其他非主属性. 换句话说, 就是所有的非主属性必须直接依赖于主键, 而不是通过其他非主属性间接依赖主键, 消除了传递依赖.

例子

如果存在学生ID → 院系, 而院系 → 院长, 这意味着学生ID间接决定了院长, 这就是传递依赖. 要达到3NF, 需要将院系和院长的信息分离成独立的表.

如图. 需要将其拆分为R1(Employee, Department), R2(Department, Location).

Boyce-Codd范式

Boyce-Codd范式, BCNF, 是3NF的增强版. 一个关系R满足BCNF当且仅当所有的非平凡函数依赖中的左侧必须是R的超键. 换句话说, 表中所有的属性必须完全依赖于超键. 更加正式地说, 对于所有的非平凡依赖X → Y, X必须是R的超键, 如图所示.

例子

假设有表, 其中Address → Teacher_name违反了BCNF. 需要分开为两个表R1(Address, Teacher_name), R2(Address, UnitofStudy).

Tip

由于BCNF是基于3NF的, 所以任何违反1NF, 2NF, 3NF的都是违反BCNF的.

第四范式

多值依赖

在第一范式中, 我们提到了每个字段都必须是不可分割的原子值, 现在来考虑一下以下的情况.

例子
名字 专业 语言
John Electron, Plumber French, Korean
Mary Doctor, Author Spanish, Chinese

根据1NF, 上述是不被允许的, 所以, 我们尝试改为:

名字 专业 语言
John Electron French
John Plumber Korean
Mary Doctor Spanish
Mary Author Chinese

这显然在语义上是不正确的. John和Mary各自都会说两门语言, 不管它们的专业是什么. 我们尝试修复这个问题:

名字 专业 语言
John Electron French
John Electron Korean
John Plumber French
John Plumber Korean
Mary Doctor Spanish
Mary Doctor Chinese
Mary Author Spanish
Mary Author Chinese

多值依赖MVD的非正式定义为, X和Y之间存在多值依赖, 如果无法从X和Z之间的关系推出X和Y之间的关系. 在我们的例子中, John有多个专业和多个语言, 但是X名字和Y专业之间的依赖和X名字和Z语言之间的依赖没有关系, 是独立的. 也就是说, John的名字决定了它的专业, 同时也决定了它的语言, 但是专业和语言之间是彼此独立的.

例子

假设我们有一组元组, t1, t2, t3, t4.

  • t1: John - Electron - French
  • t2: John - Plumber - Korean
  • t3: John - Electron - Korean

  • t4: John - Plumber - French

  • 第一步, 所有的元组在X的值上都相等, 即名字都是John, 对于t1, t2, t3, t4, 都满足

  • 第二步, 我们可以看到t3和t1在Y上的值相等, t4和t2在Y上的值相等
  • 第三步, 我们可以看到t3和t2在Z上的值相等, t4和t1在Z上的值相等

所以, 有:

  • 名字 ↠ 专业
  • 名字 ↠ 语言

但是, 这样会引发极大的冗余问题, 解决方法见下.

第四范式, 4NF, 用于处理由于多值依赖, MVD导致的数据冗余问题.

在上面的例子中, 对于每个人来说, 如果它们有多个专业和会多种语言, 那么需要列出这个人会的每种语言对于每一个专业的组合, 这种重复信息会导致冗余.

一个表要符合4NF, 至少需要满足以下一个条件:

  • X ↠ Y是平凡多值依赖, 即Y ⊆ X或X ∪ Y = R
  • X是R的一个超键
例子

在这个表格中:

名字 专业 语言
John Electron French
John Electron Korean
John Plumber French
John Plumber Korean
Mary Doctor Spanish
Mary Doctor Chinese
Mary Author Spanish
Mary Author Chinese

名字 ↠ 专业, 名字 ↠ 语言都是非平凡的多值依赖. 并且, 名字这个属性不是超键, 所以它不符合4NF的条件. 解决方法是将表格一分为二, R1(名字, 专业), R2(名字, 语言).

这个表格是否符合4NF?

答案是不符合, 因为employee_name不是一个超键, 而且employee_name ↠ project_id是非平凡的多值依赖. 解决方法是将上述表一分为二. R1(employee_name, project_id), R2(employee_name, personal_phone_number).

分解

分解用于解决冗余和异常. 将R分解为两个不同的关系, 每个新的关系包含R中的属性的子集, R中的每个属性至少出现在一个新的关系中, 有许多可能的分解方案, 但是并非所有的方案都同样有效或正确. 需要强调的是, 在分解的过程中, 不能丢失函数依赖; 并且, 在分解后的关系重新连接(自然连接)的时候, 应该能还原原始的关系模式R, 下面, 我们就从这两方面展开讲解.

检查函数依赖

例子

假设我们有关系R, 有三个属性A, B, C. 函数依赖为F={A → B, B → C, A → C}, 主键为A. 这个关系不是3NF, 因为有一个传递函数依赖B → C. 所以我们将其分为R1=(B, C), R2=(A, B), 这两个关系是3NF, 但是, 分解后的关系保持了原先的函数依赖吗?

定义F'为分解后的关系的函数依赖的union, F1是R1的函数依赖, F2是R2的函数依赖. F′ = F1 ​∪ F2. 然后, 我们要检查F'+ = (F1 ​∪ F2)+, 即分解后的属性闭包是否和原始的属性闭包相等. 由于分解后的属性闭包{A → B, B → C, A → C}, 和原始属性闭包相等, 所以没有丢失函数依赖.

检查无损连接

无损连接指的是当我们将一个关系分解为多个子关系后, 通过自然连接重新组合这些子关系的时候, 不会丢失任何信息, 能够恢复出原始的关系. 如图.

对于两个关系R1, R2, 它们具有无损连接的条件是: (R1 ​∩ R2​) → R1​或(R1 ​∩ R2​) → R2.

例子

假设我们两个关系R1, R2. R1(A, B), R2(B, C). 由于R1 ​∩ R2​ = {B}, 而B是R2(B, C)的候选键, 因此满足无损连接的条件, 当通过自然连接R1, R2的时候, 能够恢复原始R(A, B, C)的关系.

分解BCNF

例子

假设我们有一个关系R和一个非平凡依赖X → Y, 其中X不是超键, 这违反了BCNF. 我们需要将其分解为两个关系.

我们需要R分解为两个子关系, R1 = X ∪ Y; R2 = R - Y.

假设有一个关系login_info = (customer_id, loan_number, amount). 有一个非平凡依赖loan_bumber → amount, 由于loan_number不是超键的一部分, 所以不符合BCNF. 我们将其分解为R1 = (loan_number, amount); R2 = (customer_id, loan_number), 现在, 两个都符合BCNF.

  1. 数据冗余（data redundant）现象介绍-CSDN博客. (n.d.). Retrieved September 26, 2024, from https://blog.csdn.net/Dontla/article/details/134932405 ↩↩

  2. levon. (2019, December 10). 数据库范式和函数依赖. Levon’s Blog. https://www.liuvv.com/p/2e33702e.html ↩

评论