当前位置: 首页 > news >正文

《软件设计师》复习笔记(4.2)——关系代数、函数依赖、范式

目录

一、关系代数

基本运算

笛卡尔积(×)

投影(π)

选择(σ)

自然连接(⋈)

真题示例:

二、函数依赖

基本概念

Armstrong公理系统

键与约束

三、范式(Normalization)

第一范式(1NF)

第二范式(2NF)

第三范式(3NF)

BC范式(BCNF)

真题示例:


一、关系代数

  1. 基本运算

    • 并(∪):合并两张表的所有记录,重复记录仅显示一次。
      • 示例:S1 ∪ S2 结果包含 S1 和 S2 的所有不重复记录。
    • 交(∩):返回两张表中相同的记录。
      • 示例:S1 ∩ S2 结果为 Sno='No0001', Sname='Mary', Sdept='IS'
    • 差(-):返回第一张表有而第二张表没有的记录。
      • 示例:S1 - S2 结果为 Sno='No0003' 和 No0004 的记录。
  2. 笛卡尔积(×)

    • 结果包含两表所有属性列,记录数为两表记录数的乘积。
    • 示例:S1 × S2 的每条记录是 S1 和 S2 记录的排列组合。
  3. 投影(π)

    • 选择某表的特定列(可用列名或列序号表示)。
    • 示例:π(Sname)(S1) 返回 S1 的所有学生姓名。
  4. 选择(σ)

    • 按条件筛选表中的记录。
    • 示例:σ(Sdept='IS')(S1) 返回 Sdept 为 IS 的记录。
  5. 自然连接(⋈)

    • 合并两表中属性相同且值相同的记录,相同属性列仅显示一次。

真题示例:

给定关系R(A, B, C, D)和关系S(C, D, E),对其进行自然连接运算R⋈S后的属性列为( )个;与σR.B>S.E(R⋈S)等价的关系代数表达式为( )。

A. 4 B. 5 C. 6 D. 7

A. σ₂>₇(R×S) B. π₁,₂,₃,₄,₇(σ'₂' > '₇' ∧₃=₅∧₄=₆(R×S))

C. σ'₂' > '₇'(R×S) D. π₁,₂,₃,₄,₇(σ₂>₇∧₃=₅∧₄=₆(R×S))

1. 计算自然连接运算 R⋈S​ 后的属性列个数

自然连接是一种特殊的等值连接,它要求两个关系中进行比较的分量必须是相同的属性组,并且在结果中把重复的属性列去掉。 关系 R(A,B,C,D)​ 有 4​ 个属性,关系 S(C,D,E)​ 有 3​ 个属性,其中 C​ 和 D​ 是公共属性。 进行自然连接时,重复的公共属性 C​ 和 D​ 只保留一次,所以 R⋈S​ 后的属性列为 A​、B​、C​、D​、E​,共 5​ 个。 

2. 找出与 σR.B>S.E​(R⋈S)​ 等价的关系代数表达式

​σR.B>S.E​(R⋈S)​ 表示先对 R​ 和 S​ 进行自然连接,然后从连接结果中选择满足 R​ 中的属性 B​ 大于 S​ 中的属性 E​ 的元组。 在进行关系代数运算时,一般先将自然连接转换为笛卡尔积和选择、投影运算。

  • 首先将 R⋈S​ 转换为笛卡尔积 R×S​ 并添加等值连接条件,即 σR.C=S.C∧R.D=S.D​(R×S)​ 。
  • 然后要从结果中选择满足 R.B>S.E​ 的元组,完整的选择条件就是 σR.B>S.E∧R.C=S.C∧R.D=S.D​(R×S)​ 。
  • 用属性的序号表示,R×S​ 后的属性顺序为 R.A​(第 1​ 列)、R.B​(第 2​ 列)、R.C​(第 3​ 列)、R.D​(第 4​ 列)、S.C​(第 5​ 列)、S.D​(第 6​ 列)、S.E​(第 7​ 列),那么选择条件可写为 σ2>7∧3=5∧4=6​(R×S)​ 。
  • 最后,由于最终结果不需要重复的 C​ 和 D​ 列(在自然连接中重复列已被去掉),所以需要对结果进行投影,保留 A​、B​、C​、D​、E​ 对应的列,即 π1,2,3,4,7​(σ2>7∧3=5∧4=6​(R×S))​ 。


二、函数依赖

  1. 基本概念

    • 函数依赖:若属性 X 能唯一确定 Y,则称 Y 依赖于 X(记作 X→Y)。
    • 部分函数依赖:若 (A,B)→C,但 A→C 也成立,则 C 部分依赖于 (A,B)
    • 传递函数依赖:若 A→BB→C 且 A 与 B 不等价,则 A→C 是传递依赖。
  2. Armstrong公理系统

    函数依赖的公理系统(Armstrong) 设关系模式R<U,F>,U是关系模式R的属性全集,F是关系模式R的一个函数依赖集。对于R<U,F>来说有以下的:

    • 自反律(Reflexivity)

      • 若属性集Y是属性集X的子集(Y⊆X),则必然存在函数依赖X→Y。
      • 示例:若X={A,B,C},Y={A,B},则X→Y自动成立。
    • 增广律(Augmentation)

      • 若存在X→Y,则对任意属性集Z,有XZ→YZ。
    • 传递律(Transitivity)

      • 若X→Y且Y→Z,则必然有X→Z。
    • 合并规则(Union)

      • 若X→Y且X→Z,则可合并为X→YZ。
    • 伪传递规则(Pseudo-transitivity)

      • 若X→Y且WY→Z,则XW→Z。
      • 示例:若学号→姓名,(姓名,课程)→成绩,则(学号,课程)→成绩。
    • 分解规则(Decomposition)

      • 若X→Y且Z⊆Y,则X→Z。
      • 示例:若A→{B,C},则A→B和A→C均成立。
  3. 键与约束

    • 超键:能唯一标识此表的属性的组合。
    • 候选键:超键中去掉冗余的属性,剩余的属性就是候选键。
    • 主键:任选一个候选键,即可作为主键。
    • 外键:其他表中的主键。
    • 主属性:候选键内的属性为主属性,其他属性为非主属性。
    • 实体完整性约束:即主键约束,主键值不能为空,也不能重复。
    • 参照完整性约束:即外键约束,外键必须是其他表中已经存在的主键的值,或者为空。
    • 用户自定义完整性约束:自定义表达式约束,如设定年龄属性的值必须在0到150之间。


三、范式(Normalization)

  1. 第一范式(1NF)

    • 表中每个字段不可再分(无嵌套表)。
    • 原始表(不符合1NF)

      员工ID员工姓名薪资/月
      001张三基本工资:5000, 补贴:1000
      002李四基本工资:6000, 补贴:800

      1NF规范化后

      员工ID员工姓名基本工资补贴
      001张三50001000
      002李四6000800
  2. 第二范式(2NF)

    • 满足1NF,且非主属性完全依赖于候选键(消除部分依赖:每一个非主属性不会依赖复合主键中的某一个列)。
    • 原始表(不符合2NF)

      学号课程号课程名称成绩教师
      S001C001数学90王老师
      S001C002英语85李老师

      问题:课程名称和教师仅依赖于课程号(部分依赖复合主键 (学号, 课程号))。
      2NF规范化后
      选课表(完全依赖):

      学号课程号成绩
      S001C00190
      S001C00285

      课程表(消除部分依赖):

      课程号课程名称教师
      C001数学王老师
      C002英语李老师
  3. 第三范式(3NF)

    • 满足2NF,且非主属性不传递依赖于候选键
    • 原始表(不符合3NF)

      学号姓名系编号系主任
      S001张三D01刘主任
      S002李四D02陈主任

      问题:系主任传递依赖于学号(学号 → 系编号 → 系主任)。
      3NF规范化后
      学生表

      学号姓名系编号
      S001张三D01
      S002李四D02

      系表(消除传递依赖):

      系编号系主任
      D01刘主任
      D02陈主任
  4. BC范式(BCNF)

    • 满足3NF,且所有依赖的左侧必须包含候选键
    • BC范式要求在满足第三范式的条件下,进一步消除主属性对于码的部分函数依赖和传递依赖。简单通俗地讲,对于关系模式中的任意一个函数依赖X→Y(X是决定因素,Y是被决定因素),X必须是候选键或者包含候选键。也就是说,每一个函数依赖的左边决定因素都必然包含候选键,只有满足这样的条件,关系模式才符合BCNF。
      • 在给定的例子中有一个涉及S、T、J三个属性的关系模式,通过分析其依赖关系和候选键来判断是否符合BCNF:

      • 候选键与依赖集:该关系模式的候选键有两种情况,分别是组合键(S, T)和(S, J),依赖集为{SJ→T,T→J} 。由于S、T、J这三个属性都能通过候选键组合确定,所以它们都是主属性,因此该关系模式达到了3NF(因为不存在非主属性,也就不存在非主属性对码的部分依赖和传递依赖)。
      • BCNF判断:当以(S, J)作为候选键时,看依赖T→J,其中T在(S, J)这种候选键情况下并不是候选键,即T→J这个函数依赖的决定因素T不包含任意候选码,所以这个关系模式不符合BCNF的要求。
      • 转换为BCNF:为了使该关系模式满足BCNF,将依赖T→J修改为TS→J 。这样修改后,在新的依赖TS→J中,左边的决定因素TS包含了候选键之一S,满足了BCNF中每一个依赖的左边决定因素都包含候选键的条件,此时该关系模式就达到了BCNF。
    • 原始表(不符合BCNF)

      学生ID课程教师
      S001数学王老师
      S002英语李老师

      假设依赖

      教师 → 课程(每个教师只教一门课,但教师不是候选键)。
      问题:存在非平凡依赖(教师 → 课程),左侧不是候选键。

      BCNF规范化后

      学生-教师表(候选键为 (学生ID, 教师)):

      学生ID教师
      S001王老师
      S002李老师

      教师-课程表(教师为候选键):

      教师课程
      王老师数学
      李老师英语

真题示例:

给定关系模式R(U,F),U={A,B,C,D},F={AB→C,CD→B}。关系R( ),且分别有( )。

A.只有1个候选关键字ACB B.只有1个候选关键字BCD

C.有2个候选关键字ACD和ABD D.有2个候选关键字ACB和BCD

A.0个非主属性和4个主属性 B.1个非主属性和3个主属性

C.2个非主属性和2个主属性 D.3个非主属性和1个主属性

候选关键字的求法

根据函数依赖集 F = {AB→C, CD→B},我们可以按照以下步骤求候选关键字:

  1. 找出从未在右边出现过的属性

    • 在 F 中,右边出现的属性是 C 和 B
    • 因此,A 和 D 从未在右边出现过,它们必然是候选键的一部分
  2. 以 A 和 D 为基础,尝试构建候选关键字

    • 尝试 AD:
      • AD⁺ = AD
      • 无法推导出 B 或 C(因为 AB→C 和 CD→B 都需要额外的属性)
      • 所以 AD 不是候选关键字
    • 尝试 ABD:
      • ABD⁺ = ABD → C (AB→C) → ABCD
      • 可以推导出所有属性,因此 ABD 是候选关键字
    • 尝试 ACD:
      • ACD⁺ = ACD → B (CD→B) → ABCD
      • 可以推导出所有属性,因此 ACD 是候选关键字
    • 其他组合(如 AB、AC、AD、BC、BD、CD):这些组合的闭包都无法推导出所有属性,因此不是候选关键字
  3. 结论

    • 候选关键字有 2 个:ABD 和 ACD

主属性和非主属性

  1. 主属性:出现在任何候选关键字中的属性

    • ABD 包含 A、B、D
    • ACD 包含 A、C、D
    • 因此主属性是 A、B、C、D(所有属性都是主属性)
  2. 非主属性:不包含在任何候选关键字中的属性

    • 由于所有属性都是主属性,非主属性数量为 0

设有关系模式R(E,N,M,L,Q),其函数依赖集为F={E→N,EM→Q,M→L}。则关系模式R达到了______;该关系模式_________。

A. 1NF B. 2NF C. 3NF D. BCNF

A. 无需进行分解,因为已经达到了3NF

B. 无需进行分解,因为已经达到了BCNF

C. 尽管不存在部分函数依赖,但还存在传递依赖,所以需要进行分解

D. 需要进行分解,因为存在冗余、修改操作的不一致性、插入和删除异常

第一步:识别所有属性

属性集 U = {E, N, M, L, Q}

第二步:分析函数依赖集 F

F = { E → N, EM → Q, M → L }

第三步:找出从未出现在右边的属性(候选键的必须属性)

  • 在 F 中,右边出现的属性:N, Q, L

  • 从未出现在右边的属性:E, M

  • 因此,E 和 M 必须包含在候选键中

第四步:以 E 和 M 为基础构建候选键

  1. 尝试 EM:

    • 计算 EM⁺:

      • 初始:EM

      • 应用 E→N:EMN

      • 应用 EM→Q:EMNQ

      • 应用 M→L:EMNQL

    • EM⁺ = EMNQL = U(覆盖所有属性)

    • 因此,EM 是候选键

范式分析(基于候选键 EM)

1. 主属性和非主属性

  • 主属性:E, M(出现在候选键中)

  • 非主属性:N, L, Q

2. 检查 2NF(消除部分函数依赖)

  • 检查非主属性对候选键的部分依赖:

    • E→N:N 依赖于候选键的一部分(E),属于部分函数依赖 → 违反 2NF

    • M→L:L 依赖于候选键的一部分(M),属于部分函数依赖 → 违反 2NF

    • EM→Q:Q 完全依赖于整个候选键 → 符合 2NF

  • 结论:不满足 2NF

是否需要分解

  • 存在部分函数依赖和传递依赖,会导致:

    • 数据冗余(如 E→N 导致 N 重复存储)

    • 更新异常(修改 E 对应的 N 需要修改多条记录)

    • 插入异常(无法单独插入 M→L 的信息)

    • 删除异常(删除 EM 会丢失 M→L 的信息)

  • 需要进行分解,因为存在冗余、修改操作的不一致性、插入和删除异常

分解方法

  1. 将部分依赖单独分解:

    • R1(E, N):满足 E→N

    • R2(M, L):满足 M→L

    • R3(E, M, Q):满足 EM→Q

    • 每个关系模式都满足 BCNF

http://www.xdnf.cn/news/7975.html

相关文章:

  • 下载HBuilder X,使用uniapp编写微信小程序
  • Linux简介
  • 下拉框select标签类型
  • PLOS ONE:VR 游戏扫描揭示了 ADHD 儿童独特的大脑活动
  • 基础数学知识-概率论
  • 机器学习05-CNN
  • 守护进程及gdb调试(新手简略版)
  • 工作总结(十二)——迁移svn单项目到gitlab上,保留历史提交记录
  • 02.Spring_IOC详解
  • Evidential Deep Learning和证据理论教材的区别(主要是概念)
  • test ssl java
  • 【C++指南】哈希驱动的封装:如何让unordered_map/set飞得更快更稳?【上】
  • 数据结构学习笔记 :二叉搜索树与高效查找算法详解
  • React 列表渲染基础示例
  • DFS/BFS专练-搞定图论基础!(从海岛问题过渡至图论基础应用C++/C)
  • 无刷电机槽数相同、转子极数不同的核心区别
  • Nacos安装及数据持久化
  • ESP32之本地HTTP服务器OTA固件升级流程,基于VSCode环境下的ESP-IDF开发(附源码)
  • 【Spring Boot】MyBatis入门:连接Mysql数据库、测试单元、连接的常见错误
  • 汇编语言中的数据
  • 基于C++(MFC)的细胞识别程序
  • 人工智能在后端开发中的革命:从架构到运维
  • 前端:uniapp中uni.pageScrollTo方法与元素的overflow-y:auto之间的关联
  • 极狐GitLab 项目导入导出设置介绍?
  • 架构师面试(三十一):IM 消息收发逻辑
  • 手撕STL——vector
  • 利用DeepSeek设计一个HTML批量转换工具设计
  • Hadoop的三大结构及其作用?
  • hadoop的三大结构及各自的作用
  • yarn的定义